[数据结构]单链表详解

目次
一、次序表的题目及思考
二、单链表的实现
1.结构体内容的界说（typedef struct SListNode）
2.链表的打印（void SLTPrint(SLTNode* phead)）
​编辑3.链表的尾插（void SLPushBack(SLTNode* phead, SLTDataType x)）
3.1尾插错误示范：
3.2注意事项：
3.3修改后的尾插函数：
3.4打印结果：
 3.5知识梳理：
4.链表的头插：（void SListPushFront(SLTNode** pphead, SLTDataType x)）
5.链表的尾删：（void SListPushFront(SLTNode** pphead, SLTDataType x)）
6.链表的头删：（void SListPopFront(SLTNode** pphead)）
7.链表的查找：（SLTNode* SListFind(SLTNode* phead, SLTDataType x)）
8.在指定位置（pos）之前插入:（void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)）
9.在指定位置（pos）位置删除:（void SLTErase(SLTNode** pphead, SLTNode* pos)）
10.在指定位置（pos）背面插入：（void SLTInsertAfter(SLTNode* pos, SLTDataType x)）
11.链表的销毁：（void SLTDestroy(SLTNode* phead)）
三、单链表功能汇总
SList.h：
SList.c
test.c

---

一、次序表的题目及思考

   题目：    1.  中心  /  头部的插入删除，时间复杂度为  O(N)    2.  增容必要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。    3.  增容一般是呈  2  倍的增长，势必会有肯定的空间浪费。例如当前容量为  100  ，满了以后增容到    200  ，我们再继承插入了  5  个数据，背面没有数据插入了，那么就浪费了  95  个数据空间。    思考：如何解决以上题目呢？下面给出了链表的结构来看看。   

    上一个节点存着下一个结点的地点，每一个结点都是一个结构体  二、单链表的实现

1.结构体内容的界说（typedef struct SListNode）

  

1. #pragma once
2. #include <stdlib.h>
3. #include<stdio.h>
4. typedef int SLTDataType;
5. typedef struct SListNode
6. {
7.        SLDataType data;
8.        struct SListNode* Next;//这里并不是结构体里面有个结构体，而是结构体里面有个指针，它的类型是结构体类型
9.        //SListNode* Next; 这里还不能这样写，这里涉及到编译器的查找规则：如果一个函数或者一个类型需要使用，那么编译器会向上查找而不会向下
10. }SListNode;

复制代码

2.链表的打印（void SLTPrint(SLTNode* phead)）

1. void SLTPrint(SLTNode* phead)
2. {
3.        //不需要assert断言，因为空的链表可以打印，只是没有数据而已
4.        SLTNode* cur = phead;
5.        while (cur != NULL)
6.        {
7.               printf("%d->", cur->data);
8.               cur = cur->Next;//Next是下一个节点的地址
9.        }
10.        printf("NULL\n");
11. }

复制代码

3.链表的尾插（void SLPushBack(SLTNode* phead, SLTDataType x)）

  尾插本质：原尾结点中要存储新的尾结点的地点
  3.1尾插错误示范：

1. void SLPushBack(SLTNode* phead, SLTDataType x)
2. {
3.        SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
4.               if (newnode == NULL)
5.               {
6.                       perror("malloc fail");
7.               }
8.               newnode->data = x;
9.               newnode->Next = NULL;
10.               //找尾
11.               SLTNode* tail = phead;
12.               while (tail->Next != NULL)
13.               {
14.                       tail = tail->Next;
15.               }
16.               tail->Next = newnode;//tail= newnode;这样写是错的，要想把两个链表链接起来，必须要让一个链表的最后一个数的下一个地址存放着下一个数的地址，tail目前存的是最后一个元素的地址而不是最后一个元素的下一个元素的地址
17. }

复制代码

  3.2注意事项：

  test.c文件：

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include "SList.h"
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.     SLTPrint(plist);
11. }
12. int main()
13. {
14.     TestSList1();
15.     return 0;
16. }

复制代码

  

