当前位置:   article > 正文

链表 --- C语言实现_c语言实现链表

c语言实现链表

本篇文章来详细介绍一下数据结构中的链表。

目录

1.链表的概念及结构

2.链表的分类

3.单链表的实现

4.链表的面试题

5.双向链表的实现

6.顺序表和链表的区别


1.链表的概念及结构

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

注意:

  1. 从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续
  2. 现实中的结点一般都是从堆上申请出来的
  3. 从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续

2.链表的分类

实际中链表的结构非常多样,以下3种情况组合起来就有8种链表结构,2^3 = 8:
 

1.单项或者双向

 

2.带头或者不带头

 

3.循环或者非循环

 虽然有这么多的链表的结构,但是我们实际中最常用的还是两种结构

 1.无头单向非循环链表

 

2.带头双向循环链表

1.无头单向非循环链表结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表∶结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。

3.单链表的实现

  1. //无头+单行+非循环链表的增删改查实现
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. typedef int SLTDataType;
  6. typedef struct SListNode
  7. {
  8. SLTDataType data;
  9. struct SListNode* next;
  10. }SListNode;
  11. // 动态申请一个节点
  12. SListNode* BuySListNode(SLTDataType x);
  13. // 单链表打印
  14. void SListPrint(SListNode* plist);
  15. // 单链表尾插
  16. void SListPushBack(SListNode** pplist, SLTDataType x);
  17. // 单链表的头插
  18. void SListPushFront(SListNode** pplist, SLTDataType x);
  19. // 单链表的尾删
  20. void SListPopBack(SListNode** pplist);
  21. // 单链表头删
  22. void SListPopFront(SListNode** pplist);
  23. // 单链表查找
  24. SListNode* SListFind(SListNode* plist, SLTDataType x);
  25. // 单链表在pos位置之后插入x
  26. // 分析思考为什么不在pos位置之前插入?因为单链表只能向后访问
  27. void SlistInsertAfter(SListNode* pos, SLTDataType x);
  28. // 单链表删除pos位置之后的值
  29. // 分析思考为什么不删除pos位置?因为单链表只能向后访问
  30. void SlistEraseAfter(SListNode* pos);
  31. // 单链表的销毁
  32. void SListDestroy(SListNode** pphead);
  33. //在pos之前插入
  34. void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
  35. //删除pos位置的值
  36. void SListErase(SListNode** pphead, SListNode* pos);

