如何将单链表改写为长尾词？

本文共计5565个文字，预计阅读时间需要23分钟。

链表的概要概念+我们知道顺序表的存储方式是一片连续的空间里存储数据而链表则不一样+从这个图中我们可以看到在一个链表中存在两个存储空间的部分+一部分是用来存储我们的数据

链表的概念

我们知道顺序表的储存方式是一片连续的空间里面储存数据而链表就不一样了，

从这个图我们可以看到在一个链表里面有两个储存空间的部分，一部分是用以储存我们的数据，而另一部分

储存的是一个结构体的地址，而这个地址指向的空间里面也有两个部分的储存空间用处和上面的一样，直到最后一个结构体的第二个部分指向的不再是一个结构体，而是一个空指针，像这样空间并不是连续的储存方式也就是链表。

单链表头文件的创建

我们下面就来创建一个链表的头文件

typedef int SLdata;//便于我们之后修改要储存的数据类型 typedef struct SLlist { SLdata m;//要储存的数据 struct SLlist* next;//下一个链表节点的储存位置 }SL;

单链表接口一：动态申请一个节点

这一步函数的目的是给我们为头插尾插等操作做准备，因为我们头插数据肯定是要在堆区上创建一片空间，用以储存我们新增的数据

SL* BuySListNode(SLdata x)//动态申请一个节点 { SL* newnode = (SL*)malloc(sizeof(SL)); if (newnode == NULL) { perror("BUYsl error"); return; } newnode->m = x;//将要储存的数据放入这里 newnode->next = NULL;//我这里为了初始化所以置为了NULL，当然也是为了尾插的方便 //如果是头插，或是任意位置插入只需改变一下next即可 return newnode;//最后将这个空间的地址返回 }

用图像理解：

单链表接口二：单链表打印

void SListPrint(SL** plist)//单链表的打印 { //我这里之所以要使用二级指针是为了让所有的头文件的传值，类型都保持一致这里使用一级指针也可以 //若是用一级指针下面的这句代码就改成SL* = plist; SL* cur = (*plist);//这里要解引用是因为这里为二级指针即我将SL* 变量的地址给传过来了。 //解引用一次就得到了SL* 再将将其赋给SL* cur 让其打印链表的数据 while (cur != NULL) { printf("->%d", cur->m);//这里的->也是一种解引用通过cur里面的地址找到储存结构体的空间 //再将储存的数据打印出来 cur = cur->next; } printf("NULL\n"); }//为什么这里使用一级指针可以而下面的有一些接口函数使用一级指针就不可以呢？ //因为我们这里要打印的是结构体里面的值,并不需要去改变一级指针的值

单链表接口三：单链表尾插

对于尾插我们要考虑两种情况：

1.尾插的前面没有任何节点

2.尾插的前面有多个或一个节点

// 单链表尾插 void SListPushBack(SL** pplist, SLdata x)//单链表的尾插 { //1.前面如果没有节点 //那么我们创建一个节点之后我们要改变外面的一级指针的地址，让其指向空指针的地址修改为指向我们新创建的节点 //2.如果前面有1个或多个节点了 //那么我们创建了新节点之后，只用找到之前的最后个节点，然后让其next指向我们创建的这个新节点。 //在这个过程中我们并不需要去改变外面的一级指针的地址，因为它已经指向第一个节点了 if ((*pplist) == NULL)//即没有节点 { SL* newnode = BuySListNode(x); *pplist = newnode;//改变外面的一级指针让其指向我们新创建的空间 } else { SL* cur = (*pplist); SL* newnode = BuySListNode(x); while (cur->next != NULL) { cur = cur->next; } cur->next = newnode; } }

图像理解：

对于尾插如果遇到没有任何节点的情况我们必须修改plist的值，而对于有节点的情况我们，只需要改变最后一个节点的next即可。对于情况一如过我们只是将plist传过去，那么就相当于拷贝了一份plist

然后我们改变拷贝的那个plist的值，但是这对于主函数里面的plist是毫无作用的，最后就会造成程序崩溃。

测试单链表的尾插是否正常：

void test1() { SL* plist = NULL; SListPushBack(&plist, 6); SListPushBack(&plist, 5); SListPushBack(&plist, 4); SListPushBack(&plist, 3); SListPushBack(&plist, 2); SListPushBack(&plist, 1); SListPushBack(&plist, 0); SListPrint(&plist); }

