26考研——线性表_ 线性表的链式表示_单链表（2）

408答疑

---

---

三、 线性表的链式表示

• 顺序表的存储位置可以用一个简单直观的公式表示，它可以随机存取表中任一元素，但插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。

单链表

概念

• 链表是线性结构的链式实现，数据通过结点进行保存和链接。

单链表的结构

• 单链表是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。单链表结点结构如图所示，其中 data 为数据域，存放数据元素；next 为指针域，存放其后继结点的地址。

• 利用单链表可以解决顺序表需要大量连续存储单元的缺点，但附加的指针域，也存在浪费存储空间的缺点。单链表的元素离散地分布在存储空间中，因此是非随机存取的存储结构，即不能直接找到表中某个特定结点。查找特定结点时，需要从表头开始遍历，依次查找。

头结点

• 通常用头指针 L（或 head 等）来标识一个单链表，指出链表的起始地址，头指针为 NULL 时表示一个空表。此外，为了操作上的方便，在单链表第一个数据结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，但也可以记录表长等信息。单链表带头结点时，头指针 L 指向头结点，如下图(1)所示。单链表不带头结点时，头指针 L 指向第一个数据结点，如下图(2)所示。表尾结点的指针域为 NULL（用“^”表示）。

• 头结点和头指针的关系：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。

• 引入头结点后，可以带来两个优点：

  1. 第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
  2. 无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

单链表上基本操作的实现

单链表的初始化

带头结点和不带头结点的初始化操作

• 带头结点的单链表初始化时，需要创建一个头结点，并让头指针指向头结点，头结点的 next 域初始化为 NULL。
• 不带头结点的单链表初始化时，只需将头指针 L 初始化为 NULL。

注意

• 设 p 为指向链表结点的结构体指针，则 *p 表示结点本身，因此可用 p->data 或 (*p).data 访问 *p 这个结点的数据域。二者完全等价。成员运算符 . 左边是一个普通的结构体变量，而指向运算符 -> 左边是一个结构体指针。通过 (*p).next 可以得到指向下一个结点的指针，因此 (*(*p).next).data 就是下一个结点中存放的数据，或者直接用 p->next->data。

求表长操作

• 求表长操作是计算单链表中数据结点的个数，需要从第一个结点开始依次访问表中每个结点，为此需设置一个计数变量，每访问一个结点，其值加 1，直到访问到空结点为止。
• 求表长操作的时间复杂度为 $O(n)$。另需注意的是，因为单链表的长度是不包括头结点的，因此不带头结点和带头结点的单链表在求表长操作上会略有不同。

按序号查找结点

• 从单链表的第一个结点开始，沿着 next 域从前往后依次搜索，直到找到第 i 个结点为止，则返回该结点的指针；若 i 大于单链表的表长，则返回 NULL。
• 按序号查找操作的时间复杂度为 $O(n)$。

按值查找表结点

• 从单链表的第一个结点开始，从前往后依次比较表中各结点的数据域，若某结点的 data 域等于给定值 e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回 NULL。
• 按值查找操作的时间复杂度为 $O(n)$。

插入结点操作

• 插入结点操作将值为 x 的新结点插入到单链表的第 i 个位置。先检查插入位置的合法性，然后找到待插入位置的前驱，即第 i-1 个结点，再在其后插入。
• 其操作过程如图所示。

1. 首先查找第 i-1 个结点，假设第 i-1 个结点为 *p，然后令新结点 *s 的指针域指向 *p 的后继，再令结点 *p 的指针域指向新插入的结点 *s。
2. 插入时，① 和 ② 的顺序不能颠倒，否则，先执行 p->next=s 后，指向其原后继的指针就不存在了，再执行 s->next=p->next 时，相当于执行了 s->next=s，显然有误。本算法主要的时间开销在于查找第 i-1 个元素，时间复杂度为 $O(n)$。若在指定结点后插入新结点，则时间复杂度仅为 $O(1)$。需注意的是，当链表不带头结点时，需要判断插入位置 i 是否为 1，若是，则要做特殊处理，将头指针 L 指向新的首结点。当链表带头结点时，插入位置 i 为 1 时不用做特殊处理。

扩展：对某一结点进行前插操作

• 前插操作是指在某结点的前面插入一个新结点，后插操作的定义刚好与之相反。在单链表插入算法中，通常都采用后插操作。以上面的算法为例，先找到第 i-1 个结点，即插入结点的前驱，再对其执行后插操作。由此可知，对结点的前插操作均可转化为后插操作，前提是从单链表的头结点开始顺序查找到其前驱结点，时间复杂度为 $O(n)$。

