iis 发布网站 500,打开百度网站建设,论坛网站备案,建邺区建设局网站找往期文章包括但不限于本期文章中不懂的知识点#xff1a; 个人主页#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏#xff1a;数据结构 目录
双链表的实现
初始化双链表
在双链表中尾插数据
在双链表中尾删数据
在双链表中头插数据
在双链表中头删数据
在双… 找往期文章包括但不限于本期文章中不懂的知识点 个人主页我要学编程(ಥ_ಥ)-CSDN博客 所属专栏数据结构 目录
双链表的实现
初始化双链表
在双链表中尾插数据
在双链表中尾删数据
在双链表中头插数据
在双链表中头删数据
在双链表中的指定位置之后插入数据
在双链表中删除指定位置的数据
在双链表中查找指定位置
销毁双链表
双链表源码 学习完单链表后就要开始学习链表中最重要的双链表了。
双链表是双向带头循环链表。与单链表是恰恰相反。
接下来就用双链表来实现一系列增删查改的功能。
双链表的实现 在创建双链表之前还得要做一些提起准备。创建三个文件List.h List.c test.c 前面两个是实现双链表的后面的 test.c 文件是测试双链表的各种功能。同样链表是由一个一个的节点组成的。我们就得由节点的结构。
创建节点
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next; //指针保存下⼀个节点的地址struct ListNode* prev; //指针保存前⼀个节点的地址LTDataType data;
}LTNode;
初始化双链表
因为双链表带头因此我们就得创建一个哨兵位。这个函数也可以叫做初始化函数。
//初始化
void LTInit(LTNode** pphead)//注意这里需要改变哨兵位因此用二级指针接收
{//创建一个新的节点LTNode* phead (LTNode*)malloc(sizeof(LTNode));if (phead NULL){perror(malloc:);exit(1);}//把哨兵位的数据初始化为-1(无效数据)后驱指针指向自己前驱指针指向自己*pphead phead;(*pphead)-data -1;(*pphead)-next (*pphead)-prev *pphead;
}只要是增加节点就会有重复的代码因此我们分装成一个函数并且我们在初始化函数也可以传我们想要设置的无效数据。
//增加节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc:);exit(1);}newnode-data x;newnode-next newnode-prev newnode;return newnode;
}//初始化
void LTInit(LTNode** pphead)
{*pphead LTBuyNode(-1);
}在双链表中尾插数据
情况一链表中只有哨兵位 情况二链表中不止有哨兵位
我们要尾插数据就是要d3的next指针的指向还要改变head的prev指针的指向。此外还得把新增加的节点prev指针指向d3next指向head。 不能改变顺序的原因如果改变了就先把哨兵位的指向改变了后面我们就找不到原链表的尾节点了除非能把原链表的尾节点的地址提前存起来。
//尾插数据
void LTPushBack(LTNode* phead, LTDataType x)//哨兵位已经确定不再改变因此用一级指针
{assert(phead);//链表不能为空LTNode* newnode LTBuyNode(x);//开始尾插节点 //链表中只有哨兵位if (phead-next phead){//先把新节点安排好newnode-next phead;newnode-prev phead;//哨兵位phead-next newnode;phead-prev newnode;}else{//先把新节点安排好newnode-next phead;newnode-prev phead-prev;//头节点phead 尾节点phead-prev 新节点newnodephead-prev-next newnode;phead-prev newnode;}
}写完之后还得测试一下我们所写的代码是否正确可以用打印函数来判断看看结果是否和我们的预期一样。
//打印数据
void LTPrint(LTNode* phead)
{//遍历寻找LTNode* pcur phead-next;//头节点的数据是无效的因此就不需要打印//因为是循环的所以不能用空指针来判断要看看是否指向的哨兵位while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}
在双链表中尾删数据
情况一链表中由多个有效数据 情况二链表中只有一个有效数据 //尾删数据
void LTPopBack(LTNode* phead)
{assert(phead phead-next ! phead);//链表不能为空并且链表中不能没有有效元素if (phead-next-next phead)//只有一个有效数据{LTNode* freenode phead-next;free(freenode);phead-next phead;phead-prev phead;}else{phead-prev-prev-next phead;LTNode* freenode phead-prev;phead-prev phead-prev-prev;free(freenode);freenode NULL;}
}其实上面的写法可以简化为
//尾删数据
void LTPopBack(LTNode* phead)
{assert(phead phead-next ! phead);//链表不能为空并且链表中不能没有有效元素phead-prev-prev-next phead;LTNode* freenode phead-prev;phead-prev phead-prev-prev;free(freenode);freenode NULL;
}
也就是说不管链表的有效元素的个数有多少都不影响。把特殊情况带入这个简化版里判断就可以了。
在双链表中头插数据
情况一链表中不止有哨兵位 之所以在哨兵位的前面插入数据叫作尾插是因为双链表是循环的当遍历到d3后就会找到前面的节点这就是在尾部因此也叫作尾插。
同样顺序不能变的原因也是因为顺序一旦改变先把phead的next指向给改变了就找不到了要更改的数据了。
情况二链表中只有哨兵位 //头插数据
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);if (phead-next phead)//只有哨兵位{newnode-next phead;newnode-prev phead;phead-next newnode;phead-prev newnode;}else{//先安排新节点newnode-next phead-next;newnode-prev phead;//头节点phead 尾节点相较于新节点phead-prev 新节点newnodephead-next-prev newnode;phead-next newnode;}
}
这个头插也是可以简化的
//头插数据
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//先安排新节点newnode-next phead-next;newnode-prev phead;//头节点phead 尾节点相较于新节点phead-prev 新节点newnodephead-next-prev newnode;phead-next newnode;
}
简化判断的方法就是把特殊情况带入进去看看能否成功。
在双链表中头删数据 //头删数据
void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);//链表不为空并且链表的有效数据不能为空phead-next-next-prev phead;LTNode* freenode phead-next;phead-next phead-next-next;free(freenode);freenode NULL;
}
在双链表中的指定位置之后插入数据
情况一pos是哨兵位 情况二pos是中间位置 情况三pos是尾节点 上面的代码不管是在哪个位置都满足。
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//先安排好新节点newnode-prev pos;newnode-next pos-next;pos-next newnode;pos-next-prev newnode;
}
在双链表中删除指定位置的数据 情况一pos在中间位置 情况二pos在结尾位置 注意这个指定位置不能是哨兵位。
//在pos位置删除数据
void LTErase(LTNode* pos)
{assert(pos);pos-next-prev pos-prev;pos-prev-next pos-next;free(pos);
}
在双链表中查找指定位置
这个也比较简单就是直接遍历整个双链表如果没找到就返回NULL找到就返回这个地址。
//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead phead-next ! phead);//链表不能为空并且链表不能只有哨兵位LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}
销毁双链表
就是把链表中的节点一个一个的释放空间就行了。
//销毁链表
void LTDestroy(LTNode* phead)
{assert(phead);//就是节点一个一个的销毁LTNode* pcur phead-next;while (pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}free(pcur);pcur NULL;
}
综合上面的代码来看还有一个地方有点小瑕疵就是初始化链表时我们用的是二级指针为了保持接口一致性我们要用一级指针或者不传参数。
//初始化
LTNode* LTInit()
{LTNode* pplist LTBuyNode(-1);return pplist;
}双链表源码
下面就是双链表完整的源码
List.c
#include List.h//增加节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc:);exit(1);}newnode-data x;newnode-next newnode-prev newnode;return newnode;
}//初始化
LTNode* LTInit()
{LTNode* pplist LTBuyNode(-1);return pplist;
}//尾插数据
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//开始尾插节点 //链表中只有哨兵位if (phead-next phead){//先把新节点安排好newnode-next phead;newnode-prev phead;//哨兵位phead-next newnode;phead-prev newnode;}else{//先把新节点安排好newnode-next phead;newnode-prev phead-prev;//头节点phead 尾节点phead-prev 新节点newnodephead-prev-next newnode;phead-prev newnode;}
}//打印数据
void LTPrint(LTNode* phead)
{//遍历寻找LTNode* pcur phead-next;//头节点的数据是无效的因此就不需要打印//因为是循环的所以不能用空指针来判断要看看是否指向的哨兵位while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}//尾删数据
void LTPopBack(LTNode* phead)
{assert(phead phead-next ! phead);//链表不能为空并且链表中不能没有有效元素phead-prev-prev-next phead;LTNode* freenode phead-prev;phead-prev phead-prev-prev;free(freenode);freenode NULL;
}//头插数据
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//先安排新节点newnode-next phead-next;newnode-prev phead;//头节点phead 尾节点相较于新节点phead-prev 新节点newnodephead-next-prev newnode;phead-next newnode;
}//头删数据
void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);//链表不为空并且链表的有效数据不能为空phead-next-next-prev phead;LTNode* freenode phead-next;phead-next phead-next-next;free(freenode);freenode NULL;
}//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//先安排好新节点newnode-prev pos;newnode-next pos-next;pos-next newnode;pos-next-prev newnode;
}//在pos位置删除数据
void LTErase(LTNode* pos)
{assert(pos);pos-next-prev pos-prev;pos-prev-next pos-next;free(pos);pos NULL;
}//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead phead-next ! phead);//链表不能为空并且链表不能只有哨兵位LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}//销毁链表
void LTDestroy(LTNode* phead)
{assert(phead);//就是节点一个一个的销毁LTNode* pcur phead-next;while (pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}free(pcur);pcur NULL;
}
List.h
#include stdio.h
#include assert.h
#include stdlib.htypedef int LTDataType;typedef struct ListNode
{struct ListNode* next; //指针保存下⼀个节点的地址struct ListNode* prev; //指针保存前⼀个节点的地址LTDataType data;
}LTNode;//初始化
LTNode * LTInit();//销毁链表
void LTDestroy(LTNode* phead);//打印数据
void LTPrint(LTNode* phead);//尾插数据
void LTPushBack(LTNode* phead, LTDataType x);//尾删数据
void LTPopBack(LTNode* phead);//头插数据
void LTPushFront(LTNode* phead, LTDataType x);//头删数据
void LTPopFront(LTNode* phead);//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x);//在pos位置删除数据
void LTErase(LTNode* pos);//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x);
好啦本期数据结构双链表的学习就到此为止啦我们下一期再一起学习吧