运行图像：

单链表接口四：单链表头插

对于一个链表的头插我们要做的最重要一步也就是要改变主函数里面的plist的值，也就是要通过二级指针找到一级指针（plist）的空间，再改变。而且和尾插不同，尾插只是在链表的节点为0的时候才改变olist的值而头插则每一次都要改变plist的值：

图像理解：

而这里的改变plist的值也就是通过二级指针来做的，也就是我们上面说的你要改变什么数据的值，你就要使用这个数据对应的指针，这里的plist是SL* 所以我们就要用SL** 来改变它

void SListPushFront(SL** pplist, SLdata x)// 单链表的头插 { //对于头插我们就不需要考虑什么节点个数的问题了，如果有多个节点只用改变next让其链接起来即可 //需要注意的是头插相当于每一次都要改变外部的plist的值。 SL* newnode = BuySListNode(x); newnode->next = (*pplist);//让原本plist指向的那个空间放入我们新创建的这个节点 *pplist = newnode;//然后改变plist的值让其指向我们新创建的这个节点 //这里如果不是二级指针而只是一级指针，那么相当于作了一个plist的备份这个备份指向的空间和plist指向的空间是一样的 //如果我们只是想要改变plist指向的那个空间使用一级指针是毫无问题的，但是我们这里要改变的是plist的空间 //所以要使用二级指针 }

我们使用test2去检测，

void test2() { SL* plist = NULL; SListPushFront(&plist, 6); SListPushFront(&plist, 5); SListPushFront(&plist, 4); SListPushFront(&plist, 3); SListPushFront(&plist, 2); SListPrint(&plist); }

单链表接口五：单链表的尾删

我们来看实现代码：

void SListPopBack(SL** pplist)// 单链表的尾删 { //对于删除链表里面的一个节点，我们需要考虑三种情况 //1.要删除的单链表已经没有节点了 //2.要删除的单链表只有一个节点 //3.要删除的单链表有多个节点 assert(*pplist);//断言防止没有节点的链表继续进行尾删操作 if ((*pplist)->next == NULL)//要删除的链表只有一个节点 { free(*pplist);//释放掉此时的plist指向的空间 *pplist = NULL;//改变plist的值为空指针 } else//链表含有多个节点 { //找到倒数第二个节点的方式有两种 //第一种 //SL* tmp = (*pplist); //while (tmp->next->next != NULL)//找到倒数第二个节点 //{ // tmp = tmp->next; //} //free(tmp->next); //tmp->next = NULL; //第二种： SL* tmp = (*pplist); SL* last = NULL;//这一个指针变量里面储存的就是tmp所指向节点的上一个节点 while (tmp->next != NULL) { last = tmp;//在这里记录tmp上一次的节点地址数据 tmp = tmp->next; } free(tmp); last->next = NULL; } }

运用逻辑图解释：

情况2.只有一个节点：

情况三：还有多个节点

完成尾删：

void test3() { SL* plist = NULL; SListPushFront(&plist, 6); SListPushFront(&plist, 5); SListPushFront(&plist, 4); SListPushFront(&plist, 3); SListPushFront(&plist, 2); SListPrint(&plist); SListPopBack(&plist); SListPrint(&plist); SListPopBack(&plist); SListPrint(&plist); SListPopBack(&plist); SListPrint(&plist); }

检测尾删功能是否有错误

单链表接口六：单链表的头删

void SListPopFront(SL** pplist)// 单链表头删 { //对于头删我们肯定也要考虑三个问题 //1.对于没有节点的链表的尾删要处理 //2.对于只有一个节点的链表的处理 //3.对于还有多个节点的链表的处理 //对于情况一我们直接断言即可 assert(*pplist); //if ((*pplist)->next == NULL) //{ // free(*pplist); // *pplist = NULL; //}//只有一个节点的链表头删 //else //{ // SL* tmp = *pplist; // *pplist = (*pplist)->next; // free(tmp); //}//完成多个节点的头删 //但其实上面的写法复杂化了，我们只用写else里面的代码也能解决只有一个节点的链表的头删 //假设这里有一个plist的指针它指向的链表只有一个节点，即这个结构体的next指向的是NULL //那么我们重新创建一个SL*的指针变量用以储存plist的值，也就是拷贝一份plist然后改变plist //让其等于next也就是让其等于NULL //然后我们在释放tmp也就释放了，最后一个节点 SL* tmp = *pplist; *pplist = (*pplist)->next; free(tmp); }

