深圳网站建设专业公司,查看网站有没有备案,包头网站建设熊掌号,厚街做网站目录
#xff08;一#xff09;头文件
#xff08;二#xff09;功能实现
#xff08;1#xff09;打印单链表
#xff08;2#xff09;头插与头删 #xff08;3#xff09;尾插与尾删
#xff08;4#xff09; 删除指定位置节点 和 删除指定位置之后的节点 … 目录
一头文件
二功能实现
1打印单链表
2头插与头删 3尾插与尾删
4 删除指定位置节点 和 删除指定位置之后的节点 5指定位置之前插入节点 和 指定位置之后插入节点
6销毁链表 正文开始
一头文件 命名为 LST.h 这里不加解释的给出单链表的头文件并根据头文件来实现单链表的基本功能 包括打印单链表头插与头删尾插与尾删删除指定位置的节点删除指定位置之后的节点指定位置之前插入节点指定位置之后插入节点销毁链表等十个功能。
#pragma once#includestdio.h
#includestdlib.h
#includeassert.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;
} 完~
未经作者同意禁止转载
