• 手撕单链表


    > 作者简介:დ旧言~,目前大一,现在学习Java,c,c++,Python等
    > 座右铭:松树千年终是朽,槿花一日自为荣。
    > 望小伙伴们点赞👍收藏✨加关注哟💕💕 

    4909e8cfd8b84e8b92df3a0e69dfff61.jpeg

     🌟前言       

            前面我们已经学习了顺序表,顺序表可以存储动态的数据,但是一旦元素过少,而又要开辟空间,这样就造成空间的浪费,为了解决这类问题,人们发现了单链表,把一个一个元素以链子的形式存储,那单链表如何实现呢,今天咱们就实现一下--《单链表》。

    🌙主体

    咱们从三个方面实现单链表,动态管理,头插头删尾插尾删,增删查改。

    在程序中为了实现顺序表,需要创建头文件Slist.h ,创建源文件Test.c,Slist.c。

     🌠动态管理

    💤初始化动态单链表

    既然实现单链表,初始化动态的单链表必不可少,从两个方面实现初始化动态的单链表。

    1.首先我们在Slist.h定义动态的单链表,省得我们再定义节点(单链表)。

    1. //重匿名方法来定义数据类型
    2. typedef int SLTDataType;
    3. //定义动态的单链表
    4. typedef struct SListNode
    5. {
    6. //定义数据类型
    7. SLTDataType data;
    8. //指向下一个元素
    9. struct SListNode* next;
    10. }SLTNode;

    2.对单链表进行初始化。(这里和顺序表相似)

    💦这里采用malloc开辟空间

    💦采用预指令判断空间是否开辟完成(没有开辟空间返回-1)

    💦之后就是简单的初始数据

    💦记得返回值

    1. //初始化
    2. SLTNode* BuySListNode(SLTDataType x)
    3. {
    4. //开辟空间
    5. SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    6. //判断开辟的空间是否为空
    7. if (newnode == NULL)
    8. {
    9. perror("malloc fail");
    10. exit(-1);
    11. }
    12. //初始化数据
    13. newnode->data = x;
    14. newnode->next = NULL;
    15. //返回数值
    16. return newnode;
    17. }

    💤释放单链表内存 

    这里就遍历一下单链表就行,没什么好说的

    1. //销毁链表
    2. void SLTDestory(SLTNode** pphead)
    3. {
    4. assert(pphead);
    5. SLTNode* cur = *pphead;
    6. //比cur->next!=NULL更好一些
    7. while (cur)
    8. {
    9. SLTNode* next = cur->next;
    10. free(cur);
    11. cur = next;
    12. }
    13. *pphead = NULL;
    14. }

    🌠头插头删尾插尾删

    💤打印元素

    打印元素就太简单了,直接上代码

    1. //打印数据
    2. void SLTPrint(SLTNode* phead)
    3. {
    4. SLTNode* cur = phead;
    5. while (cur != NULL)
    6. {
    7. printf("%d->", cur->data);
    8. //找到下一个地址
    9. cur = cur->next;
    10. }
    11. printf("NULL\n");
    12. }

     💤头插

    💦1.因为需要改变结构体的指针,因此需要二级指针来接收

    💦2.因为头插是一个元素,因此需要初始化

    💦3.指向开始

    1. //头插
    2. void SLTPushFront(SLTNode** pphead, SLTDataType x)
    3. {
    4. //初始化
    5. SLTNode* newnode = BuySListNode(x);
    6. //改变地址指向
    7. newnode->next = *pphead;
    8. //指向开始
    9. *pphead = newnode;
    10. }

    💤尾插(重点)

    💦1.因为需要改变结构体的指针,因此需要二级指针来接收

    💦2.因为尾插是一个元素,因此需要初始化

    💦3.如果单链表没有元素,直接把头赋值给pphead

    💦4.如果单链表有元素,就需要找到尾,再把开辟好的newnode赋值给tail->next

    1. //尾插
    2. void SLTPushBack(SLTNode** pphead, SLTDataType x)
    3. {
    4. //初始化
    5. SLTNode* newnode = BuySListNode(x);
    6. //判断pphead == NULL
    7. if (*pphead == NULL)
    8. {
    9. //改变的结构体的指针,所以要用二级指针
    10. *pphead = newnode;
    11. }
    12. else
    13. {
    14. SLTNode* tail = *pphead;
    15. while (tail->next != NULL)
    16. {
    17. //找到尾
    18. tail = tail->next;
    19. }
    20. //改变的结构体,用结构体的指针即可(指向空指针)
    21. tail->next = newnode;
    22. }
    23. }

    💤头删(重点)

    头删还是比较简单的,这里就需要注意一点(单链表为空时,不为空时)

    1. //头删
    2. void SLTPopFront(SLTNode** pphead)
    3. {
    4. //空时
    5. assert(*pphead);
    6. //非空时 指向下一个
    7. SLTNode* newhead = (*pphead)->next;
    8. //释放内存
    9. free(*pphead);
    10. *pphead = newhead;
    11. }

    💤尾删(重点)

    💦1.一个节点(一个元素)直接把头指向空(NULL)

    💦2.一个节点以上(一个元素以上),先找到尾,再释放内存,最后尾指向空(NULL)

    1. //尾删
    2. void SLTPopBack(SLTNode** pphead)
    3. {
    4. //不能为空
    5. assert(*pphead);
    6. // 1、一个节点
    7. if ((*pphead)->next == NULL)
    8. {
    9. //释放空间
    10. free(*pphead);
    11. //指向空
    12. *pphead = NULL;
    13. }
    14. // 2、一个以上节点
    15. else
    16. {
    17. //找到尾
    18. SLTNode* tail = *pphead;
    19. while (tail->next->next)
    20. {
    21. tail = tail->next;
    22. }
    23. //释放空间
    24. free(tail->next);
    25. //指向空
    26. tail->next = NULL;
    27. }
    28. }

      🌠增删查改

    💤查找下标

    这个函数是为了增删查改服务的函数,这个函数还是比较好实现的。

    1. //查找下标 需要给尾phead参数
    2. SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
    3. {
    4. SLTNode* cur = phead;
    5. while (cur)
    6. {
    7. if (cur->data == x)
    8. {
    9. return cur;
    10. }
    11. cur = cur->next;
    12. }
    13. return NULL;
    14. }

    💤在pos之前插入x

    💦1.因为需要改变结构体的指针,因此需要二级指针来接收

    💦2.先断言(pphead和pos)

    💦3.如果只有一个元就头插

    💦4.再找到pos之前的地址

    💦5.初始化插入的元素

    💦6.改变元素的地址

    1. //在pos之前插入x
    2. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
    3. {
    4. //断言
    5. assert(pphead);
    6. assert(pos);
    7. //如果只有一个元素就头插
    8. if (pos == *pphead)
    9. {
    10. SLTPushFront(pphead, x);
    11. }
    12. else
    13. {
    14. SLTNode* prev = *pphead;
    15. while (prev->next != pos)
    16. {
    17. prev = prev->next;
    18. }
    19. //初始化
    20. SLTNode* newnode = BuySListNode(x);
    21. //前一个元素地址指向插入的元素
    22. prev->next = newnode;
    23. //插入的元素指向后一个元素
    24. newnode->next = pos;
    25. }
    26. }

    💤在pos之后插入x

    这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点

    1. //在pos以后插入x
    2. void SLTInsertAfter(SLTNode* pos, SLTDataType x)
    3. {
    4. //断言
    5. assert(pos);
    6. //初始化
    7. SLTNode* newnode = BuySListNode(x);
    8. pos->next = newnode;
    9. newnode->next = pos->next;
    10. }

    💤删除pos位置

    💦1.因为需要改变结构体的指针,因此需要二级指针来接收

    💦2.先断言(pphead和pos)

    💦3.如果只有一个元就头删

    💦4.再找到pos的地址

    💦5.修改pos的地址

    💦6.释放内存

    1. //删除pos位置
    2. void SLTErase(SLTNode** pphead, SLTNode* pos)
    3. {
    4. //断言
    5. assert(pphead);
    6. assert(pos);
    7. //如果只有一个元素就头删
    8. if (pos == *pphead)
    9. {
    10. SLTPopFront(pphead);
    11. }
    12. else
    13. {
    14. //找删除的地址
    15. SLTNode* prev = *pphead;
    16. while (prev->next != pos)
    17. {
    18. prev = prev->next;
    19. }
    20. //指向后一元素
    21. prev->next = pos->next;
    22. //释放内存
    23. free(pos);
    24. }
    25. }

    💤删除pos的后一个位置

     这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点

    1. //删除pos的后一个位置
    2. void SLTEraseAfter(SLTNode* pos)
    3. {
    4. //断言
    5. assert(pos);
    6. //检查pos是否是尾节点
    7. assert(pos->next);
    8. //改变地址
    9. SLTNode* posNext = pos->next;
    10. pos->next = posNext->next;
    11. //释放内存
    12. free(posNext);
    13. posNext = NULL;
    14. }

    💤单链表结点修改

           其实这个函数也没啥技术含量, 这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点

    1. // 单链表结点修改
    2. void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
    3. {
    4. SLTNode* cur = phead;
    5. while (cur != pos)
    6. {
    7. cur = cur->next;
    8. assert(cur);
    9. }
    10. pos->data = x;
    11. }

    🌙代码总结

    🌠主函数

    1. //包含头文件
    2. #include"Slist.h"
    3. void TestSList1()
    4. {
    5. int n;
    6. printf("请输入链表的长度:");
    7. scanf("%d", &n);
    8. printf("\n请依次输入每个节点的值:");
    9. SLTNode* plist = NULL;
    10. for (size_t i = 0; i < n; i++)
    11. {
    12. int val;
    13. scanf("%d", &val);
    14. SLTNode* newnode = BuySListNode(val);
    15. //头插
    16. newnode->next = plist;
    17. //指向头
    18. plist = newnode;
    19. }
    20. //打印数据
    21. SLTPrint(plist);
    22. //这里头插本质相似
    23. //SLTPushBack(&plist, 10000);
    24. //打印数据
    25. SLTPrint(plist);
    26. }
    27. void TestSList2()
    28. {
    29. //初始化
    30. SLTNode* plist = NULL;
    31. //头插
    32. SLTPushBack(&plist, 1);
    33. SLTPushBack(&plist, 2);
    34. SLTPushBack(&plist, 3);
    35. SLTPushBack(&plist, 4);
    36. SLTPushBack(&plist, 5);
    37. //打印数据
    38. SLTPrint(plist);
    39. SLTPushFront(&plist, 10);
    40. SLTPushFront(&plist, 20);
    41. SLTPushFront(&plist, 30);
    42. SLTPushFront(&plist, 40);
    43. //打印数据
    44. SLTPrint(plist);
    45. }
    46. void TestSList3()
    47. {
    48. SLTNode* plist = NULL;
    49. SLTPushBack(&plist, 1);
    50. SLTPushBack(&plist, 2);
    51. SLTPushBack(&plist, 3);
    52. SLTPushBack(&plist, 4);
    53. SLTPushBack(&plist, 5);
    54. SLTPrint(plist);
    55. SLTPopBack(&plist);
    56. SLTPrint(plist);
    57. SLTPopBack(&plist);
    58. SLTPrint(plist);
    59. SLTPopBack(&plist);
    60. SLTPrint(plist);
    61. SLTPopBack(&plist);
    62. SLTPrint(plist);
    63. SLTPopBack(&plist);
    64. SLTPrint(plist);
    65. //SLTPopBack(&plist);
    66. //SLTPrint(plist);
    67. }
    68. void TestSList4()
    69. {
    70. SLTNode* plist = NULL;
    71. SLTPushBack(&plist, 1);
    72. SLTPushBack(&plist, 2);
    73. SLTPushBack(&plist, 3);
    74. SLTPushBack(&plist, 4);
    75. SLTPushBack(&plist, 5);
    76. SLTPrint(plist);
    77. SLTPopFront(&plist);
    78. SLTPrint(plist);
    79. SLTPopFront(&plist);
    80. SLTPrint(plist);
    81. SLTPopFront(&plist);
    82. SLTPrint(plist);
    83. SLTPopFront(&plist);
    84. SLTPrint(plist);
    85. SLTPopFront(&plist);
    86. //SLTPopFront(&plist);
    87. SLTPrint(plist);
    88. }
    89. void TestSList5()
    90. {
    91. SLTNode* plist = NULL;
    92. SLTPushBack(&plist, 1);
    93. SLTPushBack(&plist, 2);
    94. SLTPushBack(&plist, 3);
    95. SLTPushBack(&plist, 4);
    96. SLTPushBack(&plist, 5);
    97. SLTPrint(plist);
    98. SLTNode* pos = SLTFind(plist, 40);
    99. if (pos)
    100. {
    101. pos->data *= 10;
    102. }
    103. SLTPrint(plist);
    104. int x;
    105. scanf("%d", &x);
    106. pos = SLTFind(plist, x);
    107. if (pos)
    108. {
    109. SLTInsert(&plist, pos, x * 10);
    110. }
    111. SLTPrint(plist);
    112. }
    113. void TestSList6()
    114. {
    115. SLTNode* plist = NULL;
    116. SLTPushBack(&plist, 1);
    117. SLTPushBack(&plist, 2);
    118. SLTPushBack(&plist, 3);
    119. SLTPushBack(&plist, 4);
    120. SLTPushBack(&plist, 5);
    121. SLTPrint(plist);
    122. int x;
    123. scanf("%d", &x);
    124. SLTNode* pos = SLTFind(plist, x);
    125. if (pos)
    126. {
    127. //SLTInsertAfter(pos, x * 10);
    128. }
    129. SLTPrint(plist);
    130. }
    131. void TestSList7()
    132. {
    133. SLTNode* plist = NULL;
    134. SLTPushBack(&plist, 1);
    135. SLTPushBack(&plist, 2);
    136. SLTPushBack(&plist, 3);
    137. SLTPushBack(&plist, 4);
    138. SLTPushBack(&plist, 5);
    139. SLTPrint(plist);
    140. int x;
    141. scanf("%d", &x);
    142. SLTNode* pos = SLTFind(plist, x);
    143. if (pos)
    144. {
    145. //SLTErase(&plist, pos);
    146. //SLTEraseAfter(pos);
    147. pos = NULL;
    148. }
    149. SLTPrint(plist);
    150. //SLTPopFront(&plist);
    151. //SLTPrint(plist);
    152. //SLTPopFront(&plist);
    153. //SLTPrint(plist);
    154. //SLTPopFront(&plist);
    155. //SLTPrint(plist);
    156. //SLTPopFront(&plist);
    157. //SLTPrint(plist);
    158. }
    159. int main()
    160. {
    161. TestSList7();
    162. return 0;
    163. }

    🌠SqList.h头文件

    1. //使用一些头文件
    2. #include
    3. #include
    4. #include
    5. //重匿名方法来定义数据类型
    6. typedef int SLTDataType;
    7. //定义动态的单链表
    8. typedef struct SListNode
    9. {
    10. //定义数据类型
    11. SLTDataType data;
    12. //指向下一个元素
    13. struct SListNode* next;
    14. }SLTNode;
    15. //初始化
    16. SLTNode* BuySListNode(SLTDataType x);
    17. //打印数据
    18. void SLTPrint(SLTNode* phead);
    19. //尾插
    20. void SLTPushBack(SLTNode** pphead, SLTDataType x);
    21. //头插
    22. void SLTPushFront(SLTNode** pphead, SLTDataType x);
    23. //尾删
    24. void SLTPopBack(SLTNode** pphead);
    25. //头删
    26. void SLTPopFront(SLTNode** pphead);
    27. //查找下标
    28. SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
    29. //在pos之前插入x
    30. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
    31. //在pos以后插入x
    32. void SLTInsertAfter(SLTNode* pos, SLTDataType x);
    33. //删除pos位置
    34. void SLTErase(SLTNode** pphead, SLTNode* pos);
    35. //删除pos的后一个位置
    36. void SLTInsertAfter(SLTNode* pos);
    37. //销毁链表
    38. void SLTDestory(SLTNode** pphead);
    39. // 单链表结点修改
    40. void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x);

    🌠SqList.c源文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. //包含头文件
    3. #include"Slist.h"
    4. //初始化
    5. SLTNode* BuySListNode(SLTDataType x)
    6. {
    7. //开辟空间
    8. SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    9. //判断开辟的空间是否为空
    10. if (newnode == NULL)
    11. {
    12. perror("malloc fail");
    13. exit(-1);
    14. }
    15. //初始化数据
    16. newnode->data = x;
    17. newnode->next = NULL;
    18. //返回数值
    19. return newnode;
    20. }
    21. //打印数据
    22. void SLTPrint(SLTNode* phead)
    23. {
    24. SLTNode* cur = phead;
    25. while (cur != NULL)
    26. {
    27. printf("%d->", cur->data);
    28. //找到下一个地址
    29. cur = cur->next;
    30. }
    31. printf("NULL\n");
    32. }
    33. //头插
    34. void SLTPushFront(SLTNode** pphead, SLTDataType x)
    35. {
    36. //初始化
    37. SLTNode* newnode = BuySListNode(x);
    38. //改变地址指向
    39. newnode->next = *pphead;
    40. //指向开始
    41. *pphead = newnode;
    42. }
    43. //尾插
    44. void SLTPushBack(SLTNode** pphead, SLTDataType x)
    45. {
    46. //初始化
    47. SLTNode* newnode = BuySListNode(x);
    48. //判断pphead == NULL
    49. if (*pphead == NULL)
    50. {
    51. //改变的结构体的指针,所以要用二级指针
    52. *pphead = newnode;
    53. }
    54. else
    55. {
    56. SLTNode* tail = *pphead;
    57. while (tail->next != NULL)
    58. {
    59. //找到尾
    60. tail = tail->next;
    61. }
    62. //改变的结构体,用结构体的指针即可(指向空指针)
    63. tail->next = newnode;
    64. }
    65. }
    66. //头删
    67. void SLTPopFront(SLTNode** pphead)
    68. {
    69. //空时
    70. assert(*pphead);
    71. //非空时
    72. SLTNode* newhead = (*pphead)->next;
    73. free(*pphead);
    74. *pphead = newhead;
    75. }
    76. //尾删
    77. void SLTPopBack(SLTNode** pphead)
    78. {
    79. //不能为空
    80. assert(*pphead);
    81. // 1、一个节点
    82. if ((*pphead)->next == NULL)
    83. {
    84. //释放空间
    85. free(*pphead);
    86. //指向空
    87. *pphead = NULL;
    88. }
    89. // 2、一个以上节点
    90. else
    91. {
    92. //找到尾
    93. SLTNode* tail = *pphead;
    94. while (tail->next->next)
    95. {
    96. tail = tail->next;
    97. }
    98. //释放空间
    99. free(tail->next);
    100. //指向空
    101. tail->next = NULL;
    102. }
    103. }
    104. //查找下标 需要给尾phead参数
    105. SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
    106. {
    107. SLTNode* cur = phead;
    108. while (cur)
    109. {
    110. if (cur->data == x)
    111. {
    112. return cur;
    113. }
    114. cur = cur->next;
    115. }
    116. return NULL;
    117. }
    118. //在pos之前插入x
    119. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
    120. {
    121. //断言
    122. assert(pphead);
    123. assert(pos);
    124. //如果只有一个元素就头插
    125. if (pos == *pphead)
    126. {
    127. SLTPushFront(pphead, x);
    128. }
    129. else
    130. {
    131. SLTNode* prev = *pphead;
    132. while (prev->next != pos)
    133. {
    134. prev = prev->next;
    135. }
    136. //初始化
    137. SLTNode* newnode = BuySListNode(x);
    138. //前一个元素地址指向插入的元素
    139. prev->next = newnode;
    140. //插入的元素指向后一个元素
    141. newnode->next = pos;
    142. }
    143. }
    144. //在pos以后插入x
    145. void SLTInsertAfter(SLTNode* pos, SLTDataType x)
    146. {
    147. //断言
    148. assert(pos);
    149. //初始化
    150. SLTNode* newnode = BuySListNode(x);
    151. pos->next = newnode;
    152. newnode->next = pos->next;
    153. }
    154. //删除pos位置
    155. void SLTErase(SLTNode** pphead, SLTNode* pos)
    156. {
    157. //断言
    158. assert(pphead);
    159. assert(pos);
    160. //如果只有一个元素就头删
    161. if (pos == *pphead)
    162. {
    163. SLTPopFront(pphead);
    164. }
    165. else
    166. {
    167. //找删除的地址
    168. SLTNode* prev = *pphead;
    169. while (prev->next != pos)
    170. {
    171. prev = prev->next;
    172. }
    173. //指向后一元素
    174. prev->next = pos->next;
    175. //释放内存
    176. free(pos);
    177. }
    178. }
    179. //删除pos的后一个位置
    180. void SLTEraseAfter(SLTNode* pos)
    181. {
    182. //断言
    183. assert(pos);
    184. //检查pos是否是尾节点
    185. assert(pos->next);
    186. SLTNode* posNext = pos->next;
    187. pos->next = posNext->next;
    188. free(posNext);
    189. posNext = NULL;
    190. }
    191. // 单链表结点修改
    192. void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
    193. {
    194. SLTNode* cur = phead;
    195. while (cur != pos)
    196. {
    197. cur = cur->next;
    198. assert(cur);
    199. }
    200. pos->data = x;
    201. }
    202. //销毁链表
    203. void SLTDestory(SLTNode** pphead)
    204. {
    205. assert(pphead);
    206. SLTNode* cur = *pphead;
    207. //比cur->next!=NULL更好一些
    208. while (cur)
    209. {
    210. SLTNode* next = cur->next;
    211. free(cur);
    212. cur = next;
    213. }
    214. *pphead = NULL;
    215. }

    🌟结束语

           今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小说手给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。

  • 相关阅读:
    Java面向对象(上)
    Linux——进程间通信(管道及共享内存)
    数据结构-堆排序及其复杂度计算
    JS-Number数字类型详解
    npm ERR! Cannot find module ‘libnpmexec‘
    Containerd 安装使用与高级命令行工具 crictl、nerdctl
    奇舞周刊第507期:通过 View Transition API 在状态之间添加丰富的过渡动画
    RISC-V特权架构 - 中断与异常概述
    SciDAVis for Mac 优秀的类Origin科研绘图软件
    BP神经网络能够做什么,bp神经网络的应用场景
  • 原文地址:https://blog.csdn.net/AAlykk/article/details/132761232