这里phead的改变不会引起plist的改变，现在要改变的是SLTNode*，传进去SLTNode*根本不起作用，应该传SLTNode**
  

  3.3修改后的尾插函数：

1. void SLTPushBack(SLTNode** pphead, SLTDataType x)
2. {
3.        SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
4.        if (newnode == NULL)
5.        {
6.               perror("malloc fail");
7.        }
8.        newnode->data = x;
9.        newnode->Next = NULL;
10.        if (*pphead == NULL)
11.        {
12.               *pphead = newnode;
13.        }。
14.        else
15.        {
16.               //找尾
17.               SLTNode* tail = *pphead;
18.               while (tail->Next != NULL)
19.               {
20.                       tail = tail->Next;
21.               }
22.               tail->Next = newnode;//tail= newnode;这样写是错的，要想把两个链表链接起来，必须要让一个链表的最后一个数的下一个地址存放着下一个数的地址，
23.               //tail目前存的是最后一个元素的地址而不是最后一个元素的下一个元素的地址
24.        }
25.       
26. }

复制代码

3.4打印结果：

  

  改变传已往的指针，那么就要传指针的地点，不改变就可以不传，以是print函数就没有传
   3.5知识梳理：

     空链表可以打印，不用断言       空链表可以尾插，不用assert(*pphead),但是必要assert(pphead)       空链表可以头插，不用assert(*pphead),但是必要assert(pphead)把       空链表不能尾删，assert(pphead)和assert(*pphead)都必要，且pphead断言在*pphead之前      4.链表的头插：（void SListPushFront(SLTNode** pphead, SLTDataType x)）

1. void SListPushFront(SLTNode** pphead, SLTDataType x)
2. {
3.     SLTNode* newnode = BuySLTNode(x);
4.     newnode->Next = *pphead;  //原本*pphead是第一个节点的地址，现在把原来第一个节点的地址放在新插入的节点的尾巴中，让新的第一个节点存放原来第一个节点的地址
5.     *pphead = newnode;// 把头指针的地址改成新插入的指针的地址
6.     //这种写法可以针对空链表，因为空链表的*pphead的next是NULL，现在相当于把newnode->Next赋值为NULL，并把newnode改为头指针，完全可行
7. }

复制代码

5.链表的尾删：（void SListPushFront(SLTNode** pphead, SLTDataType x)）

1. void SListPushFront(SLTNode** pphead, SLTDataType x)
2. {
3.     SLTNode* newnode = BuySLTNode(x);
4.     newnode->Next = *pphead;  //原本*pphead是第一个节点的地址，现在把原来第一个节点的地址放在新插入的节点的尾巴中，让新的第一个节点存放原来第一个节点的地址
5.     *pphead = newnode;// 把头指针的地址改成新插入的指针的地址
6.     //这种写法可以针对空链表，因为空链表的*pphead的next是NULL，现在相当于把newnode->Next赋值为NULL，并把newnode改为头指针，完全可行
7. }// 单链表的尾删void SListPopBack(SLTNode** pphead){    assert(pphead);    assert(*pphead != NULL);    //1.只有一个结点    //2.有多个结点    if ((*pphead)->Next == NULL)    {        free(*pphead);    }    //找尾    SLTNode* prev = NULL;    SLTNode* tail = *pphead;    while (tail->Next != NULL)    {        prev = tail;//tail在每次往下走之前先把值留给prev        tail = tail->Next;    }    free(tail);    tail = NULL;    prev->Next = NULL; }

复制代码

    为什么必要 prev？                  单链表的单向性：单链表的每个节点只有 Next 指针，指向下一个节点，而没有指向前一个节点的指针。因此，当你找到尾节点（tail）时，无法直接知道它的前一个节点是谁。         删除尾节点的操纵：                  删除尾节点时，必要将尾节点的前一个节点（prev）的 Next 指针置为 NULL，以表现它是新的尾节点。假如不记载 prev，就无法修改前一个节点的 Next 指针，链表会处于一个不精确的状态。         释放尾节点的内存：                  在释放尾节点的内存之前，必须确保前一个节点的 Next 指针已经被精确修改，否则会导致链表断裂或内存走漏。          tail 和 prev 的关系：                  tail 是用来遍历链表的指针，终极会指向尾节点（即要删除的节点）。                  prev 是用来记载 tail 的前一个节点的指针。                  tail = NULL 的作用：                  tail = NULL 只是将局部变量 tail 置为 NULL，并不会影响链表的结构。                  链表的结构是由节点的 Next 指针决定的，而不是由局部变量 tail 决定的                  尚有一种写法：      

