数据结构——单链表

fe594ea5bf754ddbb223a54d8fb1e7bc.gif

目录

一.前言

二.链表表示和实现（单链表）

1.1   顺序表的优缺点

1.2   链表的概念及结构

 1.3   打印函数

1.4   空间函数

1.5   尾插函数（最最最麻烦的）

1.5.1 尾插最关键部分！

1.6   头插函数

1.7   尾删函数 

1.8   头删函数

1.9   查找函数

1.10 在pos之前插入x函数

1.12 在pos之后插入x函数

1.13 删除pos位置函数

1.14 删除pos的后一个位置函数

1.15 小测试

三.全部代码 

四.结语

8fb442646f144d8daecdd2b61ec78ecd.png一.前言

超级详细的单链表分析，把这一口吃下去妈妈再也不担心孩子因为知识匮乏饿肚子了~ 码字不易，希望大家多多支持我呀！（三连＋关注，你是我滴神！）

二.链表表示和实现（单链表）

1.1   顺序表的优缺点

回顾前文所说的顺序表：

缺点：

  • 头部和中部插入删除效率都不行  O(N)
  • 空间不够了，扩容有一定的消耗（尤其是异地扩容）
  • 扩容逻辑，可能还存在空间 （比如100满了，你要插入110个数据，扩容到200就会浪费90个空间）

优点：

  • 尾插尾删足够快
  • 下标的随机访问和修改

1.2   链表的概念及结构

eb1c337966f243a18016cb3ca6d60898.png

顺序表只需要知道首元素地址即可有一块连续的物理空间，并且尾部用size定义，而链表在物理空间并非连续，而是按需申请释放单个空间，空间之间用指针来相互联系。链表空间尾部是用NULL定义。

c40ee35e82f7481db4e666f4909c6210.png

备注：由malloc出来的节点地址是随机的。

#define _CRT_SECURE_NO_WARNINGS 1
//Test.c
#include <stdio.h>typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;int main()
{return 0;
}

从单链表的图示我们可以知道它是有多个节点链接而成的，一个节点里意味着有一个结构体，那么我们所指向节点的指针就应该是结构体指针变量。（struct SListNode* next)

 1.3   打印函数

74804706e6644dbbb65b63042653e4e4.png

因为phead是指向第一个节点的，所以不要轻易去改变，我们可以再创造一个指针来遍历链表。

void PrintSList(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

肯定许多友友无法理解为什么 cur = cur->next;这个next明明在代码中没有明确的指向，为什么还可以去使用呢？其实在cur指向第一个节点时cur->next是去取该结构体里面next的值，而next所存储的则是下一个结构体的地址。这样使得cur去指向第二个节点。至于为什么next能够存储下一个节点的地址就是关于编译器里的汇编该做（计算机会自动识别该指令）的事情了，我们就不做过多介绍了。

接下来带大家感受一下简易链表的跑动情况；

#define _CRT_SECURE_NO_WARNINGS 1
//Test.c
#include <stdio.h>
#include <stdlib.h>typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void PrintSList(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}int main()
{SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));//注意！这里malloc出来的节点是结构体，那么sizeof也得代入结构体的大小，//又因为是用结构体指针接收，所以强制类型转换也要使用(SLTNode*)。n1->data = 10;SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));n2->data = 20;SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));n3->data = 30;n1->next = n2;n2->next = n3;n3->next = NULL;PrintSList(n1);return 0;
}

 b9ce52b2fffd4259b2389b000fa8a3ec.png

在见识到简易链表后那接下来我们就要进入真正完整结构的链表了，老规矩，先创造3个文件。

68c35c4132824d3d9e6057c0d1c5178f.png

1.4   空间函数

SLTNode* BuySlistNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;}

当我们创造空间函数后来进行测试：（不过会遇到一个难点，我们该如何把这些节点联系在一起呢？）

0d864904eeb14d33bc041f8db690afda.png 这里我们提前先用头插来进行链接并且分析：

6d596675ba7342f793548d96d1e120f5.png当我们的链表不为空时，要想头插需要用newnode这个新节点将plist与plist指向的第一个节点链接起来。先将第一个节点的地址（plist所指向）交给newnode这个新节点的next处，使新节点后面链接的是第一个节点，再把新节点的地址交给plist，使plist所指向的永远都是新的第一节点。

注意！切不可交换顺序，如果先把新节点newnode的地址交给plist，那原先第一个节点就不能通过plist找到了，成为了野指针。

