深圳幻海软件技术有限公司 欢迎您！
更多

单链表（数据结构）(C语言)

2023-04-25

amp next pos
这里特指无哨兵位单向非循环链表目录背景概念单链表的实现前景提示单链表的结构体定义单链表的打印关于为什么不断言phead关于单链表的逻辑结构和物理结构单链表的尾插关于为什么要用到二级指针关于尾插的本质关于找尾整个过程的解释关于为什么打印单链表就不需要传二级指针单链表的动态申请结点单链表的头插单链表的尾

这里特指无哨兵位单向非循环链表

目录

背景

概念

单链表的实现

前景提示

单链表的结构体定义

单链表的打印

关于为什么不断言phead

关于单链表的逻辑结构和物理结构

单链表的尾插

关于为什么要用到二级指针

关于尾插的本质

关于找尾整个过程的解释

关于为什么打印单链表就不需要传二级指针

单链表的动态申请结点

单链表的头插

单链表的尾删

单链表的头删

链表的查找

单链表在pos位置之前插入x(也可以理解为在pos位置插入)

单链表删除pos位置之前的值(也可以理解为删除pos位置的值)

单链表在pos位置之后插入x 

单链表删除pos位置之后的值

关于不传头指针如何在pos前插入/删除（巧思）

单链表的销毁

总代码（想直接看结果的可以看这里）

背景

上一篇文章我们学习了顺序表。

但顺序表要求的是连续的物理空间，这就导致了其有以下几个缺点：

1. 中间/头部的插入删除，时间复杂度为O(N)。
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
为了更好地解决以上问题，我们就引申出了链表。

概念

链表是一种 物理存储结构上非连续、非顺序的存储结构，数据元素的 逻辑顺序是通过链表 中的 指针链接次序实现的 。链表中一个数据存一个内存块。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的 数据域，另一个是存储下一个结点地址的 指针域。
单链表是一种链式存取的数据结构，用一组 地址任意的存储单元（这组存储单元既可以是连续的，也可以是不连续的）存放线性表中的数据元素。链表中的数据是以 结点( 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。)来表示的，每个结点的构成: 元素+指针，元素就是存储数据的 存储单元，指针就是连接每个结点的 地址数据。
单链表中每个结点的存储地址是存放在其前趋结点 next 域中，而开始结点无前趋，故设头指针head指向开始结点。链表由头指针 唯一确定，单链表可以用头指针的名字来命名，终端结点无后继，故终端结点的指针域为空，即NULL。

单链表的实现

前景提示

SList.h  用于  引用的头文件、单链表的定义、函数的声明。

SList.c  用于  函数的定义。

Test.c    用于  链表功能的测试。

单链表的结构体定义

在SList.h下

  1. #pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突
  2.  
  3. //先将可能使用到的头文件写上
  4. #include<stdio.h>
  5. #include<stdlib.h>
  6. #include<assert.h>
  7.  
  8. typedef int SLTDataType;//假设结点的数据域类型为 int
  9.  
  10. //单链表的结构体定义
  11. typedef struct SListNode
  12. {
  13. SLTDataType data;//结点的数据域，用来存储数据元素
  14. struct SListNode* next;//结点的指针域，用来存储下一个结点地址的指针域
  15.     //next的意思就是下一个结点的指针，上一个结点存的是下一个结点的地址
  16.     //每个结点都是结构体指针类型
  17. //有些人会把上一行代码写成SListNode* next;这是不对的，因为C语言中 
  18.     //struct SListNode 整体才是一个类型(但C++可以)
  19. //或者写成SLTNode* next;这也是错的，因为编译器的查找规则是从上忘下找
  20. }SLTNode;

单链表的打印

要理解单链表，首先我们先写一个单链表的打印。

在SList.h下

  1. //链表的打印——助于理解链表
  2. void SLTPrint(SLTNode* phead);
在SList.c下 
  1. #include "SList.h"//别忘了
  2.  
  3. //链表的打印
  4. void SLTPrint(SLTNode* phead)
  5. {
  6. //assert(phead);这里并不需要断言phead不为空
  7. //为什么这里不需要断言phead？
  8. //空链表可以打印，即phead==NULL可以打印，直接断言就不合适了
  9. //那空顺序表也可以打印，那它为什么就要断言呢？
  10. //因为phead是指向第一个存有数据的结点的
  11. //而顺序表的ps是指向一个结构体
  12. SLTNode* cur = phead;//将phead赋值给cur，所以cur也指向第一个结点
  13. while (cur != NULL)//或while(cur)
  14. {
  15. printf("%d->", cur->data);//打印的时候加了个箭头更方便理解
  16. cur = cur->next;//next是下一个结点的地址
  17. //++cur/cur++;这种是不行的，指针加加，加到的是连续的下一个位置
  18. //链表的每一个结点都是单独malloc出来的，我们不能保证结点之间的地址是连续的
  19. }
  20. printf("NULL\n");
  21. }

关于为什么不断言phead

关于单链表的逻辑结构和物理结构

                     

                     

                   

                     

在打印之前，我们得先有数据

单链表的尾插

在SList.h下

  1. // 单链表尾插
  2. void SLTPushBack(SLTNode** pphead, SLTDataType x);
  3. //用二级指针，解释看下文,x为要插入的数据

关于为什么要用到二级指针