• 此外，可采用另一种方式将其转化为后插操作来实现，设待插入结点为 *s，将 *s 插入到 *p 的前面。我们仍然将 *s 插入到 *p 的后面，然后将 p->data 与 s->data 交换，这样做既满足逻辑关系，又能使得时间复杂度为 $O(1)$。

删除结点操作

• 删除结点操作是将单链表的第 i 个结点删除。先检查删除位置的合法性，然后查找表中第 i-1 个结点，即被删结点的前驱，再删除第 i 个结点。其操作过程如图所示。

1. 假设结点 *p 为找到的被删结点的前驱，为实现这一操作后的逻辑关系的变化，仅需修改 *p 的指针域。将 *p 的指针域 next 指向 *q 的下一结点，然后释放 *q 的存储空间。

2. 同插入算法一样，该算法的主要时间也耗费在查找操作上，时间复杂度为 $O(n)$。当链表不带头结点时，需要判断被删结点是否为首结点，若是，则要做特殊处理，将头指针 L 指向新的首结点。当链表带头结点时，删除首结点和删除其他结点的操作是相同的。

扩展：删除结点 *p

• 要删除某个给定结点 *p，通常的做法是先从链表的头结点开始顺序找到其前驱，然后执行删除操作。其实，删除结点 *p 的操作可用删除 *p 的后继来实现，实质就是将其后继的值赋予其自身，然后再删除后继，也能使得时间复杂度为 $O(1)$。

采用头插法建立单链表

• 该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后，如下图所示。

• 采用头插法建立单链表时，读入数据的顺序与生成的链表中元素的顺序是相反的，可用来实现链表的逆置。每个结点插入的时间为 $O(1)$，设单链表长为 n，则总时间复杂度为 $O(n)$。

• 若单链表不带头结点，则在头部插入新结点时，每次插入新结点后，都需要将它的地址赋值给头指针 L。

采用尾插法建立单链表

• 头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，则可采用尾插法。该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针 r，使其始终指向当前链表的尾结点，如下图所示。

因为附设了一个指向表尾结点的指针，所以时间复杂度和头插法的相同。

注意

• 单链表是整个链表的基础，读者一定要熟练掌握单链表的基本操作算法。在设计算法时，建议先通过画图的方法理清算法的思路，然后进行算法的编写。

单链表的代码实操

定义结点

• 定义单链表的结点类型，包括数据域和指针域。

typedef struct ListNode {ElemType data;         // 数据域struct ListNode *next; // 指针域
} ListNode, *LinkList;

单链表的初始化

带头结点的单链表初始化

• 带头结点的单链表初始化时，需要创建一个头结点，并让头指针指向头结点，头结点的 next 域初始化为 NULL。

bool InitList(LinkList &L) {L = (ListNode*)malloc(sizeof(ListNode)); // 创建头结点L->next = NULL; // 头结点之后暂时还没有元素结点return true;
}

不带头结点的单链表初始化

• 不带头结点的单链表初始化时，只需将头指针 L 初始化为 NULL。

bool InitList(LinkList &L) {L = NULL; // 头指针初始化为 NULLreturn true;
}

带头结点的求表长操作

• 求表长操作是计算单链表中数据结点的个数，需要从第一个结点开始依次访问表中每个结点，为此需设置一个计数变量，每访问一个结点，其值加 1，直到访问到空结点为止。

int Length(LinkList L) {int len = 0; // 计数变量，初始为 0ListNode *p = L;while (p->next != NULL) { // 遍历链表直到最后一个结点p = p->next; // 移动到下一个结点len++; // 计数加 1}return len;
}

打印单链表

• 从头结点或第一个数据结点开始，依次访问每个结点，打印其数据域，直到链表结束。

带头结点的链表打印

void printList_H(LinkList L) {ListNode *p = L->next;while (p != NULL) {printf("%d-->", p->data);p = p->next;}printf("Over.\n");
}

不带头结点的链表打印

void printList(LinkList L) {ListNode *p = L;while (p != NULL) {printf("%d-->", p->data);p = p->next;}printf("Over.\n");
}

采用头插法建立带头结点的单链表

• 采用头插法建立单链表时，读入数据的顺序与生成的链表中元素的顺序是相反的，可用来实现链表的逆置。