1. SLTNode* tail = *pphead;
2.     while (tail->Next->Next != NULL)
3.     {
4.            tail = tail->Next;
5.     }
6.     free(tail->Next);
7.     tail->Next = NULL;

复制代码

  6.链表的头删：（void SListPopFront(SLTNode** pphead)）

  

1. void SListPopFront(SLTNode** pphead)
2. {
3.     assert(*pphead != NULL);
4.     SLTNode* first = *pphead;
5.     *pphead = first->Next;
6.     free(first);
7.     first = NULL;
8. }

复制代码

  7.链表的查找：（SLTNode* SListFind(SLTNode* phead, SLTDataType x)）

  

1. SLTNode* SListFind(SLTNode* phead, SLTDataType x)
2. {
3.     SLTNode* cur = phead;
4.     while (cur != NULL)
5.     {
6.         if (cur->data == x)
7.         {
8.             return cur;
9.         }
10.         else
11.         {
12.             cur = cur->Next;
13.         }
14.     }
15.     return NULL;
16. }

复制代码

  8.在指定位置（pos）之前插入:（void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)）

   这个函数一般配合SListFind函数一起使用
   pos是第几个位置，假如pos=3，那么就是在2和3之间插入，但是：单链表不适合在前面插入，由于有了3的位置却找不到2的位置，必要从头开始遍历
  

1. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
2. {
3.     //plist有可能为空，但是pphead不能为空。plist的值有可能为空，但是pphead存放的是pphead的地址，不能为空（phead有可能为空->代码空链表）
4.     assert(pphead != NULL);
5.     assert(pos);
6.     if (pos == *pphead)//如果pos为头指针，那么类似于头插
7.     {
8.         SListPushFront(pphead, x);
9.     }
10.     else
11.     {
12.         //找到pos的前一个位置
13.         SLTNode* prev = *pphead;
14.         while (prev->Next != pos)
15.         {
16.             prev = prev->Next;
17.         }
18.         SLTNode* newnode = BuySLTNode(x);
19.         prev->Next = newnode;
20.         newnode->Next = pos;
21.     }
22. }

复制代码

  9.在指定位置（pos）位置删除:（void SLTErase(SLTNode** pphead, SLTNode* pos)）

  

