数据结构和算法实现带头双向循环链表最复杂的链表

目录

前言

一、带头双向循环链表是什么？

二、实现带头双向循环链表

1.结构体和要实现函数

2.初始化和打印链表

3.头插和尾插

4.头删和尾删

5.查找和返回结点个数

6.在pos位置之前插入结点

7.删除指定pos结点

8.摧毁链表

三、完整代码

1.DSLinkList.h

2.DSLinkList.c

3.test.c

总结

---

前言

带头双向循环链表，是链表中最为复杂的一种结构，我们主要实现的功能为，头插尾插，头删尾删，初始化、打印、指定pos位置插入结点或者删除结点、寻找结点、摧毁链表等函数。

---

一、带头双向循环链表是什么？

如图所示：

---

二、实现带头双向循环链表

1.结构体和要实现函数

结构体如下：

1.  
   typedef struct DSLDataType;
2.  
   //定义双向链表的结构体
3.  
    
4.  
   //双向链表每一个节点都有一个前驱节点和后继节点，可以根据节点获得其前后的节点
5.  
   typedef struct DSListNode {
6.  
   struct DSListNode* prev;//前驱节点
7.  
   struct DSListNode* next;//后继节点
8.  
   int value;//数据域
9.  
   }DSLNode;//重定义

相比单向链表，多一个指针域prev，指向前面的结点地址

实现功能的函数：

1.  
   //初始化
2.  
   DSLNode*ListInit();
3.  
   //打印链表
4.  
   void ListPrint(DSLNode* ps);
5.  
   //尾部插入
6.  
   void ListPushBack(DSLNode* ps, int data);
7.  
   //头部插入
8.  
   void ListPushFront(DSLNode* ps, int data);
9.  
   //尾部删除
10.  
    void ListPopBack(DSLNode* ps);
11.  
    //头部删除
12.  
    void ListPopFront(DSLNode* ps);
13.  
    //判空
14.  
    bool ListEmpty(DSLNode* ps);
15.  
    //返回链表节点个数
16.  
    int Listsize(DSLNode* ps);
17.  
    //寻找指定元素，返回对应的节点
18.  
    DSLNode* ListFind(DSLNode* ps, int data);
19.  
    //在pos之前插入节点
20.  
    void ListInsert(DSLNode* pos, int data);
21.  
    //删除pos位置结点
22.  
    void ListEarse(DSLNode* pos);
23.  
    //摧毁链表
24.  
    void ListDestory(DSLNode* ps);

2.初始化和打印链表

1.  
   //对于函数的实现
2.  
   //初始化
3.  
   DSLNode* ListInit() {
4.  
   //初始化创建链表
5.  
   //创建新节点
6.  
   DSLNode* num = (DSLNode*)malloc(sizeof(DSLNode));
7.  
   //判断是否创建成功
8.  
   if (num == NULL) {
9.  
   perror("malloc fail\n");
10.  
    exit(-1);
11.  
    }
12.  
    num->prev = num;
13.  
    num->next = num;//作为头节点，前驱和后驱结点都指向自己
14.  
    return num;
15.  
    }
16.  
     
17.  
    //打印链表
18.  
    void ListPrint(DSLNode* ps) {
19.  
    assert(ps);//断言
20.  
    DSLNode* cur = ps->next;
21.  
    printf("phead->");
22.  
    while (cur != ps) {//双向链表，回到ps，就表示转了一圈
23.  
    printf("%d->", cur->value);
24.  
    cur = cur->next;
25.  
    }
26.  
    printf("NULL\n");
27.  
    }

3.头插和尾插

尾插如图所示：

代码如下：

1.  
    
2.  
   DSLNode* CreatNode(int data) {//创建新节点
3.  
   DSLNode* cur = (DSLNode*)malloc(sizeof(DSLNode));
4.  
   if (cur == NULL) {
5.  
   perror("malloc fail\n");
6.  
   exit(-1);
7.  
   }
8.  
   cur->next = cur->prev = NULL;
9.  
   cur->value = data;
10.  
    }
11.  
    //尾部插入