LinkList List_HeadInsert(LinkList &L) { // 逆向建立单链表ListNode *s, *p;int x;L = (ListNode*)malloc(sizeof(ListNode)); // 创建头结点L->next = NULL; // 初始化为空链表scanf("%d", &x);while (x != 9999) { // 输入 9999 表示结束s = (ListNode*)malloc(sizeof(ListNode)); // 创建新结点s->data = x;s->next = L->next; // 将新结点插入表中，L 为头指针L->next = s;scanf("%d", &x);}return L;
}

采用尾插法建立单链表

带头结点的链表创建

ListNode* createList_H(ElemType ar[], int n) {ListNode *phead = (ListNode*)malloc(sizeof(ListNode));phead->data = -1;phead->next = NULL;ListNode *p = phead;for (int i = 0; i < n; i++) {ListNode *s = (ListNode*)malloc(sizeof(ListNode));s->data = ar[i];s->next = NULL;p->next = s;p = s;}return phead;
}

不带头结点的链表创建

ListNode* createList(ElemType ar[], int n) {ListNode *phead = (ListNode*)malloc(sizeof(ListNode));phead->data = ar[0];phead->next = NULL;ListNode *p = phead;for (int i = 1; i < n; i++) {ListNode *s = (ListNode*)malloc(sizeof(ListNode));s->data = ar[i];s->next = NULL;p->next = s;p = s;}return phead;
}

带头结点的查找结点

按序号查找结点

• 从单链表的第一个结点开始，沿着 next 域从前往后依次搜索，直到找到第 i 个结点为止，则返回该结点的指针；若 i 大于单链表的表长，则返回 NULL。

ListNode* GetElem(LinkList L, int i) {ListNode *p = L; // 指针 p 指向当前扫描到的结点int j = 0;   // 记录当前结点的顺序，头结点是第 0 个结点while (p != NULL && j < i) { // 循环找到第 i 个结点p = p->next; // 移动到下一个结点j++;        // 结点序号加 1}return p; // 返回第 i 个结点的指针或 NULL
}

按值查找结点

• 通过遍历链表，逐个检查每个结点的数据域，直到找到目标值或遍历完整个链表。

ListNode* LocateElem(LinkList L, ElemType e) {if (L == NULL) return NULL; // 检查链表是否为空ListNode *p = L->next; // 指向第一个数据结点while (p != NULL && p->data != e) { // 从第一个结点开始查找数据域为 e 的结点p = p->next; // 移动到下一个结点}return p; // 找到后返回该结点指针，否则返回 NULL
}

插入结点

在 Key 结点的后面插入 x 结点

ListNode* insertListBack(LinkList L, ElemType key, ElemType x) {ListNode *pos = findNode(L, key);if (pos == NULL)return L;ListNode *s = (ListNode*)malloc(sizeof(ListNode));s->data = x;s->next = pos->next;pos->next = s;return L;
}

在 Key 结点的前面插入 x 结点（不带头结点）

ListNode* insertListFront(LinkList L, ElemType key, ElemType x) {ListNode *p = L, *pre = NULL;while (p != NULL && p->data != key) {pre = p;p = p->next;}if (p == NULL)return L;ListNode *s = (ListNode*)malloc(sizeof(ListNode));s->data = x;s->next = p;if (pre == NULL)L = s;elsepre->next = s;return L;
}

删除结点（不带头结点）

ListNode* deleteNode(LinkList L, ElemType key) {ListNode *p = L, *pre = NULL;while (p != NULL && p->data != key) {pre = p;p = p->next;}if (p == NULL)return L;if (pre == NULL)L = p->next;elsepre->next = p->next;free(p);return L;
}

带头结点的反转链表

ListNode* reverseList(LinkList L) {ListNode *p = L->next;L->next = NULL;while (p != NULL) {ListNode *q = p->next;p->next = L;L = p;p = q;}return L;
}

排序链表

ListNode* sortList(LinkList L) {ListNode *p = L->next;L->next = NULL;while (p != NULL) {ListNode *q = p->next;ListNode *cur = L, *pre = NULL;while (cur != NULL && p->data > cur->data) {pre = cur;cur = cur->next;}if (pre == NULL)L = p;elsepre->next = p;p->next = cur;p = q;}return L;
}

五、参考资料

鲍鱼科技课件

b站免费王道课后题讲解:

网课全程班:

26王道考研书