图像理解：

对于只有一个节点的头删和尾删逻辑图都是一样的我这里就不重复了。

多个节点：

void test4() { SL* plist = NULL; SListPushFront(&plist, 6); SListPushFront(&plist, 5); SListPushFront(&plist, 4); SListPushFront(&plist, 3); SListPushFront(&plist, 2); SListPrint(&plist); SListPopFront(&plist); SListPrint(&plist); }//测试头删功能

单链表接口七：单链表的数据查询

单链表的数据查询和顺序表的数据查询不同顺序表我们可以如同数组一样去查询顺序表里面的数据，但是链表不同链表由于它的储存数据的空间并不是连续的,所以也就意味着它不能如同顺序表一样去查询数据，我们要使用顺寻表里面的数据去寻找它所在的节点然后最后再返回这个节点。

代码：

SL* SListFind(SL* plist, SLdata x)// 单链表查找 //因为我们这次查找是在结构体里面去查找所以这里使用一级指针就可以了 { SL* newnode = plist;//这里传过来的是一级指针也就是结构体的地址，我们也是需要在结构体里面去查照我们的数据 while (newnode != NULL) { if (newnode->m == x) { return newnode;//这里也就代表找到了我们要查找的数据所在的节点，再返回这个节点的地址 } } return newnode;//在这里也就意味着没有找到这个数据在链表里面的节点返回空指针

因为单链表的数据查询很不好检测我们就放到下面的单链表pos位置后插入这个功能完成以后再来一起检测。

单链表接口八：单链表在pos位置之前插入数据

void SListInsert(SL* pos,SL**pplist, SLdata x)// 单链表在pos位置之前插入x { if (pos == *pplist)//这一步是为了防止我们如果要修改的就是plist指向的那个节点也就是头节点 { SListPushFront(pplist,x);//直接调用头插的函数接口即可 } SL* newnode = BuySListNode(x);//创建一个新节点 SL* cur = *pplist; while (cur->next != pos)//我们将第一个节点的地址传递给cur然后判断cur的next的值是否等于pos的值 { cur = cur->next; } //如果等于那么我们就找到了pos前面位置的节点现在只需要改变这个节点的next让其指向我们新创建的这个节点 //然后再让新创建的这个节点的next的值等于pos也就完成了节点之间的链接 cur->next = newnode;//这一步也就是让pos前面节点的next值等于我们新创建的这个节点 newnode->next = pos;//然后改变新创建节点的next让其值等于pos }

图像理解：

我们这里的测试是即测试了查找的功能又测试了在pos前面插入的功能

单链表接口九：单链表在pos之后增加数据

我这里依旧是先给出代码再画出逻辑图

void SListInsertAfter(SL* pos,SL**pplist, SLdata x)// 单链表在pos位置之后插入x { //和在pos前面插入数据一样我们依旧要考虑一种极端情况，也就是如果pos所指向的节点是在最后一个呢？ //那么此时增加节点也就变成了尾插节点直接调用函数接口就可以了 SL* cur = pos; if (cur->next == NULL) { SListPushBack(pplist,x); } SL* newnode = BuySListNode(x);//创建一个新节点 newnode->next = pos->next;//我们先让这个新创建的节点的next指向pos后面的那一个节点 pos->next = newnode;//然后在改变pos的next让其指向我们新创建的这一个节点 }

因为和在pos位置前面相比这个函数的实现较为简单我就不画完成图了。

这个图并没有包括极端情况

检测代码

void test6() { SL* plist = NULL; SListPushFront(&plist, 6); SListPushFront(&plist, 5); SListPushFront(&plist, 4); SListPushFront(&plist, 3); SListPushFront(&plist, 2); SListPrint(&plist); SL* emp =SListFind(plist,3); SListInsertAfter(emp, &plist, 30); SListPrint(&plist); }

单链表接口十：单链表删除pos位置之后的数据