当链表为空时，由于plist指向的是空指针，那么当插入新节点时，plist指向就变成了新节点（第一节点），而新节点所指向的就是空指针（newnode->next=NULL)。

最后得出结论：关于头插的两句代码newnode->next = plist与plist = newnode完美契合两种情况，不需要用条件来区分开来。

 最终测试：

#define _CRT_SECURE_NO_WARNINGS 1
//Test.c
#include "Slist.h"
#include <stdio.h>
#include <stdlib.h>void TestSList1()
{int n = 0;printf("请输入链表的长度：");scanf("%d", &n);printf("\n请依次输入每个节点的值：\n");SLTNode* plist = NULL;for (int i = 0; i < n; i++){int val = 0;scanf("%d", &val);SLTNode* newnode = BuySlistNode(val);newnode->next = plist;plist = newnode;PrintSList(plist);}}int main()
{TestSList1();return 0;
}

048f53ac7d7745578a8f92ebc81ab15a.png

1.5   尾插函数（最最最麻烦的）

尾插：肯定是从最后开始插入，malloc一个新空间，那么它所在节点先存储所插入的数，再然后就是空指针的地址。

不过既然从最后插入，那得在原有数据上找到尾巴，从尾巴后面开始插入成为末尾。

很多友友都会将代码误写成下面这样：（其实这样是大错特错的）

482957a8c3514205947372dee553a042.png

068119568fad4f96b6d4d87720a09962.png当我们画好物理图来分析就知道了，假如我们创造了新节点，而tail因为指向空指针而停止循环，但在我们执行最后一句代码后：tail = newnode，tail确实指向了新的节点，但是我们可以从图中看到新节点并没有和上一个节点链接起来！上一个节点所指向的仍然是空指针。

1d50ae2e899f4b0c8a4f7cf5236af055.png

该函数里有三个局部变量：phead, newnode, tail.出了作用域全部销毁。数据4并没有尾插进去，新开的这个节点反而丢失了。之所以4所在节点不会被销毁是因为该节点是malloc在堆上开辟的，除非你去free掉，否则是不会销毁的。这就是我们为什么费劲去malloc一个节点，如果单单在函数内部搞节点出了作用域就会被销毁。

另外不用担心phead的销毁而找不到链表，phead是形参，我们外面还有pilst（实参）也有指向。

最后我们再来测试是否插入：（尾插1000）

//尾插函数
void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = BuySlistNode(x);SLTNode* tail = phead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;
}
void TestSList1()
{int n = 0;printf("请输入链表的长度：");scanf("%d", &n);printf("\n请依次输入每个节点的值：\n");SLTNode* plist = NULL;for (int i = 0; i < n; i++){int val = 0;scanf("%d", &val);SLTNode* newnode = BuySlistNode(val);newnode->next = plist;plist = newnode;PrintSList(plist);}SLTPushBack(plist, 1000);PrintSList(plist);}

dd3ef00a801640b893a19de6d5dcdb04.png

1.5.1 尾插最关键部分！

前面是通过各种方式先折腾出一个链表，然后再进行尾插。

现在我们来测试一下没有链表（空链表），没有节点的时候尾插会发生什么。

