三网合一网站开源,个人建网站大概多少钱,网站域名如何更换,php网站案例文章目录 关于双向链表双向链表的初始化双向链表的打印双向链表方法调用 - 尾删为例双向链表的查找 - 指定位置之后插入为例双向链表结束 - 链表的销毁小结及整体代码实现 关于双向链表
首先链表有8种基本分法
其中在笔者之前文章种详细介绍的 单链表 是不带头单项不循环链表… 文章目录 关于双向链表双向链表的初始化双向链表的打印双向链表方法调用 - 尾删为例双向链表的查找 - 指定位置之后插入为例双向链表结束 - 链表的销毁小结及整体代码实现 关于双向链表
首先链表有8种基本分法
其中在笔者之前文章种详细介绍的 单链表 是不带头单项不循环链表 而今天笔者要介绍的就是 带头双向循环链表 双向链表
我们可以把链表理解为下图 所以我们双向链表的结构往往是这样的 即
typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{int data;struct ListNode* next;struct ListNode* prev;
}LTNode;双向链表的初始化
第一步我们需要进行双向链表的初始化双向链表的初始化需要注意的一个问题是传进去的参数是一级指针还是二级指针这本应该后面大致写完了再讨论但是这里提前说了
在笔者后面的方法中例如尾插头插尾删头删等都是用一级指针这是因为双向链表有一个好处我们存在一个哨兵位这个节点是初始化时创立的不需要改变同时有存储着前后节点的地址只需要通过成员名调用即可这里呈现一下会出现的方法参数
//打印
void LTPrint(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataType x);//插入数据之前链表必须初始化到只有一个头结点的情况
//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos之后插入数据
void LTInsert(LTNode* pos, LTDataType x);笔者这里据大多数关于双向链表的地址传参都是一级指针这在一定程度上保证了接口的一致性为后来调用双向链表数据结构者降低了理解成本这也就是我们在设计程序时需要注意的一点
笔者这里通过二级指针传参和无传参的方法各创建了一个初始化方法 大家可以看到两种方法连语句都基本一致但是后者明显会比前者好因为在以后不论是我们还是其他人通过一览所有的方法名后不需要刻意去记初始化需要传参二级指针直接空着使用就行了
//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc newnode);exit(1);}newnode-data x;newnode-next newnode-prev newnode;//指向自己return newnode;
}//初始化1
void LTInit(LTNode** pphead)
{//该双向链表创建一个哨兵位*pphead LTBuyNode(-1);
}
//初始化2
LTNode* newLTInit()
{return LTBuyNode(-1);
}双向链表的打印
双向链表的打印比单链表好理解太多了 因为存在一个无意义的 哨兵位 用来记录开头链接末尾 所以只需要新创建一个新的节点用来帮忙定位当前位置如果这个节点的值跟 哨兵位 一样便退出
代码如下
//打印
void LTPrint(LTNode* phead)
{LTNode* pcur phead-next;while (pcur ! phead){printf(%d-,pcur-data);pcur pcur-next;}printf(\n);
}双向链表方法调用 - 尾删为例
大家可以先看一下下图我们在双向链表的末尾放上新节点 为了保证双向链表在使用时不发生意外 我们先将 newnode 的 prev 和 next 对接好 d3 和 头节点phead 这样做只是给新的节点的前后向确定好不影响原来的双向链表
再将 d3 的 next 对准 newnode phead 的 prev 对准 newnode
下面代码呈现
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);newnode-prev phead-prev;newnode-next phead;phead-prev-next newnode;phead-prev newnode;
}双向链表的查找 - 指定位置之后插入为例 指定位置之后插入除了插入这个重要点就是指定位置这个大头了那么我们该如何实现找到指定位置呢
同样因为 哨兵位 的存在我们新定义节点来一个一个对比下去知道等于 哨兵位 为止代表整个双向链表中都没有这个要查找的数据
即
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x)return pcur;pcur pcur-next;}return NULL;
}既然知道如何找到指定位置那么接下来就是插入了 我们通过指定位置的节点信息按照前面尾插的方法就行了也是很简单的
//在pos之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);newnode-next pos-next-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}双向链表结束 - 链表的销毁
因为我们前面有提到为保证接口的一致性我们同意设定为一级指针但这样我们能做的就是将除 哨兵位 以外的节点全部置为空但是外部所创建的节点即我们一开始所初始化的点无法在内部置为空所以出去后仍然需要置为空
即
//销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* pcur phead;while (pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}free(phead);phead NULL;pcur NULL;//这点无所谓跳出方法就会为空
}
这是内部的销毁出去后在置为空一次即
LTDestory(plist);
plist NULL;小结及整体代码实现
有一说一双向链表真的很好理解而且写方法时往往不用循环就能很容易解出来比单链表和数组方便许多大家如果想要自己实现双向链表尽量没完成一次方法时调试检验一下方便找到错误
下面为大家展现一下笔者的代码
“List.h”
#pragma once#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)#includestdio.h
#includestdlib.h
#includeassert.htypedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{int data;struct ListNode* next;struct ListNode* prev;
}LTNode;//声明双向链表中提供的方法
//尽量都用一级指针降低调用方的理解成本保持接口的一致性
//初始化
//void LTInit(LTNode** pphead);
LTNode* newLTInit();//打印
void LTPrint(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataType x);//插入数据之前链表必须初始化到只有一个头结点的情况
//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos之后插入数据
void LTInsert(LTNode* pos, LTDataType x);“List.c”
#includeList.h//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc newnode);exit(1);}newnode-data x;newnode-next newnode-prev newnode;//指向自己return newnode;
}//初始化
void LTInit(LTNode** pphead)
{//该双向链表创建一个哨兵位*pphead LTBuyNode(-1);
}LTNode* newLTInit()
{return LTBuyNode(-1);
}//销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* pcur phead;while (pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}free(phead);phead NULL;pcur NULL;//这点无所谓跳出方法就会为空
}//打印
void LTPrint(LTNode* phead)
{LTNode* pcur phead-next;while (pcur ! phead){printf(%d-,pcur-data);pcur pcur-next;}printf(\n);
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);newnode-prev phead-prev;newnode-next phead;phead-prev-next newnode;phead-prev newnode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);newnode-prev phead;newnode-next phead-next;phead-next-prev newnode;phead-next newnode;
}//尾删
void LTPopBack(LTNode* phead)
{//链表必须有效且不为空assert(phead phead-next ! phead);phead-prev-prev-next phead;phead-prev phead-prev-prev;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);phead-next-next-prev phead;phead-next phead-next-next;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x)return pcur;pcur pcur-next;}return NULL;
}//在pos之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);newnode-next pos-next-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}
//在pos之前插入数据
void LTInsertAfter(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);newnode-next pos;newnode-prev pos-prev;pos-prev-next newnode;pos-prev newnode;
}
//删除pos节点
void LTErase(LTNode* pos)
{assert(pos);pos-next-prev pos-prev;pos-prev-next pos-next;free(pos);pos NULL;
}测试文件就不展示了没有什么参考价值能够独自理解并写出上述方法名一个简简单单的调试自然不在话下
