双向链表的存储设计与实现(C语言版本)

╰半夏微凉° 2022-05-24 01:06 191阅读 0赞

双向链表的插入操作：

70

双向链表的删除操作：

70 1 

  1. //DLinkList.h
  2. #ifndef _DLINKLIST_H_
  3. #define _DLINKLIST_H_
  5. //双向链表的存储结构
  6. //结点中包含后继结点的地址的指针域可以理解为指向下一个结构体(结点)
  7. //(这里不包含数据域,是实现了 链表的api(链表的算法) 和 具体的数据分离)
  8. typedef struct _tag_DLinkListNode
  9. {
  10.     struct _tag_DLinkListNode *next;//指向后继的next指针
  11.     struct _tag_DLinkListNode *pre;//指向前驱的pre指针
  12. }DLinkListNode;
  14. //为void 再重新多取一个名字，DLinkList等价于void
  15. //typedef + 已有的数据类型+新的数据类型(自己取的新名字)
  16. typedef void DLinkList;
  19. //创建并且返回一个空的双向链表
  20. DLinkList* DLinkList_Create();
  22. //销毁一个双向链表list 
  23. void DLinkList_Destroy(DLinkList* list);
  25. //将一个双向链表list中的所有元素清空, 循环链表回到创建时的初始状态  
  26. void DLinkList_Clear(DLinkList* list);
  28. //返回一个双向链表list中的元素个数
  29. int DLinkList_Length(DLinkList* list);
  31. //向一个双向链表list的pos位置处插入元素
  32. int DLinkList_Insert(DLinkList* list, DLinkList* node, int pos);
  34. //获取一个双向链表list中pos位置处的元素
  35. DLinkListNode* DLinkList_Get(DLinkList* list, int pos);
  37. //删除一个双向链表list中pos位置处的元素,返回值为被删除的元素,NULL表示删除失败
  38. DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);
  40. //add
  42. //直接指定删除双向链表中的某个数据元素
  43. DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);
  45. //将游标重置指向双向链表中的第一个数据元素
  46. DLinkListNode* DLinkList_SliderReset(DLinkList* list);
  48. //双向链表 获取当前游标指向的数据元素
  49. DLinkListNode* DLinkList_SliderCurrent(DLinkList* list);
  51. //将游标移动指向到双向链表中的下一个数据元素
  52. DLinkListNode* DLinkList_SliderNext(DLinkList* list);
  54. //将游标移动指向双向链表中的前一个数据元素
  55. DLinkListNode* DLinkList_SliderPre(DLinkList *list);
  57. #endif
  59. //DLinkList.c
  60. #include <stdlib.h>  
  61. #include <string.h>  
  62. #include <stdio.h>  
  63. #include "DLinkList.h"
  65. //定义双向链表的头结点 双向链表头结点：表示链表中第一个节点,包含指向第一个数据元素的指针以及链表自身的一些信息
  66. //这样能把所有结点串起来
  67. typedef struct _tag_DLinkList
  68. {
  69.     DLinkListNode   header;  //要有个头指针---指向头结点的指针
  70.     DLinkListNode  *slider;//在双向链表中可以定义一个“当前指针”，这个指针通常称为游标，可以通过游标来遍历链表中所有元素
  71.     int             length;//链表的长度
  72. }TDLinkList;
  73. //创建并且返回一个空的双向链表
  74. DLinkList* DLinkList_Create()
  75. {
  76.     //1 申请动态内存空间
  77.     TDLinkList *tmp = (TDLinkList *)malloc(sizeof(TDLinkList));
  78.     if (NULL == tmp)
  79.     {
  80.         printf("func err malloc:%d\n");
  81.         return NULL;
  82.     }
  83.     //2 让开辟的内存 完成链式线性表初始化  
  84.     memset(tmp, 0, sizeof(TDLinkList));
  85.     //3 链表的初始化
  86.     tmp->header.next = NULL;
  87.     tmp->header.pre = NULL;
  88.     tmp->slider = NULL;
  89.     tmp->length = 0;
  90.     return tmp;
  91. }
  93. //销毁一个双向链表list 
  94. //由于数据元素节点的生命周期不是由链表算法管理的，所以只需要销毁申请的头节点元素即可
  95. void DLinkList_Destroy(DLinkList* list)
  96. {
  97.     //1 缓存下来 进行操作
  98.     TDLinkList *tmp = NULL;
  99.     tmp = (TDLinkList *)list;
  100.     if (NULL == list)
  101.     {
  102.         printf("func err DLinkList_Destroy()\n");
  103.     }
  104.     //2 释放头结点空间 
  105.     if (tmp != NULL)
  106.     {
  107.         free(tmp);
  108.     }
  109. }
  112. //将一个双向链表list中的所有元素清空, 双向链表回到创建时的初始状态  
  113. void DLinkList_Clear(DLinkList* list)
  114. {
  115.     //1 缓存下来 进行操作
  116.     TDLinkList *tmp = NULL;
  117.     tmp = (TDLinkList *)list;
  118.     if (NULL == list)
  119.     {
  120.         printf("func err DLinkList_Clear()\n");
  121.     }
  122.     //2 清空链表
  123.     tmp->header.next = NULL;
  124.     tmp->header.pre = NULL;
  125.     tmp->slider = NULL;
  126.     tmp->length = 0;
  127. }
  130. //返回一个双向链表list中的元素个数
  131. int DLinkList_Length(DLinkList* list)
  132. {
  133.     int ret = 0;
  134.     //1 缓存下来 进行操作
  135.     TDLinkList *tmp = NULL;
  136.     tmp = (TDLinkList *)list;
  137.     if (NULL == list)
  138.     {
  139.         ret = -1;
  140.         printf("func err DLinkList_Length():%d\n", ret);
  141.         return ret;
  142.     }
  143.     ret = tmp->length;
  144.     return ret;
  145. }
  148. //向一个双向链表list的pos位置处插入元素
  149. int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos)
  150. {
  151.     int ret = 0;
  152.     //1 缓存下来 进行操作
  153.     TDLinkList *tmp = NULL;
  154.     tmp = (TDLinkList *)list;
  155.     //辅助指针 用来遍历当前指针位置
  156.     DLinkListNode *pCur = NULL;
  157.     //辅助指针 用来缓存当前指针下移位置
  158.     DLinkListNode *pNext = NULL;
  159.     if (NULL == list || NULL == node || pos < 0)
  160.     {
  161.         ret = -1;
  162.         printf("func err (NULL == list || NULL == node || pos < 0):%d\n", ret);
  163.         return ret;
  164.     }
  165.     //注意：容错修正,假如链表当前长度为5,你插入pos位置是10,这个时候可以做容错修正,直接修正为尾插法  
  166.     if (pos > tmp->length)
  167.     {
  168.         pos = tmp->length;
  169.     }
  170.     //1 当前指针 初始化 指向 头结点
  171.     pCur = &(tmp->header);
  172.     //2 进行遍历 找到插入位置
  173.     for (int i = 0; i < pos; i++)
  174.     {
  175.         pCur = pCur->next;
  176.     }
  177.     //3 进行插入操作
  178.     //进行缓存pCur next域
  179.     pNext = pCur->next;
  180.     //插入操作
  181.     pCur->next = node;//1
  182.     node->next = pNext;//2
  184.     if (pNext != NULL)
  185.     {
  186.         pNext->pre = node;//3 若是尾插法,就不需要这部操作
  187.     }
  188.     node->pre = NULL;//若是头插法,需要这部操作,如图1  4
  189.     if (pCur !=(DLinkListNode *)tmp)//若不是头插法,普通插入如图2 3情况 
  190.     {
  191.         node->pre = pCur;//4
  192.     }
  193.     //若第一次插入结点 让游标指向0号结点
  194.     if (tmp->length == 0)
  195.     {
  196.         tmp->slider = node;
  197.     }
  199.     //4 链表长度++
  200.     tmp->length++;
  201.     return ret;
  202. }
  205. //获取一个双向链表list中pos位置处的元素
  206. DLinkListNode* DLinkList_Get(DLinkList* list, int pos)
  207. {
  208.     //1 缓存下来 进行操作
  209.     TDLinkList    *tmp = (TDLinkList *)list;
  210.     //辅助指针 用来遍历当前指针位置
  211.     DLinkListNode *pCur = NULL;
  212.     if (NULL == list || pos < 0)
  213.     {
  214.         printf("func err DLinkList_Get\n");
  215.         return NULL;
  216.     }
  217.     //2 当前指针 初始化 指向 头结点
  218.     pCur = &(tmp->header);
  219.     //3 搜索要获得的结点
  220.     for (int i = 0; i < pos; i++)
  221.     {
  222.         pCur = pCur->next;
  223.     }
  224.     return pCur->next;
  225. }
  228. //删除一个循环链表list中pos位置处的元素,返回值为被删除的元素,NULL表示删除失败
  229. DLinkListNode* DLinkList_Delete(DLinkList* list, int pos)
  230. {
  231.     //1 缓存下来 进行操作
  232.     TDLinkList    *tmp = (TDLinkList *)list;
  233.     //辅助指针 用来遍历当前指针位置
  234.     DLinkListNode *pCur = NULL;
  235.     //辅助指针 用来缓存删除结点下一元素
  236.     DLinkListNode *pAfter = NULL;
  237.     //辅助指针 用来缓存删除元素
  238.     DLinkListNode *DeletNode = NULL;
  239.     if (NULL == list || pos < 0)
  240.     {
  241.         printf("func err DLinkList_Delete\n");
  242.         return NULL;
  243.     }
  244.     //删除位置的pos点不能大于链表长度  做一个容错修正 
  245.     //当删除位置pos大于双向链表长度,就尾部删除
  246.     if (pos > DLinkList_Length(tmp))
  247.     {
  248.         pos = tmp->length;
  249.     }
  250.     //2 当前指针 初始化 指向 头结点
  251.     pCur = &(tmp->header);
  252.     //3 搜索要获得的结点
  253.     for (int i = 0; i < pos; i++)
  254.     {
  255.         pCur = pCur->next;
  256.     }
  257.     //4 缓存结点位置
  258.     DeletNode = pCur->next;
  259.     pAfter = DeletNode->next;
  260.     //5 开启删除操作 分三种情况
  261.     pCur->next = pAfter;//普通情况1
  262.     if (pAfter !=NULL)
  263.     {
  264.         pAfter->pre = pCur;//普通情况2
  265.     }
  266.     DeletNode->pre = NULL;//第三种情况需要置空 第二种已经自己置空
  268.     //6 链表长度--
  269.     tmp->length--;
  271.     //7 若删除元素为游标所指元素 需要后移
  272.     if (tmp->slider == DeletNode)
  273.     {
  274.         tmp->slider = pAfter;
  275.     }
  277.     //8 若删除元素后链表长度为0  
  278.     if (tmp->length == 0)
  279.     {
  280.         tmp->header.next = NULL;
  281.         tmp->header.pre = NULL;
  282.         tmp->slider = NULL;
  283.     }
  284.     return DeletNode;
  285. }
  288. //add
  290. //根据结点 直接指定删除链表中的某个数据元素
  291. DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node)
  292. {
  293.     //1 缓存下来 进行操作
  294.     TDLinkList    *tmp = (TDLinkList *)list;
  295.     //辅助指针 用来遍历当前指针位置
  296.     DLinkListNode *pCur = NULL;
  297.     //辅助指针 用来缓存删除元素
  298.     DLinkListNode *DeletNode = NULL;
  299.     if (NULL == list || 0  == node)
  300.     {
  301.         printf("func err DLinkList_DeleteNode\n");
  302.         return NULL;
  303.     }
  304.     //2 当前指针 初始化 指向 头结点
  305.     pCur = &(tmp->header);
  306.     //3 搜索要获得的结点
  307.     int i;
  308.     for ( i = 0; i < tmp->length; i++)
  309.     {
  310.         if (pCur->next == node)//根据删除结点搜索到要删除位置
  311.         {
  312.             DeletNode = pCur->next;//缓存删除元素
  313.             break;//这里搜索到要删除的结点,结束循环,否则会报错
  314.         }
  315.         pCur = pCur->next;
  316.     }
  317.     //4 根据pos位置删除元素
  318.     if (DeletNode != NULL)
  319.     {
  320.         DLinkList_Delete(tmp,i);
  321.     }
  322.     return DeletNode;
  323. }
  326. //将游标重置指向链表中的第一个数据元素
  327. DLinkListNode* DLinkList_SliderReset(DLinkList* list)
  328. {
  329.     //1 缓存下来 进行操作
  330.     TDLinkList    *tmp = (TDLinkList *)list;
  331.     //辅助指针 用来缓存重置游标位置
  332.     DLinkListNode *tmpReset = NULL;
  333.     if (NULL == list)
  334.     {
  335.         printf("func err DLinkList_SliderReset\n");
  336.         return NULL;
  337.     }
  338.     if (tmp!=NULL)
  339.     {
  340.         tmp->slider = tmp->header.next;//重置指向第一个数据元素
  341.         tmpReset = tmp->slider;//缓存游标位置
  342.     }
  343.     return tmpReset;
  344. }
  347. //获取当前游标指向的数据元素
  348. DLinkListNode* DLinkList_SliderCurrent(DLinkList* list)
  349. {
  350.     //1 缓存下来 进行操作
  351.     TDLinkList    *tmp = (TDLinkList *)list;
  352.     //辅助指针 用来缓存当前游标位置
  353.     DLinkListNode *tmpCur = NULL;
  354.     if (NULL == list)
  355.     {
  356.         printf("func err DLinkList_SliderCurrent\n");
  357.         return NULL;
  358.     }
  359.     if (tmp!=NULL)
  360.     {
  361.         tmpCur = tmp->slider;//缓存当前游标位置
  362.     }
  363.     return tmpCur;
  364. }
  367. //将游标移动指向到链表中的下一个数据元素
  368. DLinkListNode* DLinkList_SliderNext(DLinkList* list)
  369. {
  370.     //1 缓存下来 进行操作
  371.     TDLinkList    *tmp = (TDLinkList *)list;
  372.     //辅助指针 用来缓存游标位置
  373.     DLinkListNode *tmpNext = NULL;
  374.     if (NULL == list)
  375.     {
  376.         printf("func err DLinkList_SliderNext\n");
  377.         return NULL;
  378.     }
  379.     if (tmp != NULL)
  380.     {
  381.         tmpNext = tmp->slider;//缓存当前游标位置
  382.         tmp->slider = tmpNext->next;//将游标下移
  383.     }
  384.     return tmpNext;
  385. }
  387. //将游标移动指向双向链表中的前一个数据元素
  388. DLinkListNode* DLinkList_SliderPre(DLinkList *list)
  389. {
  390.     //1 缓存下来 进行操作
  391.     TDLinkList    *tmp = (TDLinkList *)list;
  392.     //辅助指针 用来缓存游标位置
  393.     DLinkListNode *tmpPre = NULL;
  394.     if (NULL == list)
  395.     {
  396.         printf("func err DLinkList_SliderPre\n");
  397.         return NULL;
  398.     }
  399.     if (tmp != NULL)
  400.     {
  401.         tmpPre = tmp->slider;//缓存当前游标位置
  402.         tmp->slider = tmpPre->pre;//将游标上移
  403.     }
  404.     return tmpPre;
  405. }
  407. //双向链表的设计与实现测试框架
  408. //text.c
  409. #include <stdlib.h>  
  410. #include <string.h>  
  411. #include <stdio.h>  
  412. #include "DLinkList.h"//c里面.h和.cpp没有差别 但是c++里如果模块化编程，两个头文件都必须包含进来
  415. //业务结点
  416. typedef struct _tag_Teacher
  417. {
  418.     DLinkListNode node;//包含底层结点
  419.     //业务域
  420.     int age;
  422. }Teacher;
  425. int main()
  426. {
  427.     int ret = 0;
  428.     DLinkList *dlist = NULL;
  429.     Teacher t1, t2, t3, t4;
  430.     t1.age = 1;
  431.     t2.age = 2;
  432.     t3.age = 3;
  433.     t4.age = 4;
  434.     //1 创建并且返回一个空的双向链表
  435.     dlist = DLinkList_Create();
  436.     if (NULL == dlist)
  437.     {
  438.         ret = -1;
  439.         printf("func err DLinkList_Create:%d\n", ret);
  440.         return ret;
  441.     }
  442.     //2 向一个双向链表list的pos位置处插入元素
  443.     ret = DLinkList_Insert(dlist, (DLinkListNode *)&t1, DLinkList_Length(dlist));
  444.     if (ret != 0)
  445.     {
  446.         ret = -2;
  447.         printf("func err DLinkList_Insert:%d\n", ret);
  448.         return ret;
  449.     }
  450.     ret = DLinkList_Insert(dlist, (DLinkListNode *)&t2, DLinkList_Length(dlist));
  451.     ret = DLinkList_Insert(dlist, (DLinkListNode *)&t3, DLinkList_Length(dlist));
  452.     ret = DLinkList_Insert(dlist, (DLinkListNode *)&t4, DLinkList_Length(dlist));
  454.     //返回一个双向链表list中的元素个数
  455.     ret = DLinkList_Length(dlist);
  456.     printf("%d ",ret);
  457.     printf("\n========================我是分界线====================\n");
  458.     //遍历双向链表
  459.     for (int i = 0; i < DLinkList_Length(dlist); i++)
  460.     {
  461.         //获取游标所指元素,然后游标下移
  462.         //双向链表 获取当前游标指向的数据元素
  463.         Teacher *tmp = (Teacher *)DLinkList_SliderNext(dlist);
  464.         if (NULL == tmp)
  465.         {
  466.             ret = -3;
  467.             printf("func err DLinkList_SliderNext:%d\n", ret);
  468.             return ret;
  469.         }
  470.         printf("%d ",tmp->age);
  471.     }
  472.     printf("\n========================我是分界线====================\n");
  473.     将一个双向链表list中的所有元素清空, 循环链表回到创建时的初始状态  
  474.     //DLinkList_Clear(dlist);
  475.     返回一个双向链表list中的元素个数
  476.     //ret = DLinkList_Length(dlist);
  477.     //printf("%d ", ret);
  479.     //再一次 遍历双向链表
  480.     for (int i = 0; i < DLinkList_Length(dlist); i++)
  481.     {
  482.         //获取一个双向链表list中pos位置处的元素
  483.         //DLinkListNode* DLinkList_Get(DLinkList* list, int pos);
  484.         Teacher *tmp = (Teacher *)DLinkList_Get(dlist,i);
  485.         if (NULL == tmp)
  486.         {
  487.             ret = -4;
  488.             printf("func err DLinkList_SliderCurrent:%d\n", ret);
  489.             return ret;
  490.         }
  491.         printf("%d ", tmp->age);
  492.     }
  493.     printf("\n========================我是分界线====================\n");
  494.     //将游标重置指向双向链表中的第一个数据元素
  495.     //DLinkListNode* DLinkList_SliderReset(DLinkList* list);
  497.     Teacher *tmp1 = (Teacher *)DLinkList_SliderReset(dlist);
  498.     printf("%d ", tmp1->age);
  500.     Teacher *tmp2 = (Teacher *)DLinkList_SliderNext(dlist);
  501.     printf("%d ", tmp2->age);
  503.     //直接指定删除双向链表中的某个数据元素
  504.     //DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);
  505.     tmp2 = (Teacher *)DLinkList_DeleteNode(dlist, (DLinkListNode*)tmp2);
  506.     printf("%d ", tmp2->age);
  508.     //删除一个双向链表list中pos位置处的元素,返回值为被删除的元素,NULL表示删除失败
  509.     //DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);
  510.     tmp2 = (Teacher *)DLinkList_Delete(dlist, 1);
  511.     printf("%d ", tmp2->age);
  514.     //将游标移动指向双向链表中的前一个数据元素
  515.     //DLinkListNode* DLinkList_SliderPre(DLinkList *list);
  516.     tmp2 = (Teacher *)DLinkList_SliderPre(dlist);
  517.     printf("%d ", tmp2->age);
  519.     DLinkList_Destroy(dlist);
  521.     system("pause");
  522.     return 0;
  523. }