//修改后的尾插函数
void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = BuySlistNode(x);if (phead == NULL){phead = newnode;}else{SLTNode* tail = phead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

34dea38481b94df983cc20d9617fb3f2.png

51186dfa351b467e9cd41eba296809bb.png 结果插入失败，这又是为什么呢？

我们来一起分析一波：

f6c627c881c1401cae71a1374564ba2c.png

当if条件执行完后离开作用域phead和newnode变量跟之前一样销毁。

ecde27c8fe8a477085eff53c5019c38f.png

这时候跟前面测试已经不同！测试1中是已经有了链表，在外面作为实参的plist已经是指向了第一个节点，在只进行尾插的情况下plist会一直指向第一节点，所以反而不用在意出了局部作用域就销毁的phead。在测试1中phead的作用更多是让tail能顺利指向首节点，而不是去尝试改变plist的值。

而现在的测试2中链表是空的，这意味着外面的plist的指向一直是空指针，需要phead来传递新节点的地址让外面的plist能够顺利指向它。可是phead只要离开作用域就会被销毁，无法起到传递地址的作用，这该怎么办呢？

其实，这里的形参phead和实参plist本质上还是传值调用，phead只是plist的一份临时拷贝，改变phead的值是起不到改变plist的目的的，可它们不都是指针吗？怎么会改变不了呢？接下来，我为大家来演示一个小案例就明白了~

小案例：

void Swap1(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void Swap2(int** pp1, int** pp2)
{int* tmp = **pp1;**pp1 = **pp2;**pp2 = tmp;
}int main()
{TestSList1();int a = 0;int b = 1;Swap1(&a, &b);int* x1 = &a;int* x2 = &b;Swap1(x1, x2);return 0;
}

在上述代码中，如果需要改变int的值，那就得传int*去接收。万一要改变的值是int*呢？那就得用int**去接收。我们在空链表的时候就相当于是传递x1,x2两个int*类型的值，但却用int*去接收，那x1,x2怎么可能会改变呢~

所以要想让外面的plist能够改变，首先先传递plist的地址，再用二级指针去接收~

void TestSList2()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);
}int main()
{//TestSList1();TestSList2();//int a = 0;//int b = 1;//Swap1(&a, &b);//int* x1 = &a;//int* x2 = &b;//Swap1(x1, x2);return 0;
}
//修改后的尾插函数
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySlistNode(x);if (*pphead == NULL){//改变结构体的指针，用二级指针改变*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}//改变结构体（next)，用结构体指针（tail)tail->next = newnode;}
}

c1ca8e41e2344ab0afe480619ee3c19f.png

现在情况发生改变，我们的pphead是指向plist,而*pphead变成了去解引用地址，就是去看plist里面的所存储的地址，解引用发现plist里面存储的地址为空，那就把newnode的地址传递进去，达到传址调用的目的。c851911bb4ed49c4bc2e4001c67ebf36.png

那为什么tail不用二级指针呢？，首先tail（结构体指针）指向的是一个结构体，tail->next是结构体里面的成员，而我们要想对结构体进行改变，用结构体指针就可以了。

最费劲的地方结束啦，相信后面的内容大家肯定可以轻松掌握~

1.6   头插函数

在经历复杂的尾插函数洗礼后，那头插函数还需要二级指针吗？

肯定需要啊，尾插只是在空链表时有必要用二级指针，那头插可就次次都需要二级指针了。

尾插需要判断链表是否为空，因为一方是改变结构体，另一方是改变结构体指针。而头插就不用去判断链表是否为空了，反正都是去改变结构体指针。

 de98f8d113814b8aa0cd3699e53b172e.png

//头插函数
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySlistNode(x);newnode->next = *pphead;*pphead = newnode;
}

 测试一下：

void TestSList2()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);SLTPushFront(&plist, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);PrintSList(plist);
}

 a10d6e3c35c64fc5884941c038d33fbc.png

1.7   尾删函数 

如题：尾删需要二级指针吗？

d08f29507dc74fcebb6be28aa839c566.png

前面确实只需要注意改结构体就行了，不需要用到二级指针~，但单我们删到只剩下最后一个节点时，没有前一个节点置空，所以是需要改变plist让它指向NULL滴~所以还是需要用到二级指针哦。

哈哈有没有发现只要把二级指针这一口吃下去了，后面都好说了~神挡杀神，佛挡杀佛~

如果free掉最后的空间节点，那么它的前一个节点由于所存地址的空间已经丢失，那么所存储该地址的指针就会变成野指针。所以我们需要把在尾部前面的节点所存储的地址变成空指针，确保它是尾部删除后成为新的尾部。

f9beca57ddd441db9d955e3ee8401e9c.png

//尾删函数
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//这里断言的目的是因为pphead指向的是plist的地址，而plist永远有所指向//要么指向NULL，要么指向链表，所以pphead是不能为空的。//空assert(*pphead);//一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//一个节点以上else{SLTNode* tailpre = NULL;SLTNode* tail = *pphead;while (tail->next != NULL){tailpre = tail;tail = tail->next;}free(tail);tailpre->next = NULL;}
}

也有一种难看懂的写法：自行选择~

//尾删函数
void SLTPopBack(SLTNode** pphead)
{//空assert(*pphead);//一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//一个节点以上else{SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}}

老规矩测试一下：

void TestSList3()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);SLTPopBack(&plist);PrintSList(plist);SLTPopBack(&plist);PrintSList(plist);}

251ab3f8c4bf46c8b09e975f520e83c5.png

1.8   头删函数

