数据结构入门指南单链表附源码

目录

前言

尾删

头删

查找

位置前插入

 位置后插入

 位置删除

 位置后删除

 链表销毁

总结

---

前言

        前边关于链表的基础如果已经理解透彻，那么接下来就是对链表各功能的实现，同时也希望大家能把这部分内容熟练于心，这部分内容对有关链表部分的刷题很有帮助。废话不多讲我们步入正题。

---

        前边已经实现了头插、尾插的操作，今天主要的内容是：头删、尾删、位置删除、位置后删除、查找、位置前插入、位置后插入。

尾删

        要想进行尾删，就要先找到链表的尾。

        我们知道单链表的缺点之一就是只可以单向遍历，所以要想删除最后一个节点，就要先找到倒数第二个节点，然后释放掉最后一个节点，将倒数第二个节点的next（指针域）置为NULL。

 

 具体代码实现：

1.  
   void SLPopBlack(SLNode** pphead)
2.  
   {
3.  
    
4.  
   assert(*pphead);
5.  
   if ((*pphead)->next == NULL)
6.  
   {
7.  
   free(*pphead);
8.  
   *pphead = NULL;
9.  
   }
10.  
    SLNode* tail = *pphead;
11.  
     
12.  
    while (tail->next->next)
13.  
    {
14.  
    tail = tail->next;
15.  
    }
16.  
    free(tail->next);
17.  
    tail->next = NULL;
18.  
    }

        这里为什么要传二级指针？有人可能会有这样的疑惑， 传二级指针就是为了防止链表被删空的情况，在链表的许多情节中都要考虑像链表删空等这种极端情况，要做到面面俱到。

        当然我们也可以选择不使用二级指针，而是直接返回头指针的地址。但这样函数的类型就变成了结构体指针类型，而要调用这个函数还需要相同类型的结构体指针变量接收，这种情况在刷题中经常遇到，但在写链表时不推荐，这样写调用函数会比较麻烦。

头删

头删大家可以先思考一下，需不需要使用二级指针。

有这样一个链表：

         想要删除第一个节点，只需要把头指针指向的位置改为指向第二个节点。把头指针修改，这是修改结构体指针，到这里想必大家已经清楚，需要使用二级指针。

        接下来我们理一下删除的逻辑，直接将头指针指向第二个节点，这样就会造成第一个节点丢失没办法释放掉空间。如果先将第一个节点释放就会使第二个节点丢失，头指针无法连接剩余节点。

        这要怎么解决呢？这里就需要创建一个新的变量来存储一下第二个节点的地址，然后再将第一个节点释放。 

具体代码实现：

1.  
   void SLPopFront(SLNode** pphead)
2.  
   {
3.  
   assert(*pphead);
4.  
    
5.  
   SLNode* newhead = (*pphead)->next;
6.  
   free(*pphead);
7.  
   *pphead = newhead;
8.  
   }

查找

        查找很简单，顺序表的查找返回的是下标，而链表返回的是节点的地址，后续的操作也是比较简单，我就不再画逻辑图。

1.  
   SLNode* SLFind(SLNode* phead, Datatype x)
2.  
   {
3.  
   SLNode* cur = phead;
4.  
   while (cur)
5.  
   {
6.  
   if (cur->data == x)
7.  
   {
8.  
   return cur;
9.  
   }
10.  
    cur = cur->next;
11.  
    }
12.  
    return NULL;
13.  
    }

位置前插入

        位置前插入，如果是在第一个节点位置前插入，就是头插，其次是要想在位置前插入就必须要知道前有个节点，单链表是无法逆向遍历的，所以要想知道前一个节点就必须要传头指针。然后将前一个节点的next置为新节点的地址，新节点的next置为pos位置节点的地址。

1.  
   void SLFrontInsert(SLNode** pphead, SLNode* pos, Datatype x)
2.  
   {
3.  
    
4.  
   assert(pos);
5.  
   if (pos == *pphead)
6.  
   {
7.  
   SLPushFront(pphead, x);
8.  
   }
9.  
   else
10.  
    {
11.  
    SLNode* prev = *pphead;
12.  
    SLNode* newnode = NewNode(x);
13.  
    while (prev->next != pos)
14.  
    {
15.  
    prev = prev->next;
16.  
    }
17.  
    newnode->next = pos;
18.  
    prev->next = newnode;
19.  
    }
20.  
    }

 位置后插入

        位置后插入，可以不需要头指针。操作也非常简单，把pos位置的下一个节点赋给新节点的next，把新节点的地址赋给pos位置节点的next。这里有人可能会有疑惑，不考虑极端情况吗？位置后插入是无法进行头插的，如果链表为空，传进来pos就为空，就会直接保错，至于尾插，这段代码也是可以解决的。

