快捷搜索： 迪奥冰雪蜜城店加盟费多少开化妆品店需要多少钱开火锅店需要多少钱开个洗车店要多少钱开淘宝店要多少钱1
首页 / 创业资讯

front row function(c代码实现链表的操作函数 增减删改)

野许雅居认证优质作者 2022-04-20 17:16:26

代码实现链表的操作函数

1.首先是尾插 ，要实现尾插，首先的先有一个链表，并且为空。

即先构造一个链表，并且进行初始化。

[html] view plain copy

  1. //构造链表
  2. typedef int DataType;
  3. typedef struct SListNode {
  4. DataType data;
  5. struct SListNode *pNext;
  6. } SListNode;
  7. // 初始化
  8. void SListInit(SListNode **ppFirst)
  9. {
  10. assert(ppFirst != NULL);
  11. *ppFirst = NULL;
  12. }
  13. 进行尾插前，我们的在构造一个新链表，用来存放尾插后形成的新链表。
  14. SListNode * CreateNewNode(int data)
  15. {
  16. SListNode *pNewNode = (SListNode *)malloc(sizeof(SListNode));
  17. assert(pNewNode);
  18. pNewNode->data = data;
  19. pNewNode->pNext = NULL;
  20. return pNewNode;
  21. }
  22. 下面进行尾插
  23. void PushBack(SListNode **ppFirst, DataType data)
  24. {
  25. assert(ppFirst != NULL);
  26. SListNode *pNewNode = CreateNewNode(data);
  27. if (*ppFirst == NULL) {
  28. *ppFirst = pNewNode;
  29. return;
  30. }
  31. SListNode *pNode;
  32. pNode = *ppFirst;
  33. while (pNode->pNext != NULL) {
  34. pNode = pNode->pNext;
  35. }
  36. // pNode 就是倒数第一个
  37. pNode->pNext = pNewNode;
  38. }
  39. 再加上打印函数与测试函数，main函数。
  40. //print
  41. void Print(SListNode *pFirst)
  42. {
  43. SListNode *pNode;
  44. for (pNode = pFirst; pNode; pNode = pNode->pNext) {
  45. printf("%d -> ", pNode->data);
  46. }
  47. printf("NULLn");
  48. }
  49. //测试函数
  50. void TestSList()
  51. {
  52. SListNode *pFirst;
  53. SListInit(&pFirst);
  54. assert(pFirst == NULL);
  55. PushBack(&pFirst, 1);
  56. assert(pFirst != NULL);
  57. Print(pFirst);
  58. PushBack(&pFirst, 2);
  59. PushBack(&pFirst, 3);
  60. PushBack(&pFirst, 4);
  61. Print(pFirst);
  62. }
  63. //main函数
  64. #include"SList.h"
  65. int main(){
  66. TestSList();
  67. system("pause");
  68. }
  69. 效果如下


2.头插

[html] view plain copy

  1. void PushFront(SListNode **ppFirst, DataType data)
  3. {assert(ppFirst != NULL);
  5. SListNode *pNewNode = CreateNewNode(data);
  7. pNewNode->pNext = *ppFirst;
  8. *ppFirst = pNewNode;
  9. }
  10. 测试函数如下：
  11. PushFront(&pFirst, 5);
  12. PushFront(&pFirst, 8);
  13. Print(pFirst);


3.按下标插入（令给定下标是pos,pos一定存在）

[html] view plain copy

  1. void Insert(SListNode **ppFirst, SListNode *pPos, DataType data)
  2. {
  3. assert(ppFirst != NULL);
  4. SListNode *pNode;
  5. pNode = *ppFirst;
  6. // pPos 是第一个结点地址
  7. if (pPos == *ppFirst) {
  8. PushFront(ppFirst, data);
  9. return;
  10. }
  11. while (pNode->pNext != pPos){
  12. pNode = pNode->pNext;
  13. }
  14. SListNode *pNewNode = CreateNewNode(data);
  15. pNode->pNext = pNewNode;
  16. pNewNode->pNext = pPos;
  17. }
  18. 进行按给定位置插入 需确定pos位置，需定义find函数
  19. //find
  20. SListNode * Find(SListNode *pFirst, DataType data)
  21. {
  22. SListNode *pNode;
  23. for (pNode = pFirst; pNode; pNode = pNode->pNext) {
  24. if (pNode->data == data) {
  25. return pNode;
  26. }
  27. }
  28. return NULL;
  29. }
  30. 测试代码如下：
  31. SListNode *pFound = Find(pFirst, 3);
  32. if (pFound == NULL) {
  33. printf("没有找到n");
  34. }
  35. else {
  36. printf("%dn", pFound->data);
  37. Insert(&pFirst, pFound, 100);
  38. }
  39. Print(pFirst);
  40. 效果如下：