基本逻辑就是保存好下一节点newhead,然后再free掉首个节点，最后让plist指向newhead.

b5097b5582eb4c7cbcd91a40fcf5a098.png

//头删函数
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//空assert(*pphead);//非空SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;}

测试一下：

void TestSList4()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);SLTPopFront(&plist);PrintSList(plist);SLTPopFront(&plist);PrintSList(plist);SLTPopFront(&plist);PrintSList(plist);}

4576c4b139754bf2ad0cf54de791a026.png

1.9   查找函数

20c2ab31baa5491a9aa0df559c3f5a90.png

//查找函数
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

6f52d3d6123441d5a472cc7dc2864594.png

查找函数也可以起到修改数值的作用

1.10 在pos之前插入x函数

首先暴力断言，避免链表为空的情况。其次，当我们想要在链表的首个节点之前插入时，可以用到头插函数的复用。那么这时候需要往头插函数里面传递什么呢？由图可知我们最终头插要修改的是plist的指向，所以需要把plist的地址给传过去，而pphead恰好指向plist的地址，所以这里可以传pphead。

5a8afcab2c1d48638acf2891f1af0759.png

a6ca7ba3398f48dab467b79705dfa347.png

至于在其他位置插入我们只能找到pos之前的指针了~ 

我们这里只需要注意让删除节点的前后节点相连就行了。其实这里和指定插入是一样的操作都是通过prev和pos来进行连接。后面就随便改就行了，这里反而不用在意顺序。

03a53afe9b5d4de99c3fed130863dba2.png

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySlistNode(x);prev->next = newnode;newnode->next = pos;}}

测试一下：

void TestSList5()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);int x = 0;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTInsert(&plist, pos, 40);}PrintSList(plist);}

0547c49f978647ddb37b828512515101.png

1.12 在pos之后插入x函数

由于该函数不可能实现头插（不可能改变plist），所以就不用传递头指针给该函数接收了。

b400c29ab3304972af2570670f4f3c6b.png

该函数只需要注意一点，不要先在pos—>next存入newnode的地址，这样会丢失原本d3的地址，导致newnode—>next指向自己造成死循环。

//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySlistNode(x);newnode->next = pos->next;pos->next = newnode;}

测试一下：

void TestSList6()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);int x = 0;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTInsertAfter(pos, 3);}PrintSList(plist);}

7811dd1c46314dd5ae7e09bc074c6a8f.png

1.13 删除pos位置函数

该函数有两点需要注意：

  • 需要记录pos之前的指针
  • 头删需要单独处理，直接复用头删函数（这时候就需要接收plist来改变它的指向了）

82fa6a04455e40b9876200be89deba82.png

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;{while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}}
}

测试一下:

void TestSList7()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);int x = 0;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTErase(&plist,pos);pos = NULL;//用完pos记得置空，不然它还是会一直指向原位置}PrintSList(plist);}

ab4a518dadcd4ea8b1da5930bb97efd8.png

1.14 删除pos的后一个位置函数

8c511a23707b46859a585420f76009c4.png

//删除pos的后一个位置
void SLTInsertErase(SLTNode* pos)
{assert(pos);assert(pos->next);//如果pos指向尾节点，那是没有意义的SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);
}

测试一下：


void TestSList8()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);int x = 0;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTEraseAfter(pos);pos = NULL;}PrintSList(plist);}

634c822aa23c4d97b1b179770dd80b97.png

1.15 小测试

9a85beb8e62840a59e1f7441d81127f9.png

如图所示，在不给头指针的情况下我们是没办法找到pos前面的指针的，这样起不到链接pos后面节点的作用。

 8f13a8080fb441dc991682f47bd5778c.png

我们可以把d2的值给到前面的d1，然后让pos->next指向d2地址后面节点的地址，再free掉d2就好了，不过这样有一个缺陷，就是当pos指向尾节点时，后面没有值可以跟它换。

三.全部代码 

#pragma once
//Slist.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//打印函数
void PrintSList(SLTNode* phead);//空间函数
SLTNode* BuySlistNode(SLTDataType x);//尾插函数
void  SLTPushBack(SLTNode** pphead, SLTDataType x);//头插函数
void  SLTPushFront(SLTNode** pphead, SLTDataType x);//尾删函数
void  SLTPopBack(SLTNode** pphead);//头删函数
void  SLTPopFront(SLTNode** pphead);//查找函数
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);