接口实现:

  1. // 动态申请一个节点
  2. SListNode* BuySListNode(SLTDataType x)
  3. {
  4. SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  5. if (newnode == NULL)
  6. {
  7. perror("malloc fail");
  8. return NULL;
  9. }
  10. //申请成功
  11. newnode->data = x;
  12. newnode->next = NULL;
  13. return newnode;
  14. }
  15. // 单链表打印
  16. void SListPrint(SListNode* plist)
  17. {
  18. SListNode* cur = plist;
  19. while (cur)
  20. {
  21. printf("%d->", cur->data);
  22. cur = cur->next;
  23. }
  24. printf("NULL\n");
  25. }
  26. // 单链表尾插
  27. void SListPushBack(SListNode** pplist, SLTDataType x)
  28. {
  29. assert(pplist);//链表为空,pphead也不为空,因为它是头指针plist的地址
  30. SListNode* newnode = BuySListNode(x);
  31. //空链表
  32. if (*pplist == NULL)
  33. {
  34. *pplist = newnode;
  35. }
  36. else
  37. {
  38. SListNode* tail = *pplist;
  39. while (tail->next)
  40. {
  41. tail = tail->next;
  42. }
  43. tail->next = newnode;
  44. }
  45. }
  46. // 单链表的头插
  47. void SListPushFront(SListNode** pplist, SLTDataType x)
  48. {
  49. assert(pplist);//链表为空,pphead也不为空,因为它是头指针plist的地址
  50. SListNode* newnode = BuySListNode(x);
  51. newnode->next = *pplist;
  52. *pplist = newnode;
  53. }
  54. // 单链表的尾删
  55. void SListPopBack(SListNode** pplist)
  56. {
  57. assert(pplist);//链表为空,pphead也不为空,因为它是头指针plist的地址
  58. assert(*pplist);//空链表不能尾删
  59. if ((*pplist)->next == NULL)
  60. {
  61. free(*pplist);
  62. *pplist = NULL;
  63. }
  64. else
  65. {
  66. //方法一:
  67. SListNode* tail = *pplist;
  68. while (tail->next->next)
  69. {
  70. tail = tail->next;
  71. }
  72. free(tail->next);
  73. tail->next = NULL;
  74. //方法二
  75. /*SListNode* tail = *pplist;
  76. SListNode* prev = *pplist;
  77. while (tail->next)
  78. {
  79. prev = tail;
  80. tail = tail->next;
  81. }
  82. free(tail);
  83. prev->next = NULL;*/
  84. }
  85. }
  86. // 单链表头删
  87. void SListPopFront(SListNode** pplist)
  88. {
  89. assert(pplist);//链表为空,pphead也不为空,因为它是头指针plist的地址
  90. assert(*pplist);//空链表不能头删
  91. SListNode* del = *pplist;
  92. *pplist = (*pplist)->next;
  93. free(del);
  94. del = NULL;
  95. }
  96. // 单链表查找
  97. SListNode* SListFind(SListNode* plist, SLTDataType x)
  98. {
  99. SListNode* cul = plist;
  100. while (cul)
  101. {
  102. if (cul->data == x)
  103. return cul;
  104. cul = cul->next;
  105. }
  106. return NULL;
  107. }
  108. // 单链表在pos位置之后插入x
  109. // 分析思考为什么不在pos位置之前插入?没有地址,找不到,单链表只能找后面的
  110. void SlistInsertAfter(SListNode* pos, SLTDataType x)
  111. {
  112. assert(pos);
  113. SListNode* newnode = BuySListNode(x);
  114. newnode->next = pos->next;
  115. pos->next = newnode;
  116. }
  117. // 单链表删除pos位置之后的值
  118. // 分析思考为什么不删除pos位置?没有地址,找不到
  119. void SlistEraseAfter(SListNode* pos)
  120. {
  121. assert(pos);
  122. assert(pos->next);
  123. SListNode* del = pos->next;
  124. pos->next = pos->next->next;
  125. free(del);
  126. del = NULL;
  127. }
  128. // 单链表的销毁
  129. void SListDestroy(SListNode** pphead)
  130. {
  131. SListNode* del = *pphead;
  132. while (*pphead)
  133. {
  134. del = *pphead;
  135. *pphead = (*pphead)->next;
  136. free(del);
  137. }
  138. }
  139. //在pos之前插入
  140. void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
  141. {
  142. assert(pphead);
  143. SListNode* newnode = BuySListNode(x);
  144. if (pos == *pphead)
  145. {
  146. newnode->next = *pphead;
  147. *pphead = newnode;
  148. }
  149. else
  150. {
  151. SListNode* cur = *pphead;
  152. while (cur)
  153. {
  154. if (cur->next == pos)
  155. {
  156. newnode->next = pos;
  157. cur->next = newnode;
  158. return;
  159. }
  160. cur = cur->next;
  161. }
  162. }
  163. }
  164. //删除pos位置的值
  165. void SListErase(SListNode** pphead, SListNode* pos)
  166. {
  167. assert(pphead);
  168. assert(*pphead);
  169. assert(pos);
  170. if (pos == *pphead)
  171. {
  172. *pphead = (*pphead)->next;
  173. free(pos);
  174. }
  175. else
  176. {
  177. SListNode* cur = *pphead;
  178. while (cur)
  179. {
  180. if (cur->next == pos)
  181. {
  182. cur->next = pos->next;
  183. free(pos);
  184. return;
  185. }
  186. cur = cur->next;
  187. }
  188. }
  189. }

4.链表的面试题

1.删除链表中等于给定值val的所有结点。OJ链接

2.反转一个单链表。OJ链接

3.给定一个带有头结点head的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。ОJ链接

4.输入一个链表,输出该链表中倒数第k个结点。OJ链接

5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。OJ链接

6.编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前。OJ链接

7.链表的回文结构。OJ链接

8.输入两个链表,找出它们的第一个公共结点。OJ链接

9.给定一个链表,判断链表中是否有环OJ链接

【思路】

快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。

【扩展问题】

1.为什么快指针每次走两步,慢指针走一步可以?

假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快指针相遇了,最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况,因此:在慢指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。

2.快指针一次走3步,走4步,...n步行吗?

假设:快指针每次走3步,满指针每次走一步,此时快指针肯定先进环,慢指针后来才进
环。假设慢指针进环时候,快指针的位置如图所示:

此时按照上述方法来绕环移动,每次快指针走3步,慢指针走1步,是永远不会相遇的,快指针刚好将慢指针套圈了,因此不行。
只有快指针走2步,慢指针走一步才可以,因为换的最小长度是1,即使套圈了两个也在相同的位置。