12.  
    void ListPushBack(DSLNode* ps, int data) {
13.  
    assert(ps);//断言
14.  
    DSLNode* newnode = CreatNode(data);
15.  
    DSLNode* tail = ps->prev;//把头节点之前的那个地址给tail
16.  
    tail->next = newnode;//将ps之前的那个数值，实际上是这个双向链表的最后一个元素的位置，的next指针指向新节点
17.  
    newnode->prev = tail;//新节点前后为 tail和ps
18.  
    newnode->next = ps;
19.  
    ps->prev = newnode;//tail的两个指针域都指向完成，就只剩下ps的前驱指针
20.  
     
21.  
    }

头插如图所示：
 代码如下：

1.  
    
2.  
   //头部插入
3.  
   void ListPushFront(DSLNode* ps, int data) {
4.  
   assert(ps);
5.  
   //头部插入就是将ps之后的一个地址给临时变量tail
6.  
   DSLNode* tail = ps->next;
7.  
   DSLNode* newnode = CreatNode(data);//创建新节点
8.  
   ps->next->prev = newnode;
9.  
   newnode->next = ps->next;
10.  
    newnode->prev = ps;
11.  
    ps->next = newnode;
12.  
    }

4.头删和尾删

尾部删除如图所示：

代码如下：

1.  
   //判空
2.  
   bool ListEmpty(DSLNode* ps) {
3.  
   assert(ps);//断言
4.  
   return ps->next == ps;//如果是只有一个ps头节点，则表示为空，返回true，否则返回false
5.  
    
6.  
   }
7.  
   //尾部删除
8.  
   void ListPopBack(DSLNode* ps) {
9.  
    
10.  
    assert(ps);//断言
11.  
    assert(!ListEmpty(ps));//先判断是否为空
12.  
    DSLNode* cur = ps->prev;
13.  
    //将cur的next值为NULL
14.  
    ps->prev = ps->prev->prev;
15.  
    ps->prev->next = ps;
16.  
    //这是直接略过尾部最后一个元素
17.  
    //跳过ps之前的一个节点，先让其左右节点相连，然后释放这个地址
18.  
    free(cur);
19.  
    cur = NULL;
20.  
    }

 头部删除如图所示：

代码如下：

1.  
   //头部删除
2.  
   void ListPopFront(DSLNode* ps) {
3.  
   assert(ps);
4.  
   assert(!ListEmpty(ps));
5.  
   DSLNode* cur = ps->next;
6.  
   //头删 是将头节点之后的第一个节点删除释放空间
7.  
   ps->next = ps->next->next;
8.  
   ps->next->prev = ps;
9.  
   free(cur);
10.  
    cur = NULL;
11.  
    }

5.查找和返回结点个数

查找：返回一个结点，根据data数值域，来返回第一个遇到的结点cur，若没有返回NULL

1.  
   //返回链表节点个数
2.  
   int Listsize(DSLNode* ps) {
3.  
   assert(ps);
4.  
   int count = 0;
5.  
   DSLNode* cur = ps->next;
6.  
   while (cur != ps) {
7.  
   count ;
8.  
   cur = cur->next;
9.  
   }
10.  
    return count;
11.  
    }
12.  
    //查找
13.  
    DSLNode* ListFind(DSLNode* ps, int data) {
14.  
    assert(ps);
15.  
    DSLNode* cur = ps->next;
16.  
    while (cur != ps) {
17.  
    if (cur->value == data) {
18.  
    return cur;
19.  
    }
20.  
    }
21.  
    return NULL;//NULL表示不存在
22.  
    }

6.在pos位置之前插入结点

如图所示：

 代码如下：

1.  
   //插入节点
2.  
   void ListInsert(DSLNode* pos, int data) {
3.  
    
4.  
   assert(pos);
5.  
   //pos三种可能
6.  
   //1.空链表
7.  
   //2.只有一个节点
8.  
   DSLNode* cur = pos->prev;
9.  
   //双向链表可以直接找到pos之前的位置，单向链表只能进行循环
10.  
    DSLNode* newnode = CreatNode(data);
11.  
    pos->prev = newnode;//把新节点newnode的位置给pos的prev
12.  
    newnode->prev = cur;//cur表示的是创建new节点之前的时候pos之前的结点
13.  
    cur->next = newnode;
14.  
    newnode->next = pos;
15.  
    //另一种不使用cur的方法
16.  
    //newnode->next = pos;
17.  
    //pos->prev->next = newnode;
18.  
    //newnode->prev = pos->prev;
19.  
    //pos->prev = newnode;
20.  
    }