二、删除

1.头删

[html] view plain copy

  1. void PopFront(SListNode **ppFirst)
  2. {
  3. assert(ppFirst != NULL);
  4. assert(*ppFirst != NULL);
  6. SListNode *pOldFirst = *ppFirst;
  7. *ppFirst = (*ppFirst)->pNext;
  8. free(pOldFirst);
  9. }
  10. 测试代码如下：
  11. PopFront(&pFirst);
  12. Print(pFirst);
  13. 效果如下：


frontrow

2.尾删

[html] view plain copy

  1. void PopBack(SListNode **ppFirst)
  2. {
  3. assert(ppFirst != NULL);
  4. assert(*ppFirst != NULL);
  5. if ((*ppFirst)->pNext == NULL) {
  6. free(*ppFirst);
  7. *ppFirst = NULL;
  8. return;
  9. }
  10. SListNode *pNode = *ppFirst;
  11. while (pNode->pNext->pNext != NULL)
  12. {
  13. pNode = pNode->pNext;
  14. }
  15. free(pNode->pNext);
  16. pNode->pNext = NULL;
  17. }
  18. 测试函数如下：
  19. PopBack(&pFirst);
  20. Print(pFirst);
  21. 效果如下：


3.按位置删除（根据结点地址删除，结点肯定在链表里，令节点位置为pPos）

[html] view plain copy

  1. void Erase(SListNode **ppFirst, SListNode *pPos)
  2. {
  3. assert(ppFirst != NULL);
  4. assert(*ppFirst != NULL);
  5. if (*ppFirst == pPos) {
  6. PopFront(ppFirst);
  7. return;
  8. }
  9. SListNode *pCur;
  10. for (pCur = *ppFirst; pCur->pNext != pPos; pCur = pCur->pNext) {
  11. }
  12. // pCur 就是 pPos的前一个
  13. pCur->pNext = pPos->pNext;
  14. free(pPos);
  15. }
  16. 测试函数如下：
  17. SListNode *pFound = Find(pFirst, 1);
  18. { if (pFound == NULL) {
  19. printf("没有找到n");
  20. }
  21. else {
  22. printf("%dn", pFound->data);
  23. Erase(&pFirst, pFound);
  24. }
  25. SListDestroy(&pFirst);
  26. }
  27. 运行效果如下

4.按值删除（根据数据去删除，删除遇到的第一个结点）

