【数据结构导论】第二章-线性表

笔记目录

线性表的概念

线性表（Linear List）是由一个或多个数据元素组成的有限序列。

线性表的基本特征

• 线性表中的结点具有一对一的关系，且个数有限。
• 如果节点数不为零，则除起始结点没有直接前驱外，其他每个结点，有且仅有一个直接前驱；除终端结点没有直接后继外，其他每个节点有且仅有一个直接后继。
• 同一个线性表中的所有结点代表的数据元素具有相同的特性。

线性表表长和基本操作

• 表长：线性表中的结点个数为表长。
• 基本操作包括：
  • 初始化
  • 求表长
  • 读表元素
  • 定位
  • 插入
  • 删除

线性表的顺序存储结构-顺序表

线性表顺序存储方法：

将表中的结点依次存放在计算机内存中一段连续的存储单元中。

• 特点

数据元素在线性表中的邻接关系决定它们在存储空间中的存储位置。

• 类 C 语言描述

//假定线性表的表元素类型为DataType
const int Maxsize = 7; //预先定义数组大小
typedef struct
{
    int num;      //学号
    char name[8]; //姓名
    char sex[2];  //性别
    int age;      //年龄
    int score;    //入学成绩
} DataType;       //定义结点的类型

• 顺序表插入、删除和定位运算的实现算法。

插入

void InsertSeqList(SeqList L, DataType x, int i)
{ //将元素x插入到顺序表L的第i个元素之前
    int j;
    if (L.length == Maxsize)
        exit("表已满");
    if (i < 1 || i > L.length + 1) //检查插入位置是否合法
        exit("位置错");
    for (j = L.length; j > i; j--) //初始i=L.length
        L.data[j] = L.data[j - 1]; //依次后移
    L.data[i - 1] = x;             //元素x放到下标为i-1的位置
    L.length++;                    //表长度加1
}

删除

void DeleteSeqList(SeqList L, int i)
{ //删除线性表 L 中的第 i 个数据结点
    int j;
    if (i < 1 || i > L.length) //检查位置合法性
        exit("非法位置");
    for (j = i; j < L.length; j++) //第 i 个元素的下标为 i-1
        L.data[j - 1] = L.data[j]; //依次左移
    L.length--;                    //表长度减一
}

定位

int LocateSeqList(SeqList L, DataType x)
{
    int i = 0;
    while ((i < L.length) && L.data[i] != x) //在顺序表中查找值为x的结点
        i++;
    if (i < L.length) //若找到值为x的元素，返回元素的序号
        return i + 1;
    else //若未找到值为x的元素，返回0
        return 0;
}

线性表的链式存储结构–单链表

结点的结构

一个数据元素和一个指针组成单链表的一个结点

单链表的类 C 语言描述

typedef struct node
{
    DataType data;     //数据域
    struct node *next; //指针域
} Node, *LinkList;

• 头指针

  指向单链表第一个结点的指针

• 头结点

  在单链表的第一个结点之前增设一个类型相同的结点，称为头节点。

• 首结点

  链表中的第一个元素结点称为首结点。

• 尾结点

  链表中的最后一个元素结点称为首结点。

• 空链表

  如果头指针变量 head 等于 NULL，则表示该链表无任何结点，为空链表。
  一个空单链表仅有一个头节点，它的指针与为 NULL

单链表插入、删除和定位运算的关键步骤

• 建立空表

LinkList InitiateLinkList()
{ //建立一个空的链表
    LinkList head;               //头指针
    head = malloc(sizeof(Node)); //动态建立一结点，它是头节点
    head->next = NULL;
    return head;
}

• 求表长

int LengthLinkList(LinkList head)
{
    //求单链表表head的长度
    Node *p = head;         //工作指针p初始指向头结点
    int count = 0;          //计数器
    while (p->next != NULL) //判断是否为尾结点
    {
        p = p->next; //指针移动到下一结点
        count++;    //计数器+1
    }
    return count; //返回表长
}

• 读表元素

Node *GetLinkList(LinkList head, int i)
{
    //在单链表查找第i个元素结点，找到返回该节点指针，否则返回NULL
    Node *p;        //工作指针
    p = head->next; //初始指向首结点
    int c = 1;
    while ((c < i) && (p != NULL))
    { //当未到i结点和尾结点是继续后移
        p = p->next;
        c++;
    }
    if (i == c) //找到第i个结点
        return p;
    else
        return NULL; //i值不合法
}

• 定位

int LocateLinkList(LinkList head, DataType x)
{
    //求表中第一个值为x的结点的序号，若找不到，返回0
    Node *p = head;
    p = p->next;
    int i = 0;
    while (p != NULL && p->data != x)
    {
        i++;
        p = p->next;
    }
    if (p != NULL)
        return i + 1;
    else
        return 0;
}

• 插入

void InsertLinkList(LinkList head, DataType x, int i)
{ //在表head的第i个元素之前插入一个值为x的新结点
    Node *p, *q;
    if (i == 1)
        q = head;
    else
        q = GetLinkList(head, i - 1); //找第i-1个元素结点
    if (q == NULL)                    //第i-1个结点不存在
        exit("找不到插入的位置");
    else
    {
        p = malloc(sizeof(Node)); //生成新的结点
        p->data = x;
        p->next = q->next;  //新结点链域指向*q的后继结点
        q->next = p;        //修改*q的链域
    }
}

• 删除

void DeleteLinkList(LinkList head, int i)
{
    //删除表head中地i的结点
    Node *q, *p;
    if (i = -= 1)
        q = head;
    else
        q = GetLinkList(head, i - 1); //找到待删除的结点的直接前驱
    if (q != NULL && q->next != NULL) //若直接前驱存在且待删除结点也存在
    {
        p = q->next;        //p指向待删除结点
        q->next = p->next;  //待删除结点的直接前驱指向待删除结点的直接后继
        free(p);            //释放已经移除链表的结点p的空间
    }
    else
        exit("找不到要删除的结点"); //结点不存在
}

循环链表和双向循环链表

循环链表的结点结构

链表中最后一个链表的指针域指向头结点。

双向循环链表的结点结构

头节点的 prior 指向最后一个结点，最后一个结点的 nex 点

【本章完】