10.给定一个链表,返回链表开始入环的第一个结点。如果链表无环,则返回NULL。OJ链接

结论:

双指针:先让一个指针走一步,一个指针走两步,最终两个指针会在环内相遇。再让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。

证明:

说明:

phead为链表的起始点,E为环入口点,M与判断是否是环的时候相遇点(快慢指针第9题)

设:

环的长度为R,H到E的距离为LE到M的距离为X则:M到E的距离为R-x

在判环时,快慢指针相遇时所走的路径长度:

  • fast: L +X + nR
  • slow: L+ x

注意:

1.当慢指针进入环时,快指针可能已经在环中绕了n圈了,n至少为1因为:快指针先进环走到M的位置,最后又在M的位置与慢指针相遇

2.慢指针进环之后,快指针肯定会在慢指针走一圈之内追上慢指针

因为:慢指针进环后,快慢指针之间的距离最多就是环的长度,而两个指针在移动时,每次它们至今的距离都缩减一步(速度差是1),因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的

而快指针速度是满指针的两倍,因此有如下关系是:2*(L+ X)= L+ X + nR
L+ x = nR
L= nR- x(n为1,2,3,4.......n的大小取决于环的大小,环越小n越大)

极端情况下,假设n = 1,此时:L =R- x

即:一个指针从链表起始位置运行,一个指针从相遇点位置绕环,每次都走一步,两个指针最终会在入口点的位置相遇

11.给定一个链表,每个结点包含一个额外增加的随机指针,该指针可以指向链表中的任何结点
或空结点。

要求返回这个链表的深度拷贝。OJ链接
 

