【数据结构】链表-C语言版（一）-阿里云开发者社区

顺序表缺点

顺序表随机访问很方便，但是也会有不足啊：

（1）挪动数据时间开销较大：头部/中间的插入删除，需要挪动后面的所有数据，时间复杂度为O(N)

（2）增容有代价：增容需要重新申请空间，拷贝数据，释放旧空间，系统消耗不小

（3）空间浪费：增容一般增至原来的2倍大空间，会有空间浪费，假如当前容量为100，满了以后增容到200，再继续插入了5个数据，后面没有插入数据了，这就浪费了95个空间。

不存在扩容代价、不存在空间浪费、按需申请空间、头部或者中间插入数据而不需要挪动数据的链表可以解决以上问题。

链表的概念和结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

注意：

（1）链式结构在逻辑上连续，逻辑上不一定连续。（逻辑结构是想象的，物理结构是内存中实际存储的）。

（2）结点一般从堆上申请。

（3）堆上申请的空间时按照一定策略分配的，两次申请的空间可能连续也可能不连续。

链表的分类

有8种链表结构：

（1）单向和双向

（2）带头单链表和不带头单链表

（3）非循环链表和循环链表

以上3种分类的链表一共有2*2*2=8种组合，最实用的有两种：

（1）无头单向非循环链表：结构简单，一般不会用来单独存储数据。十几种更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等。

（2）带头双向循环链表：结构最复杂，一般用来单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。虽然结构复杂，但是使用代码实现以后会发现该结构会带来很多优势，实现反而简单。

链表的实现

如果需要交换两个int的值，那么swap函数的实参是两个int的地址，形参是两个int型指针。

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. 
4. void swap(int* pa, int* pb)//用两个指针作为形参接收两个地址
5. {
6.  int temp = *pa;
7.  *pa = *pb;
8.  *pb = temp;
9. }
10. 
11. int main()
12. {
13.   int a = 3;
14.   int b = 5;
15.   swap(&a, &b);//实参是两个int的地址
16.   printf("a = %d\n", a);
17.   printf("a = %d\n", b);
18.   return 0;
19. }

同理，对于链表的增删，如果需要改变指针指向，就要传指针的地址，即二级指针。

链表实现：

025-SList.h 链表函数定义

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #pragma once
3. 
4. typedef int SLTDataType;
5. 
6. typedef struct SListNode
7. {
8.  SLTDataType data;
9.  struct SListNode* next;
10. }SLTNode;
11. 
12. //单向+不带头+非循环
13. 
14. //打印
15. void SListPrint(SLTNode* plist);
16. 
17. //尾插(需要改变指针指向，就要传指针的地址，即二级指针，如需要交换两个int的值，那么swap函数的实参是两个int的地址，形参是两个int型指针)
18. void SListPushBack(SLTNode** plist,SLTDataType x);
19. 
20. //头插
21. void SListPushFront(SLTNode** plist, SLTDataType x);
22. 
23. //尾删
24. void SListPopBack(SLTNode** plist);
25. 
26. //头删
27. void SListPopFront(SLTNode** plist);
28. 
29. //单链表查找
30. SLTNode* SListFind(SLTNode* plist, SLTDataType x);
31. 
32. //在pos之后插入x
33. void SListInsertAfter(SLTNode* pos, SLTDataType x);
34. 
35. //在pos之前插入x
36. void SListInsertBefore(SLTNode** plist,SLTNode* pos, SLTDataType x);
37. 
38. //在pos之前插入x，没有头的情况:后插一个值为x的节点，再跟前面的结点值交换。
39. void SListInsertBeforeNoHead(SLTNode* pos, SLTDataType x);
40. 
41. //删除后一个节点
42. void SListEraseAfter(SLTNode* pos);
43. 
44. //删除当前位置
45. void SListEraseCur(SLTNode** plist, SLTNode* pos);

025-SList.c 链表函数实现

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #pragma once
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include<assert.h>
6. 
7. #include "025-SList.h"
8. 
9. //打印
10. void SListPrint(SLTNode* plist)
11. {
12.   SLTNode* cur = plist;
13. 
14.   //找空节点，找到后不再打印
15.   while (cur != NULL)
16.   {
17.     printf("%d->", cur->data);
18. 
19.     //让cur指向下一个节点
20.     cur = cur->next;
21.   }
22. 
23.   printf("NULL\n");
24. }
25. 
26. //创建新节点
27. SLTNode* BuySLTNode(SLTDataType x)
28. {
29.   //申请空间
30.   SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
31.   if (node == NULL)
32.   {
33.     return NULL;
34.   }
35. 
36.   //数据赋值
37.   node->data = x;
38. 
39.   //指针赋值
40.   node->next = NULL;
41. 
42.   return node;
43. }