// 单链表删除pos位置之后的值 void SListEraseAfter(SL* pos)// 单链表删除pos位置之后的值 { assert(pos);//防止传入空指针 SL* tmp = pos->next;//因为要删除pos之后的值在将pos->next置空之前先将这个值传递出去 pos->next = NULL;//将原节点的next置空 while (tmp != NULL) { SL* t = tmp; tmp = tmp->next; free(t); }//这里的逻辑和当初找到倒数第二个节点的逻辑很相似都是将tmp的上一个节点储存起来然后先让tmp的值改变再释放前一个空间 }

测试代码

void test7() { SL* plist = NULL; SListPushFront(&plist, 6); SListPushFront(&plist, 5); SListPushFront(&plist, 4); SListPushFront(&plist, 3); SListPushFront(&plist, 2); SListPrint(&plist); SL* tmp = SListFind(plist, 4); SListEraseAfter(tmp); SListPrint(&plist); }

单链表所有的头文件

//总结如果是在两个不同的栈帧中例如在一个栈帧里面有一个变量a我要在另外的一个栈帧里面修改a的值那么 //我就要传a的地址，而这个a可能本就是一个指针变量 #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLdata;//便于我们之后修改要储存的数据类型 typedef struct SLlist { SLdata m;//要储存的数据 struct SLlist* next;//下一个链表节点的储存位置 }SL; SL* BuySListNode(SLdata x);//动态申请一个节点 void SListPrint(SL** plist);//单链表的打印 void SListPushBack(SL** pplist, SLdata x);//单链表的尾插 void SListPushFront(SL** pplist, SLdata x);// 单链表的头插 void SListPopBack(SL** pplist);// 单链表的尾删 void SListPopFront(SL** pplist);// 单链表头删 void SListInsertAfter(SL* pos,SL** pplist, SLdata x);// 单链表在pos位置之后插入x void SListInsert(SL* pos,SL**pplist, SLdata x);//单链表在pos位置之前插入x SL* SListFind(SL* plist, SLdata x);// 单链表查找 void SListEraseAfter(SL* pos);// 单链表删除pos位置之后的值

单链表所有的实现函数接口的文件

