• 售前

  • 售后

热门帖子
入门百科

一篇解双链表(0底子看)(C语言)《数据布局与算法》

[复制链接]
乔微博 显示全部楼层 发表于 2022-1-16 21:38:10 |阅读模式 打印 上一主题 下一主题
目次
序言
带头双向循环链表
1. 概念
2. 效果展示图
3. 接口实现 
3.01. 本文章要实现的接口
​3.02. 双链表的实现
3.03. 双链表的初始化
3.04. 打印链表
3.05. 动态申请一个节点
3.06. 头插
3.07. 尾插
3.08. 头删
3.09. 尾删
3.10. 查某个值,返回地点
3.11. 某个位置前插入数据 
3.12. 删除某个位置数据
3.13. 改某个值
3.14. 烧毁 
总结
4. 源代码 
test.c
List.h
List.c 

  谁都不能拦截你成为更精良的人。     
  序言

   起首本文是和上一篇单链表有关联哈,上篇文章已经具体阐明确链表的概念和分类,这里就不外多赘述了,就简朴阐明一下哈,链接在下面。一篇解单链表(0底子看)(C语言)《数据布局与算法》_原来45的博客-CSDN博客
  上文我们讲到了链表最告急的两个分类,一个是单向不带头不循环,本篇文章就讲另一个告急的带头双向循环链表哈,废话不多说,直接看代码。
  对了,这里附上作者的qq:2777137742。要是有什么标题可以在qq上面问我哈,大概文章有错误的地方,等候和各人共同讨论,由于caogenba的消息有大概会遗漏哈,末了感谢你的支持。
  带头双向循环链表

1. 概念


     带头双向循环链表:布局最复杂,一样寻常用在单独存储数据。现实中使用的链表数据布局,都      是带头双向循环链表。别的这个布局固然布局复杂,但是使用代码实现以后会发现布局会带      来很多上风,实现反而简朴了,反面我们代码实现了就知道了。           这里我们来渐渐发表上文说到的实现更简朴,以及单链表的缺点。缺点就直接说了,我们可以很直观得发现单链表的两个很大的缺点,一个是尾插尾删等都是必要遍历也就是说时间复杂度是O(N),但是双链表对应的都是O(1),服从之高。另一个缺点就是单链表不能找到本身的上一个节点,这都是很大的缺陷。然后我们接着看双链表实现的上风。 
  
2. 效果展示图


3. 接口实现 

   还是老话,对于接口的实现我们起首是要知道要实现什么,本文是对于双链表的根本使用,以是就只实现序次表的增删查改,尚有特定位置前插入删除特定位置值等固然代码也不肯定要作者这么写,这里只是提供一种思绪,废话不多说,看代码。  
  3.01. 本文章要实现的接口




3.02. 双链表的实现


   这是定名是ListNode是与c++对应的,各人也可以和单链表SListNode对应取名DListnode,但是作者为了养成一个好的风俗就取名为了ListNode哈。 
  3.03. 双链表的初始化


   注意这里初始化是本身指向本身,由于是循环,然后本篇文章不用二级指针(不消传地点),这里就用了一个返回值。
  3.04. 打印链表


3.05. 动态申请一个节点


3.06. 头插


3.07. 尾插


3.08. 头删


3.09. 尾删


3.10. 查某个值,返回地点


3.11. 某个位置前插入数据 


3.12. 删除某个位置数据


3.13. 改某个值


3.14. 烧毁 


总结

   我们可以发现对于带头双向循环链表的实现不必要像单链表那样要去判定没有大概有一个节点的情况,布局非常之美满,可以使用头结点举行各种变革,实现也非常简朴,而且也不消传地点。
  这里要再表明一下为什么可以不传地点,由于我们的头没有改变,不必要改变头,这个改变指的是我们一开始传的参数plist,他是不停指向我们的头的,是指向没有变,内容可以改变,也就是说plist的前驱prev后继next的指向和date可以变的,这个明确很告急!
  4. 源代码 