在SList.c下

  1. // 单链表尾插
  2. void SLTPushBack(SLTNode** pphead, SLTDataType x)
  3. {
  4. assert(pphead);//pphead是plist的地址，不能为空
  5.     //注意区分几个断言的判断，plist有可能是空，pphead一定不能为空
  6.  
  7. SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//先创建个结点
  8. if (newnode == NULL)//如果malloc失败
  9. {
  10. perror("malloc fail");
  11. return;
  12. }
  13. //如果malloc成功
  14. newnode->data = x;//插入的数据
  15. newnode->next = NULL;//初始化为空
  16. //找尾(尾插之前先找到尾)
  17. if (*pphead == NULL)//若链表为空
  18. {
  19. *pphead = newnode;
  20. }
  21. else//若链表不为空
  22. {
  23. SLTNode* tail = *pphead;
  24. while (tail->next != NULL)//对于不为空的链表：尾插的本质
  25.                                   //是原尾结点要存新尾结点的地址
  26. {
  27. tail = tail->next;
  28. }
  29. tail->next = newnode;
  30. /*有些同学会写成:
  31. while (tail != NULL)
  32. {
  33. tail = tail->next;
  34. }
  35. tail = newnode;*/
  36. }
  37. }

关于尾插的本质

 

 而

关于找尾整个过程的解释

↓

 

 ↓

在Test.c下

  1. #include "SList.h"//别忘了
  2.  
  3. //用于函数功能的测试
  4. void TestSList1()
  5. {
  6. SLTNode* plist = NULL;
  7. SLTPushBack(&plist, 1);
  8. SLTPushBack(&plist, 2);
  9. SLTPushBack(&plist, 3);
  10. SLTPushBack(&plist, 4);
  11.  
  12. SLTPrint(plist);
  13. }
  14.  
  15. int main()
  16. {
  17. TestSList1();
  18. return 0;
  19. }

关于为什么打印单链表就不需要传二级指针

因为打印单链表没有改变指针。如果要改变传过去的指针(实参)，那就要传实参的地址，不改变就不传。

单链表的动态申请结点

要写头插时，我们发现不管是尾插和头插都要动态申请一个结点，所以我们可以先写一个函数来复用。

在SList.c下

  1. // 动态申请一个结点
  2. SLTNode* BuySLTNode(SLTDataType x)
  3. {
  4. //同样不需要断言
  5. SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//先创建个结点
  6. if (newnode == NULL)//如果malloc失败
  7. {
  8. perror("malloc fail");
  9. return NULL;
  10. }
  11. //如果malloc成功
  12. newnode->data = x;//插入的数据
  13. newnode->next = NULL;//初始化为空
  14.  
  15. return newnode;//返回newnode
  16. }
  17.  
  18. // 单链表尾插
  19. void SLTPushBack(SLTNode** pphead, SLTDataType x)
  20. {
  21.     assert(pphead);//pphead是plist的地址，不能为空
  22.  
  23. SLTNode* newnode = BuySLTNode(x);
  24. //找尾(尾插之前先找到尾)
  25. if (*pphead == NULL)//若链表为空
  26. {
  27. *pphead = newnode;
  28. }
  29. else//若链表不为空
  30. {
  31. SLTNode* tail = *pphead;
  32. while (tail->next != NULL)
  33.         //对于不为空的链表：尾插的本质是原尾结点要存新尾结点的地址
  34. {
  35. tail = tail->next;
  36. }
  37. tail->next = newnode;
  38. /*有些同学会写成:
  39. while (tail != NULL)
  40. {
  41. tail = tail->next;
  42. }
  43. tail = newnode;*/
  44. }
  45. }

单链表的头插

 在SList.h下

  1. // 单链表的头插
  2. void SLTPushFront(SLTNode** pphead, SLTDataType x);

在SList.c下

  1. // 单链表的头插
  2. void SLTPushFront(SLTNode** pphead, SLTDataType x)
  3. {
  4. //发现plist不管是否为空,头插的方法都一样
  5. SLTNode* newnode = BuySLTNode(x);
  6. newnode->next = *pphead;
  7. *pphead = newnode;
  8. }

在Test.c下

  1. void TestSList1()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushBack(&plist, 1);
  5. SLTPushBack(&plist, 2);
  6. SLTPushBack(&plist, 3);
  7. SLTPushBack(&plist, 4);
  8.  
  9. SLTPrint(plist);
  10. }
  11.  
  12. void TestSList2()
  13. {
  14. SLTNode* plist = NULL;
  15. SLTPushFront(&plist, 1);
  16. SLTPushFront(&plist, 2);
  17. SLTPushFront(&plist, 3);
  18. SLTPushFront(&plist, 4);
  19.  
  20. SLTPrint(plist);
  21. }
  22.  
  23.  
  24. int main()
  25. {
  26. TestSList1();
  27. TestSList2();
  28. return 0;
  29. }

单链表的尾删

尾删是否需要二级指针？要！

在SList.h下

  1. // 单链表的尾删
  2. void SLTPopBack(SLTNode** pphead);

在Test.c下

  1. void TestSList2()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushFront(&plist, 1);
  5. SLTPushFront(&plist, 2);
  6. SLTPushFront(&plist, 3);
  7. SLTPushFront(&plist, 4);
  8. SLTPrint(plist);
  9.  
  10. SLTPopBack(&plist);
  11. SLTPrint(plist);
  12. }
  13.  
  14.  
  15. int main()
  16. {
  17. TestSList2();
  18. return 0;
  19. }

在SList.c下

有些人一开始会这样写：

  1. // 单链表的尾删
  2. void SLTPopBack(SLTNode** pphead)
  3. {
  4.     assert(pphead);//pphead是plist的地址，不能为空
  5.  
  6. SLTNode* tail = *pphead;
  7. while (tail->next != NULL)
  8. {
  9. tail = tail->next;
  10. }
  12. free(tail);
  13. tail = NULL;
  14. }

结果是：

出现随机值——>很有可能是因为野指针。

 →

 为什么呢？

这里给更改后的SList.c的两种方法