[html] view plain copy

  1. void Remove(SListNode **ppFirst, DataType data)
  2. {
  3. SListNode *pFound = Find(*ppFirst, data);
  4. if (pFound != NULL) {
  5. Erase(ppFirst, pFound);
  6. }
  7. }
  8. 测试函数如下：
  9. void TestRemove()
  10. {
  11. SListNode *pFirst;
  12. SListInit(&pFirst);
  13. PushBack(&pFirst, 4);
  14. PushBack(&pFirst, 3);
  15. PushBack(&pFirst, 1);
  16. PushBack(&pFirst, 3);
  17. PushBack(&pFirst, 3);
  18. PushBack(&pFirst, 3);
  19. PushBack(&pFirst, 3);
  20. PushBack(&pFirst, 3);
  21. PushBack(&pFirst, 5);
  22. PushBack(&pFirst, 3);
  23. Print(pFirst);
  24. Remove(&pFirst, 3);
  25. Print(pFirst);
  26. 运行效果如图

5.按值删除（ 根据数据去删除，删除遇到的所有结点）

[html] view plain copy

  1. void RemoveAll(SListNode **ppFirst, DataType data)
  2. {
  3. SListNode *pNode = *ppFirst;
  4. SListNode *pNext;
  5. while (pNode->pNext) {
  6. if (pNode->pNext->data == data) {
  7. pNext = pNode->pNext;
  8. pNode->pNext = pNode->pNext->pNext;
  9. free(pNext);
  10. }
  11. else {
  12. pNode = pNode->pNext;
  13. }
  14. }
  15. if ((*ppFirst)->data == data) {
  16. PopFront(ppFirst);
  17. }
  18. }
  19. 测试函数如下：
  20. RemoveAll(&pFirst, 3);
  21. Print(pFirst);
  22. 测试效果如下


源代码如下：

[html] view plain copy

  1. Hello.h
  2. #pragma once
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. #include <stdio.h>
  6. typedef int DataType;
  7. typedef struct SListNode {
  8. DataType data;
  9. struct SListNode *pNext;
  10. } SListNode;
  11. // 初始化
  12. void SListInit(SListNode **ppFirst)
  13. {
  14. assert(ppFirst != NULL);
  15. *ppFirst = NULL;
  16. }
  17. SListNode * CreateNewNode(int data)
  18. {
  19. SListNode *pNewNode = (SListNode *)malloc(sizeof(SListNode));
  20. assert(pNewNode);
  21. pNewNode->data = data;
  22. pNewNode->pNext = NULL;
  24. return pNewNode;
  25. }
  26. //打印函数
  27. void Print(SListNode *pFirst)
  28. {
  29. SListNode *pNode;
  30. for (pNode = pFirst; pNode; pNode = pNode->pNext) {
  31. printf("%d -> ", pNode->data);
  32. }
  33. printf("NULLn");
  34. }
  35. // 销毁
  36. void SListDestroy(SListNode **ppFirst)
  37. {
  38. assert(ppFirst != NULL);
  39. SListNode *pNode, *pNext;
  41. pNode = *ppFirst;
  42. while (pNode != NULL) {
  43. pNext = pNode->pNext;
  44. free(pNode);
  45. pNode = pNext;
  46. }
  47. *ppFirst = NULL;
  48. }
  50. // 查找，返回遇到的第一个
  51. // 如果找到了，返回结点地址
  52. // 否则返回 NULL
  53. SListNode * Find(SListNode *pFirst, DataType data)
  54. {
  55. SListNode *pNode;
  56. for (pNode = pFirst; pNode; pNode = pNode->pNext) {
  57. if (pNode->data == data) {
  58. return pNode;
  59. }
  60. }
  61. return NULL;
  62. }
  63. // 增删改查
  65. // 尾插
  66. void PushBack(SListNode **ppFirst, DataType data)
  67. {
  68. assert(ppFirst != NULL);
  69. SListNode *pNewNode = CreateNewNode(data);
  70. if (*ppFirst == NULL) {
  71. *ppFirst = pNewNode;
  72. return;
  73. }
  74. SListNode *pNode;
  75. pNode = *ppFirst;
  76. while (pNode->pNext != NULL) {
  77. pNode = pNode->pNext;
  78. }
  79. // pNode 就是倒数第一个
  80. pNode->pNext = pNewNode;
  81. }
  82. /*
  83. // 头插
  84. void PushFront(SListNode **ppFirst, DataType data)
  85. {
  86. assert(ppFirst != NULL);
  87. SListNode *pNewNode = CreateNewNode(data);
  88. pNewNode->pNext = *ppFirst;
  89. *ppFirst = pNewNode;
  90. }
  91. // 插入到给定结点 pPos 前，pPos 肯定在链表里
  92. void Insert(SListNode **ppFirst, SListNode *pPos, DataType data)
  93. {
  94. assert(ppFirst != NULL);
  95. SListNode *pNode;
  96. pNode = *ppFirst;
  97. // pPos 是第一个结点地址
  98. if (pPos == *ppFirst) {
  99. PushFront(ppFirst, data);
  100. return;
  101. }
  102. while (pNode->pNext != pPos){
  103. pNode = pNode->pNext;
  104. }
  105. SListNode *pNewNode = CreateNewNode(data);
  106. pNode->pNext = pNewNode;
  107. pNewNode->pNext = pPos;
  108. }
  109. */
  110. // 头删
  111. void PopFront(SListNode **ppFirst)
  112. {
  113. assert(ppFirst != NULL);
  114. assert(*ppFirst != NULL);
  115. SListNode *pOldFirst = *ppFirst;
  116. *ppFirst = (*ppFirst)->pNext;
  117. free(pOldFirst);
  118. }
  119. // 尾删
  120. void PopBack(SListNode **ppFirst)
  121. {
  122. assert(ppFirst != NULL);
  123. assert(*ppFirst != NULL);
  124. if ((*ppFirst)->pNext == NULL) {
  125. free(*ppFirst);
  126. *ppFirst = NULL;
  127. return;
  128. }
  129. SListNode *pNode = *ppFirst;
  130. while (pNode->pNext->pNext != NULL)
  131. {
  132. pNode = pNode->pNext;
  133. }
  134. free(pNode->pNext);
  135. pNode->pNext = NULL;
  136. }
  137. // 根据结点地址删除，结点肯定在链表里
  138. void Erase(SListNode **ppFirst, SListNode *pPos)
  139. {
  140. assert(ppFirst != NULL);
  141. assert(*ppFirst != NULL);
  142. if (*ppFirst == pPos) {
  143. PopFront(ppFirst);
  144. return;
  145. }
  146. SListNode *pCur;
  147. for (pCur = *ppFirst; pCur->pNext != pPos; pCur = pCur->pNext) {
  148. }
  149. // pCur 就是 pPos的前一个
  150. pCur->pNext = pPos->pNext;
  151. free(pPos);
  152. }
  153. /*
  154. void TestSList()
  155. {
  156. SListNode *pFirst;
  157. SListInit(&pFirst);
  158. assert(pFirst == NULL);
  159. PushBack(&pFirst, 1);
  160. assert(pFirst != NULL);
  161. Print(pFirst);
  162. PushBack(&pFirst, 1);
  163. PushBack(&pFirst, 2);
  164. PushBack(&pFirst, 3);
  165. Print(pFirst);
  166. PushFront(&pFirst, 5);
  167. PushFront(&pFirst, 8);
  168. Print(pFirst);
  169. SListNode *pFound = Find(pFirst, 3);
  170. if (pFound == NULL) {
  171. printf("没有找到n");
  172. }
  173. else {
  174. printf("%dn", pFound->data);
  175. Insert(&pFirst, pFound, 100);
  176. }
  177. Print(pFirst);
  178. PopFront(&pFirst);
  179. Print(pFirst);
  180. PopBack(&pFirst);
  181. Print(pFirst);
  182. SListNode *pFound = Find(pFirst, 9);
  183. { if (pFound == NULL) {
  184. printf("没有找到n");
  185. }
  186. else {
  187. printf("%dn", pFound->data);
  188. Erase(&pFirst, pFound);
  189. }
  190. SListDestroy(&pFirst);
  191. }
  192. }
  193. */
  194. // 根据数据去删除，删除遇到的第一个结点
  195. void Remove(SListNode **ppFirst, DataType data)
  196. {
  197. SListNode *pFound = Find(*ppFirst, data);
  198. if (pFound != NULL) {
  199. Erase(ppFirst, pFound);
  200. }
  201. }
  202. // 根据数据去删除，删除遇到的所有结点
  203. void RemoveAll(SListNode **ppFirst, DataType data)
  204. {
  205. SListNode *pNode = *ppFirst;
  206. SListNode *pNext;
  207. while (pNode->pNext) {
  208. if (pNode->pNext->data == data) {
  209. pNext = pNode->pNext;
  210. pNode->pNext = pNode->pNext->pNext;
  211. free(pNext);
  212. }
  213. else {
  214. pNode = pNode->pNext;
  215. }
  216. }
  217. if ((*ppFirst)->data == data) {
  218. PopFront(ppFirst);
  219. }
  220. }
  221. void TestRemove()
  222. {
  223. SListNode *pFirst;
  224. SListInit(&pFirst);
  225. PushBack(&pFirst, 4);
  226. PushBack(&pFirst, 3);
  227. PushBack(&pFirst, 1);
  228. PushBack(&pFirst, 3);
  229. PushBack(&pFirst, 3);
  230. PushBack(&pFirst, 3);
  231. PushBack(&pFirst, 3);
  232. PushBack(&pFirst, 3);
  233. PushBack(&pFirst, 5);
  234. PushBack(&pFirst, 3);
  235. Print(pFirst);
  236. Remove(&pFirst, 3);
  237. Print(pFirst);
  238. RemoveAll(&pFirst, 3);
  239. Print(pFirst);
  240. }

[html] view plain copy

  1. main.c
  2. #include"Hello.h"
  3. int main(){
  4. TestRemove();
  5. //TestSList();
  6. system("pause");
  7. }

到此，单链表的基本功能差不多都实现了。


frontrow

您可以还会对下面的文章感兴趣

相关文章：

使用微信扫描二维码后

点击右上角发送给好友