双向链表

1、基本概念



















单链表的结点都只有一个指向下一个结点的指针

单链表的数据元素无法直接访问其前驱元素

逆序访问单链表中的元素是极其耗时的操作！

len = LinkList_Length(list);

for (i=len-1; len>=0; i++) //O(n)

{

LinkListNode *p = LinkList_Get(list, i); //O(n)

//访问数据元素p中的元素

//

}

双向链表的定义

在单链表的结点中增加一个指向其前驱的pre指针

双向链表拥有单链表的所有操作

创建链表

销毁链表

获取链表长度

清空链表

获取第pos个元素操作

插入元素到位置pos

删除位置pos处的元素

2、设计与实现




























插入操作




删除操作

双向链表的新操作

获取当前游标指向的数据元素

将游标重置指向链表中的第一个数据元素

将游标移动指向到链表中的下一个数据元素

将游标移动指向到链表中的上一个数据元素

直接指定删除链表中的某个数据元素

DLinkListNode DLinkList_DeleteNode(DLinkList list, DLinkListNode node);

DLinkListNode DLinkList_Reset(DLinkList list);

DLinkListNode DLinkList_Current(DLinkList list);

DLinkListNode DLinkList_Next(DLinkList list);

DLinkListNode DLinkList_Pre(DLinkList* list);

//大家一定要注意：教科书不会告诉你项目上如何用；哪些点是项目的重点；

做一个企业级的财富库，完成你人生开发经验的积累，是我们的学习重点，要注意！

3、优点和缺点










优点：双向链表在单链表的基础上增加了指向前驱的指针

功能上双向链表可以完全取代单链表的使用

循环链表的Next，Pre和Current操作可以高效的遍历链表中的所有元素

缺点：代码复杂

发表评论

表情：
评论列表 （有 0 条评论，191人围观）

还没有评论，来说两句吧...

相关阅读