法一：

  1. // 单链表的尾删
  2. void SLTPopBack(SLTNode** pphead)
  3. {
  4. assert(pphead);//pphead是plist的地址，不能为空
  5.  
  6.     //法一：
  7. SLTNode* prev=NULL;
  8. SLTNode* tail = *pphead;
  9. while (tail->next != NULL)
  10. { 
  11. prev = tail;
  12. tail = tail->next;
  13. }
  15. free(tail);
  16. tail = NULL;
  18. prev->next = NULL;
  19. }

法二：

  1. // 单链表的尾删
  2. void SLTPopBack(SLTNode** pphead)
  3. {
  4. assert(pphead);//pphead是plist的地址，不能为空
  5.  
  6. //法二：
  7. SLTNode* tail = *pphead;
  8. while (tail->next->next != NULL)
  9. {
  10. tail = tail->next;
  11. }
  12.  
  13. free(tail->next);
  14. tail->next = NULL;
  15. }

 但是我们再多测试几组

在Test.c下

  1. void TestSList2()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushFront(&plist, 1);
  5. SLTPushFront(&plist, 2);
  6. SLTPushFront(&plist, 3);
  7. SLTPushFront(&plist, 4);
  8. SLTPrint(plist);
  9.  
  10.     //尾删四个数据
  11. SLTPopBack(&plist);
  12. SLTPrint(plist);
  13. SLTPopBack(&plist);
  14. SLTPrint(plist);
  15. SLTPopBack(&plist);
  16. SLTPrint(plist);
  17. SLTPopBack(&plist);
  18. SLTPrint(plist);
  19. }
  20.  
  21.  
  22. int main()
  23. {
  24. TestSList2();
  25. return 0;
  26. }

结果：

两方法最后都还剩一个！

原因是未考虑到只有一个结点或没有结点的情况。

这里是再次更改后的SList.c

  1. // 单链表的尾删
  2. void SLTPopBack(SLTNode** pphead)
  3. {
  4. assert(pphead);//pphead是plist的地址，不能为空
  5.  
  6. //检查有无结点
  7. assert(*pphead != NULL);
  8. //1.只有一个结点
  9. if ((*pphead)->next == NULL)
  10. {
  11. free(*pphead);
  12. *pphead = NULL;
  13. }
  14. else
  15. {
  16. //2.有多个结点
  17. /*//法一：
  18. SLTNode* prev=NULL;
  19. SLTNode* tail = *pphead;
  20. while (tail->next != NULL)
  21. {
  22. prev = tail;
  23. tail = tail->next;
  24. }
  26. free(tail);
  27. tail = NULL;
  29. prev->next = NULL;*/
  30. //法二：
  31. SLTNode* tail = *pphead;
  32. while (tail->next->next != NULL)
  33. {
  34. tail = tail->next;
  35. }
  36.  
  37. free(tail->next);
  38. tail->next = NULL;
  39. }
  40. }

只有一个结点

没有结点 

单链表的头删

在SList.h下

  1. // 单链表头删
  2. void SLTPopFront(SLTNode** pphead);

在SList.c下

  1. // 单链表头删
  2. void SLTPopFront(SLTNode** pphead)
  3. {
  4. //检查有无结点
  5. assert(*pphead != NULL);
  6.  
  7. SLTNode* first = *pphead;
  8. *pphead = first->next;
  9. free(first);
  10. first = NULL;
  11. }

在Test.c下

  1. TestSList3()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushFront(&plist, 1);
  5. SLTPushFront(&plist, 2);
  6. SLTPushFront(&plist, 3);
  7. SLTPushFront(&plist, 4);
  8. SLTPrint(plist);
  9.  
  10. SLTPopFront(&plist);
  11. SLTPrint(plist);
  12. SLTPopFront(&plist);
  13. SLTPrint(plist);
  14. SLTPopFront(&plist);
  15. SLTPrint(plist);
  16. SLTPopFront(&plist);
  17. SLTPrint(plist);
  18. }
  19.  
  20. int main()
  21. {
  22. TestSList3();
  23. return 0;
  24. }

链表的查找

在SList.h下

  1. // 单链表查找
  2. SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

在SList.c下

  1. // 单链表查找
  2. SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
  3. {
  4. SLTNode* cur = phead;//用cur去遍历,不用phead
  5. while (cur)//找x
  6. {
  7. if (cur->data == x)//如果找到了
  8. {
  9. return cur;
  10. }
  11. cur = cur->next;
  12. }
  13. return NULL;//如果找不到
  14. }

在Test.c下

  1. void TestSList4()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushBack(&plist, 1);
  5. SLTPushBack(&plist, 2);
  6. SLTPushBack(&plist, 3);
  7. SLTPushBack(&plist, 4);
  8. SLTPrint(plist);
  9.  
  10. //将寻找和修改结合
  11. //eg:值为2的结点*2
  12. SLTNode* ret = SLTFind(plist, 2);
  13. ret->data *= 2;
  14. SLTPrint(plist);
  15. }
  16.  
  17.  
  18. int main()
  19. {
  20. TestSList4();
  21. return 0;
  22. }

单链表在pos位置之前插入x(也可以理解为在pos位置插入)

在SList.h下

  1. //单链表在pos位置之前插入x(效率较低)(得传头指针)(也可以理解为在pos位置插入)
  2. void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);

在SList.c下

  1. //单链表在pos位置之前插入x(也可以理解为在pos位置插入)
  2. void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
  3. {
  4. assert(pphead);//pphead是plist的地址，不能为空
  5.  
  6. assert(pos);//默认pos一定会找到
  7. if (pos == *pphead)//如果pos在第一个位置——那就是头插
  8. {
  9. SLTPushFront(pphead, x);
  10. }
  11. else//如果pos不是第一个位置
  12. {
  13. //找到pos的前一个位置
  14. SLTNode* prev = *pphead;
  15. while (prev->next != pos)
  16. {
  17. prev = prev->next;
  18. }
  19. SLTNode* newnode = BuySLTNode(x);
  20. prev->next = newnode;
  21. newnode->next = pos;
  22. }
  23. }