7.删除指定pos结点

如图所示：

代码如下：

1.  
    
2.  
   //删除指针
3.  
   void ListEarse(DSLNode* pos) {
4.  
   assert(pos);
5.  
   DSLNode* cur = pos->prev;
6.  
   DSLNode* tail = pos->next;
7.  
   cur->next = tail;//两者相互指向，最后释放pos空间
8.  
   tail->prev = cur;
9.  
   free(pos);
10.  
    pos = NULL;
11.  
    }

8.摧毁链表

两种方式，可以直接使用二级指针，也可以使用一级指针一个一个free和NULL

1.  
   //摧毁链表
2.  
   void ListDestory(DSLNode* ps) {
3.  
   //可以设计二级指针直接将ps地址滞空为NULL
4.  
   //这里还是使用一级指针
5.  
   assert(ps);
6.  
   DSLNode* cur = ps->next;
7.  
   while (cur != ps) {
8.  
   DSLNode* tail = cur->next;//这个地方就是一个精彩的地方
9.  
   free(cur);//使用临时变量tail得到cur的下一个地址，然后再free cur
10.  
    cur = tail;//tail这个时候就是cur 的下一个结点
11.  
    }
12.  
    free(ps);
13.  
    ps = NULL;
14.  
     
15.  
    }
16.  
    void ListDestory2(DSLNode** ps) {
17.  
    assert(ps);
18.  
    free(ps);//二级指针直接free
19.  
    *ps = NULL;
20.  
    }

三、完整代码

1.DSLinkList.h

1.  
   #define _CRT_SECURE_NO_WARNINGS
2.  
    
3.  
   #include<stdio.h>
4.  
   #include<stdlib.h>
5.  
   #include<malloc.h>
6.  
   #include<assert.h>
7.  
   #include<stdbool.h>
8.  
    
9.  
   typedef struct DSLDataType;
10.  
    //定义双向链表的结构体
11.  
     
12.  
    //双向链表每一个节点都有一个前驱节点和后继节点，可以根据节点获得其前后的节点
13.  
    typedef struct DSListNode {
14.  
    struct DSListNode* prev;//前驱节点
15.  
    struct DSListNode* next;//后继节点
16.  
    int value;//数据域
17.  
    }DSLNode;//重定义
18.  
     
19.  
    //创建头节点，并将tail和head都指向第一个节点
20.  
    struct DSList {
21.  
    struct DSListNode* tail;
22.  
    struct DSListNode* head;
23.  
    unsigned int len;//表示链表的长度
24.  
    };
25.  
    //初始化
26.  
    DSLNode*ListInit();
27.  
    //打印链表
28.  
    void ListPrint(DSLNode* ps);
29.  
    //尾部插入
30.  
    void ListPushBack(DSLNode* ps, int data);
31.  
    //头部插入
32.  
    void ListPushFront(DSLNode* ps, int data);
33.  
    //尾部删除
34.  
    void ListPopBack(DSLNode* ps);
35.  
    //头部删除
36.  
    void ListPopFront(DSLNode* ps);
37.  
    //判空
38.  
    bool ListEmpty(DSLNode* ps);
39.  
    //返回链表节点个数
40.  
    int Listsize(DSLNode* ps);
41.  
    //寻找指定元素，返回对应的节点
42.  
    DSLNode* ListFind(DSLNode* ps, int data);
43.  
    //在pos之前插入节点
44.  
    void ListInsert(DSLNode* pos, int data);
45.  
    //删除pos位置结点
46.  
    void ListEarse(DSLNode* pos);
47.  
    //摧毁链表
48.  
    void ListDestory(DSLNode* ps);
49.  
     

2.DSLinkList.c

1.  
   #define _CRT_SECURE_NO_WARNINGS
2.  
    
3.  
   #include"DSLinkList.h"
4.  
    
5.  
   //对于函数的实现
6.  
   //初始化
7.  
   DSLNode* ListInit() {
8.  
   //初始化创建链表
9.  
   //创建新节点
10.  
    DSLNode* num = (DSLNode*)malloc(sizeof(DSLNode));
11.  
    //判断是否创建成功
12.  
    if (num == NULL) {
13.  
    perror("malloc fail\n");
14.  
    exit(-1);
15.  
    }
16.  
    num->prev = num;
17.  
    num->next = num;
18.  
    return num;
19.  
    }
