【C语言】实现单链表

---

目录

（一）头文件

（二）功能实现

（1）打印单链表

（2）头插与头删 

 （3）尾插与尾删

（4） 删除指定位置节点 和 删除指定位置之后的节点

 （5）指定位置之前插入节点 和 指定位置之后插入节点

（6）销毁链表

---

正文开始：

（一）头文件

         命名为 "LST.h"

        这里不加解释的给出单链表的头文件，并根据头文件来实现单链表的基本功能：

        包括打印单链表，头插与头删，尾插与尾删，删除指定位置的节点，删除指定位置之后的节点，指定位置之前插入节点，指定位置之后插入节点，销毁链表等十个功能。

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//链表的数据类型
typedef int SLTDatatype;//链表的一个节点
typedef struct SLTNode
{SLTDatatype data;struct SLTNode* next;
}SLTNode;//print SLT
void slPrint(SLTNode* phead);//buy_new_new
SLTNode* Get_Newnode(SLTDatatype x);//head_push
void slHeadpush(SLTNode** pphead, SLTDatatype x);//head_del
void slHeaddel(SLTNode** pphead);//tail_push
void slTailpush(SLTNode** pphead,SLTDatatype x);//tail_del
void slTaildel(SLTNode** pphead);//查找数据
SLTNode* sl_find(SLTNode** pphead, SLTDatatype x);/**** FUN 删除指定位置之后的节点* 参数 pos表示data==这个数据的节点* 返回值 无
****/
void SLTEraseAfter(SLTNode* pos);/**** Fun 删除指定位置的节点* 参数 pos* 返回值 无
****/
void slDelPos(SLTNode** pphead, SLTNode* pos);/**** Fun 指定位置之前插入节点* 参数 pos* 返回值 无
****/
void slInsertpos(SLTNode** pphead, SLTNode* pos, SLTDatatype x);//在指定位置之后插入数据
void slInsertAfter(SLTNode* pos, SLTDatatype x);//销毁链表
void sl_destory(SLTNode**pphead);

（二）功能实现

         创建链表（以及初始化）：

	SLTNode* pl = NULL;    //链表存储的是空指针，此时表示链表为空

（1）打印单链表

        打印链表并不需要改变链表本身，因此只需要传值（传值意味着形参与实参没有联系）调用；

        通常我们在遍历链表时，总会创建一个pcur指针表示当前指向的节点，这样不会因为遍历而丢失重要指针的值；

//print SLT
void slPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d-->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

（2）头插与头删 

         在执行插入（包括头插，尾插，特定位置插入）操作时，总会重复使用一个功能：获取新节点，所以我们将获取新节点封装为一个函数：

Get_Newnode（）：

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

头插与头删

头插

        首先传递的指针不为空，通过assert断言来判断；

        申请新节点，并将新节点放在链表的头部；

//head_push
void slHeadpush(SLTNode** pphead, SLTDatatype x)
{//指针不为空assert(pphead);//申请新节点SLTNode* newnode = Get_Newnode(x);//转变头节点newnode->next = *pphead;*pphead = newnode;
}

头删

        首先传递的指针不为空，链表也不为空（如果为空，那么无法执行头删），通过assert断言来判断；

        如果直接将头free掉，就无法对链表的原头解引用（->也是解引用的一种）那么链表的新头就无法找到了。所以创建一个del指针，暂时保存链表的原头（也是将要释放的节点），当链表的头指针后移找到新头后，再通过del释放原头。

//head_del
void slHeaddel(SLTNode** pphead)
{//指针不为空assert(pphead);//链表不为空assert(*pphead);SLTNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;
}

 （3）尾插与尾删

尾插

         首先传递的指针不为空，通过assert断言来判断；

        尾插通常是在尾部插入，但是如果链表为空，尾插就变成了头插；

        如果链表为空，新节点作为头节点；链表不为空，找到尾节点，进行尾插；

//tail_push
void slTailpush(SLTNode** pphead, SLTDatatype x)
{assert(pphead);SLTNode* newnode = Get_Newnode(x);//链表为空，新节点作为头节点if (*pphead == NULL){*pphead = newnode;return;}SLTNode* pcur = *pphead;//链表不为空，找到尾节点while (pcur->next){pcur = pcur->next;}pcur->next = newnode;
}