test.c

  1. #include"List.h"
  2. int main()
  3. {
  4.         printf("初始化\n");
  5.         ListNode* plist = ListInit();
  6.         printf("头插 1 2 3 并打印\n");
  7.         ListPushFront(plist, 1);
  8.         ListPushFront(plist, 2);
  9.         ListPushFront(plist, 3);
  10.         ListPrint(plist);
  11.         printf("尾插4 5 6 并打印\n");
  12.         ListPushBack(plist, 4);
  13.         ListPushBack(plist, 5);
  14.         ListPushBack(plist, 6);
  15.         ListPrint(plist);
  16.         printf("头删并打印\n");
  17.         ListPopFront(plist);
  18.         ListPrint(plist);
  19.         printf("尾删并打印\n");
  20.         ListPopBack(plist);
  21.         ListPrint(plist);
  22.         printf("1前插入3并打印\n");
  23.         ListNode* pos = ListFind(plist, 1);
  24.         ListInsert(plist, pos, 3);
  25.         ListPrint(plist);
  26.         printf("2前插入8并打印\n");
  27.         pos = ListFind(plist, 2);
  28.         ListInsert(plist, pos, 8);
  29.         ListPrint(plist);
  30.         printf("删除4并打印\n");
  31.         pos = ListFind(plist, 4);
  32.         ListErase(plist, pos);
  33.         ListPrint(plist);
  34.         printf("把1改成9并打印\n");
  35.         ListChange(plist, 1, 9);
  36.         ListPrint(plist);
  37.         printf("销毁链表\n");
  38.         ListDestory(plist);
  39.         return 0;
  40. }
复制代码
List.h

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<stdio.h>
  3. #include<malloc.h>
  4. #include<assert.h>
  5. typedef int ListDateType;
  6. typedef struct ListNode
  7. {
  8.         struct ListNode* prev;
  9.         struct ListNode* next;
  10.         ListDateType date;
  11. }ListNode;
  12. //增删查改
  13. //初始化
  14. ListNode* ListInit();
  15. //销毁
  16. void ListDestory(ListNode* phead);
  17. //得到一个节点
  18. ListNode* BuyListNode(ListDateType x);
  19. //打印
  20. void ListPrint(ListNode* phead);
  21. //头插
  22. void ListPushFront(ListNode* phead, ListDateType x);
  23. //尾插
  24. void ListPushBack(ListNode* phead, ListDateType x);
  25. //头删
  26. void ListPopFront(ListNode* phead);
  27. //尾删
  28. void ListPopBack(ListNode* phead);
  29. //查某个值,返回地址
  30. ListNode* ListFind(ListNode* phead, ListDateType x);
  31. //改某个值
  32. void ListChange(ListNode* phead, ListDateType source, ListDateType destination);
  33. //某个位置前插入数据
  34. void ListInsert(ListNode* phead, ListNode* pos, ListDateType x);
  35. //删除某个位置数据
  36. void ListErase(ListNode* phead, ListNode* pos);