20.  
     
21.  
    //打印链表
22.  
    void ListPrint(DSLNode* ps) {
23.  
    assert(ps);//断言
24.  
    DSLNode* cur = ps->next;
25.  
    printf("phead->");
26.  
    while (cur != ps) {//双向链表，回到ps，就表示转了一圈
27.  
    printf("%d->", cur->value);
28.  
    cur = cur->next;
29.  
    }
30.  
    printf("NULL\n");
31.  
    }
32.  
     
33.  
    DSLNode* CreatNode(int data) {//创建新节点
34.  
    DSLNode* cur = (DSLNode*)malloc(sizeof(DSLNode));
35.  
    if (cur == NULL) {
36.  
    perror("malloc fail\n");
37.  
    exit(-1);
38.  
    }
39.  
    cur->next = cur->prev = NULL;
40.  
    cur->value = data;
41.  
    }
42.  
    //尾部插入
43.  
    void ListPushBack(DSLNode* ps, int data) {
44.  
    assert(ps);//断言
45.  
    DSLNode* newnode = CreatNode(data);
46.  
    DSLNode* tail = ps->prev;//把头节点之前的那个地址给tail
47.  
    tail->next = newnode;//将ps之前的那个数值，实际上是这个双向链表的最后一个元素的位置，的next指针指向新节点
48.  
    newnode->prev = tail;//新节点前后为 tail和ps
49.  
    newnode->next = ps;
50.  
    ps->prev = newnode;//tail的两个指针域都指向完成，就只剩下ps的前驱指针
51.  
     
52.  
    }
53.  
     
54.  
    //头部插入
55.  
    void ListPushFront(DSLNode* ps, int data) {
56.  
    assert(ps);
57.  
    //头部插入就是将ps之后的一个地址给临时变量tail
58.  
    DSLNode* tail = ps->next;
59.  
    DSLNode* newnode = CreatNode(data);//创建新节点
60.  
    ps->next->prev = newnode;
61.  
    newnode->next = ps->next;
62.  
    newnode->prev = ps;
63.  
    ps->next = newnode;
64.  
    }
65.  
     
66.  
    //判空
67.  
    bool ListEmpty(DSLNode* ps) {
68.  
    assert(ps);//断言
69.  
    return ps->next == ps;//如果是只有一个ps头节点，则表示为空，返回true，否则返回false
70.  
     
71.  
    }
72.  
     
73.  
    //返回链表节点个数
74.  
    int Listsize(DSLNode* ps) {
75.  
    assert(ps);
76.  
    int count = 0;
77.  
    DSLNode* cur = ps->next;
78.  
    while (cur != ps) {
79.  
    count ;
80.  
    cur = cur->next;
81.  
    }
82.  
    printf("\n");
83.  
    return count;
84.  
    }
85.  
    //尾部删除
86.  
    void ListPopBack(DSLNode* ps) {
87.  
     
88.  
    assert(ps);//断言
89.  
    assert(!ListEmpty(ps));//先判断是否为空
90.  
    DSLNode* cur = ps->prev;
91.  
    //将cur的next值为NULL
92.  
    ps->prev = ps->prev->prev;
93.  
    ps->prev->next = ps;
94.  
    //这是直接略过尾部最后一个元素
95.  
    //跳过ps之前的一个节点，先让其左右节点相连，然后释放这个地址
96.  
    free(cur);
97.  
    cur = NULL;
98.  
    }
99.  
    //头部删除
100.  
     void ListPopFront(DSLNode* ps) {
101.  
     assert(ps);
102.  
     assert(!ListEmpty(ps));
103.  
     DSLNode* cur = ps->next;
104.  
     //头删 是将头节点之后的第一个节点删除释放空间
105.  
     ps->next = ps->next->next;
106.  
     ps->next->prev = ps;
107.  
     free(cur);
108.  
     cur = NULL;
109.  
     }
110.  
     //查找
111.  
     DSLNode* ListFind(DSLNode* ps, int data) {
112.  
     assert(ps);
113.  
     DSLNode* cur = ps->next;
114.  
     while (cur != ps) {
115.  
     if (cur->value == data) {
116.  
     return cur;
117.  
     }
118.  
     }
119.  
     return NULL;//NULL表示不存在
120.  
     }
