< 返回新闻公共列表
【数据结构】- 几个步骤教你认识并实现一个链表之带头(哨兵位)双向循环链表(上)
发布时间：2023-06-28 13:00:17
一、带头双向循环链表
==带头双向循环链表：==结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。
二、带头双向循环链表结构图：
三、带头双向循环链表代码实现：
3.1头插：
void LTPushFornt(LTNode* phead, LTDataType x) { LTNode* newnode = BuyLTNode(x); LTNode* cur = phead->next; newnode->prev = phead; phead->next = newnode; newnode->next = cur; cur->prev = newnode; }
3.1.1头插流程图
第一种写法如上代码：
第二种写法如下图：
最后最重要的一点：
3.1.2 相较于无头单向非循环链表：
3.2尾插
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
3.2.1尾插流程图
3.3全部代码：
//List.h #define _CRT_SECURE_NO_WARNINGS 1 #include
#include #include typedef int LTDataType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }LTNode; LTNode* LTInit(); void LTPushFront(LTNode* phead, LTDataType x); void LTPushBack(LTNode* phead, LTDataType x); void LTNodePrint(LTNode* phead); //List.c #define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; } LTNode* LTInit() { LTNode* phead = BuyLTNode(-1); phead->next = phead; phead->prev = phead; return phead; } void LTNodePrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; printf("哨兵位<==>"); while (cur != phead) { printf("%d<==>", cur->data); cur = cur->next; } printf("\n"); } void LTPushFront(LTNode* phead, LTDataType x) { LTNode* newnode = BuyLTNode(x); LTNode* cur = phead->next; newnode->prev = phead; phead->next = newnode; newnode->next = cur; cur->prev = newnode; } void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } //Test.c #define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" void TestList() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTNodePrint(plist); } int main() { TestList(); return 0; }
总结
Ending,今天的链表之带头双向循环链表(上)的内容就到此结束啦~，如果后续想了解更多，就请关注我吧。
