wordpress仿站插件,wordpress下载附件,电子商城采购平台官网,衡水电子商务网站建设前言#xff1a;小伙伴们好久不见啦#xff0c;上篇文章我们一起学习了数据结构线性表其一的单链表#xff0c;了解了单链表的不少好处#xff0c;但是不可能有完美的数据结构#xff0c;就算是单链表#xff0c;也会有很多缺点。
那么今天这篇文章#xff0c;我们就来…前言小伙伴们好久不见啦上篇文章我们一起学习了数据结构线性表其一的单链表了解了单链表的不少好处但是不可能有完美的数据结构就算是单链表也会有很多缺点。
那么今天这篇文章我们就来学习单链表的promax版本——带头双向循环链表。 一.什么是带头双向循环链表
关于带头双向循环链表我们将它拆分为带头、双向、循环、链表四个部分其中链表我们已经知道是怎么回事了那我们就来一起结合下图分析前三个概念。 1.带头 所谓带头也就是在链表的开头处有一个不存放任何数据的头节点我们通常称其为“哨兵位”。 那么哨兵位存在的意义是什么呢 它可以帮助我们更方便的进行对链表的各种操作。具体好在哪里我们结合后边实现链表的各种操作来进行展示。 2.双向 我们前边学习过的单链表它的每个节点之间只有一条链子相连并且只能由前一个节点去找到后一个节点。 而双向链表也就是两个节点之间有两条链子相连不仅能从前一个找到后一个也能从后一个去找到前一个。 3.循环 循环顾名思义就是将链表的头尾也进行连接形成一个逻辑意义上的环形链表。 那么理解完带头双向循环链表的含义之后我就就一起来看看到底来如何实现它吧。
此后我们将该链表的名字简化为双链表。 二.双链表的实现
1.双链表的定义
typedef int DLLDataType;
//定义双链表
typedef struct DLinkList
{DLLDataType data;struct DLinkList* prev;//指向前一个节点struct DLinkList* next;//指向后一个节点
}DLLNode;
双链表是在单链表的基础上比它多出一个prev指针去指向前一个节点还是比较容易理解的。 2.双链表的初始化
//初始化双链表
DLLNode* DLinkListInit()
{DLLNode* phead (DLLNode*)malloc(sizeof(DLLNode));if (phead NULL){perror(DLinkListInit-malloc);}phead-next phead;phead-prev phead;return phead;
}
双链表的初始化需要先造出哨兵位考虑到链表为空并且链表还要循环所以我们将哨兵位的prev和next都指向自己。 DLLNode* dll DLinkListInit(); 创建一个双链表我们习惯于运用上述方式。
因为如果用单链表的初始化方式我们需要用到二级指针但是我们后续双链表各种功能的操作完全不和二级指针沾边。
所以为了让我们的双链表全部由一级指针完成选择采用接收函数返回值的方式来创建双链表。 3.双链表节点的创建
DLLNode* CreateNewNode(DLLDataType x)
{DLLNode* newnode (DLLNode*)malloc(sizeof(DLLNode));if (newnode NULL){perror(CreateNewNode-malloc);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}
双链表创建新节点就和单链表差不多啦要注意的就是不要忘记两个指针置空防止出现野指针。
这样我们就实现了一个基本的双链表框架下面来实现双链表的各种基础操作。 三.双链表的操作
1.双链表的打印
那么为了方便其他功能的测试我们还是先来实现双链表的打印功能
void DLinkListPrint(DLLNode* phead)
{assert(phead);DLLNode* cur phead-next;printf(phead);while (cur ! phead){printf(%d, cur-data);cur cur-next;}printf(phead\n);
}
我们还是严格的进行一下assert断言如果phead为空就说明双链表不存在。
这里要注意两点 1.cur为什么是phead-next 不难理解我们在双链表初始化的时候给到dll的返回值是哨兵位但是哨兵位不存储数据所以要从哨兵位的下一个节点开始。 2.while循环的判断条件 因为我们是一个可循环的链表所以并不存在cur为空的情况但是cur最后会重新指向哨兵位所以当cur phead时说明我们已经将双链表遍历一遍了。 至于printf函数的内容只是为了好看哈哈展示一下 这样能够让大家更形象的认识双链表。 2.双链表的尾插
双链表的尾插相较于单链表有什么优势呢
单链表想尾插首先要进行循环找尾时间复杂度就高了但是双链表就好办因为哨兵位的前一个节点就是尾也就是phead-prev尾找到之后就好办了
//尾插
void DLinkListPushBack(DLLNode* phead, DLLDataType x)
{assert(phead);DLLNode* newnode CreateNewNode(x);DLLNode* tail phead-prev;tail-next newnode;newnode-next phead;newnode-prev tail;phead-prev newnode;
}
用tail代替尾接下来的一顿操作就是 旧尾的next指向新尾 新尾的next指向哨兵位 新尾的prev指向旧尾 哨兵位的prev指向新尾 看起来很简单但是我们知道单链表必须得考虑一下链表是否为空的特例但是双链表不需要。
因为双链表如果为空那就只有哨兵位哨兵位自己的头尾相连带入上述代码操作之后不会有任何错误。 3.双链表的尾删
尾删就更简单了只需要找到尾再通过尾找到尾的前一个节点再让此节点和哨兵位互连再将尾free即可
//尾删
void DLinkListPopBack(DLLNode* phead)
{assert(phead);assert(phead-next ! phead);DLLNode* tail phead-prev;DLLNode* tailprev tail-prev;phead-prev tailprev;tailprev-next phead;free(tail);tail NULL;
}
尾删要考虑只有一个节点的特例吗依然不用因为进行一顿操作之后还是让哨兵位自己头尾相连。
但是尾删要考虑空链表的情况因为如果链表为空free的就是哨兵位了哨兵位一旦不存在了我们就无法进行后续的操作了。所以要多进行一次assert断言。
到这里小伙伴们是否已经感受到了哨兵位以及双链表的强势之处啦。 4.双链表的头插
头插就和尾插差不多了这里我直接给出代码希望小伙伴们可以自己理解掌握哦。
//头插
void DLinkListPushFront(DLLNode* phead, DLLDataType x)
{assert(phead);DLLNode* head phead-next;DLLNode* newnode CreateNewNode(x);phead-next newnode;newnode-next head;head-prev newnode;newnode-prev phead;
} 5.双链表的头删
头删也和尾删类似要考虑空链表的情况
//头删
void DLinkListPopFront(DLLNode* phead)
{assert(phead);assert(phead-next ! phead);DLLNode* head phead-next;DLLNode* headnext head-next;phead-next headnext;headnext-prev phead;free(head);head NULL;
} 6.双链表的查找
如果是查找的话那我们还得老老实实的从头遍历
//查找
DLLNode* DLinkListFind(DLLNode* phead,DLLDataType x)
{assert(phead);DLLNode* cur phead-next;while(cur){if (cur-data x)return cur;elsecur cur-next;}return NULL;
}
还是要注意这里while循环的条件和双链表的打印一样。 7.双链表的任意插
双链表的任意位置的插入依然要和查找连用因为只有查找才能得到pos位置的地址。
但是我们这里规定一下任意插就是pos位置前插。
比如说我想在表的第四个位置插入新数据那我就要把第四个位置空出来让原来的第四位以及他后边的都老老实实往后退。
这样一来我们就需要找到pos节点的前一个节点这样方便我们进行操作
//pos位置插
void DLinkListInsert(DLLNode* pos, DLLDataType x)
{assert(pos);DLLNode* newnode CreateNewNode(x);DLLNode* posprev pos-prev;posprev-next newnode;newnode-prev posprev;pos-prev newnode;newnode-next pos;
} 8.双链表的任意删
任意删的形式就和任意插差不多只是还需要另外记录pos的下一个节点
//pos位置删
void DLinkListEease(DLLNode* pos)
{assert(pos);DLLNode* posprev pos-prev;DLLNode* posnext pos-next;posprev-next posnext;posnext-prev posprev;free(pos);pos NULL;
} 9.双链表的修改
想要修改数据还是要用查找操作来找到要修改pos位置的地址而后就简单了
//pos位置改
void DLinkListAmend(DLLNode* pos, DLLDataType x)
{assert(pos);pos-data x;
}
直接修改data即可。 10.双链表的销毁
双链表的销毁同样是需要遍历对个个空间进行free值得注意的是哨兵位也需要销毁
//销毁
void DLinkListDestroy(DLLNode* phead)
{assert(phead);DLLNode* cur phead-next;while (cur ! phead){DLLNode* next cur-next;free(cur);cur next;}free(phead);phead NULL;
} 四.完整代码展示
1.DLinkList.h
#include stdio.h
#include assert.h
#include stdlib.htypedef int DLLDataType;
//定义双链表
typedef struct DLinkList
{DLLDataType data;struct DLinkList* prev;struct DLinkList* next;
}DLLNode;//初始化双链表
DLLNode* DLinkListInit();
//打印双链表
void DLinkListPrint(DLLNode* phead);
//创造新节点
DLLNode* CreateNewNode(DLLDataType x);
//尾插
void DLinkListPushBack(DLLNode* phead, DLLDataType x);
//尾删
void DLinkListPopBack(DLLNode* phead);
//头插
void DLinkListPushFront(DLLNode* phead, DLLDataType x);
//头删
void DLinkListPopFront(DLLNode* phead);
//查找
DLLNode* DLinkListFind(DLLNode* phead,DLLDataType x);
//pos位置插
void DLinkListInsert(DLLNode* pos, DLLDataType x);
//pos位置删
void DLinkListEease(DLLNode* pos);
//pos位置改
void DLinkListAmend(DLLNode* pos,DLLDataType x);
//销毁
void DLinkListDestroy(DLLNode* phead); 2.DLinkList.c
#include DLinkList.h
//初始化双链表
DLLNode* DLinkListInit()
{DLLNode* phead (DLLNode*)malloc(sizeof(DLLNode));if (phead NULL){perror(DLinkListInit-malloc);}phead-next phead;phead-prev phead;return phead;
}
//打印双链表
void DLinkListPrint(DLLNode* phead)
{assert(phead);DLLNode* cur phead-next;printf(phead);while (cur ! phead){printf(%d, cur-data);cur cur-next;}printf(phead\n);
}
//创造新节点
DLLNode* CreateNewNode(DLLDataType x)
{DLLNode* newnode (DLLNode*)malloc(sizeof(DLLNode));if (newnode NULL){perror(CreateNewNode-malloc);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}
//尾插
void DLinkListPushBack(DLLNode* phead, DLLDataType x)
{assert(phead);DLLNode* newnode CreateNewNode(x);DLLNode* tail phead-prev;tail-next newnode;newnode-next phead;newnode-prev tail;phead-prev newnode;
}
//尾删
void DLinkListPopBack(DLLNode* phead)
{assert(phead);DLLNode* tail phead-prev;DLLNode* tailprev tail-prev;phead-prev tailprev;tailprev-next phead;free(tail);tail NULL;
}
//头插
void DLinkListPushFront(DLLNode* phead, DLLDataType x)
{assert(phead);DLLNode* head phead-next;DLLNode* newnode CreateNewNode(x);phead-next newnode;newnode-next head;head-prev newnode;newnode-prev phead;
}
//头删
void DLinkListPopFront(DLLNode* phead)
{assert(phead);DLLNode* head phead-next;DLLNode* headnext head-next;phead-next headnext;headnext-prev phead;free(head);head NULL;
}
//查找
DLLNode* DLinkListFind(DLLNode* phead,DLLDataType x)
{assert(phead);DLLNode* cur phead-next;while(cur){if (cur-data x)return cur;elsecur cur-next;}return NULL;
}
//pos位置插
void DLinkListInsert(DLLNode* pos, DLLDataType x)
{assert(pos);DLLNode* newnode CreateNewNode(x);DLLNode* posprev pos-prev;posprev-next newnode;newnode-prev posprev;pos-prev newnode;newnode-next pos;
}
//pos位置删
void DLinkListEease(DLLNode* pos)
{assert(pos);DLLNode* posprev pos-prev;DLLNode* posnext pos-next;posprev-next posnext;posnext-prev posprev;free(pos);pos NULL;
}
//pos位置改
void DLinkListAmend(DLLNode* pos, DLLDataType x)
{assert(pos);pos-data x;
}
//销毁
void DLinkListDestroy(DLLNode* phead)
{assert(phead);DLLNode* cur phead-next;while (cur ! phead){DLLNode* next cur-next;free(cur);cur next;}free(phead);phead NULL;
}
测试代码大家自行进行测试这里就不在进行展示啦。 五.总结
双链表相比于单链表还是有很大优势的建议大家在学习过单链表的基础上完全靠自己的写一写双链表这将会让你对链表知识的掌握更上一层楼
最后还是提醒大家不要忘记一键三连哦
我们下期再见啦