#include"SLlist.h" SL* BuySListNode(SLdata x)//动态申请一个节点 { SL* newnode = (SL*)malloc(sizeof(SL)); if (newnode == NULL) { perror("BUYsl error"); return NULL; } newnode->m = x;//将要储存的数据放入这里 newnode->next = NULL;//我这里为了初始化所以置为了NULL，当然也是为了尾插的方便 //如果是头插，或是任意位置插入只需改变一下next即可 return newnode;//最后将这个空间的地址返回 } void SListPrint(SL** plist)//单链表的打印 { //我这里之所以要使用二级指针是为了让所有的头文件的传值，类型都保持一致这里使用一级指针也可以 //若是用一级指针下面的这句代码就改成SL* = plist; SL* cur = (*plist);//这里要解引用是因为这里为二级指针即我将SL* 变量的地址给传过来了。 //解引用一次就得到了SL* 再将将其赋给SL* cur 让其打印链表的数据 while (cur != NULL) { printf("%d->", cur->m); cur = cur->next; } printf("NULL\n"); }//为什么这里使用一级指针可以而下面的有一些接口函数使用一级指针就不可以呢？ //因为我们这里要打印的是结构体里面的值,并不需要去改变一级指针的值 void SListPushBack(SL** pplist, SLdata x)//单链表的尾插 { //1.前面如果没有节点 //那么我们创建一个节点之后我们要改变外面的一级指针的地址，让其指向空指针的地址修改为指向我们新创建的节点 //2.如果前面有1个或多个节点了 //那么我们创建了新节点之后，只用找到之前的最后个节点，然后让其next指向我们创建的这个新节点。 //在这个过程中我们并不需要去改变外面的一级指针的地址，因为它已经指向第一个节点了 if ((*pplist) == NULL)//即没有节点 { SL* newnode = BuySListNode(x); *pplist = newnode;//改变外面的一级指针让其指向我们新创建的空间 } else { SL* cur = (*pplist); SL* newnode = BuySListNode(x); while (cur->next != NULL) { cur = cur->next; } cur->next = newnode; } } void SListPushFront(SL** pplist, SLdata x)// 单链表的头插 { //对于头插我们就不需要考虑什么节点个数的问题了，如果有多个节点只用改变next让其链接起来即可 //需要注意的是头插相当于每一次都要改变外部的plist的值。 SL* newnode = BuySListNode(x); newnode->next = (*pplist);//让原本plist指向的那个空间放入我们新创建的这个节点 *pplist = newnode;//然后改变plist的值让其指向我们新创建的这个节点 //这里如果不是二级指针而只是一级指针，那么相当于作了一个plist的备份这个备份指向的空间和plist指向的空间是一样的 //如果我们只是想要改变plist指向的那个空间使用一级指针是毫无问题的，但是我们这里要改变的是plist的空间 //所以要使用二级指针 } void SListPopBack(SL** pplist)// 单链表的尾删 { //对于删除链表里面的一个节点，我们需要考虑三种情况 //1.要删除的单链表已经没有节点了 //2.要删除的单链表只有一个节点 //3.要删除的单链表有多个节点 assert(*pplist);//断言防止没有节点的链表继续进行尾删操作 if ((*pplist)->next == NULL)//要删除的链表只有一个节点 { free(*pplist);//释放掉此时的plist指向的空间 *pplist = NULL;//改变plist的值为空指针 } else//链表含有多个节点 { //找到倒数第二个节点的方式有两种 //第一种 //SL* tmp = (*pplist); //while (tmp->next->next != NULL)//找到倒数第二个节点 //{ // tmp = tmp->next; //} //free(tmp->next); //tmp->next = NULL; //第二种： SL* tmp = (*pplist); SL* last = NULL;//这一个指针变量里面储存的就是tmp所指向节点的上一个节点 while (tmp->next != NULL) { last = tmp;//在这里记录tmp上一次的节点地址数据 tmp = tmp->next; } free(tmp); last->next = NULL; } } void SListPopFront(SL** pplist)// 单链表头删 { //对于头删我们肯定也要考虑三个问题 //1.对于没有节点的链表的尾删要处理 //2.对于只有一个节点的链表的处理 //3.对于还有多个节点的链表的处理 //对于情况一我们直接断言即可 assert(*pplist); //if ((*pplist)->next == NULL) //{ // free(*pplist); // *pplist = NULL; //}//只有一个节点的链表头删 //else //{ // SL* tmp = *pplist; // *pplist = (*pplist)->next; // free(tmp); //}//完成多个节点的头删 //但其实上面的写法复杂化了，我们只用写else里面的代码也能解决只有一个节点的链表的头删 //假设这里有一个plist的指针它指向的链表只有一个节点，即这个结构体的next指向的是NULL //那么我们重新创建一个SL*的指针变量用以储存plist的值，也就是拷贝一份plist然后改变plist //让其等于next也就是让其等于NULL //然后我们在释放tmp也就释放了，最后一个节点 SL* tmp = *pplist; *pplist = (*pplist)->next; free(tmp); } SL* SListFind(SL* plist, SLdata x)// 单链表查找 //因为我们这次查找是在结构体里面去查找所以这里使用一级指针就可以了 { SL* newnode = plist;//这里传过来的是一级指针也就是结构体的地址，我们也是需要在结构体里面去查照我们的数据 while (newnode != NULL) { if (newnode->m == x) { return newnode;//这里也就代表找到了我们要查找的数据所在的节点，再返回这个节点的地址 } newnode = newnode->next; } return newnode;//在这里也就意味着没有找到这个数据在链表里面的节点返回空指针 } void SListInsert(SL* pos,SL**pplist, SLdata x)// 单链表在pos位置之前插入x { if (pos == *pplist)//这一步是为了防止我们如果要修改的就是plist指向的那个节点也就是头节点 { SListPushFront(pplist,x);//直接调用头插的函数接口即可 } SL* newnode = BuySListNode(x);//创建一个新节点 SL* cur = *pplist; while (cur->next != pos)//我们将第一个节点的地址传递给cur然后判断cur的next的值是否等于pos的值 { cur = cur->next; } //如果等于那么我们就找到了pos前面位置的节点现在只需要改变这个节点的next让其指向我们新创建的这个节点 //然后再让新创建的这个节点的next的值等于pos也就完成了节点之间的链接 cur->next = newnode;//这一步也就是让pos前面节点的next值等于我们新创建的这个节点 newnode->next = pos;//然后改变新创建节点的next让其值等于pos } void SListInsertAfter(SL* pos,SL**pplist, SLdata x)// 单链表在pos位置之后插入x { //和在pos前面插入数据一样我们依旧要考虑一种极端情况，也就是如果pos所指向的节点是在最后一个呢？ //那么此时增加节点也就变成了尾插节点直接调用函数接口就可以了 SL* cur = pos; if (cur->next == NULL) { SListPushBack(pplist,x); } SL* newnode = BuySListNode(x);//创建一个新节点 newnode->next = pos->next;//我们先让这个新创建的节点的next指向pos后面的那一个节点 pos->next = newnode;//然后在改变pos的next让其指向我们新创建的这一个节点 } void SListEraseAfter(SL* pos)// 单链表删除pos位置之后的值 { assert(pos);//防止传入空指针 SL* tmp = pos->next;//因为要删除pos之后的值在将pos->next置空之前先将这个值传递出去 pos->next = NULL;//将原节点的next置空 while (tmp != NULL) { SL* t = tmp; tmp = tmp->next; free(t); }//这里的逻辑和当初找到倒数第二个节点的逻辑很相似都是将tmp的上一个节点储存起来然后先让tmp的值改变再释放前一个空间 }