在Test.c下

  1. TestSList5()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushBack(&plist, 1);
  5. SLTPushBack(&plist, 2);
  6. SLTPushBack(&plist, 3);
  7. SLTPushBack(&plist, 4);
  8. SLTPrint(plist);
  9.  
  10. //寻找值为2的结点
  11. SLTNode* ret = SLTFind(plist, 2);
  12. SLTInsertBefore(&plist, ret, 20);//在该结点前插入值为20的结点
  13. SLTPrint(plist);
  14.  
  15. }
  16.  
  17. int main()
  18. {
  19. TestSList5();
  20. return 0;
  21. }

单链表删除pos位置之前的值(也可以理解为删除pos位置的值)

在SList.h下

  1. // 单链表删除pos位置之前的值(效率较低)(得传头指针)(也可以理解为删除pos位置的值)
  2. void SLTEraseBefore(SLTNode** pphead, SLTNode* pos);

在SList.c下

  1. // 单链表删除pos位置之前的值(也可以理解为删除pos位置的值)
  2. void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
  3. {
  4. assert(pphead);
  5. assert(pos);
  6.  
  7. if (*pphead == pos)//如果pos在第一个位置
  8. {
  9. SLTPopFront(pphead);//头删
  10. }
  11. else//如果不在第一个位置
  12. {
  13. SLTNode* prev = *pphead;
  14. while (prev->next != pos)
  15. {
  16. prev = prev->next;
  17. }
  18. prev->next = pos->next;
  19. free(pos);
  20. //pos = NULL;形参的改变不影响实参,加不加这句话都可以
  21. }
  22. }

在Test.c下

  1. TestSList6()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushBack(&plist, 1);
  5. SLTPushBack(&plist, 2);
  6. SLTPushBack(&plist, 3);
  7. SLTPushBack(&plist, 4);
  8. SLTPrint(plist);
  9.  
  10. //寻找值为2的结点
  11. SLTNode* ret = SLTFind(plist, 2);
  12. SLTEraseBefore(&plist, ret);
  13. ret = NULL;//一般在这里置空
  14. SLTPrint(plist);
  15. }
  16.  
  17. int main()
  18. {
  19. TestSList6();
  20. return 0;
  21. }

单链表在pos位置之后插入x 

在SList.h下

  1. // 单链表在pos位置之后插入x,单链表比较适合这种
  2. void SLTInsertAfter(SLTNode* pos, SLTDataType x);

在SList.c下

有些人会这样写：

  1. //单链表在pos位置之后插入x
  2. void SLTInsertAfter(SLTNode* pos, SLTDataType x)
  3. {
  4. assert(pos);
  5. SLTNode* newnode = BuySLTNode(x);
  6. pos->next = newnode;
  7. newnode->next=pos->next;
  8. }

后果：

 所以橙色和紫色的两步应该互换位置

更改后的SList.c

  1. //单链表在pos位置之后插入x
  2. void SLTInsertAfter(SLTNode* pos, SLTDataType x)
  3. {
  4. assert(pos);
  5. SLTNode* newnode = BuySLTNode(x);
  6. newnode->next = pos->next;
  7. pos->next = newnode;
  8. }

在Test.c下

  1. TestSList7()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushBack(&plist, 1);
  5. SLTPushBack(&plist, 2);
  6. SLTPushBack(&plist, 3);
  7. SLTPushBack(&plist, 4);
  8. SLTPrint(plist);
  9.  
  10. SLTNode* ret = SLTFind(plist, 2);
  11. SLTInsertAfter(ret, 20);
  12. SLTPrint(plist);
  13. }
  14.  
  15. int main()
  16. {
  17. TestSList7();
  18. return 0;
  19. }

单链表删除pos位置之后的值

在SList.h下

  1. // 单链表删除pos位置之后的值,单链表比较适合这种
  2. void SLTEraseAfter(SLTNode* pos);

在SList.c下

  1. // 单链表删除pos位置之后的值
  2. void SLTEraseAfter(SLTNode* pos)
  3. {
  4. assert(pos);
  5. assert(pos->next);
  6.  
  7. SLTNode* del = pos->next;//保存要删除的结点
  8. pos->next = pos->next->next;//或者写成pos->next=del->next;
  9. free(del);
  10. del = NULL;
  11. }

在Test.c下

  1. TestSList8()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushBack(&plist, 1);
  5. SLTPushBack(&plist, 2);
  6. SLTPushBack(&plist, 3);
  7. SLTPushBack(&plist, 4);
  8. SLTPrint(plist);
  9.  
  10. SLTNode* ret = SLTFind(plist, 2);
  11. SLTEraseAfter(ret);
  12. SLTPrint(plist);
  13. }
  14.  
  15. int main()
  16. {
  17. TestSList8();
  18. return 0;
  19. }

关于不传头指针如何在pos前插入/删除（巧思）

插入：先利用单链表在pos位置之后插入x的函数,再交换pos和pos->next的值。

在SList.h下

  1. // 不传头指针,在pos前插入x(也可以理解为在pos位置插入)
  2. void SLTInsertBefore1(SLTNode* pos, SLTDataType x);

在SList.c下

  1. // 不传头指针,在pos前插入x(也可以理解为在pos位置插入)
  2. void SLTInsertBefore1(SLTNode* pos, SLTDataType x)
  3. {
  4. assert(pos);
  5.  
  6. //调用单链表在pos位置之后插入x的函数
  7. SLTInsertAfter(pos, x);
  9. //交换pos和pos->next的值
  10. SLTDataType temp;
  11. temp = pos->data;
  12. pos->data = pos->next->data;
  13. pos->next->data = temp;
  14. }