（1）尾插：

1. //尾插
2. void SListPushBack(SLTNode** pplist, SLTDataType x)
3. {
4.  SLTNode* newNode = BuySLTNode(x);
5. 
6.  //不能使用tail->next != NULL直接作为判断条件，因为有可能是空链表，对空指针解引用会造成非法访问，因此要分两种情况
7. 
8.  if (*pplist == NULL)//链表为空
9.  {
10.     *pplist = newNode;
11.   }
12.   else //链表不为空
13.   {
14.     SLTNode* tail = *pplist;
15. 
16.     //找尾节点
17.     while (tail->next != NULL)
18.     {
19.       tail = tail->next;
20.     }
21.     tail->next = newNode;
22.   }
23. }

（2）头插，不需要区分空链表和非空链表

1. //头插
2. void SListPushFront(SLTNode** pplist, SLTDataType x)
3. {
4.  SLTNode* newNode = BuySLTNode(x);
5.  newNode->next = *pplist;//新节点的下一个指向第一个节点
6.  *pplist = newNode;//链表指向新节点
7. }

（3）尾删

1. //尾删
2. void SListPopBack(SLTNode** pplist)
3. {
4.  //链表为空
5.  if (*pplist == NULL)
6.  {
7.    return;
8.  }
9.  //链表只有一个结点
10.   else if ((*pplist)->next == NULL)
11.   {
12.     free(*pplist);
13.     *pplist = NULL;
14.   }
15.   //链表有多个结点
16.   else
17.   {
18.     SLTNode* pre = NULL;//后面用该结点指向尾节点的前驱结点，因为删除为节点后，尾节点的前驱结点的后继结点要赋为空指针
19.     SLTNode* tail = *pplist;
20. 
21.     //寻找最后一个结点，循环结束后，tail为尾结点，pre为尾结点的前驱结点
22.     while (tail->next != NULL)
23.     {
24.       pre = tail;
25.       tail = tail->next;
26.     }
27. 
28. 
29.     free(tail);
30.     tail = NULL;
31. 
32.     pre->next = NULL;
33.   }
34. }

（4）头删

1. //头删
2. void SListPopFront(SLTNode** pplist)
3. {
4.  if (*pplist == NULL)
5.  {
6.    return;
7.  }
8.  else
9.  {
10.     SLTNode* next = (*pplist)->next;//保存后一个节点
11.     free(*pplist);
12.     *pplist = next;//链表指向下一个节点
13.   }
14. }

（5）单链表查找

1. //单链表查找
2. SLTNode* SListFind(SLTNode* plist, SLTDataType x)
3. {
4.  SLTNode* cur = plist;
5.  while (cur)//没找到就往后继续走
6.  {
7.    if (cur->data == x)
8.    {
9.      return cur;//找到了就返回
10.     }
11.     cur = cur->next;
12.   }
13.   return NULL;
14. }

（6）在pos之后插入

1. //在pos之后插入
2. void SListInsertAfter(SLTNode* pos, SLTDataType x)
3. {
4.  assert(pos);
5. 
6.  SLTNode* newNode = BuySLTNode(x);//插入需要先创建结点
7.  newNode->next = pos->next;//新节点的下一个指向pos的下一个
8.  pos->next = newNode;//pos的下一个指向新节点
9. }

（7）在pos之前插入x

1. //在pos之前插入x
2. void SListInsertBefore(SLTNode** pplist, SLTNode* pos, SLTDataType x)
3. {
4.  assert(pos);
5. 
6.  SLTNode* newNode = BuySLTNode(x);
7. 
8.  //第一个节点就是pos，即头插
9.  if (pos == *pplist)
10.   {
11.     newNode->next = pos;
12.     *pplist = newNode;
13.   }
14.   else
15.   {
16.     SLTNode* prev = NULL;//用来记录pos的前一个结点
17.     SLTNode* cur = *pplist;
18. 
19.     while (cur != pos)//找pos
20.     {
21.       prev = cur;
22.       cur = cur->next;
23.     }
24. 
25.     newNode->next = cur;//新节点的下一个指向pos，此时跳出while循环的cur=pos
26.     prev->next = newNode;//前一个结点的下一个指向新节点
27.   }
28. }

（8）在pos之前插入x，没有头(plist)：后插一个值为x的节点，再跟前面的结点值交换