尾删

        首先传递的指针不为空，链表也不为空（如果为空，那么无法执行尾删），通过assert断言来判断；

        尾删通常是删除尾部的节点，如果只有一个节点，尾删就变成了头删；

        如果只有一个节点，直接删除；如果有多个节点，现找尾，再执行尾删；

//tail_del
void slTaildel(SLTNode** pphead)
{assert(pphead);assert(*pphead);//链表不为空//只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}//有多个节点SLTNode* prev = NULL;SLTNode* ptail = *pphead;//找尾while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾节点free(ptail);ptail = NULL;
}

（4） 删除指定位置节点 和 删除指定位置之后的节点

        指定位置指定的是某一个存在于链表中的数据的位置，这意味着我们先要找到这个已经存在的数据，封装一个函数：

        sl_find（）：

//查找数据
SLTNode* sl_find(SLTNode** pphead, SLTDatatype x)
{SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

删除指定位置之后的数据

        相比于删除指定位置，删除指定位置之后更简单；

        因为删除指定位置之后仅需要指定位置的节点，不需要遍历查找；删除指定位置需要知道指定位置之前的节点，需要遍历查找；

删除指定位置之后

        首先传递的指针不为空，这个位置也不能是尾节点（尾节点后面没有可以删除的节点），通过assert断言来判断；

        如果直接将节点free掉（设指定位置为P节点），就无法对P节点解引用（->也是解引用的一种）那么链表P节点后的就无法找到了。所以创建一个del指针，暂时保存链表的P节点后的指针，当P前与P后相连后，再通过del释放P节点。

/**** FUN 删除指定位置之后的节点* 参数 pos表示data==这个数据的节点* 返回值 无
****/
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//pos->next不能为空assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

删除指定位置

        首先传递的指针不为空，链表也不为空（如果为空，那么无法执行删除），通过assert断言来判断；

        如果pos 刚好是头节点，直接删除；

        pos不是头节点，找到pos，再执行删除；先创建一个prev节点，遍历链表，指向P节点之前；

/**** Fun 删除指定位置的节点* 参数 pos* 返回值 无
****/
void slDelPos(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos 刚好是头节点，直接删除if (*pphead == pos){slHeaddel(pphead);return;}//pos不是头节点，找到posSLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//链接prev->next = pos->next;free(pos);pos = NULL;
}

 （5）指定位置之前插入节点 和 指定位置之后插入节点

         指定位置之前插入节点 与 指定位置之前删除节点类似，都需要创建prev指针，遍历链表；

指定位置之前插入节点 

        首先传递的指针不为空，链表也不为空（如果pos不为空，所以链表一定不为空，【因为链表为空是pos为空的充分条件】两者是逆否命题），通过assert断言来判断；

         如果pos是头节点，则头插；pos不是头节点，则找到pos，通过prev插入新节点；

/**** Fun 指定位置之前插入节点* 参数 pos* 返回值 无
****/
void slInsertpos(SLTNode** pphead, SLTNode* pos,SLTDatatype x)
{assert(pphead);assert(pos);//要加上链表不能为空assert(*pphead);SLTNode* newnode = Get_Newnode(x);//pos是头节点if (*pphead == pos){slHeadpush(pphead, x);return;}//pos不是头节点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;
}

指定位置之后插入节点

        直接插入即可；

//在指定位置之后插入数据
void slInsertAfter(SLTNode* pos, SLTDatatype x)
{assert(pos);SLTNode* newnode = Get_Newnode(x);newnode->next = pos->next;pos->next = newnode;
}

（6）销毁链表

       首先传递的指针不为空，通过assert断言来判断；

        通过循环一个接着一个释放，在每次释放之前，创建一个next指针保存下一个节点，防释放后无法通过解引用找到下一个节点；

        最后，将链表置空；

//销毁链表
void sl_destory(SLTNode**pphead)
{assert(pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

完~

未经作者同意禁止转载