在Test.c下

  1. TestSList9()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushBack(&plist, 1);
  5. SLTPushBack(&plist, 2);
  6. SLTPushBack(&plist, 3);
  7. SLTPushBack(&plist, 4);
  8. SLTPrint(plist);
  9.  
  10. SLTNode* ret = SLTFind(plist, 2);
  11. SLTInsertBefore1(ret,20);
  12. SLTPrint(plist);
  13. }
  14.  
  15. int main()
  16. {
  17. TestSList9();
  18. return 0;
  19. }

删除：先将pos->next的值赋给pos,再利用单链表删除pos位置之后的值的函数。(但此方法不能尾删)

在SList.h下

  1. // 不传头指针,删除pos位置之前的值(也可以理解为删除pos位置的值)
  2. void SLTEraseBefore1(SLTNode* pos);

在SList.c下

  1. // 不传头指针,删除pos位置之前的值(也可以理解为删除pos位置的值)
  2. void SLTEraseBefore1(SLTNode* pos)
  3. {
  4. assert(pos);
  5. assert(pos->next);//不能尾删
  7. SLTNode* del = pos->next;
  8. pos->data = pos->next->data;
  9. pos->next = pos->next->next;
  10. free(del);
  11. del = NULL;
  12. }

在Test.c下

  1. TestSList10()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushBack(&plist, 1);
  5. SLTPushBack(&plist, 2);
  6. SLTPushBack(&plist, 3);
  7. SLTPushBack(&plist, 4);
  8. SLTPrint(plist);
  9.  
  10. SLTNode* ret = SLTFind(plist, 2);
  11. SLTEraseBefore1(ret);
  12. SLTPrint(plist);
  13. }
  14.  
  15. int main()
  16. {
  17. TestSList10();
  18. return 0;
  19. }

单链表的销毁

方法一(不传二级指针):

在SList.h下

  1. // 单链表的销毁,不传二级
  2. void SLTDestroy(SLTNode* phead);

在SList.c下

  1. // 单链表的销毁
  2. void SLTDestroy(SLTNode* phead)
  3. {
  4. SLTNode* cur = phead;
  5. /*//有些人一开始会这样写
  6. while (cur)
  7. {
  8. //free不是销毁这个指针指向的内存,而是将指针指向的内存还给操作系统
  9. free(cur);//cur依旧指向free之前的地址
  10. cur = cur->next;
  11. }*/
  12.  
  13. while (cur)
  14. {
  15. SLTNode* tmp = cur->next;
  16. free(cur);
  17. cur = tmp;
  18. }
  19. }

在Test.c下

  1. TestSList11()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushBack(&plist, 1);
  5. SLTPushBack(&plist, 2);
  6. SLTPushBack(&plist, 3);
  7. SLTPushBack(&plist, 4);
  8. SLTPrint(plist);
  9.  
  10. SLTDestroy(plist);
  11. plist = NULL;
  12. }
  13.  
  14.  
  15. int main()
  16. {
  17. TestSList11();
  18. return 0;
  19. }

方法二(传二级指针):

在SList.h下

  1. // 单链表的销毁,传二级
  2. void SLTDestroy1(SLTNode** pphead);

在SList.c下

  1. // 单链表的销毁,传二级
  2. void SLTDestroy1(SLTNode** pphead)
  3. {
  4. assert(pphead);
  5. SLTNode* cur = *pphead;
  6. while (cur)
  7. {
  8. SLTNode* tmp = cur->next;
  9. free(cur);
  10. cur = tmp;
  11. }
  12. *pphead = NULL;
  13. }

在Test.c下

  1. TestSList12()
  2. {
  3. SLTNode* plist = NULL;
  4. SLTPushBack(&plist, 1);
  5. SLTPushBack(&plist, 2);
  6. SLTPushBack(&plist, 3);
  7. SLTPushBack(&plist, 4);
  8. SLTPrint(plist);
  9.  
  10. SLTDestroy1(&plist);
  11. SLTPrint(plist);
  12. }
  13.  
  14. int main()
  15. {
  16. TestSList12();
  17. return 0;
  18. }

总代码（想直接看结果的可以看这里）

