26考研——线性表_ 线性表的链式体现_双循环链表（2） ...

408答疑

---

  

---

三、 线性表的链式体现

双循环链表

单链表与双链表的比较

单链表的特点

• 单链表结点中只有一个指向其后继的指针，使得单链表只能从前今后依次遍历。
  
• 访问某个结点的前驱（插入、删除操作时），只能重新开始遍历，访问前驱的时间复杂度为                                         O                            (                            n                            )                                  O(n)                     O(n)。
  
• 为了克服单链表的这个缺点，引入了双链表。
  

双链表的特点

• 双链表结点中有两个指针 prior 和 next，分别指向其直接前驱和直接后继，如下图所示。表头结点的 prior 域和尾结点的 next 域都是 NULL。
  

• 双链表在单链表结点中增长了一个指向其前驱的指针 prior，因此双链表的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是由于“链”厘革时也需要对指针 prior 做出修改，其关键是包管在修改的过程中不断链。此外，双链表可以很方便地找到当前结点的前驱，因此，插入、删除操作的时间复杂度仅为                                         O                            (                            1                            )                                  O(1)                     O(1)。
  

双链表上根本操作的实现

双链表的插入操作

• 在双链表中 p 所指的结点之后插入结点 *s，其指针的厘革过程如图所示。
  

• 插入操作的步骤如下：
  
  
  
  • 将 s->next 指向 p->next。
    
  • 将 p->next->prior 指向 s。
    
  • 将 s->prior 指向 p。
    
  • 将 p->next 指向 s。
    
  
  
• 上述代码的语句顺序不是唯一的，但也不是任意的。步骤 1 必须在步骤 4 之前，否则 *p 的后继结点的指针就会丢失，导致插入失败。
  

双链表的删除操作

• 删除双链表中结点 *p 的后继结点 *q，其指针的厘革过程如图所示。
  

• 删除操作的步骤如下：
  
  
  
  • 将 p->next 指向 q->next。
    
  • 将 q->next->prior 指向 p。
    
  • 释放 q 结点空间
    
  
  

双链表的代码实操

定义结点

• 定义双链表的节点范例，包括数据域、前驱指针和后继指针。
  

1. typedef struct DCListNode {
2.     ElemType data;          // 数据域
3.     struct DCListNode *prev; // 前驱指针
4.     struct DCListNode *next; // 后继指针
5. } DCListNode, *DCLinkList;

复制代码

创建一个结点

• 创建并初始化一个新的双链表节点。
  

1. DCListNode* buyNode(ElemType x) {
2.     DCListNode *s = (DCListNode*)malloc(sizeof(DCListNode));
3.     s->data = x;
4.     return s;
5. }

复制代码

带头结点的双链表初始化

• 初始化一个带头结点的双链表。
  

1. void initDCList(DCListNode **head) {
2.     *head = (DCListNode*)malloc(sizeof(DCListNode));
3.     (*head)->prev = *head;
4.     (*head)->next = *head;
5. }

复制代码

创建双链表

• 根据给定命组创建一个双链表。
  

1. void createDCList(DCLinkList DCL, ElemType ar[], int n) {
2.     DCListNode *p = DCL;
3.     for (int i = 0; i < n; ++i) {
4.         DCListNode *s = (DCListNode*)malloc(sizeof(DCListNode));
5.         s->data = ar[i];
6.         s->prev = p->prev;
7.         s->next = p;
8.         p->prev->next = s;
9.         p->prev = s;
10.     }
11. }

复制代码

打印双链表

• 重新结点的下一个节点开始，打印链表中的每个节点数据，直到回到头结点。
  

1. void printDCList(DCLinkList DCL) {
2.     DCListNode *p = DCL->next;
3.     while (p != DCL) {
4.         printf("%d-->", p->data);
5.         p = p->next;
6.     }
7.     printf("Over.\n");
8. }

复制代码

查找结点

• 重新结点开始，遍历链表直到找到目标节点或到达头结点。
  

1. DCListNode* findDCNode(DCLinkList DCL, ElemType key) {
2.     DCListNode *p = DCL->next;
3.     while (p != DCL && p->data != key)
4.         p = p->next;
6.     if (p != DCL)
7.         return p; // 找到了节点
9.     return NULL;  // 没有找到节点
10. }

复制代码

插入结点

在指定节点后插入新节点

• 在双链表中指定节点 pos 之后插入一个新节点 x。
  