单链表所有的测试文件

#include"SLlist.h" void test1() { SL* plist = NULL; SListPushBack(&plist, 6); SListPushBack(&plist, 5); SListPushBack(&plist, 4); SListPushBack(&plist, 3); SListPushBack(&plist, 2); SListPushBack(&plist, 1); SListPushBack(&plist, 0); SListPrint(&plist); } void test2() { SL* plist = NULL; SListPushFront(&plist, 6); SListPushFront(&plist, 5); SListPushFront(&plist, 4); SListPushFront(&plist, 3); SListPushFront(&plist, 2); SListPrint(&plist); } void test3() { SL* plist = NULL; SListPushFront(&plist, 6); SListPushFront(&plist, 5); SListPushFront(&plist, 4); SListPushFront(&plist, 3); SListPushFront(&plist, 2); SListPrint(&plist); SListPopBack(&plist); SListPrint(&plist); SListPopBack(&plist); SListPrint(&plist); SListPopBack(&plist); SListPrint(&plist); } void test4() { SL* plist = NULL; SListPushFront(&plist, 6); SListPushFront(&plist, 5); SListPushFront(&plist, 4); SListPushFront(&plist, 3); SListPushFront(&plist, 2); SListPrint(&plist); SListPopFront(&plist); SListPrint(&plist); } void test5() { SL* plist = NULL; SListPushFront(&plist, 6); SListPushFront(&plist, 5); SListPushFront(&plist, 4); SListPushFront(&plist, 3); SListPushFront(&plist, 2); SListPrint(&plist); SL* tmp = SListFind(plist,6); SListInsert(tmp, &plist, 50); SListPrint(&plist); } void test6() { SL* plist = NULL; SListPushFront(&plist, 6); SListPushFront(&plist, 5); SListPushFront(&plist, 4); SListPushFront(&plist, 3); SListPushFront(&plist, 2); SListPrint(&plist); SL* emp =SListFind(plist,3); SListInsertAfter(emp, &plist, 30); SListPrint(&plist); } void test7() { SL* plist = NULL; SListPushFront(&plist, 6); SListPushFront(&plist, 5); SListPushFront(&plist, 4); SListPushFront(&plist, 3); SListPushFront(&plist, 2); SListPrint(&plist); SL* tmp = SListFind(plist, 4); SListEraseAfter(tmp); SListPrint(&plist); } int main() { //test1();//测试单链表的尾插是否正常 //test2();//测试单链表的头插是否正常 //test3();//测试单链表的尾删是否正常 //test4();//测试单链表里面的头删是否正常 //test5();//测试我们要在6前面插入一个50 //test6();//测试我们要在3的后面插入一个30 //test7();//测试销毁4之后的链表节点 return 0; }

希望这篇博客能对你有所帮助，如果有错误请严厉指出我一定改正。

一个还在学习c的萌新希望能和大家一起进步。