在SList.h下

  1. #pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突
  2.  
  3. //先将可能使用到的头文件写上
  4. #include<stdio.h>
  5. #include<stdlib.h>
  6. #include<assert.h>
  7.  
  8. typedef int SLTDataType;//假设结点的数据域类型为 int
  9.  
  10. // 单链表的结构体定义
  11. //↓结点  单链表 Singly Linked List
  12. typedef struct SListNode
  13. {
  14. SLTDataType data;//结点的数据域,用来存储数据元素
  15. struct SListNode* next;//结点的指针域，用来存储下一个结点地址的指针域
  16. //next的意思就是下一个结点的指针，上一个结点存的是下一个结点的地址
  17. //每个结点都是结构体指针类型
  18. //有些人会把上一行代码写成SListNode* next;
  19.     //这是不对的，因为C语言中 struct SListNode 整体才是一个类型(但C++可以)
  20. //或者写成SLTNode* next;这也是不对的,因为编译器的查找规则是从上忘下找
  21. }SLTNode;
  22.  
  23.  
  24. // 链表的打印——助于理解链表
  25. void SLTPrint(SLTNode* phead);
  26.  
  27. // 单链表尾插
  28. void SLTPushBack(SLTNode** pphead, SLTDataType x);//用二级指针,x为要插入的数据
  29.  
  30. // 单链表的头插
  31. void SLTPushFront(SLTNode** pphead, SLTDataType x);
  32.  
  33. // 单链表的尾删
  34. void SLTPopBack(SLTNode** pphead);
  35.  
  36. // 单链表头删
  37. void SLTPopFront(SLTNode** pphead);
  38.  
  39. // 单链表查找
  40. SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
  41.  
  42. // 单链表在pos位置之前插入x(效率较低)(得传头指针)(也可以理解为在pos位置插入)
  43. void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);
  44.  
  45. // 单链表删除pos位置之前的值(效率较低)(得传头指针)(也可以理解为删除pos位置的值)
  46. void SLTEraseBefore(SLTNode** pphead, SLTNode* pos);
  47.  
  48. // 单链表在pos位置之后插入x,单链表比较适合这种
  49. void SLTInsertAfter(SLTNode* pos, SLTDataType x);
  50.  
  51. // 单链表删除pos位置之后的值,单链表比较适合这种
  52. void SLTEraseAfter(SLTNode* pos);
  53.  
  54. // 不传头指针,在pos前插入x(也可以理解为在pos位置插入)
  55. void SLTInsertBefore1(SLTNode* pos, SLTDataType x);
  56.  
  57. // 不传头指针,删除pos位置之前的值(也可以理解为删除pos位置的值)
  58. void SLTEraseBefore1(SLTNode* pos);
  59.  
  60. // 单链表的销毁,不传二级
  61. void SLTDestroy(SLTNode* phead);
  62.  
  63. // 单链表的销毁,传二级
  64. void SLTDestroy1(SLTNode** pphead);

