邢台移动端网站建设,响应式网站设计思路,微机做网站的软件,宿迁市住房和城乡建设局网站#x1f493;博主个人主页:不是笨小孩#x1f440; ⏩专栏分类:数据结构与算法#x1f440; #x1f69a;代码仓库:笨小孩的代码库#x1f440; ⏩社区#xff1a;不是笨小孩#x1f440; #x1f339;欢迎大家三连关注#xff0c;一起学习#xff0c;一起进步#… 博主个人主页:不是笨小孩 ⏩专栏分类:数据结构与算法 代码仓库:笨小孩的代码库 ⏩社区不是笨小孩 欢迎大家三连关注一起学习一起进步 单链表 链表的概念及结构概念结构 单链表的实现结构它的接口有哪些呢申请节点打印链表尾插头插尾删头删查找在pos位置之后插入x在pos位置前面插入删除pos之后的值删除pos位置的值销毁链表 链表的概念及结构
概念 链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 结构
在逻辑上链表应该是这样子的 在现实中是这样子的 注意 链表在逻辑上时连续的但是在物理上不一定连续。 现实中的节点一般是从堆上申请出来的 。 从堆上申请的空间可能是连续的也可能是不连续的。 单链表的实现
结构 单链表结构中有两个数据一个是存储数据的还有一个指针指向下一个节点。 typedef int SLTDateType;typedef struct SListNode
{SLTDateType date;struct SListNode* next;
}SLTNode;它的接口有哪些呢
// 动态申请一个节点
SLTNode* BuySListNode(SLTDateType x);// 单链表打印
void SListPrint(SLTNode* plist);// 单链表尾插
void SListPushBack(SLTNode** pplist, SLTDateType x);// 单链表的头插
void SListPushFront(SLTNode** pplist, SLTDateType x);// 单链表的尾删
void SListPopBack(SLTNode** pplist);// 单链表头删
void SListPopFront(SLTNode** pplist);// 单链表查找
// 找到返回这个节点的地址。找不到返回NULL
SLTNode* SListFind(SLTNode* plist, SLTDateType x);// 单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDateType x);// 单链表删除pos位置之后的值
void SListEraseAfter(SLTNode* pos);// 单链表的销毁
void SListDestroy(SLTNode* plist);//在pos前插入
void SListInsert(SLTNode** pplist,SLTNode* pos, SLTDateType x);// 删除pos节点
void SListErase(SLTNode** pplist, SLTNode* pos);
申请节点 我们要添加数据难免要频繁的开辟节点所以我们分装以个函数专门来开辟节点。 // 动态申请一个节点
SLTNode* BuySListNode(SLTDateType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);//开辟失败结束掉程序exit(-1);}newnode-date x;newnode-next NULL;return newnode;
}打印链表 打印链表比较简单只需要遍历一遍链表即可。 void SListPrint(SLTNode* plist)
{SLTNode* cur plist;while (cur){printf(%d-, cur-date);cur cur-next;}printf(NULL\n);
}尾插 尾插时链表可能为空所以这时就要把将头指向开辟的节点这是需要改变头想要改变一级指针所以就要传一级指针的地址这时就需要用一个二级指针来接收如果链表不为空我们正常尾插就可以我们需要先找到尾节点然后就为节点的next指向newnode即可。 // 单链表尾插
void SListPushBack(SLTNode** pplist, SLTDateType x)
{
// 断言pplist一定不为空为空时程序异常终止程序assert(pplist);SLTNode* newnode BuySListNode(x);if (*pplist NULL){//链表为空*pplist newnode;}else{SLTNode* cur *pplist;//找尾节点while (cur-next){cur cur-next;}cur-next newnode;}
}头插 头插同样需要改变头结点所以还是需要二级指针头插只需要将newnode的next指向原链表的头然后将原链表的头指向newnode就可以了。 void SListPushFront(SLTNode** pplist, SLTDateType x)
{
// 断言pplist一定不为空为空时程序异常终止程序assert(pplist);SLTNode* newnode BuySListNode(x);newnode-next *pplist;(*pplist) newnode;
}尾删 尾删只剩一个节点时同样的需要改变头指针这时free掉头结点将其置NULL即可。正常情况下我们只需要找到尾节点的前一个然后释放掉尾节点然后把前一个的next置NULL即可。 // 单链表的尾删
void SListPopBack(SLTNode** pplist)
{
// 断言pplist一定不为空为空时程序异常终止程序assert(pplist);
//断言链表为空就不要删了assert(*pplist);if ((*pplist)-next NULL){free(*pplist);*pplist NULL;}else{SLTNode* tail *pplist;// 至少有两个节点所以tail-next一定不为NULLwhile (tail-next-next){tail tail-next;}free(tail-next);tail-next NULL;}
}头删 头删一定需要改变头结点所以同样需要二级指针我们需要保存头结点的next让然后释放掉头结点将头结点重新指向保存下来的next即可。 // 单链表头删
void SListPopFront(SLTNode** pplist)
{
// 断言pplist一定不为空为空时程序异常终止程序assert(pplist);
//断言链表为空就不要删了assert(*pplist);//*pplist一定不为NULLSLTNode* cur (*pplist)-next;free(*pplist);*pplist cur;}查找 查找就很简单了我们只需要遍历一遍链表即可。 // 单链表查找
SLTNode* SListFind(SLTNode* plist, SLTDateType x)
{
//断言链表为空就不要查了assert(plist);SLTNode* cur plist;while (cur){if (cur-date x){return cur;}cur cur-next;}return NULL;
}在pos位置之后插入x 只需要将newnode的next指向pos的next然后将pos的next指向newnode即可。 // 单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos);SLTNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}在pos位置前面插入 如果是一个节点间的话接相当于头插我们可以复用上面头插的代码正常情况下我们需要遍历找到pos的前一个位置将newnode的next指向pos再把该节点指向newnode即可。 void SListInsert(SLTNode** pplist, SLTNode* pos, SLTDateType x)
{assert(pplist);if (pos *pplist){SListPushFront(pplist, x);}else{SLTNode* cur *pplist;while (cur-next ! pos){cur cur-next;}SLTNode* newnode BuySListNode(x);newnode-next pos;cur-next newnode;}
}删除pos之后的值 不能删除最后一个节点其他情况我们可以直接释放掉pos的next将pos的next指向下一个即可。 // 单链表删除pos位置之后的值
void SListEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* cur pos-next;pos-next cur-next;free(cur);cur NULL;
}删除pos位置的值 我们需要遍历找pos的前一个位置然后将pos的前一个位置的next指向pos的next然后释放掉pos即可但是如果pos是头结点我们这样处理不了我们可以单独处理相当头删。 void SListErase(SLTNode** pplist, SLTNode* pos)
{assert(pplist);if (pos *pplist){SListPopFront(pplist);}else{SLTNode* cur *pplist;while (cur-next ! pos){cur cur-next;}cur-next pos-next;free(pos);}
}销毁链表 销毁只需要遍历释放即可。 // 单链表的销毁
void SListDestroy(SLTNode* plist)
{assert(plist);SLTNode* cur plist;while (cur){SLTNode* pur cur;cur cur-next;free(pur);}
}到这里对于单链表的增删查改已经讲的差不多了我们的查找可以充当改找到那个节点直接修改date即可。 今天的分享就到这里结束了感谢大家的支持和关注。