———————————————————————————————————————————

#define _CRT_SECURE_NO_WARNINGS 1
//Slist.c
#include "Slist.h"//打印函数
void PrintSList(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//空间函数
SLTNode* BuySlistNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;}尾插函数
//SLTNode* SLTPushBack(SLTNode* phead, SLTDataType x)
//{
//	SLTNode* newnode = BuySlistNode(x);
//	SLTNode* tail = phead;
//	while (tail->next != NULL)
//	{
//		tail = tail->next;
//	}
//	tail->next = newnode;
//}//修改后的尾插函数
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySlistNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}//头插函数
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySlistNode(x);newnode->next = *pphead;*pphead = newnode;
}//尾删函数
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//这里断言的目的是因为pphead指向的是plist的地址，而plist永远有所指向//要么指向NULL，要么指向链表，所以pphead是不能为空的。//空assert(*pphead);//一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//一个节点以上else{SLTNode* tailpre = NULL;SLTNode* tail = *pphead;while (tail->next != NULL){tailpre = tail;tail = tail->next;}free(tail);tailpre->next = NULL;}
}尾删函数
//SLTNode* SLTPopBack(SLTNode** pphead)
//{
//	//空
//	assert(*pphead);
//	//一个节点
//	if ((*pphead)->next != NULL)
//	{
//		free(*pphead);
//		*pphead = NULL;
//	}
//	//一个节点以上
//	else
//	{
//		SLTNode* tail = *pphead;
//		while (tail->next->next)
//		{
//
//			tail = tail->next;
//		}
//		free(tail->next);
//		tail->next = NULL;
//	}
//	//头删函数
void  SLTPopFront(SLTNode** pphead)
{assert(pphead);//空assert(*pphead);//非空SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;}//查找函数
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySlistNode(x);prev->next = newnode;newnode->next = pos;}}在pos之后删除x
//void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
//{
//	assert(pos);
//	SLTNode* after = pos->next;
//	while (after->data != x)
//	{
//		after = after->next;
//	}
//	pos->next = after->next;
//	free(after);
//	pos->next = after;
//	
//}//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySlistNode(x);newnode->next = pos->next;pos->next = newnode;}//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;{while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}}
}//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);//如果pos指向尾节点，那是没有意义的SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);
}

—————————————————————————————————————————— 

#define _CRT_SECURE_NO_WARNINGS 1
//Test.c
#include "Slist.h"
#include <stdio.h>
#include <stdlib.h>void TestSList1()
{int n = 0;printf("请输入链表的长度：");scanf("%d", &n);printf("\n请依次输入每个节点的值：\n");SLTNode* plist = NULL;for (int i = 0; i < n; i++){int val = 0;scanf("%d", &val);SLTNode* newnode = BuySlistNode(val);newnode->next = plist;plist = newnode;PrintSList(plist);}SLTPushBack(plist, 1000);PrintSList(plist);}//void Swap1(int* p1, int* p2)
//{
//	int tmp = *p1;
//	*p1 = *p2;
//	*p2 = tmp;
//}
//
//void Swap2(int** p1, int** p2)
//{
//	int* tmp = **p1;
//	**p1 = **p2;
//	**p2 = tmp;
//}void TestSList2()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);SLTPushFront(&plist, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);PrintSList(plist);
}
void TestSList3()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);SLTPopBack(&plist);PrintSList(plist);SLTPopBack(&plist);PrintSList(plist);}
void TestSList4()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);SLTPopFront(&plist);PrintSList(plist);SLTPopFront(&plist);PrintSList(plist);SLTPopFront(&plist);PrintSList(plist);}void TestSList5()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);int x = 0;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTInsert(&plist, pos, 40);}PrintSList(plist);}void TestSList6()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);int x = 0;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTInsertAfter(pos, 3);}PrintSList(plist);}
void TestSList7()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);int x = 0;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTErase(&plist,pos);pos = NULL;}PrintSList(plist);}void TestSList8()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);PrintSList(plist);int x = 0;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTEraseAfter(pos);pos = NULL;}PrintSList(plist);}int main()
{//TestSList1();//TestSList2();TestSList8();//int a = 0;//int b = 1;//Swap1(&a, &b);//int* x1 = &a;//int* x2 = &b;//Swap1(x1, x2);return 0;
}

4b12323f94834afd9ec146a3c10df229.jpeg四.结语