在SList.c下

  1. #include"SList.h"//别忘了
  2.  
  3. //链表的打印
  4. void SLTPrint(SLTNode* phead)
  5. {
  6. //assert(phead);这里并不需要断言phead不为空
  7. //为什么这里不需要断言？
  8. //空链表可以打印，即phead==NULL可以打印，直接断言就不合适了
  9. //那空顺序表也可以打印，那它为什么就要断言呢？
  10. //因为phead是指向第一个存有数据的结点的
  11. //而顺序表的ps是指向一个结构体
  12. SLTNode* cur = phead;//将phead赋值给cur，所以cur也指向第一个结点
  13. while (cur != NULL)//或while(cur)
  14. {
  15. printf("%d->", cur->data);//打印的时候加了个箭头更方便理解
  16. cur = cur->next;//next是下一个结点的地址
  17. //++cur/cur++;这种是不行的，指针加加，加到的是连续的下一个位置
  18. //链表的每一个结点都是单独malloc出来的，我们不能保证结点之间的地址是连续的
  19. }
  20. printf("NULL\n");
  21. }
  22.  
  23. // 动态申请一个结点
  24. SLTNode* BuySLTNode(SLTDataType x)
  25. {
  26. //同样不需要断言
  27. SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//先创建个结点
  28. if (newnode == NULL)//如果malloc失败
  29. {
  30. perror("malloc fail");
  31. return NULL;
  32. }
  33. //如果malloc成功
  34. newnode->data = x;//插入的数据
  35. newnode->next = NULL;//初始化为空
  36.  
  37. return newnode;//返回newnode
  38. }
  39.  
  40. // 单链表尾插
  41. void SLTPushBack(SLTNode** pphead, SLTDataType x)
  42. {
  43. assert(pphead);//pphead是plist的地址，不能为空
  44. //注意区分几个断言的判断，plist有可能是空，pphead一定不能为空
  45.  
  46. SLTNode* newnode = BuySLTNode(x);
  47. //找尾(尾插之前先找到尾)
  48. if (*pphead == NULL)//若链表为空
  49. {
  50. *pphead = newnode;
  51. }
  52. else//若链表不为空
  53. {
  54. SLTNode* tail = *pphead;
  55. while (tail->next != NULL)
  56.         //对于不为空的链表：尾插的本质是原尾结点要存新尾结点的地址
  57. {
  58. tail = tail->next;
  59. }
  60. tail->next = newnode;
  61. /*有些同学会写成:
  62. while (tail != NULL)
  63. {
  64. tail = tail->next;
  65. }
  66. tail = newnode;*/
  67. }
  68. }
  69.  
  70.  
  71. // 单链表的头插
  72. void SLTPushFront(SLTNode** pphead, SLTDataType x)
  73. {
  74. assert(pphead);//pphead是plist的地址，不能为空
  75.  
  76. //发现plist不管是否为空,头插的方法都一样
  77. SLTNode* newnode = BuySLTNode(x);
  78. newnode->next = *pphead;
  79. *pphead = newnode;
  80. }
  81.  
  82. // 单链表的尾删
  83. void SLTPopBack(SLTNode** pphead)
  84. {
  85. assert(pphead);//pphead是plist的地址，不能为空
  86.  
  87. //检查有无结点
  88. assert(*pphead != NULL);//或者写成assert(*pphead);
  89. //1.只有一个结点
  90. if ((*pphead)->next == NULL)
  91. {
  92. free(*pphead);
  93. *pphead = NULL;
  94. }
  95. else
  96. {
  97. //2.有多个结点
  98. /*//法一：
  99. SLTNode* prev=NULL;
  100. SLTNode* tail = *pphead;
  101. while (tail->next != NULL)
  102. {
  103. prev = tail;
  104. tail = tail->next;
  105. }
  107. free(tail);
  108. tail = NULL;
  110. prev->next = NULL;*/
  111. //法二：
  112. SLTNode* tail = *pphead;
  113. while (tail->next->next != NULL)
  114. {
  115. tail = tail->next;
  116. }
  117.  
  118. free(tail->next);
  119. tail->next = NULL;
  120. }
  121. }
  122.  
  123. // 单链表头删
  124. void SLTPopFront(SLTNode** pphead)
  125. {
  126. assert(pphead);//pphead是plist的地址，不能为空
  127.  
  128. //检查有无结点
  129. assert(*pphead != NULL);
  130.  
  131. SLTNode* first = *pphead;
  132. *pphead = first->next;
  133. free(first);
  134. first = NULL;
  135. }
  136.  
  137. // 单链表查找
  138. SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
  139. {
  140. SLTNode* cur = phead;//用cur去遍历,不用phead
  141. while (cur)//找x
  142. {
  143. if (cur->data == x)//如果找到了
  144. {
  145. return cur;
  146. }
  147. cur = cur->next;
  148. }
  149. return NULL;//如果找不到
  150. }
  151.  
  152. //单链表在pos位置之前插入x(也可以理解为在pos位置插入)
  153. void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
  154. {
  155. assert(pos);//默认pos一定会找到
  156. assert(pphead);//pphead是plist的地址，不能为空
  157. if (pos == *pphead)//如果pos在第一个位置——那就是头插
  158. {
  159. SLTPushFront(pphead, x);
  160. }
  161. else//如果pos不是第一个位置
  162. {
  163. //找到pos的前一个位置
  164. SLTNode* prev = *pphead;
  165. while (prev->next != pos)
  166. {
  167. prev = prev->next;
  168. }
  169. SLTNode* newnode = BuySLTNode(x);
  170. prev->next = newnode;
  171. newnode->next = pos;
  172. }
  173. }
  174.  
  175. // 单链表删除pos位置之前的值(也可以理解为删除pos位置的值)
  176. void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
  177. {
  178. assert(pphead);
  179. assert(pos);
  180.  
  181. if (*pphead == pos)//如果pos在第一个位置
  182. {
  183. SLTPopFront(pphead);//头删
  184. }
  185. else//如果不在第一个位置
  186. {
  187. SLTNode* prev = *pphead;
  188. while (prev->next != pos)
  189. {
  190. prev = prev->next;
  191. }
  192. prev->next = pos->next;
  193. free(pos);
  194. //pos = NULL;形参的改变不影响实参,加不加这句话都可以
  195. }
  196. }
  197.  
  198. //单链表在pos位置之后插入x
  199. void SLTInsertAfter(SLTNode* pos, SLTDataType x)
  200. {
  201. assert(pos);
  202. SLTNode* newnode = BuySLTNode(x);
  203. newnode->next = pos->next;
  204. pos->next = newnode;
  205. }
  206.  
  207. // 单链表删除pos位置之后的值
  208. void SLTEraseAfter(SLTNode* pos)
  209. {
  210. assert(pos);
  211. assert(pos->next);
  212.  
  213. SLTNode* del = pos->next;//保存要删除的结点
  214. pos->next = pos->next->next;//或者写成pos->next=del->next;
  215. free(del);
  216. del = NULL;
  217. }
  218.  
  219. // 不传头指针,在pos前插入x(也可以理解为在pos位置插入)
  220. void SLTInsertBefore1(SLTNode* pos, SLTDataType x)
  221. {
  222. assert(pos);
  223.  
  224. //调用单链表在pos位置之后插入x的函数
  225. SLTInsertAfter(pos, x);
  226.  
  227. //交换pos和pos->next的值
  228. SLTDataType temp;
  229. temp = pos->data;
  230. pos->data = pos->next->data;
  231. pos->next->data = temp;
  232. }
  233.  
  234. // 不传头指针,删除pos位置之前的值(也可以理解为删除pos位置的值)
  235. void SLTEraseBefore1(SLTNode* pos)
  236. {
  237. assert(pos);
  238. assert(pos->next);//不能尾删
  239.  
  240. SLTNode* del = pos->next;
  241. pos->data = pos->next->data;
  242. pos->next = pos->next->next;
  243. free(del);
  244. del = NULL;
  245. }
  246.  
  247. // 单链表的销毁
  248. void SLTDestroy(SLTNode* phead)
  249. {
  250. SLTNode* cur = phead;
  251. /*//有些人一开始会这样写
  252. while (cur)
  253. {
  254. //free不是销毁这个指针指向的内存,而是将指针指向的内存还给操作系统
  255. free(cur);//cur依旧指向free之前的地址
  256. cur = cur->next;
  257. }*/
  258.  
  259. while (cur)
  260. {
  261. SLTNode* tmp = cur->next;
  262. free(cur);
  263. cur = tmp;
  264. }
  265. }
  266.  
  267. // 单链表的销毁,传二级
  268. void SLTDestroy1(SLTNode** pphead)
  269. {
  270. assert(pphead);
  271. SLTNode* cur = *pphead;
  272. while (cur)
  273. {
  274. SLTNode* tmp = cur->next;
  275. free(cur);
  276. cur = tmp;
  277. }
  278. *pphead = NULL;
  279. }