5.双向链表的实现

  1. // 带头+双向+循环链表增删查改实现
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. #include<stdio.h>
  6. #include<stdlib.h>
  7. #include<assert.h>
  8. #include<stdbool.h>
  9. typedef int LTDataType;
  10. typedef struct ListNode
  11. {
  12. struct ListNode* prev;
  13. LTDataType data;
  14. struct ListNode* next;
  15. }LTNode;
  16. //初始化
  17. //void InitListNode(LTNode** phead)//使用二级指针
  18. LTNode* InitListNode();//使用返回值
  19. //打印
  20. void LTPrint(LTNode* phead);
  21. //尾插
  22. void LTPushBack(LTNode* phead, LTDataType x);
  23. //头插
  24. void LTPushFront(LTNode* phead, LTDataType x);
  25. //判空
  26. bool LTEmpty(LTNode* phead);
  27. //尾删
  28. void LTPopBack(LTNode* phead);
  29. //头删
  30. void LTPopFront(LTNode* phead);
  31. //查找
  32. LTNode* LTFind(LTNode* phead, LTDataType x);
  33. //pos之前插入(与顺序表一致)
  34. void LTInsert(LTNode* pos, LTDataType x);
  35. //删除pos位置的值
  36. void LTErase(LTNode* pos);
  37. //释放链表
  38. void LTDestroy(LTNode* phead);

 接口实现:

  1. LTNode* BuyaNewNode(LTDataType x)
  2. {
  3. LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  4. if (newnode == NULL)
  5. {
  6. perror("malloc fail");
  7. return NULL;
  8. }
  9. newnode->prev = NULL;
  10. newnode->next = NULL;
  11. newnode->data = x;
  12. return newnode;
  13. }
  14. //初始化
  15. LTNode* InitListNode()
  16. {
  17. LTNode* phead = BuyaNewNode(0);
  18. phead->next = phead;
  19. phead->prev = phead;
  20. return phead;
  21. }
  22. //打印
  23. void LTPrint(LTNode* phead)
  24. {
  25. assert(phead);
  26. printf("gurad<==>");
  27. LTNode* cur = phead->next;
  28. while (cur != phead)
  29. {
  30. printf("%d<==>", cur->data);
  31. cur = cur->next;
  32. }
  33. printf("gurad\n");
  34. }
  35. //尾插
  36. void LTPushBack(LTNode* phead, LTDataType x)
  37. {
  38. //LTInsert(phead, x);
  39. assert(phead);
  40. LTNode* newnode = BuyaNewNode(x);
  41. LTNode* tail = phead->prev;
  42. tail->next = newnode;
  43. newnode->prev = tail;
  44. newnode->next = phead;
  45. phead->prev = newnode;
  46. }
  47. //头插
  48. void LTPushFront(LTNode* phead, LTDataType x)
  49. {
  50. //LTInsert(phead->next, x);
  51. assert(phead);
  52. LTNode* newnode = BuyaNewNode(x);
  53. newnode->next = phead->next;
  54. phead->next = newnode;
  55. newnode->prev = phead;
  56. newnode->next->prev = newnode;
  57. }
  58. bool LTEmpty(LTNode* phead)
  59. {
  60. if (phead->next == phead)
  61. {
  62. return true;
  63. }
  64. else
  65. {
  66. return false;
  67. }
  68. }
  69. //尾删
  70. void LTPopBack(LTNode* phead)
  71. {
  72. assert(phead);
  73. assert(!LTEmpty(phead));//空链表
  74. //LTErase(phead->prev);
  75. LTNode* tail = phead->prev;
  76. LTNode* tailprev = tail->prev;
  77. free(tail);
  78. phead->prev = tailprev;
  79. tailprev->next = phead;
  80. }
  81. //头删
  82. void LTPopFront(LTNode* phead)
  83. {
  84. assert(phead);
  85. assert(!LTEmpty(phead));//空链表
  86. //LTErase(phead->next);
  87. LTNode* frist = phead->next;
  88. LTNode* second = frist->next;
  89. free(frist);
  90. phead->next = second;
  91. second->prev = phead;
  92. }
  93. //查找
  94. LTNode* LTFind(LTNode* phead, LTDataType x)
  95. {
  96. assert(phead);
  97. LTNode* cur = phead->next;
  98. while (cur != phead)
  99. {
  100. if (cur->data == x)
  101. {
  102. return cur;
  103. }
  104. cur = cur->next;
  105. }
  106. return NULL;
  107. }
  108. //pos之前插入(与顺序表一致)
  109. void LTInsert(LTNode* pos, LTDataType x)
  110. {
  111. assert(pos);
  112. LTNode* newnode = BuyaNewNode(x);
  113. LTNode* prev = pos->prev;
  114. newnode->prev = prev;
  115. newnode->next = pos;
  116. prev->next = newnode;
  117. pos->prev = newnode;
  118. }
  119. //删除pos位置的值
  120. void LTErase(LTNode* pos)
  121. {
  122. assert(pos);
  123. LTNode* prev = pos->prev;
  124. LTNode* next = pos->next;
  125. prev->next = next;
  126. next->prev = prev;
  127. free(pos);
  128. }
  129. //释放链表
  130. void LTDestroy(LTNode* phead)
  131. {
  132. assert(phead);
  133. LTNode* cur = phead->next;
  134. while (cur != phead)
  135. {
  136. LTNode* next = cur->next;
  137. free(cur);
  138. cur = next;
  139. }
  140. free(phead);
  141. }

6.顺序表和链表的区别

链表(双向循环带头链表):

 优点:

  1. 任意位置插入删除O(1)
  2. 按需申请释放空间

 缺点:

  1. 不支持下标随机访问
  2. CPU高速缓存命中率会更低

顺序表:

缺点:

  1. 前面部分插入删除数据,效率是O(N),需要挪动数据。
  2. 空间不够,需要扩容。a、扩容是需要付出代价的 b、一般还会伴随空间浪费。

优点:

  1. 尾插尾删效率不错。
  2. 下标的随机访问。
  3. CPU高速缓存命中率会更高
     
不同点顺序表链表
存储空间上物理上一定连续逻辑上连续,但物理上不一定连续
随机访问支持O(1)不支持,为O(N)
任意位置插入或者删除元素可能需要搬移元素,效率低O(N)只需要修改指针指向
插入动态顺序表,空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入或删除频繁
缓存利用率

 备注:缓存利用率参考存储体系结构 以及 程序的局部性原理。

 数据结构是为了帮助我们跟好的管理内存。内存需要电,关机后就会消失,磁盘存储的数据在关机后也不会消失。

在CPU与内存之间存在寄存器和三级缓存。内存小使用寄存器(一般几个字节),大的使用三级缓存。

CPU读取数据时

  1.  先去看数据是否在缓存,在就叫缓存命中,则直接访问
  2. 不在就不命中,先加载数据到缓存,再访问

因为缓存一次会加载需要的数据以及这个数据旁边的数据,数组是连续存放的,所以缓存利用率高

可以参考:与程序员相关的CPU缓存知识

本篇结束。

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/645920
推荐阅读
相关标签
  

闽ICP备14008679号