虽然单链表用起来挺矬的哈哈，但是我们平时的oj题大部分都是用单链表举例子，正是因为有自身缺陷才方便出题嘛~单链表也会对后面的哈希图理解起到辅助效果。最后感谢大家的观看，友友们能够学习到新的知识是额滴荣幸，期待我们下次相见~

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/139007.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

云流化：XR扩展现实应用发展的一个新方向！

云流化：XR扩展现实应用发展的一个新方向！

扩展现实的发展已经改变了我们工作、生活和娱乐的方式&#xff0c;而且这才刚刚开始。扩展现实 (Extended reality, XR) 涵盖了沉浸式技术&#xff0c;包括虚拟现实、增强现实和混合现实。从游戏到虚拟制作再到产品设计&#xff0c;XR 使人们能够以前所未有的方式在计算机生成的…
阅读更多...
#循循渐进学51单片机#指针基础与1602液晶的初步认识#not.11

#循循渐进学51单片机#指针基础与1602液晶的初步认识#not.11

1、把本节课的指针相关内容&#xff0c;反复学习3到5遍&#xff0c;彻底弄懂指针是怎么回事&#xff0c;即使是死记硬背也要记住&#xff0c;等到后边用的时候可以实现顿悟。学会指针&#xff0c;就是突破了C语言的一道壁垒。 2&#xff0c;1602所有的指令功能都应用一遍&#…
阅读更多...
vue3——pixi初学，编写一个简单的小游戏,复制粘贴可用学习

vue3——pixi初学，编写一个简单的小游戏,复制粘贴可用学习

pixi官网 小游戏效果 两个文件夹 一个index.html 一个data.js //data.js import { reactive } from "vue"; import { Sprite, utils, Rectangle, Application, Text, Graphics } from "pixi.js";//首先 先创建一个舞台 export const app new Applicat…
阅读更多...
[Go疑难杂症]为什么nil不等于nil

[Go疑难杂症]为什么nil不等于nil

现象 在日常开发中&#xff0c;可能一不小心就会掉进 Go 语言的某些陷阱里&#xff0c;而本文要介绍的 nil ≠ nil 问题&#xff0c;便是其中一个&#xff0c;初看起来会让人觉得很诡异&#xff0c;摸不着头脑。 先来看个例子&#xff1a; type CustomizedError struct {Err…
阅读更多...
【面试必刷TOP101】 删除有序链表中重复的元素-I 删除有序链表中重复的元素-II

【面试必刷TOP101】 删除有序链表中重复的元素-I 删除有序链表中重复的元素-II

目录 题目&#xff1a;删除有序链表中重复的元素-I_牛客题霸_牛客网 (nowcoder.com) 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 题目&#xff1a;删除有序链表中重复的元素-II_牛客题霸_牛客网 (nowcoder…
阅读更多...
摩尔信使MThings实用功能盘点

摩尔信使MThings实用功能盘点

“冗长的用户手册”与“精简的交互设计”之间势必产生一条信息鸿沟&#xff0c;现在就来盘点一下摩尔信使MThings有哪些隐蔽而实用的功能。 01 数据配置类 一键刷新 功能&#xff1a;快速读取所有位数据、寄存器数据的当前数值。 操作&#xff1a;双击“数值”列表头。 一键…
阅读更多...
11:STM32---spl通信

11:STM32---spl通信

目录 一:SPL通信 1:简历 2:硬件电路 3:移动数据图 4:SPI时序基本单元 A : 开/ 终条件 B:SPI时序基本单元 A:模式0 B:模式1 C:模式2 D:模式3 C:SPl时序 A:发送指令 B: 指定地址写 C:指定地址读 二: W25Q64 1:简历 2: 硬件电路 3:W25Q64框图 4: Flash操作注意…
阅读更多...
MongoDB的搭建 和crud操作

MongoDB的搭建 和crud操作

MongoDB docker 下载 docker run --restartalways -d --name mongo -v /docker/mongodb/data:/data/db -p 27017:27017 mongo:4.0.6使用navcat工具使用MongoDB Crud操作 jar包 <dependency><groupId>org.projectlombok</groupId><artifactId>lom…
阅读更多...
小小购物车案例（V3）

小小购物车案例（V3）