1. //在pos之前插入x，没有头(plist)的情况:后插一个值为x的节点，再跟前面的结点值交换。
2. void SListInsertBeforeNoHead(SLTNode* pos, SLTDataType x)
3. {
4.  assert(pos);
5. 
6.  SLTNode* newNode = BuySLTNode(x);
7. 
8.  //后插新节点
9.  newNode->next = pos->next;
10.   pos->next = newNode;
11. 
12.   //将新结点的值和pos的值进行交换
13.   SLTDataType temp = pos->data;
14.   newNode->data = temp;
15.   pos->data = x;
16. }

（9）删除后一个结点

1. //删除后一个节点
2. void SListEraseAfter(SLTNode* pos)
3. {
4.  assert(pos);
5. 
6.  if (pos->next == NULL)
7.  {
8.    return;
9.  }
10.   SLTNode* next = pos->next;
11.   pos->next = next->next;//pos的下一个指向pos的下一个结点的下一个结点
12.   free(next);
13.   next = NULL;
14. }

（10）删除当前位置

1. //删除当前位置
2. void SListEraseCur(SLTNode** pplist, SLTNode* pos)
3. {
4.  assert(pos);
5.  SLTNode* prev = NULL;
6.  SLTNode* cur = *pplist;
7.  while (cur != pos)//寻找pos
8.  {
9.    prev = cur;
10.     cur = cur->next;
11.   }
12.   prev->next = cur->next;//前一个结点的下一个指向当前结点即pos的下一个
13.   free(cur);
14.   cur = NULL;
15. }

025-test.c 测试代码

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. #include<assert.h>
4. 
5. #include "025-SList.h"
6. 
7. void TestSList1()
8. {
9.  SLTNode* plist = NULL;
10.   SListPushBack(&plist, 1);
11.   SListPushBack(&plist, 2);
12.   SListPushBack(&plist, 3);
13.   SListPushBack(&plist, 4);
14. 
15.   SListPrint(plist);
16. 
17.   SListPushFront(&plist, 0);
18.   SListPrint(plist);
19. 
20.   SListPopBack(&plist);
21.   SListPrint(plist);
22.   SListPopBack(&plist);
23.   SListPrint(plist);
24.   SListPopBack(&plist);
25.   SListPrint(plist);
26.   SListPopBack(&plist);
27.   SListPrint(plist);
28. 
29. }
30. void TestSList2()
31. {
32.   SLTNode* plist = NULL;
33.   SListPushBack(&plist, 1);
34.   SListPushBack(&plist, 2);
35.   SListPushBack(&plist, 3);
36.   SListPushBack(&plist, 4);
37.   SListPrint(plist);
38. 
39.   SListPopFront(&plist);
40.   SListPopFront(&plist);
41.   SListPopFront(&plist);
42.   SListPopFront(&plist);
43.   SListPopFront(&plist);
44.   SListPrint(plist);
45. }
46. 
47. void TestSList3()
48. {
49.   SLTNode* plist = NULL;
50.   SListPushBack(&plist, 1);
51.   SListPushBack(&plist, 2);
52.   SListPushBack(&plist, 3);
53.   SListPushBack(&plist, 4);
54.   SListPrint(plist);
55. 
56.   SLTNode* pos = SListFind(plist, 3);
57.   if (pos)
58.   {
59.     //单链表查找兼具修改功能
60.     pos->data = 100;
61.     printf("找到了\n");
62.   }
63.   else
64.   {
65.     printf("没找到\n");
66.   }
67. 
68.   SListPrint(plist);
69. }
70. 
71. void TestSList4()
72. {
73.   SLTNode* plist = NULL;
74.   SListPushBack(&plist, 1);
75.   SListPushBack(&plist, 2);
76.   SListPushBack(&plist, 3);
77.   SListPushBack(&plist, 4);
78.   SListPrint(plist);
79. 
80.   SLTNode* pos = SListFind(plist, 3);
81.   SListInsertAfter(pos, 300);
82.   SListPrint(plist);
83. 
84.   SListInsertBefore(&plist, pos,400);
85.   SListPrint(plist);
86. 
87.   SListEraseCur(&plist, pos);
88.   SListPrint(plist);
89. }
90. 
91. int main()
92. {
93.   TestSList4();
94. 
95.   return 0;
96. }

执行结果：

【数据结构】链表-C语言版（一）

顺序表缺点

链表的概念和结构

链表的分类

链表的实现

热门文章

最新文章

相关课程

相关电子书