1.  
   void SLAfterInsert(SLNode* pos, Datatype x)
2.  
   {
3.  
   assert(pos);
4.  
   SLNode* newnode = NewNode(x);
5.  
   newnode->next = pos->next;
6.  
   pos->next = newnode;
7.  
    
8.  
   }

 位置删除

        位置删除，需要把pos位置前一个节点的next置为pos位置下一个节点的地址，同时还需要将删除的节点释放空间。考虑极端情况，如果删除位置是第一个节点，这种方法就失效了，因为没有第一个节点的前一个节点，这时也就是头删，我们可以调用前边已经实现的函数接口。

1.  
   void SLErase(SLNode** pphead, SLNode* pos) {
2.  
   assert(pphead);
3.  
   assert(pos);
4.  
   if (pos == *pphead)
5.  
   {
6.  
   SLPopFront(pphead);
7.  
   }
8.  
   else
9.  
   {
10.  
    SLNode* prev = *pphead;
11.  
    while (prev->next != pos)
12.  
    {
13.  
    prev = prev->next;
14.  
    }
15.  
    prev->next = pos->next;
16.  
    free(pos);
17.  
    pos = NULL;
18.  
    }
19.  
    }

 位置后删除

        位置后删除，如果位置为最后一个节点，就不需要删除，且位置后删除无法进行头删，然后是正常情况，把pos位置节点的next置为pos位置后第二个节点的地址，就完成了。那是否可以这样写呢？

pos->next = pos->next->next

 答案是不可以，这样会造成pos后一个节点丢失，无法释放。所以这里我们需要分成两步来写：

1.  
   void SLEraseAfter(SLNode* pos)
2.  
   {
3.  
   assert(pos);
4.  
   if (pos->next == NULL)
5.  
   {
6.  
   return;
7.  
   }
8.  
   else
9.  
   {
10.  
    SLNode* posnext = pos->next;//不可以写成一步，否则pos后一个节点就会丢失，无法释放
11.  
    pos->next = posnext->next;
12.  
    free(posnext);
13.  
    posnext = NULL;
14.  
    }
15.  
     
16.  
    }

 链表销毁

        执行完所有操作后，就需要将链表销毁了

1.  
   void SLDestory(SLNode** pphead)
2.  
   {
3.  
   assert(pphead);
4.  
   SLNode* cur = *pphead;
5.  
    
6.  
   while (cur)
7.  
   {
8.  
   SLNode* next =cur->next;
9.  
   free(cur);
10.  
    cur = next;
11.  
    }
12.  
    *pphead = NULL;
13.  
    }

 完整代码：

SList.c

1.  
   #include"SList.h"
2.  
   void SLprint(SLNode* phead)
3.  
   {
4.  
   SLNode* cur = phead;
5.  
   while (cur)
6.  
   {
7.  
   printf("%d->", cur->data);
8.  
   cur = cur->next;
9.  
   }
10.  
    printf("NULL\n");
11.  
    }
12.  
    SLNode* NewNode(Datatype x)
13.  
    {
14.  
    SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
15.  
    if (newnode == NULL)
16.  
    {
17.  
    perror("malloc");
18.  
    exit(-1);
19.  
    }
20.  
    newnode->data = x;
21.  
    newnode->next = NULL;
22.  
    return newnode;
23.  
    }
24.  
    void SLPushBlack(SLNode** pphead, Datatype x)
25.  
    {
26.  
    assert(pphead);
27.  
    SLNode* newnode = NewNode(x);
28.  
    SLNode* tail = *pphead;
29.  
    if (*pphead == NULL)
30.  
    {
31.  
    *pphead = newnode;
32.  
    }
33.  
    else
34.  
    {
35.  
    while (tail->next)
36.  
    {
37.  
    tail = tail->next;
38.  
    }
39.  
    tail->next = newnode;
40.  
    }
41.  
    }
