• 数据结构篇其二---单链表(C语言+超万字解析)


    目录

    前言:

    一、顺序表的缺点和链表的引入。

    二、链表概述

    实现一个简单的链表

    空链表的概念

    三、链表的功能实现

    链表的打印

     链表节点的创建

    链表的头插(自上而下看完分析,相信你会有所收获)

    头插的前置分析

    传值调用和传址调用的理解

    头插函数的最终实现

    链表的尾插

    ​编辑

    链表的头删 

    链表的尾删

    链表节点的查找

    ​编辑链表的指定位置之前插入数据

    链表的指定位置之后插入数据

     链表指定节点的删除

     链表删除指定节点之前的节点

    链表的销毁

    四、最终测试结果(附带源代码)

    结尾


    一些无关紧要的废话:

        翻出笔记,回忆当初学链表的日子,啊!真是痛苦的回忆。自以为C语言学得很扎实,结构体,指针。当时我就决心把指针和结构体的博客写好了,翻书翻网课,复习一下笔记。现在,终于还是更新链表,直面当初的恐惧。

      学到后面,发现链表在整个数据结构只是个大头兵罢了。就像一开始学顺序表,觉得还行,发现链表已经比较难啃了,后面,呃,自己体会吧。

    链表篇:单链表,双向链表,静态链表,循环链表。

    由于分时间段写的,后面跟不上最初写的思路,见谅。

    前言:

      单链表,这里不带头节点,只有头指针。

    单链表篇-------我认为单链表帮我深入理解指针和结构体;

    指针部分:

    1.传值和传址调用

    2.涉及到二级指针

    结构体部分:

    结构体自引用;结构体指针;

    一、顺序表的缺点和链表的引入。

    我们要"批判"顺序表,不否认顺序表有它自己的优势,但我们要把使用过程的毛病指出来。

    1.顺序表需要动态扩容

    一般情况都会造成空间浪费,因为刚好装满太不现实。动态顺序表和静态顺序表或多或少都会浪费。

    2.按需申请释放空间

    realloc函数在增容中如果在原有空间后没有足够大,就会另辟蹊径,释放旧空间,重新申请新空间拷贝数据,造成运行效率低下。

    3.实现指定位置的插入和删除整体挪动数据

    时间复杂度O(n),效率低。

    以上"批判"都是鉴于顺序表连续存储的”缺点”。

    那我们思考一下如何解决这些问题。

    Q1:既然有空间浪费问题,那我们难道不能存一个数据开一个数据的空间吗?

    Q2:既然realloc有释放就空间,重新开辟新空间拷贝数据的效率问题,那开一个数据的空间,不用就直接释放,不就可以解决了吗?

    Q3:因为连续存储导致实现指定位置的插入和删除要整体挪动数据,那让每个数据独立的空间,要插入删除,只需要改变它们之间的先后顺序不就可以了吗?

    OK,大致想法有了,下面是整形数据 0,1,2,3,4.

    每个数据都有独立的空间,有新数据了也单独给它开一块刚好大的空间。那么问题来了,我知道0后面的数是1,但我怎么用程序语言描述呢?0和1不是在内存连续存储的,程序可不知到0后面是1。有了!指针就是地址,通过指针变量存储下一个数据的地址不就行了吗。

    哦哦哦,原来每块小的空间要存储这一块的数据和指向下一块的指针。有了下一块的指针就可以访问下一块空间的数据了。

    注意:这里的箭头不是真实存在的,只是逻辑上想象出来的。

    那么每一小块是什么数据类型呢?

    显然就是结构体类型了呗。

    1. struct S {
    2. int data;//存放整型数据
    3. struct S* next;//下一块和这一块都是相同的结构体类型,这里是下一块的指针。
    4. };

    这不就是结构体的自引用吗,不了解可以看看我写的结构体的博客。

    这里只能存储int类型的数据吗?

    当然不是了。因此我们得到了一般的情况。

    1. typedef int SLTDataType;//可以是内置类型,数组,结构体类型,这里可以替换。
    2. typedef struct STLNode {
    3. SLTDataType data;
    4. struct STLNode* next;
    5. }STLNode;

    最后,每次叫一块一块的空间感觉没有逼格,单独起个名字吧,就叫做结点(节点)。

    原来如此,每个节点一部分存储数据(数据域)。另一部存储下一个节点的指针(指针域)。这里的最后一个结点的指向就是空指针了(NULL),最后一个结点叫做尾结点。

    注意:结点和节点是同一个东西。就和同一事物的不同称呼一样。

    🆗下面就引出了链表的概念。

    二、链表概述

    由一的引入,可以说链表是由一个个结点组成的有序集合。

    首先,链表是一种线性表。线性表有逻辑结构和物理结构的特点,那么链表呢?

    链表:

    逻辑结构:连续(线性),满足线性表的定义。

    物理结构:不连续(非线性)。

    那么我们就可以借此画图分析了,即逻辑图和物理图。

    以下就是逻辑图:

    由于链表逻辑上是线性的,我们就可以如此看链表。

    由于每个结点都存储了下一个结点的地址,哪怕尾结点也存储了NULL。

    但是第一个结点的位置(这里不称为头节点,这里不提头节点相关的内容)不知道,需要一个结构体指针变量来记住(存储)这个值,这个结构体指针就称为头指针。

    现在你明白了一个链表(单链表)的结构:

    头指针,各个结点,尾结点指向NULL。

    实现一个简单的链表

    链表(单链表)的结构:

    头指针,各个结点(各节点),尾结点指向NULL。

    按照这种结构在main函数实现一个简单的链表

    1. #include
    2. #include//malloc函数
    3. typedef int SLTDataType;
    4. typedef struct STLNode {
    5. SLTDataType data;
    6. struct STLNode* next;
    7. }STLNode;
    8. int main()
    9. {
    10. //头指针
    11. STLNode* phead = NULL;
    12. //第一个结点
    13. STLNode* s1 = (STLNode*)malloc(sizeof(STLNode));
    14. //头指针指向第一个节点
    15. phead = s1;
    16. //第二个结点
    17. STLNode* s2 = (STLNode*)malloc(sizeof(STLNode));
    18. //第三个结点
    19. STLNode* s3 = (STLNode*)malloc(sizeof(STLNode));
    20. //第四个结点(尾结点)
    21. STLNode* s4 = (STLNode*)malloc(sizeof(STLNode));
    22. //连接前后两个结点,并给相应结点数据域赋值。
    23. s1->data = 1;
    24. s1->next = s2;
    25. s2->data = 2;
    26. s2->next = s3;
    27. s3->data = 3;
    28. s3->next = s4;
    29. s4->data = 4;
    30. s4->next = NULL;
    31. //打印部分先简单看看,稍后具体实现相关函数会解释
    32. STLNode* cur = phead;
    33. while (cur)
    34. {
    35. printf("%d->",cur->data);
    36. cur = cur->next;
    37. }
    38. printf("NULL\n");
    39. return 0;
    40. }

     运行结果如下:

     

    空链表的概念

    如果一个链表没有任何结点,那么称其为空链表。

    那么对于空链表,可以定义为节点指针指向空,或者说头指针指向空;

    即 STLNode* plist = NULL;

    三、链表的功能实现

    链表的打印

    思考一下,打印函数实现的具体步骤是什么?

    1.需要一个结点结构体指针变量,遍历整个链表,要用循环逻辑

    2.每次到一个结点,打印数据部分,并挪动指针到下一个节点。

    1. void STLPrint(STLNode* phead)
    2. {
    3. STLNode* cur = phead;//常见写法,引入循环变量来操作。
    4. //先打印前一个结点的数据域,在通过结点指针变量的赋值,来访问下一个结点。
    5. while (cur)
    6. {
    7. printf("%d->", cur->data);
    8. cur = cur->next;
    9. }
    10. //尾结点的指针部分指向空,打印好观察。
    11. printf("NULL\n");
    12. }

     看看总的效果,代码如下:

    1. #include
    2. #include
    3. #include
    4. typedef int SLTDataType;
    5. typedef struct STLNode {
    6. SLTDataType data;
    7. struct STLNode* next;
    8. }STLNode;
    9. void STLPrint(STLNode* phead);
    10. int main()
    11. {
    12. //头指针
    13. STLNode* phead = (STLNode*)malloc(sizeof(STLNode));
    14. //第一个结点
    15. STLNode* s1 = phead;
    16. //第二个结点
    17. STLNode* s2 = (STLNode*)malloc(sizeof(STLNode));
    18. //第三个结点
    19. STLNode* s3 = (STLNode*)malloc(sizeof(STLNode));
    20. //第四个结点(尾结点)
    21. STLNode* s4 = (STLNode*)malloc(sizeof(STLNode));
    22. //连接前后两个结点,并给相应结点数据域赋值。
    23. s1->data = 1;
    24. s1->next = s2;
    25. s2->data = 2;
    26. s2->next = s3;
    27. s3->data = 3;
    28. s3->next = s4;
    29. s4->data = 4;
    30. s4->next = NULL;
    31. STLPrint(phead);
    32. return 0;
    33. }
    34. void STLPrint(STLNode* phead)
    35. {
    36. STLNode* cur = phead;
    37. while (cur)
    38. {
    39. printf("%d->", cur->data);
    40. cur = cur->next;
    41. }
    42. printf("NULL\n");
    43. }

    附带运行结果。 

     链表节点的创建

    比如创建一个数据为0,指针部分为空的节点,如何想呢?

    这种写法是否准确?

    1. void BuyNode(SLTDataType x)
    2. {
    3. STLNode newnode;
    4. newnode.data = x;
    5. newnode.next = NULL;
    6. }

     很明显这是错误的,因为函数内部声明的变量为局部变量,栈区上申请空间,生命周期是变量声明到出函数。

    因此,显然不能在栈区上申请。我们用动态内存开辟函数在堆区申请空间。

    动态开辟要用节点(结构体)指针。于是就有了第二种想法:

    1. void BuyNode(SLTDataType x)
    2. {
    3. STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
    4. if (NULL == newnode)//判断动态空间是否开辟成功。
    5. {
    6. perror("malloc fail");
    7. exit(1);//异常退出
    8. }
    9. newnode->data = x;//修改数据域
    10. newnode->next = NULL;//指针域为空。
    11. }

     这种情况节点申请成功了,节点会一直存在直至程序结束(如果不主动释放)。但又出现一个问题:这个函数没有其连接功能,它只是单独创建一个节点,我们压根不知道它怎么联系整个链表。创建成功后,出函数我们能找到这个节点吗?答案是不能。这个节点指针是局部变量,存储了指向节点的地址。出函数后也销毁了,再也找不到这个节点了。

    所以第二种方法已经相对成功了,只需要进行如下修改:

    1. STLNode* BuyNode(SLTDataType x)
    2. {
    3. STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
    4. if (NULL == newnode)//判断动态空间是否开辟成功。
    5. {
    6. perror("malloc fail");
    7. exit(1);//异常退出
    8. }
    9. newnode->data = x;//修改数据域
    10. newnode->next = NULL;//指针域为空。
    11. return newnode;
    12. }

    🆗,总结以下这个函数的功能,这个函数需要接受相应的数据,来作为数据域的部分。在堆区为节点开辟空间,并返回指向该节点的地址。

    从功能上它只是单独创建了一个节点,并没有其连接作用,但其返回了地址,使得我们在后面进行尾插和头插操作时,能找到这个节点和起连接作用。

    链表的头插(自上而下看完分析,相信你会有所收获)

    头插的前置分析

     如何实现头插的功能?

    这个头插函数传什么参数,返回类型是什么,思考一下。

    首先,我们考虑把头指针传过去,其次由于要创建节点(调用BuyNode这个函数),也要传入相应的数据部分;最后考虑实现节点之间的连接。

    雏形有了

    1. void STLPushFront(STLNode* phead, SLTDataType x)
    2. {
    3. STLNode* newnode = BuyNode(x);//创建一个节点
    4. //如何连接呢?
    5. }

    如何连接呢,画图分析一下

     先让这个新节点的指针域指向原来的第一个节点,然后让头指针指向新节点。

    1. void STLPushFront(STLNode* phead, SLTDataType x)
    2. {
    3. STLNode* newnode = BuyNode(x);//创建一个节点
    4. //如何连接呢?
    5. newnode->next = phead;
    6. phead = newnode;
    7. }

    这个实际上也有问题。 

     调试分析一下下面代码,并观察运行结果。

    1. #include
    2. #include
    3. #include
    4. typedef int SLTDataType;
    5. typedef struct STLNode {
    6. SLTDataType data;
    7. struct STLNode* next;
    8. }STLNode;
    9. void STLPushFront(STLNode* phead, SLTDataType x);
    10. STLNode* BuyNode(SLTDataType x);
    11. void STLPrint(STLNode* phead);
    12. int main()
    13. {
    14. //头指针
    15. STLNode* phead = (STLNode*)malloc(sizeof(STLNode));
    16. //第一个结点
    17. STLNode* s1 = phead;
    18. //第二个结点
    19. STLNode* s2 = (STLNode*)malloc(sizeof(STLNode));
    20. //第三个结点
    21. STLNode* s3 = (STLNode*)malloc(sizeof(STLNode));
    22. //第四个结点(尾结点)
    23. STLNode* s4 = (STLNode*)malloc(sizeof(STLNode));
    24. //连接前后两个结点,并给相应结点数据域赋值。
    25. s1->data = 1;
    26. s1->next = s2;
    27. s2->data = 2;
    28. s2->next = s3;
    29. s3->data = 3;
    30. s3->next = s4;
    31. s4->data = 4;
    32. s4->next = NULL;
    33. //先打印,头插后再打印一遍。
    34. STLPrint(phead);
    35. STLPushFront(phead, 0);
    36. STLPrint(phead);
    37. return 0;
    38. }
    39. STLNode* BuyNode(SLTDataType x)
    40. {
    41. STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
    42. if (newnode==NULL)//判断动态空间是否开辟成功。
    43. {
    44. perror("malloc fail");
    45. exit(1);//异常退出
    46. }
    47. newnode->data = x;//修改数据域
    48. newnode->next = NULL;//指针域为空。
    49. return newnode;
    50. }
    51. void STLPushFront(STLNode* phead, SLTDataType x)
    52. {
    53. STLNode* newnode = BuyNode(x);//创建一个节点
    54. //如何连接呢?
    55. newnode->next = phead;
    56. phead = newnode;
    57. }
    58. void STLPrint(STLNode* phead)
    59. {
    60. assert(phead);
    61. STLNode* cur = phead;
    62. while (cur)
    63. {
    64. printf("%d->", cur->data);
    65. cur = cur->next;
    66. }
    67. printf("NULL\n");
    68. }

    运行结果说明了,头指针始终指向数据为1的节点,并没有如期望的那样修改。

    为什么呢?

     

    进了头插函数,phead由调试可以知道,“头指针”修改了,但出函数头指针怎么指回去了呢。

    哦哦哦,学了函数你知道形参是实参的一份临时拷贝,是把值得数据复制了一份,这里本质是两个phead,对头插函数内部修改指向,并不能影响原来得phead的指向。本质这里是传值调用。

    那么如何解决呢?

    传值调用和传址调用的理解

    过去,学习的误区,认为传址调用就是传递地址,不理解本质上操作了什么。

    1. #include
    2. void swap1(int* x, int* y)
    3. {
    4. int tmp = *x;
    5. *x = *y;
    6. *y = tmp;
    7. }
    8. void swap2(int** x, int** y)
    9. {
    10. int* tmp = *x;
    11. *x = *y;
    12. *y = tmp;
    13. }
    14. int main()
    15. {
    16. int a = 10;
    17. int b = 20;
    18. printf("交换前:a = %d , b = %d\n", a, b);
    19. swap1(&a, &b);//传a和b的地址。
    20. printf("交换后:a = %d , b = %d\n", a, b);
    21. int* p1 = &a;
    22. int* p2 = &b;
    23. printf("交换前:p1 = %p ,p2 = %p\n", p1, p2);
    24. swap2(&p1, &p2);//传p1和p2的地址。
    25. printf("交换后:p1 = %p , p2 = %p\n", p1, p2);
    26. }

    传址调用本质是通过向函数传递指针,在通过指针解引用的方式来间接操作内部的值。

    这里要修改p1和p2,但是它们的类型是int* ,意味着要在swap2中交换它们的值,就要传递它们的地址。它们本身就是指针,这里要传指针的指针,也就是二级指针,通过二级指针解引用在swap2函数内交换。

    要修改节点就用结构体(节点)指针,要修改结构体指针(头指针)就要用二级指针。 

    头插函数的最终实现

    上面修改头指针失败了,本质就是进行了值拷贝,而没有传址调用。

    1. void STLPushFront(STLNode** pphead, SLTDataType x)
    2. {
    3. assert(pphead);//由于是头指针的指针,需要判断是否为空
    4. STLNode* newnode = BuyNode(x);//创建一个节点
    5. newnode->next = *pphead;
    6. *pphead = newnode;
    7. }

    将这个函数替换原来的STLPushFront函数,再传头指针的地址,打印结果如下:

     那么最后结束了吗?

    并没有,我们还没考虑特殊情况。如果链表本身就是空表呢?检验一下头插代码是否对空表也适用。

    这里的*pphead就为NULL了;

    带进去分析一下,也是成立的。这里不再赘述,不理解,请自己画图分析。头插函数的最终代码就是这个了。

    1. void STLPushFront(STLNode** pphead, SLTDataType x)
    2. {
    3. assert(pphead);//由于是头指针的指针,需要判断是否为空
    4. STLNode* newnode = BuyNode(x);//创建一个节点
    5. newnode->next = *pphead;
    6. *pphead = newnode;
    7. }

    链表的尾插

    这里要创建数据为5的节点并连接上尾部,思考一下如何实现?

    先创建一个节点BuyNode(5);

    这里感觉用不着修改头指针, 可以传头指针的值吧。

    由于我们传递的是头指针,但要实现尾部连接,我们下一步就是找尾部。(用循环实现)

    最后,考虑怎么连接的问题。

    找到尾结点,这里循环终止条件是pcur->next==NULL;此时说明pcur到最后了。

    1. void STLPushBack(STLNode* phead,SLTDataType x)
    2. {
    3. STLNode* newnode = BuyNode(x);
    4. STLNode* pcur = phead;
    5. while (pcur->next != NULL)
    6. {
    7. pcur = pcur->next;
    8. }
    9. //如何连接呢?
    10. }

     

     直接让尾结点的下一个指针部分指向新节点就行了。请自行测试代码是否符合逻辑。

    1. void STLPushBack(STLNode* phead,SLTDataType x)
    2. {
    3. STLNode* newnode = BuyNode(x);
    4. STLNode* pcur = phead;
    5. while (pcur->next != NULL)
    6. {
    7. pcur = pcur->next;
    8. }
    9. pcur->next = newnode;
    10. }

    最后考虑空链表的情况。

    显然这种情况非空链表的逻辑就不符合了,用分支结构吧。

     这里只要修改一下头指针的指向就行了,让头指针指向新节点就可以了。

    嗯?要修改头指针,看来尾插还是要传址调用啊。

    于是就得到了尾插的最终代码。

    1. void STLPushBack(STLNode** pphead,SLTDataType x)
    2. {
    3. assert(pphead);//判断二级指针是否为空,即头指针的有效性
    4. STLNode* newnode = BuyNode(x);//创建节点
    5. STLNode* pcur = *pphead;//引入循环变量,找尾节点
    6. if (NULL==*pphead)//判断空表
    7. {
    8. *pphead = newnode;
    9. return;
    10. }
    11. else//非空表执行尾插逻辑
    12. {
    13. while (pcur->next != NULL)
    14. {
    15. pcur = pcur->next;
    16. }
    17. pcur->next = newnode;
    18. }
    19. }

    链表的头删 

    删除数据为1的节点。

     思路很简单,由于要修改头指针的指向,就要在头删函数内部采用二级指针。

    引入临时变量存储头指针的值;

    改变头指针的指向;

    释放原先的第一个节点;

    1. void STLPopFront(STLNode** pphead)
    2. {
    3. assert(pphead);//判断二级指针是否为空,即头指针的有效性
    4. assert(*pphead);//判断是否为空表,空表不能执行删除操作。
    5. STLNode* tmp = *pphead;//临时变量存储头指针的值
    6. *pphead = (*pphead)->next;//头指针改变执行,指向第二个节点
    7. free(tmp);//释放原来头指针指向的节点
    8. }

    请自行测试代码!

    链表的尾删

    这里还是用二级指针作参数,具体原因不在废话了。

    还是这幅图,不过我们这次删除数据为4的节点。

     思考一下

    首先,对于空表不能执行删除操作。

    其次,对于上述情形,我们还是要找尾结点,然后释放尾结点。但是有个问题倒数第二个节点的指针域应该指向空,如果不置空,就要非法访问了(因为它还记得尾结点的地址,但尾结点已经释放了不归我们管了)。

    很简单,用双指针不就行了吗。

    1. void STLPopBack(STLNode** pphead)
    2. {
    3. assert(pphead && *pphead);//二级指针不为空且不为空表
    4. STLNode* prev = *pphead;//找倒数第二个节点
    5. STLNode* ptail = *pphead;//找尾节点
    6. while (ptail->next)
    7. {
    8. prev = ptail;
    9. ptail = ptail->next;
    10. }
    11. free(ptail);//释放尾结点
    12. prev->next = NULL;//倒数第二个节点置空
    13. }

    那么代码实现完了吗?看一下结果。 

    最后不应该打印NULL;看来双指针实现的代码还是有问题,前面打印都正常,唯独只剩下一个节点的时候出问题了。

     这里其实就很简单了,直接释放头指针指向的节点,再让头指针指向空就OK了,这里的逻辑和双指针是两种情况,用if else语句实现。

    最终代码实现:

    1. void STLPushBack(STLNode** pphead,SLTDataType x)
    2. {
    3. assert(pphead);//判断二级指针是否为空,即头指针的有效性
    4. STLNode* newnode = BuyNode(x);//创建节点
    5. STLNode* pcur = *pphead;//引入循环变量,找尾节点
    6. if (NULL==*pphead)//判断空表
    7. {
    8. *pphead = newnode;
    9. return;
    10. }
    11. else//非空表执行尾插逻辑
    12. {
    13. while (pcur->next != NULL)
    14. {
    15. pcur = pcur->next;
    16. }
    17. pcur->next = newnode;
    18. }
    19. }

    链表节点的查找

    请自行阅读下面代码,从上而下看过来,已经很容易了。

    这里只是遍历查找原链表不用修改头指针,传值调用即可。看完自行实现该代码,会使用这个函数。

    1. STLNode* STLFind(STLNode* phead, SLTDataType x)
    2. {
    3. assert(phead);//空表不能查找
    4. STLNode* pcur = phead;
    5. while (pcur)//遍历链表查找
    6. {
    7. if (x == pcur->data)
    8. {
    9. return pcur;//找到返回指向该节点的指针
    10. }
    11. else
    12. pcur = pcur->next;
    13. }
    14. return NULL;//找不到返回空指针。
    15. }

     测试结果

    链表的指定位置之前插入数据

    给定指定节点的地址pos,要求在其之前插入数据为x节点

     比如在数据为3的节点之前插入数据为5的节点。

    这里我们操作的是2,3和新节点newnode,3节点的地址已经知道了,新节点也知道。二节点的不知道,需要pcur来找到二节点的位置。

    1. void STLInsert(STLNode** pphead, STLNode* pos, SLTDataType x)
    2. {
    3. assert(pphead && *pphead);//二级指针不为空且不能为空表
    4. assert(pos);//节点地址的有效性
    5. STLNode* newnode = BuyNode(x);//创建新节点
    6. STLNode* pcur = *pphead;//临时变量找pos的前一个结点。
    7. while (pcur->next != pos)
    8. {
    9. if (pcur == NULL)//给定节点不存在
    10. {
    11. perror("Not Found!");
    12. return;
    13. }
    14. pcur = pcur->next;
    15. }
    16. //自行画逻辑图分析,很简单
    17. newnode->next = pos;
    18. pcur->next = newnode;
    19. }

    按照惯例,考虑特殊情况,当pos是第一个节点时,意味着这是头插。那么上面代码适用头插的情况吗?

    不适用,从代码上由于循环条件是pcur->next != pos,但此时pcur==pos;这个会一直循环下去直到进入if分支结束函数。

    最终代码:

    1. void STLInsert(STLNode** pphead, STLNode* pos, SLTDataType x)
    2. {
    3. assert(pphead && *pphead);//二级指针不为空且不能为空表
    4. assert(pos);//节点地址的有效性
    5. STLNode* newnode = BuyNode(x);//创建新节点
    6. STLNode* pcur = *pphead;//临时变量找pos的前一个结点。
    7. if (pcur == pos)//分类讨论
    8. {
    9. STLPushFront(pphead,x);//直接调用先前的头插函数,暴力解决
    10. }
    11. else
    12. {
    13. while (pcur->next != pos)
    14. {
    15. if (pcur == NULL)//给定节点不存在
    16. {
    17. perror("Not Found!");
    18. return;
    19. }
    20. pcur = pcur->next;
    21. }
    22. //自行画逻辑图分析,很简单
    23. newnode->next = pos;
    24. pcur->next = newnode;
    25. }
    26. }

    测试一下

    链表的指定位置之后插入数据

    还是这幅图,这里在节点三的位置插入数据为5的节点

    这里不要什么pcur了,因为在指定节点后面插入,位置已经知道了。 

    1. void STLInsertAfter(STLNode** pphead, STLNode* pos, SLTDataType x)
    2. {
    3. assert(pphead && *pphead);//二级指针不为空且不能为空表
    4. assert(pos);//节点地址的有效性
    5. STLNode* newnode = BuyNode(x);//创建新节点
    6. //下面两句代码不能交换,要考虑顺序问题。
    7. newnode->next = pos->next;
    8. pos->next = newnode;
    9. }

    如果是尾插的情况呢?

    即pos->next=NULL;代入发现也成立,所以这个就是最终代码了。 

     链表指定节点的删除

     不再解释,自行分析。

    1. void STLErase(STLNode** pphead, STLNode* pos)
    2. {
    3. assert(pphead && *pphead);
    4. assert(pos);
    5. STLNode* prev = *pphead;
    6. while (prev->next != pos)
    7. {
    8. if (NULL == prev)
    9. {
    10. perror("Not Found!");
    11. return;
    12. }
    13. prev = prev->next;
    14. }
    15. prev->next = pos->next;
    16. free(pos);
    17. }

     链表删除指定节点之前的节点

    1. void STLEraseAfter(STLNode* pos)
    2. {
    3. assert(pos && pos->next);//指定节点存在且有下一个节点
    4. STLNode* del = pos->next;
    5. pos->next = del->next;
    6. free(del);
    7. del = NULL;
    8. }

    链表的销毁

    1. void STLDestroy(STLNode** pphead)
    2. {
    3. assert(pphead);//二级指针不为空
    4. if (NULL == *pphead)
    5. {
    6. return;//已经是空表了,不需要销毁。
    7. }
    8. STLNode* prev = *pphead;
    9. STLNode* ptail = *pphead;
    10. while (ptail->next)
    11. {
    12. prev = ptail;//prev跟上ptail
    13. ptail = ptail->next;//ptail往后挪一位
    14. free(prev);//释放当前节点。
    15. }
    16. prev = ptail = NULL;
    17. *pphead = NULL;//头指针指向空,链表为空表了。
    18. }

    四、最终测试结果(附带源代码)

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. #include
    4. #include
    5. #include
    6. typedef int SLTDataType;
    7. typedef struct STLNode {
    8. SLTDataType data;
    9. struct STLNode* next;
    10. }STLNode;
    11. //函数声明
    12. void STLEraseAfter(STLNode* pos);
    13. void STLErase(STLNode** pphead,STLNode* pos);
    14. void STLDestroy(STLNode** pphead);
    15. void STLInsertAfter(STLNode** pphead, STLNode* pos, SLTDataType x);
    16. void STLInsert(STLNode** pphead, STLNode* pos, SLTDataType x);
    17. void STLPushFront(STLNode** phead, SLTDataType x);
    18. void STLPushBack(STLNode** phead, SLTDataType x);
    19. void STLPopFront(STLNode** pphead);
    20. void STLPopBack(STLNode** pphead);
    21. STLNode* BuyNode(SLTDataType x);
    22. STLNode* STLFind(STLNode* phead, SLTDataType x);
    23. void STLPrint(STLNode* phead);
    24. int main()
    25. {
    26. //头指针
    27. STLNode* phead = (STLNode*)malloc(sizeof(STLNode));
    28. //第一个结点
    29. STLNode* s1 = phead;
    30. //第二个结点
    31. STLNode* s2 = (STLNode*)malloc(sizeof(STLNode));
    32. //第三个结点
    33. STLNode* s3 = (STLNode*)malloc(sizeof(STLNode));
    34. //第四个结点(尾结点)
    35. STLNode* s4 = (STLNode*)malloc(sizeof(STLNode));
    36. //连接前后两个结点,并给相应结点数据域赋值。
    37. s1->data = 1;
    38. s1->next = s2;
    39. s2->data = 2;
    40. s2->next = s3;
    41. s3->data = 3;
    42. s3->next = s4;
    43. s4->data = 4;
    44. s4->next = NULL;
    45. STLPushBack(&phead, 5);
    46. STLPrint(phead);
    47. STLPushFront(&phead, 0);
    48. STLPrint(phead);
    49. STLNode* ret = STLFind(phead, 3);
    50. STLInsert(&phead, ret, 10086);
    51. STLPrint(phead);
    52. STLInsertAfter(&phead, ret, 114514);
    53. STLPrint(phead);
    54. STLEraseAfter(ret);
    55. STLPrint(phead);
    56. STLErase(&phead, ret);
    57. STLPrint(phead);
    58. printf("销毁链表\n");
    59. STLDestroy(&phead);
    60. STLPrint(phead);
    61. return 0;
    62. }
    63. STLNode* BuyNode(SLTDataType x)
    64. {
    65. STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
    66. if (newnode==NULL)//判断动态空间是否开辟成功。
    67. {
    68. perror("malloc fail");
    69. exit(1);//异常退出
    70. }
    71. newnode->data = x;//修改数据域
    72. newnode->next = NULL;//指针域为空。
    73. return newnode;
    74. }
    75. void STLDestroy(STLNode** pphead)
    76. {
    77. assert(pphead);//二级指针不为空
    78. if (NULL == *pphead)
    79. {
    80. return;//已经是空表了,不需要销毁。
    81. }
    82. STLNode* prev = *pphead;
    83. STLNode* ptail = *pphead;
    84. while (ptail->next)
    85. {
    86. prev = ptail;//prev跟上ptail
    87. ptail = ptail->next;//ptail往后挪一位
    88. free(prev);//释放当前节点。
    89. }
    90. prev = ptail = NULL;
    91. *pphead = NULL;//头指针指向空,链表为空表了。
    92. }
    93. void STLEraseAfter(STLNode* pos)
    94. {
    95. assert(pos && pos->next);//指定节点存在且有下一个节点
    96. STLNode* del = pos->next;
    97. pos->next = del->next;
    98. free(del);
    99. del = NULL;
    100. }
    101. void STLErase(STLNode** pphead, STLNode* pos)
    102. {
    103. assert(pphead && *pphead);
    104. assert(pos);
    105. STLNode* prev = *pphead;
    106. while (prev->next != pos)
    107. {
    108. if (NULL == prev)
    109. {
    110. perror("Not Found!");
    111. return;
    112. }
    113. prev = prev->next;
    114. }
    115. prev->next = pos->next;
    116. free(pos);
    117. }
    118. void STLInsertAfter(STLNode** pphead, STLNode* pos, SLTDataType x)
    119. {
    120. assert(pphead && *pphead);//二级指针不为空且不能为空表
    121. assert(pos);//节点地址的有效性
    122. STLNode* newnode = BuyNode(x);//创建新节点
    123. //下面两句代码不能交换,要考虑顺序问题。
    124. newnode->next = pos->next;
    125. pos->next = newnode;
    126. }
    127. void STLInsert(STLNode** pphead, STLNode* pos, SLTDataType x)
    128. {
    129. assert(pphead && *pphead);//二级指针不为空且不能为空表
    130. assert(pos);//节点地址的有效性
    131. STLNode* newnode = BuyNode(x);//创建新节点
    132. STLNode* pcur = *pphead;//临时变量找pos的前一个结点。
    133. if (pcur == pos)//分类讨论
    134. {
    135. STLPushFront(pphead,x);//直接调用先前的头插函数,暴力解决
    136. }
    137. else
    138. {
    139. while (pcur->next != pos)
    140. {
    141. if (pcur == NULL)//给定节点不存在
    142. {
    143. perror("Not Found!");
    144. return;
    145. }
    146. pcur = pcur->next;
    147. }
    148. //自行画逻辑图分析,很简单
    149. newnode->next = pos;
    150. pcur->next = newnode;
    151. }
    152. }
    153. void STLPopBack(STLNode** pphead)
    154. {
    155. assert(pphead && *pphead);//二级指针不为空且不为空表
    156. if ((*pphead)->next == NULL)
    157. {
    158. free(*pphead);
    159. *pphead = NULL;
    160. }
    161. else
    162. {
    163. STLNode* prev = *pphead;//找倒数第二个节点
    164. STLNode* ptail = *pphead;//找尾节点
    165. while (ptail->next)
    166. {
    167. prev = ptail;
    168. ptail = ptail->next;
    169. }
    170. free(ptail);//释放尾结点
    171. prev->next = NULL;//倒数第二个节点置空
    172. }
    173. }
    174. void STLPopFront(STLNode** pphead)
    175. {
    176. assert(pphead);//判断二级指针是否为空,即头指针的有效性
    177. assert(*pphead);//判断是否为空表,空表不能执行删除操作。
    178. STLNode* tmp = *pphead;//临时变量存储头指针的值
    179. *pphead = (*pphead)->next;//头指针改变执行,指向第二个节点
    180. free(tmp);//释放原来头指针指向的节点
    181. }
    182. STLNode* STLFind(STLNode* phead, SLTDataType x)
    183. {
    184. assert(phead);//空表不能查找
    185. STLNode* pcur = phead;
    186. while (pcur)//遍历链表查找
    187. {
    188. if (x == pcur->data)
    189. {
    190. return pcur;//找到返回指向该节点的指针
    191. }
    192. else
    193. pcur = pcur->next;
    194. }
    195. return NULL;//找不到返回空指针。
    196. }
    197. void STLPushBack(STLNode** pphead,SLTDataType x)
    198. {
    199. assert(pphead);//判断二级指针是否为空,即头指针的有效性
    200. STLNode* newnode = BuyNode(x);//创建节点
    201. STLNode* pcur = *pphead;//引入循环变量,找尾节点
    202. if (NULL==*pphead)//判断空表
    203. {
    204. *pphead = newnode;
    205. return;
    206. }
    207. else//非空表执行尾插逻辑
    208. {
    209. while (pcur->next != NULL)
    210. {
    211. pcur = pcur->next;
    212. }
    213. pcur->next = newnode;
    214. }
    215. }
    216. void STLPushFront(STLNode** pphead, SLTDataType x)
    217. {
    218. assert(pphead);//由于是头指针的指针,需要判断是否为空
    219. STLNode* newnode = BuyNode(x);//创建一个节点
    220. newnode->next = *pphead;
    221. *pphead = newnode;
    222. }
    223. void STLPrint(STLNode* phead)
    224. {
    225. STLNode* cur = phead;
    226. while (cur)
    227. {
    228. printf("%d->", cur->data);
    229. cur = cur->next;
    230. }
    231. printf("NULL\n");
    232. }

    结尾

    数据结构篇其二---链表---单链表结束!

    链表系列:单链表,双向链表,循环链表。

    静态链表如果有必要也会更一篇,因为C语言有指针可以实现链表,静态链表目前我看来意义不大。

    总算写完了8个小时,手废了,可利用的时间太少了。我觉得自己独立写完此篇是很爽的,但我现在太累了。后面还有更难的数据结构要更(链表篇还没更完),总之加油吧。

    今天,哦不昨天忘记提交代码了,没有小绿点了。痛!

  • 相关阅读:
    Vue.js vs React:哪一个更适合你的项目?
    Kafka 面试 22 连问,看完直接跟面试官聊骚都没问题
    常见LLM使用的分词算法总结
    MacOS 中Boost的安装和使用
    springboot+vue实现登录案例(附VUE整个项目代码)
    MySQL 索引
    解锁IT能力:JVS快速开发平台引领企业数字化未来
    蓝书 0x01 位运算
    c++结构体
    JS | “购物车”增、删、改、查的案例
  • 原文地址:https://blog.csdn.net/2303_79972050/article/details/138078373