C语言手把手带你掌握带头双向循环链表
目录
前言带头双向循环链表的结构代码操作前言
关于链表这一块,写了多篇博客,学习了顺序表、单链表、及其一些练习题
顺序表:传送门:顺序表
单链表:传送门:单链表1 链表2
链表OJ:传送门:链表OJ
今天,我又来水一水博客,介绍关于双链表。
带头双向循环链表的结构
实际上,单链表也存在一个比较大的缺陷:
1.不能从后往前遍历
2.无法找到前驱
除了单链表之外,我们自然还有双向链表,我们要说的就是带头双向循环链表,简单理解为:带头结点的,有两个方向的。循环的。结构图如下:
结构虽然比较复杂,但是极大方便我们找结点,比如可以直接找到尾结点,然后再进入相关的操作。实际代码的操作将会比单链表简单,极为方便,这里不做过多说明,直接上手代码
代码操作
我们直奔主题,进入代码实现的操作,之前的操作如果理解了,那我相信这个对于你来说肯定是不难的。下面直接给出源码:
List.h
#pragma once #include#include #include #include #include typedef int LTDataType; //带头双向循环--最优链表结构,在任意位置插入删除数据都是O(1) typedef struct listNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }ListNode; //初始化 ListNode*ListInit(); //销毁 void ListDestory(ListNode* phead); //打印 void ListPrint(ListNode* phead); //尾插 void ListPushBack(ListNode* phead, LTDataType x); //头插 void ListPushFront(ListNode* phead, LTDataType x); //头删 void ListPopFront(ListNode* phead); //尾删 void ListPopBack(ListNode* phead); ListNode* ListFind(ListNode* phead, LTDataType x); //在pos位置之前插入x void ListInsert(ListNode* pos, LTDataType x); //删除pos位置的值 void ListErase(ListNode* pos);
List.c
#include "List.h" //开辟一个新结点 ListNode* BuyListNode(LTDataType x) { ListNode* newnode =(ListNode*)malloc(sizeof(ListNode)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } //初始化 ListNode* ListInit() { ListNode*phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; } //销毁 void ListDestory(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; } //打印 void ListPrint(ListNode* phead) { ListNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } //尾插 void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); ListNode* tail = phead->prev; ListNode* newnode = BuyListNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } //头插 void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode* first = phead->next; ListNode* newnode = BuyListNode(x); newnode->next = first; first->prev = newnode; phead->next = newnode; newnode->prev = phead; } //头删 void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* first = phead->next; ListNode* second = first->next; phead->next = second; second->prev = phead; free(first); first = NULL; } //尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev; prev->next = phead; phead->prev = prev; free(tail); tail = NULL; } ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos位置之前插入x void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } //删除pos位置的值 void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); }
Test.c
#include "List.h" void TestList1() { ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListPushFront(plist, 0); ListPushFront(plist, -1); ListPrint(plist); ListPopFront(plist); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); ListPopBack(plist); ListPrint(plist); } void TestList2() { ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListNode* pos = ListFind(plist, 3); if (pos) { pos->data *= 10; printf("找到了,并且*10\n"); } else { printf("没找到\n"); } ListPrint(plist); ListInsert(pos, 300); ListPrint(plist); ListErase(pos); ListPrint(plist); } int main() { TestList2(); return 0; }
到此这篇关于C语言手把手带你掌握带头双向循环链表的文章就介绍到这了,更多相关C语言带头双向循环链表内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
X 关闭
X 关闭
- 15G资费不大降!三大运营商谁提供的5G网速最快?中国信通院给出答案
- 2联想拯救者Y70发布最新预告:售价2970元起 迄今最便宜的骁龙8+旗舰
- 3亚马逊开始大规模推广掌纹支付技术 顾客可使用“挥手付”结账
- 4现代和起亚上半年出口20万辆新能源汽车同比增长30.6%
- 5如何让居民5分钟使用到各种设施?沙特“线性城市”来了
- 6AMD实现连续8个季度的增长 季度营收首次突破60亿美元利润更是翻倍
- 7转转集团发布2022年二季度手机行情报告:二手市场“飘香”
- 8充电宝100Wh等于多少毫安?铁路旅客禁止、限制携带和托运物品目录
- 9好消息!京东与腾讯续签三年战略合作协议 加强技术创新与供应链服务
- 10名创优品拟通过香港IPO全球发售4100万股 全球发售所得款项有什么用处?