42.  
    void SLPushFront(SLNode** pphead, Datatype x)
43.  
    {
44.  
    assert(pphead);
45.  
    SLNode* newnode = NewNode(x);
46.  
    newnode->next = *pphead;
47.  
    *pphead = newnode;
48.  
    }
49.  
    void SLPopBlack(SLNode** pphead)
50.  
    {
51.  
    assert(pphead);
52.  
    assert(*pphead);
53.  
    if ((*pphead)->next == NULL)
54.  
    {
55.  
    free(*pphead);
56.  
    *pphead = NULL;
57.  
    }
58.  
    SLNode* tail = *pphead;
59.  
     
60.  
    while (tail->next->next)
61.  
    {
62.  
    tail = tail->next;
63.  
    }
64.  
    free(tail->next);
65.  
    tail->next = NULL;
66.  
    }
67.  
    void SLPopFront(SLNode** pphead)
68.  
    {
69.  
    assert(pphead);
70.  
    assert(*pphead);
71.  
     
72.  
     
73.  
    SLNode* newhead = (*pphead)->next;
74.  
    free(*pphead);
75.  
    *pphead = newhead;
76.  
    }
77.  
    SLNode* SLFind(SLNode* phead, Datatype x)
78.  
    {
79.  
    SLNode* cur = phead;
80.  
    while (cur)
81.  
    {
82.  
    if (cur->data == x)
83.  
    {
84.  
    return cur;
85.  
    }
86.  
    cur = cur->next;
87.  
    }
88.  
    return NULL;
89.  
    }
90.  
    void SLFrontInsert(SLNode** pphead, SLNode* pos, Datatype x)
91.  
    {
92.  
    assert(pphead);
93.  
    assert(pos);
94.  
    if (pos == *pphead)
95.  
    {
96.  
    SLPushFront(pphead, x);
97.  
    }
98.  
    else
99.  
    {
100.  
     SLNode* prev = *pphead;
101.  
     SLNode* newnode = NewNode(x);
102.  
     while (prev->next != pos)
103.  
     {
104.  
     prev = prev->next;
105.  
     }
106.  
     newnode->next = pos;
107.  
     prev->next = newnode;
108.  
     }
109.  
     }
110.  
     void SLAfterInsert(SLNode* pos, Datatype x)
111.  
     {
112.  
     assert(pos);
113.  
     SLNode* newnode = NewNode(x);
114.  
     newnode->next = pos->next;
115.  
     pos->next = newnode;
116.  
      
117.  
     }
118.  
     void SLErase(SLNode** pphead, SLNode* pos) {
119.  
     assert(pphead);
120.  
     assert(pos);
121.  
     if (pos == *pphead)
122.  
     {
123.  
     SLPopFront(pphead);
124.  
     }
125.  
     else
126.  
     {
127.  
     SLNode* prev = *pphead;
128.  
     while (prev->next != pos)
129.  
     {
130.  
     prev = prev->next;
131.  
     }
132.  
     prev->next = pos->next;
133.  
     free(pos);
134.  
     pos = NULL;
135.  
     }
136.  
     }
137.  
     void SLEraseAfter(SLNode* pos)
138.  
     {
139.  
     assert(pos);
140.  
     if (pos->next == NULL)
141.  
     {
142.  
     return;
143.  
     }
144.  
     else
145.  
     {
146.  
     SLNode* posnext = pos->next;
147.  
     pos->next = posnext->next;
148.  
     free(posnext);
149.  
     posnext = NULL;
150.  
     }
151.  
      
152.  
     }
153.  
     void SLDestory(SLNode** pphead)
154.  
     {
155.  
     assert(pphead);
156.  
     SLNode* cur = *pphead;
157.  
      
158.  
     while (cur)
159.  
     {
160.  
     SLNode* next =cur->next;
161.  
     free(cur);
162.  
     cur = next;
163.  
     }
164.  
     *pphead = NULL;
165.  
     }

 SList.h

1.  
   #include<stdio.h>
2.  
   #include<assert.h>
3.  
   #include<stdlib.h>
4.  
    
5.  
   typedef int Datatype;
6.  
   typedef struct SLNode
7.  
   {
8.  
   Datatype data;
9.  
   struct SLNode* next;
10.  
    }SLNode;
11.  
    //打印链表