121.  
     //插入节点
122.  
     void ListInsert(DSLNode* pos, int data) {
123.  
      
124.  
     assert(pos);
125.  
     //pos三种可能
126.  
     //1.空链表
127.  
     //2.只有一个节点
128.  
     DSLNode* cur = pos->prev;
129.  
     //双向链表可以直接找到pos之前的位置，单向链表只能进行循环
130.  
     DSLNode* newnode = CreatNode(data);
131.  
     pos->prev = newnode;//把新节点newnode的位置给pos的prev
132.  
     newnode->prev = cur;//cur表示的是创建new节点之前的时候pos之前的结点
133.  
     cur->next = newnode;
134.  
     newnode->next = pos;
135.  
     //另一种不使用cur的方法
136.  
     //newnode->next = pos;
137.  
     //pos->prev->next = newnode;
138.  
     //newnode->prev = pos->prev;
139.  
     //pos->prev = newnode;
140.  
     }
141.  
      
142.  
      
143.  
     //删除指针
144.  
     void ListEarse(DSLNode* pos) {
145.  
     assert(pos);
146.  
     DSLNode* cur = pos->prev;
147.  
     DSLNode* tail = pos->next;
148.  
     cur->next = tail;//两者相互指向，最后释放pos空间
149.  
     tail->prev = cur;
150.  
     free(pos);
151.  
     pos = NULL;
152.  
     }
153.  
     //摧毁链表
154.  
     void ListDestory(DSLNode* ps) {
155.  
     //可以设计二级指针直接将ps地址滞空为NULL
156.  
     //这里还是使用一级指针
157.  
     assert(ps);
158.  
     DSLNode* cur = ps->next;
159.  
     while (cur != ps) {
160.  
     DSLNode* tail = cur->next;
161.  
     free(cur);
162.  
     cur = tail;
163.  
     }
164.  
     free(ps);
165.  
     ps = NULL;
166.  
      
167.  
     }
168.  
     void ListDestory2(DSLNode** ps) {
169.  
     assert(ps);
170.  
     free(ps);
171.  
     *ps = NULL;
172.  
     }

3.test.c

1.  
   #define _CRT_SECURE_NO_WARNINGS
2.  
   #include"DSLinkList.h"
3.  
    
4.  
   void test()
5.  
   {
6.  
   DSLNode* phead = ListInit();//初始化
7.  
    
8.  
   ListPushBack(phead, 1);
9.  
   ListPushBack(phead, 2);
10.  
    ListPushBack(phead, 3);
11.  
    ListPushBack(phead, 4);
12.  
    ListPushBack(phead, 5);//检验尾插
13.  
    ListPrint(phead);//打印
14.  
     
15.  
    ListPushFront(phead, 10);
16.  
    ListPushFront(phead, 20);
17.  
    ListPushFront(phead, 30);
18.  
    ListPushFront(phead, 40);
19.  
    ListPushFront(phead, 50);//检验头插
20.  
    ListPrint(phead);//打印
21.  
    printf("%d\n", Listsize(phead));//检验返回结点个数
22.  
     
23.  
    ListPopBack(phead);
24.  
    ListPopBack(phead);
25.  
    ListPopBack(phead);
26.  
    ListPopBack(phead);
27.  
    ListPopBack(phead);//尾删
28.  
    ListPopFront(phead);
29.  
    ListPopFront(phead);
30.  
    ListPopFront(phead);
31.  
    ListPopFront(phead);
32.  
    ListPopFront(phead);//头删
33.  
    ListPrint(phead);//打印
34.  
    ListInsert(phead->next, 10);//pos指定结点之前插入newnode新节点
35.  
    ListPrint(phead);//打印
36.  
    }
37.  
    int main()
38.  
    {
39.  
    test();
40.  
    return 0;
41.  
    }

总结

我们本文主要讲解了，链表中最为复杂的带头双向循环链表的使用和代码实现，实现了头插尾插，头删尾删，初始化、打印、指定pos位置插入结点或者删除结点、寻找结点、摧毁链表等函数。并做了板书图示解释相应函数的流程，附带完整代码，以便帮助大家更好的理解。

接下来我们就要进行栈和队列的学习，本文不足之处，欢迎大佬指导一二，让我们开始新章节的学习！！！

这篇好文章是转载于：学新通技术网