1. void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos的位置必须知道pos的前一个的位置
2. {
3.     assert(pphead);
4.     assert(pos);
5.     assert(*pphead);
6.     if (pos == *pphead)
7.     {
8.         SListPopFront(pos);
9.     }
10.     else
11.     {
12.         //找到pos的前一个位置
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. }

复制代码

  10.在指定位置（pos）背面插入：（void SLTInsertAfter(SLTNode* pos, SLTDataType x)）

  

1. void SLTInsertAfter(SLTNode* pos, SLTDataType x)
2. {
3.     assert(pos);
4.     SLTNode* newnode = BuySLTNode(x);
5.     newnode->Next = pos->Next;
6.     pos->Next = newnode;
7. }
8. //在pos位置后面删除
9. void SLTEraseAfter(SLTNode* pos)
10. {
11.     assert(pos);
12.     assert(pos->Next);
13.     SLTNode* del = pos->Next;//先标记好要删除的节点，以免后面这块结点丢失
14.     pos->Next = pos->Next->Next;
15.     free(del);
16.     del = NULL;
17. }

复制代码

  11.链表的销毁：（void SLTDestroy(SLTNode* phead)）

   注意用完这个函数后得把实参置空，由于这个函数里面phead=NULL这句话是没意义的，由于形参改变不会改变实参。或者用二级指针。
  

1. void SLTDestroy(SLTNode* phead)
2. {
3.     SLTNode* cur = phead;
4.     while (cur)
5.     {
6.         SLTNode* tmp = cur->Next;
7.         free(cur);
8.         cur = tmp;
9.     }
10.    
11. }

复制代码

   //删除的经典错误：
        // 1.
        // free(cur);
        // cur=cur->Next;  野指针，cur的使用权被释放了，这行代码黑白法操纵
        // 2.
        // SLTNode *tmp=cur;
        // free(cur);
        // cur=tmp->Next;  和上面一样，tmp和cur指向的是同一块内存空间，假如释放就一起释放了
        //你退房了，把房卡给别人，别人也不能开旅店的房门，一样的道理
        //最好的方法不是保存cur而是保存cur的next
   三、单链表功能汇总

   SList.h：

  

1. #pragma once
2. #include <stdlib.h>
3. #include <stdio.h>
4. #include <assert.h>
5. #include <errno.h>
6. typedef int SLTDataType;
7. typedef struct SListNode
8. {
9.     SLTDataType data; // 数据域
10.     struct SListNode* Next; // 这里并不是结构体里面有个结构体，而是结构体里面有个指针，它的类型是结构体类型
11.     // SListNode* Next; 这里还不能这样写，这里涉及到编译器的查找规则：如果一个函数或者一个类型需要使用，那么编译器会向上查找而不会向下
12. } SLTNode;
13. // 打印链表
14. void SLTPrint(SLTNode* phead);
15. // 尾插
16. void SLTPushBack(SLTNode** pphead, SLTDataType x);
17. // 单链表的头插
18. void SListPushFront(SLTNode** pphead, SLTDataType x);
19. // 单链表的尾删
20. void SListPopBack(SLTNode** pphead);
21. // 单链表头删
22. void SListPopFront(SLTNode** pphead);
23. // 单链表查找
24. SLTNode* SListFind(SLTNode* phead, SLTDataType x);
25. //在pos之前插入
26. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
27. //在pos位置删除
28. void SLTErase(SLTNode** pphead, SLTNode* pos);
29. //在pos后面插入
30. void SLTInsertAfter(SLTNode*pos, SLTDataType x);
31. //在pos位置后面删除
32. void SLTEraseAfter(SLTNode* pos);
34. //链表的删除
35. void SLTDestroy(SLTNode* phead);

复制代码

  SList.c

  

1. #include "SList.h"//创建插入元素的封装节点 函数SLTNode* BuySLTNode(SLTDataType x){    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));    if (newnode == NULL)    {        perror("malloc fail");    }    newnode->data = x;    newnode->Next = NULL;    return newnode;}//打印void SLTPrint(SLTNode* phead){    //不必要assert断言，由于空的链表可以打印，只是没有数据而已    SLTNode* cur = phead;    while (cur != NULL)    {        printf("%d->", cur->data);        cur = cur->Next;//Next是下一个节点的地点    }    printf("NULL\n");}// 尾插void SLTPushBack(SLTNode** pphead, SLTDataType x){    SLTNode* newnode = BuySLTNode(x);    if (*pphead == NULL)    {        *pphead = newnode;    }    else    {        //找尾        SLTNode* tail = *pphead;        while (tail->Next != NULL)        {            tail = tail->Next;        }        tail->Next = newnode;//tail= newnode;这样写是错的，要想把两个链表链接起来，必须要让一个链表的最后一个数的下一个地点存放着下一个数的地点，        //tail现在存的是最后一个元素的地点而不是最后一个元素的下一个元素的地点    }}// 单链表的头插void SListPushFront(SLTNode** pphead, SLTDataType x)
2. {
3.     SLTNode* newnode = BuySLTNode(x);
4.     newnode->Next = *pphead;  //原本*pphead是第一个节点的地址，现在把原来第一个节点的地址放在新插入的节点的尾巴中，让新的第一个节点存放原来第一个节点的地址
5.     *pphead = newnode;// 把头指针的地址改成新插入的指针的地址
6.     //这种写法可以针对空链表，因为空链表的*pphead的next是NULL，现在相当于把newnode->Next赋值为NULL，并把newnode改为头指针，完全可行
7. }// 单链表的尾删void SListPopBack(SLTNode** pphead){    assert(pphead);    assert(*pphead != NULL);    //1.只有一个结点    //2.有多个结点    if ((*pphead)->Next == NULL)    {        free(*pphead);    }    //找尾    SLTNode* prev = NULL;    SLTNode* tail = *pphead;    while (tail->Next != NULL)    {        prev = tail;//tail在每次往下走之前先把值留给prev        tail = tail->Next;    }    free(tail);    tail = NULL;    prev->Next = NULL;   }// 单链表头删void SListPopFront(SLTNode** pphead)
8. {
9.     assert(*pphead != NULL);
10.     SLTNode* first = *pphead;
11.     *pphead = first->Next;
12.     free(first);
13.     first = NULL;
14. }// 单链表查找SLTNode* SListFind(SLTNode* phead, SLTDataType x)
15. {
16.     SLTNode* cur = phead;
17.     while (cur != NULL)
18.     {
19.         if (cur->data == x)
20.         {
21.             return cur;
22.         }
23.         else
24.         {
25.             cur = cur->Next;
26.         }
27.     }
28.     return NULL;
29. }//在pos之前插入,配合SListFind函数一起使用void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
30. {
31.     //plist有可能为空，但是pphead不能为空。plist的值有可能为空，但是pphead存放的是pphead的地址，不能为空（phead有可能为空->代码空链表）
32.     assert(pphead != NULL);
33.     assert(pos);
34.     if (pos == *pphead)//如果pos为头指针，那么类似于头插
35.     {
36.         SListPushFront(pphead, x);
37.     }
38.     else
39.     {
40.         //找到pos的前一个位置
41.         SLTNode* prev = *pphead;
42.         while (prev->Next != pos)
43.         {
44.             prev = prev->Next;
45.         }
46.         SLTNode* newnode = BuySLTNode(x);
47.         prev->Next = newnode;
48.         newnode->Next = pos;
49.     }
50. }//在pos位置删除void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos的位置必须知道pos的前一个的位置
51. {
52.     assert(pphead);
53.     assert(pos);
54.     assert(*pphead);
55.     if (pos == *pphead)
56.     {
57.         SListPopFront(pos);
58.     }
59.     else
60.     {
61.         //找到pos的前一个位置
62.         SLTNode* prev = *pphead;
63.         while (prev->Next != pos)
64.         {
65.             prev = prev->Next;
66.         }
67.         prev->Next = pos->Next;
68.         free(pos);
69.         //pos = NULL;这句话其实没用因为形参的改变不影响实参
70.     }
71. }//在pos背面插入void SLTInsertAfter(SLTNode* pos, SLTDataType x)
72. {
73.     assert(pos);
74.     SLTNode* newnode = BuySLTNode(x);
75.     newnode->Next = pos->Next;
76.     pos->Next = newnode;
77. }
78. //在pos位置后面删除
79. void SLTEraseAfter(SLTNode* pos)
80. {
81.     assert(pos);
82.     assert(pos->Next);
83.     SLTNode* del = pos->Next;//先标记好要删除的节点，以免后面这块结点丢失
84.     pos->Next = pos->Next->Next;
85.     free(del);
86.     del = NULL;
87. }//链表的删除void SLTDestroy(SLTNode* phead){    SLTNode* cur = phead;    while (cur)    {                SLTNode* tmp = cur->Next;        free(cur);        cur = tmp;    }    }

复制代码

  test.c

  

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include "SList.h"
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.     SLTPrint(plist);
11.     SListPopFront(&plist);
12.     SLTPrint(plist);
13.     SLTNode* ret=SListFind(plist, 2);
14.     SLTPrint(plist);
15.     SLTInsert(&plist, ret, 20);
16.     SLTPrint(plist);
17. }
18. int main()
19. {
20.     TestSList1();
21.     return 0;
22. }

复制代码

  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。