在Test.c下

  1. #include"SList.h"
  2.  
  3. void TestSList1()
  4. {
  5. SLTNode* plist = NULL;
  6. SLTPushBack(&plist, 1);
  7. SLTPushBack(&plist, 2);
  8. SLTPushBack(&plist, 3);
  9. SLTPushBack(&plist, 4);
  10.  
  11. SLTPrint(plist);
  12. }
  13.  
  14. void TestSList2()
  15. {
  16. SLTNode* plist = NULL;
  17. SLTPushFront(&plist, 1);
  18. SLTPushFront(&plist, 2);
  19. SLTPushFront(&plist, 3);
  20. SLTPushFront(&plist, 4);
  21. SLTPrint(plist);
  22.  
  23. SLTPopBack(&plist);
  24. SLTPrint(plist);
  25. SLTPopBack(&plist);
  26. SLTPrint(plist);
  27. SLTPopBack(&plist);
  28. SLTPrint(plist);
  29. SLTPopBack(&plist);
  30. SLTPrint(plist);
  31. }
  32.  
  33. TestSList3()
  34. {
  35. SLTNode* plist = NULL;
  36. SLTPushFront(&plist, 1);
  37. SLTPushFront(&plist, 2);
  38. SLTPushFront(&plist, 3);
  39. SLTPushFront(&plist, 4);
  40. SLTPrint(plist);
  41.  
  42. SLTPopFront(&plist);
  43. SLTPrint(plist);
  44. SLTPopFront(&plist);
  45. SLTPrint(plist);
  46. SLTPopFront(&plist);
  47. SLTPrint(plist);
  48. SLTPopFront(&plist);
  49. SLTPrint(plist);
  50. }
  51.  
  52. void TestSList4()
  53. {
  54. SLTNode* plist = NULL;
  55. SLTPushBack(&plist, 1);
  56. SLTPushBack(&plist, 2);
  57. SLTPushBack(&plist, 3);
  58. SLTPushBack(&plist, 4);
  59. SLTPrint(plist);
  60.  
  61. //将寻找和修改结合
  62. //eg:值为2的结点*2
  63. SLTNode* ret = SLTFind(plist, 2);
  64. ret->data *= 2;
  65. SLTPrint(plist);
  66. }
  67.  
  68. TestSList5()
  69. {
  70. SLTNode* plist = NULL;
  71. SLTPushBack(&plist, 1);
  72. SLTPushBack(&plist, 2);
  73. SLTPushBack(&plist, 3);
  74. SLTPushBack(&plist, 4);
  75. SLTPrint(plist);
  76.  
  77. //寻找值为2的结点
  78. SLTNode* ret = SLTFind(plist, 2);
  79. SLTInsertBefore(&plist, ret, 20);//在该结点前插入值为20的结点
  80. SLTPrint(plist);
  81.  
  82. }
  83.  
  84. TestSList6()
  85. {
  86. SLTNode* plist = NULL;
  87. SLTPushBack(&plist, 1);
  88. SLTPushBack(&plist, 2);
  89. SLTPushBack(&plist, 3);
  90. SLTPushBack(&plist, 4);
  91. SLTPrint(plist);
  92.  
  93. //寻找值为2的结点
  94. SLTNode* ret = SLTFind(plist, 2);
  95. SLTEraseBefore(&plist, ret);
  96. ret = NULL;//一般在这里置空
  97. SLTPrint(plist);
  98. }
  99.  
  100. TestSList7()
  101. {
  102. SLTNode* plist = NULL;
  103. SLTPushBack(&plist, 1);
  104. SLTPushBack(&plist, 2);
  105. SLTPushBack(&plist, 3);
  106. SLTPushBack(&plist, 4);
  107. SLTPrint(plist);
  108.  
  109. SLTNode* ret = SLTFind(plist, 2);
  110. SLTInsertAfter(ret, 20);
  111. SLTPrint(plist);
  112. }
  113.  
  114. TestSList8()
  115. {
  116. SLTNode* plist = NULL;
  117. SLTPushBack(&plist, 1);
  118. SLTPushBack(&plist, 2);
  119. SLTPushBack(&plist, 3);
  120. SLTPushBack(&plist, 4);
  121. SLTPrint(plist);
  122.  
  123. SLTNode* ret = SLTFind(plist, 2);
  124. SLTEraseAfter(ret);
  125. SLTPrint(plist);
  126. }
  127.  
  128. TestSList9()
  129. {
  130. SLTNode* plist = NULL;
  131. SLTPushBack(&plist, 1);
  132. SLTPushBack(&plist, 2);
  133. SLTPushBack(&plist, 3);
  134. SLTPushBack(&plist, 4);
  135. SLTPrint(plist);
  136.  
  137. SLTNode* ret = SLTFind(plist, 2);
  138. SLTInsertBefore1(ret, 20);
  139. SLTPrint(plist);
  140. }
  141.  
  142. TestSList10()
  143. {
  144. SLTNode* plist = NULL;
  145. SLTPushBack(&plist, 1);
  146. SLTPushBack(&plist, 2);
  147. SLTPushBack(&plist, 3);
  148. SLTPushBack(&plist, 4);
  149. SLTPrint(plist);
  150.  
  151. SLTNode* ret = SLTFind(plist, 2);
  152. SLTEraseBefore1(ret);
  153. SLTPrint(plist);
  154. }
  155.  
  156. TestSList11()
  157. {
  158. SLTNode* plist = NULL;
  159. SLTPushBack(&plist, 1);
  160. SLTPushBack(&plist, 2);
  161. SLTPushBack(&plist, 3);
  162. SLTPushBack(&plist, 4);
  163. SLTPrint(plist);
  164.  
  165. SLTDestroy(plist);
  166. plist = NULL;
  167. }
  168.  
  169. TestSList12()
  170. {
  171. SLTNode* plist = NULL;
  172. SLTPushBack(&plist, 1);
  173. SLTPushBack(&plist, 2);
  174. SLTPushBack(&plist, 3);
  175. SLTPushBack(&plist, 4);
  176. SLTPrint(plist);
  177.  
  178. SLTDestroy1(&plist);
  179. SLTPrint(plist);
  180. }
  181.  
  182. int main()
  183. {
  184. //TestSList1();
  185. //TestSList2();
  186. //TestSList3();
  187. //TestSList4();
  188. //TestSList5();
  189. //TestSList6();
  190. //TestSList7();
  191. //TestSList8();
  192. //TestSList9();
  193. //TestSList10();
  194. //TestSList11();
  195. TestSList12();
  196. return 0;
  197. }

欢迎指正❀

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览45038 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