复制代码
List.c 

  1. #include"List.h"
  2. //初始化
  3. ListNode* ListInit()
  4. {
  5.         ListNode* phead = BuyListNode(0);
  6.         phead->prev = phead;
  7.         phead->next = phead;
  8.         phead->date = 0;
  9.         return phead;
  10. }
  11. //得到一个节点
  12. ListNode* BuyListNode(ListDateType x)
  13. {
  14.         ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  15.         newnode->prev = NULL;
  16.         newnode->next = NULL;
  17.         newnode->date = x;
  18.         return newnode;
  19. }
  20. //头插
  21. void ListPushFront(ListNode* phead, ListDateType x)
  22. {
  23.         assert(phead);
  24.         ListNode* newnode = BuyListNode(x);
  25.         ListNode* first = phead->next;
  26.         phead->next = newnode;
  27.         newnode->prev = phead;
  28.         newnode->next = first;
  29.         first->prev = newnode;
  30. }
  31. //尾插
  32. void ListPushBack(ListNode* phead, ListDateType x)
  33. {
  34.         assert(phead);
  35.         ListNode* tail = phead->prev;
  36.         ListNode* newnode = BuyListNode(x);
  37.         phead->prev = newnode;
  38.         newnode->next=phead;
  39.         tail->next = newnode;
  40.         newnode->prev = tail;
  41. }
  42. //打印
  43. void ListPrint(ListNode* phead)
  44. {
  45.         ListNode* cur = phead->next;
  46.         while (cur != phead)
  47.         {
  48.                 printf("%d ", cur->date);
  49.                 cur = cur->next;
  50.         }
  51.         printf("\n");
  52. }
  53. //头删
  54. void ListPopFront(ListNode* phead)
  55. {
  56.         assert(phead);
  57.         //别把头删了
  58.         assert(phead->next != phead);
  59.         ListNode* first = phead->next;
  60.         phead->next = first->next;
  61.         first->next->prev = phead;
  62.         free(first);
  63.         first = NULL;
  64. }
  65. //尾删
  66. void ListPopBack(ListNode* phead)
  67. {
  68.         assert(phead);
  69.         //别把头删了
  70.         assert(phead->next != phead);
  71.         ListNode* tail = phead->prev;
  72.         ListNode* prev = tail->prev;
  73.         prev->next = phead;
  74.         phead->prev = prev;
  75.         free(tail);
  76.         tail = NULL;
  77. }
  78. //查某个值,返回地址
  79. ListNode* ListFind(ListNode* phead, ListDateType x)
  80. {
  81.         assert(phead);
  82.         ListNode* cur = phead->next;
  83.         while (cur != phead)
  84.         {
  85.                 if (cur->date == x)
  86.                 {
  87.                         return cur;
  88.                 }
  89.                 else
  90.                 {
  91.                         cur = cur->next;
  92.                 }
  93.         }
  94.         return NULL;
  95. }
  96. //某个位置前插入数据   
  97. void ListInsert(ListNode* phead, ListNode* pos, ListDateType x)
  98. {
  99.         assert(phead);
  100.         ListNode* newnode = BuyListNode(x);
  101.         ListNode* prev = pos->prev;
  102.        
  103.         prev->next = newnode;
  104.         newnode->prev = prev;
  105.         newnode->next = pos;
  106.         pos->prev = newnode;
  107. }
  108. //删除某个位置数据
  109. void ListErase(ListNode* phead, ListNode* pos)
  110. {
  111.         assert(phead);
  112.         //别把头删了
  113.         assert(phead->next != phead);
  114.         ListNode* prev = pos->prev;
  115.         ListNode* next = pos->next;
  116.         prev->next = next;
  117.         next->prev = prev;
  118.         free(pos);
  119.         pos = NULL;
  120. }
  121. //改某个值
  122. void ListChange(ListNode* phead, ListDateType source, ListDateType destination)
  123. {
  124.         assert(phead);
  125.         ListNode* pos = ListFind(phead, source);
  126.         pos->date = destination;
  127. }
  128. //销毁
  129. void ListDestory(ListNode* phead)
  130. {
  131.         assert(phead);
  132.         ListNode* cur = phead->next;
  133.         ListNode* tail = cur->next;
  134.         while (tail != phead)
  135.         {
  136.                 free(cur);
  137.                 cur = NULL;
  138.                 cur = tail;
  139.                 tail = tail->next;
  140.         }
  141.         free(cur);
  142.         cur = NULL;
  143.         if (cur != tail)
  144.         {
  145.                 free(tail);
  146.                 tail = NULL;
  147.         }
  148. }
复制代码
  本日的内容就到这里了哈!!!
  要是以为作者有一点资助你的话!
  就来一个点赞加关注吧!!!固然订阅是更是梦寐以求!
  赠人玫瑰,手有余香=。=!
  末了的末了感谢各人的观看!!!
  你们的支持是作者写作的最大动力!!!
  下期见哈!!!

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作