12.  
    void SLprint(SLNode* phead);
13.  
    //创建新节点
14.  
    SLNode* NewNode(Datatype x);
15.  
    //尾插
16.  
    void SLPushBlack(SLNode** phead, Datatype x);
17.  
    //头插
18.  
    void SLPushFront(SLNode** pphead, Datatype x);
19.  
     
20.  
    //尾删
21.  
    void SLPopBlack(SLNode** pphead);
22.  
    //头删
23.  
    void SLPopFront(SLNode** pphead);
24.  
    //查找
25.  
    SLNode* SLFind(SLNode* phead, Datatype x);
26.  
    //pos位置前插入
27.  
    void SLFrontInsert(SLNode** pphead, SLNode* pos, Datatype x);
28.  
    //pos位置后插入
29.  
    void SLAfterInsert(SLNode* pos, Datatype x);
30.  
    //pos位置后删除
31.  
    void SLEraseAfter(SLNode* pos);
32.  
    //pos位置删除
33.  
    void SLErase(SLNode** pphead, SLNode* pos);
34.  
     
35.  
    void SLDestory(SLNode** pphead);

 test.c

这里基本都是测试接口，没有什么太大的参考价值，代码如下，便于大家调试。

1.  
   #include"SLNode.h"
2.  
   void test1()
3.  
   {
4.  
   SLNode* plist = NULL;
5.  
   int n = 0;
6.  
   printf("请输入链表的长度\n");
7.  
   scanf("%d", &n);
8.  
   printf("请输入数据\n");
9.  
   for (int i = 0; i < n; i )
10.  
    {
11.  
    int val = 0;
12.  
    scanf("%d", &val);
13.  
    SLNode *newnode= NewNode(val);
14.  
    newnode->next = plist;
15.  
    plist = newnode;
16.  
    }
17.  
    SLNode* pos= SLFind(plist, 2);
18.  
    if (pos)
19.  
    {
20.  
    pos->data *= 10;
21.  
    }
22.  
    SLFrontInsert(&plist, pos, 10);
23.  
    SLprint(plist);
24.  
     
25.  
    SLPushBlack(&plist,100);
26.  
    SLprint(plist);
27.  
     
28.  
    SLPushFront(&plist, 200);
29.  
    SLprint(plist);
30.  
     
31.  
    SLPopBlack(&plist);
32.  
    SLprint(plist);
33.  
     
34.  
    SLPopFront(&plist);
35.  
    SLprint(plist);
36.  
    }
37.  
    void test2()
38.  
    {
39.  
    SLNode* plist = NULL;
40.  
    SLPushBlack(&plist, 1);
41.  
    SLPushBlack(&plist, 2);
42.  
    SLPushBlack(&plist, 3);
43.  
    SLPushBlack(&plist, 4);
44.  
    SLPushBlack(&plist, 5);
45.  
    SLprint(plist);
46.  
    SLNode* pos = SLFind(plist, 5);
47.  
    SLAfterInsert(pos, 20);
48.  
    SLprint(plist);
49.  
    SLFrontInsert(&plist, pos, 10);
50.  
    SLprint(plist);
51.  
    }
52.  
    void test3()
53.  
    {
54.  
    SLNode* plist = NULL;
55.  
    SLPushBlack(&plist, 1);
56.  
    SLPushBlack(&plist, 2);
57.  
    SLPushBlack(&plist, 3);
58.  
    SLPushBlack(&plist, 4);
59.  
    SLPushBlack(&plist, 5);
60.  
    SLprint(plist);
61.  
    SLNode* pos = SLFind(plist, 1);
62.  
    //SLErase(&plist, pos);
63.  
    SLEraseAfter(pos);
64.  
    SLprint(plist);
65.  
    SLDestory(&plist);
66.  
     
67.  
    }
68.  
     
69.  
    int main()
70.  
    {
71.  
    test2();
72.  
     
73.  
     
74.  
    return 0;
75.  
    }

---

总结

        好的，内容到这里就要结束了，这部分内容或许看来很繁琐，但在刷链表相关的题时就会惊奇的发现，题解都是这些操作的变形。熟练这部分内容，可以让你在刷链表相关的题时会感觉非常的爽，刷题也会更加顺利。最后，感谢阅读！

这篇好文章是转载于：学新通技术网