1. void insertDCNodeBack(DCLinkList DCL, DCListNode *pos, ElemType x) {
2.     DCListNode *s = buyNode(x);
3.     s->prev = pos;
4.     s->next = pos->next;
5.     s->next->prev = s;
6.     s->prev->next = s;
7. }

复制代码

在指定节点前插入新节点

• 在双链表中指定节点 pos 之前插入一个新节点 x。
  

1. void insertDCNodeFront(DCLinkList DCL, DCListNode *pos, ElemType x) {
2.     DCListNode *s = buyNode(x);
3.     s->prev = pos->prev;
4.     s->next = pos;
5.     s->next->prev = s;
6.     s->prev->next = s;
7. }

复制代码

删除结点

• 找到目标节点，调整前后节点的指针并释放目标节点。
  

1. void deleteDCNode(DCLinkList DCL, ElemType key) {
2.     DCListNode *p = findDCNode(DCL, key);
3.     if (p == NULL)
4.         return; // 删除失败
6.     p->prev->next = p->next;
7.     p->next->prev = p->prev;
8.     free(p);
9. }

复制代码

反转链表

• 逐个摘除链表中的节点并重新插入到链表头部。
  

1. void reverseDCList(DCLinkList DCL) {
2.     DCListNode *p = DCL->next;
3.     DCListNode *q = p->next;
4.     p->next = DCL;
5.     DCL->prev = p;
7.     while (q != DCL) {
8.         p = q;
9.         q = q->next;
11.         p->next = DCL->next;
12.         p->prev = DCL;
13.         p->prev->next = p;
14.         p->next->prev = p;
15.     }
16. }

复制代码

排序链表

• 逐个摘除链表中的节点并按顺序插入到链表中。
  

1. void sortDCList(DCLinkList DCL) {
2.     DCListNode *p = DCL->next;
3.     DCListNode *q = p->next;
5.     p->next = DCL;
6.     DCL->prev = p;
8.     while (q != DCL) {
9.         p = q;
10.         q = q->next;
12.         DCListNode *cur = DCL->next;
13.         while (cur != DCL && p->data > cur->data)
14.             cur = cur->next;
16.         p->next = cur;
17.         p->prev = cur->prev;
18.         p->prev->next = p;
19.         p->next->prev = p;
20.     }
21. }

复制代码

循环链表

循环单链表

• 循环单链表的特点是最后一个结点的 next 指针指向头结点，形成一个环。这种结构使得链表可以从任意位置开始遍历，而不必担心到达链表的末端，如下图所示。
  

• 特点：
  
  
  
  • 表尾结点的 next 域指向头结点。
    
  • 判空条件不是头结点的指针是否为空，而是它是否等于头指针 L。
    
  
  

操作形貌

• 循环单链表的插入、删除算法与单链表的几乎一样，所不同的是，若操作是在表尾进行，则执行的操作不同，以让单链表继续保持循环的性子。这是由于循环单链表是一个“环”，以是在任何位置上的插入和删除操作都是等价的，而无须判定是否是表尾。
  

操作特点

• 在单链表中只能从表头结点开始今后顺序遍历整个链表，而循环单链表可以从表中的任意一个结点开始遍历整个链表。
  
• 有时对循环单链表不设头指针而仅设尾指针，以使得操作服从更高。其原因是，若设的是头指针，对在表尾插入元素需要                                         O                            (                            n                            )                                  O(n)                     O(n) 的时间复杂度，而若设的是尾指针 r，r->next 即头指针，对在表头或表尾插入元素都只需要                                         O                            (                            1                            )                                  O(1)                     O(1) 的时间复杂度。
  

循环双链表

• 循环双链表在循环单链表的底子上增长了一个指向前驱的指针 prior，使得链表可以从任意结点向前或向后遍历，如下图所示。
  

• 特点：
  
  
  
  • 头结点的 prior 指针指向表尾结点。
    
  • 尾结点的 next 指针指向头结点。
    
  • 判空条件是头结点的 prior 和 next 域都等于 L。
    
  
  

链表的分类

• 循环链表可以是单链表或双链表，可以带头结点或不带头结点，也可以是循环的或非循环的（                                                   2                               3                                            2^3                     23种大概性）。这三种特性可以组合出八种不同的链表范例，如下图所示。
  
  
  
  
  
  
  
  
  
  

五、参考资料

鲍鱼科技课件

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

网课全程班:

26王道考研书


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。