效果如下&#xff1a; 可以添加和减少商品个数&#xff08;最少个为1&#xff09;&#xff0c;在添加的时候总价格会随着改变&#xff0c;也可以点击按钮移除商品 代码分为三个模块&#xff08;html、js、css&#xff09; html部分&#xff1a; <!DOCTYPE html> <h…
阅读更多...
计算机毕业设计 基于SSM+Vue的物资存储系统（以消防物资为例）的设计与实现 Java实战项目 附源码+文档+视频讲解

计算机毕业设计 基于SSM+Vue的物资存储系统（以消防物资为例）的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…
阅读更多...
2023华为杯研究生数学建模竞赛选题统计+分析

2023华为杯研究生数学建模竞赛选题统计+分析

2023年研赛的选题统计&#xff0c;我们主要基于根据两个平台投票统计。最终得出2023年研赛选题人数&#xff0c;这个结果仅供参考&#xff0c;但是应该具备一定的可信度。&#xff08;时间截止为22号中午1点&#xff09; 大家可以看到&#xff0c;AB题仅占10%&#xff0c;E题独…
阅读更多...
操作系统：系统调用

操作系统：系统调用

1.系统调用的定义 凡是与共享资源有关的操作、会直接影响到其他进程的操作, 就一定需要操作系统介入,就需要通过系统调用来实现。 1.回顾系统调用 操作系统作为用户和计算机硬件之间的接口&#xff0c;需要向上提供一些简单易用的服务。主要包括命令接口和程序接口。其中&a…
阅读更多...
Lua学习笔记：探究package

Lua学习笔记：探究package

前言 本篇在讲什么 理解Lua的package 本篇需要什么 对Lua语法有简单认知 对C语法有简单认知 依赖Visual Studio工具 本篇的特色 具有全流程的图文教学 重实践&#xff0c;轻理论&#xff0c;快速上手 提供全流程的源码内容 ★提高阅读体验★ &#x1f449; ♠ 一级…
阅读更多...
kafka的 ack 应答机制

kafka的 ack 应答机制

目录 一 ack 应答机制 二 ISR 集合 一 ack 应答机制 kafka 为用户提供了三种应答级别&#xff1a; all&#xff0c;leader&#xff0c;0 acks &#xff1a;0 这一操作提供了一个最低的延迟&#xff0c;partition的leader接收到消息还没有写入磁盘就已经返回ack&#x…
阅读更多...
Unity新收费模式：开启游戏开发者的持续盈利时代

Unity新收费模式：开启游戏开发者的持续盈利时代

Unity引擎近日宣布自2024年1月1日起&#xff0c;将根据游戏安装量对开发者进行收费。这一消息在游戏开发圈引起了广泛关注和讨论。根据Unity技术博客发布的《Unity收费模式和配套服务更新》一文&#xff0c;他们之所以选择这种计费方式&#xff0c;是因为每次游戏被下载时&…
阅读更多...
基于SSM+Vue的亿互游在线平台的设计与开发

基于SSM+Vue的亿互游在线平台的设计与开发

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用Vue技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…
阅读更多...
Linux下的Docker安装，以Ubuntu为例

Linux下的Docker安装，以Ubuntu为例

Docker是一种流行的容器化平台&#xff0c;它能够简化应用程序的部署和管理。 Docker安装 1、检查卸载老版本Docker&#xff08;为保证安装正确&#xff0c;尽量在安装前先进行一次卸载&#xff09; apt-get remove docker docker-engine docker.io containerd runc 2、Dock…
阅读更多...
Qt创建线程(线程池)

Qt创建线程(线程池)

1.线程池可以创建线程统一的管理线程&#xff08;统一创建、释放线程&#xff09; 2.使用线程池方法实现点击开始按钮生成10000个随机数&#xff0c;然后分别使用冒泡排序和快速排序排序这10000个随机数&#xff0c;最后在窗口显示排序后的数字&#xff1a; mainwindow.h文件…
阅读更多...
基础课-排列组合

基础课-排列组合

1.排列 2.组合 定义 从n个不同元素中&#xff0c;任意取出m(m<n)元素并为一组&#xff0c;叫做从n个不同元素中取出m个元素的一个组合 注意:1.不同元素 2.只取不排 3.相同组合:元素相同 3.把位置当成特殊元素 这个元素不一定入选的时候&#xff0c;把位置当特殊元素 4.插空…
阅读更多...
please choose a certificate and try again.(-5)报错怎么解决

please choose a certificate and try again.(-5)报错怎么解决

the server you want to connect to requests identification,please choose a certificate and try again.(-5)
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023