数据结构（5）线性表之双向链表

╰+哭是因爲堅強的太久メ 2023-06-04 06:55 256阅读 0赞

数据结构（5）线性表之双向链表

      • 前言
      • 增加双向链表的管理结构
      • 双向链表的插入
        • 尾部插入
        • 头部与按值插入
      • 双向链表的删除
      • 排序与逆置
      • 全部代码
        • DList.h
        • DList.cpp
        • Main.cpp

前言

在先前讨论的链式存储结构中，无论是单链表还是单循环链表，都只有一个指向后继的指针，因此可以很容易找到它的后继，但是要找它的前驱却很麻烦。那么可不可以再增加一个指向前驱的指针，这样在遍历链表时不仅能从前往后遍历，也能从后往前遍历呢？这就是我们今天所说的双向链表。

顾名思义，双向链表就是其结点中有两个指针域，一个指向直接前驱，一个指向直接后继。当然，链表的第一个结点无直接前驱，最后一个结点无直接后继，设置为空即可。

img\_1

实现双向链表的相关操作，思路上同单链表是一致的，唯一的区别是还需要考虑Prior指针的指向问题。

增加双向链表的管理结构

我们同样为双向链表设置管理结构，first指针指向头结点，last指针指向最后一个结点，size保存链表结点的数量。同单链表一样，在增加了管理结构之后，在做插入、删除操作时，除了保证链表本身的正确性，还要考虑到管理结构的正确性，也就是注意first和last指针指向的正确，和size的数量正确。

img\_2

双向链表的插入

与单链表不同的是，双向链表的改动除了涉及Next指针外，还涉及Prior指针，因此每当我们要执行插入操作时，一般要考虑四个指针的指向

  • 待插入结点的Prior指针
  • 待插入结点的Next指针
  • 待插入结点前驱的Next指针
  • 待插入结点后继的Prior指针

img\_3

只要想好了这四个指针的指向问题，双向链表的操作也就没什么难点了

尾部插入

尾部插入只涉及两个结点，因此只需要考虑两个指针，以及管理结构的last指针即可

img\_4

头部与按值插入

头部插入是直接插在头结点后的位置，按值插入是找到插入位置后直接进行插入(如果是最后一位直接进行尾部插入)，两种方式都需要考虑四个指针的指向

同时，在设置四个指针指向的时候要注意先后的顺序，避免出现指针丢失的问题

img\_5

双向链表的删除

双向链表的删除比单链表的删除方便，因为可以找到直接前驱，所以也不需要使用修改值的方法了，直接修改直接前驱和直接后继的指针就好了。尾部、头部和按值删除的方法都类似，只是涉及到的指针有区别，不详谈了。

img\_6

排序与逆置

与单链表的思路一样，在进行双向链表的排序时，可以借鉴按值插入的思路，将原有的双向链表断开，再遍历一个个取出结点，进行按值插入。而在进行逆置时，则进行头部插入即可。

在这里我是利用了已经写好的方法，直接调用方法进行按值插入，再将原来的结点释放掉。

  1. while (q != NULL) { 
  2.         //取出后续结点
  3.         s = q;
  4.         q = q->next;
  5.         //进行按值插入
  6.         insert_val(list, s->data);
  7.         //释放原来的结点
  8.         free(s);
  9.         list->size --;
  10.     }

也可以不调用方法，通过设置指针的方式将结点重新连接到链表中

  1. while (q != NULL) { 
  2.         //取出后续结点
  3.         s = q;
  4.         q = q->next;
  6.         Node *p = list->first;
  7.           //寻找插入位置
  8.           while (p->next != NULL && p->next->data<s->data) { 
  9.               p = p->next;
  10.           }
  12.           //判断是否是最后一个
  13.           if (p->next == NULL) { 
  14.               //是，进行尾部插入
  15.               s->next = NULL;
  16.               s->prior = list->last;
  17.               list->last->next = s;
  18.               list->last = s;
  19.           }else{       
  20.               //s的后继指向p的后继
  21.               s->next = p->next;
  22.               //s的前驱指向p
  23.               s->prior = p;
  24.               //p后继的前驱指向s
  25.               p->next->prior = s;
  26.               //p的后继指向s
  27.               p->next = s;
  28.           }

逆置同理

全部代码

DList.h

  1. #ifndef DList_h
  2. #define DList_h
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <assert.h>
  8. #define ElemType int
  10. typedef struct Node{ 
  11.     ElemType data;
  12.     struct Node *prior;
  13.     struct Node *next;
  14. }Node,*PNode;
  16. typedef struct List{ 
  17.     PNode first;
  18.     PNode last;
  19.     int size;
  20. }List;
  22. //初始化双链表
  23. void InitDList(List *list);
  25. //1.尾部插入
  26. void push_back(List *list,ElemType x);
  27. //2.头部插入
  28. void push_fount(List *list,ElemType x);
  29. //3.展示
  30. void show_list(List *list);
  31. //4.尾部删除
  32. void pop_back(List *list);
  33. //5.头部删除
  34. void pop_fount(List *list);
  35. //6.按值插入(要求插入前的链表是有序的(此处为顺序
  36. void insert_val(List *list,ElemType x);
  37. //7.按值查找
  38. Node* find(List *list,ElemType x);
  39. //8.获取长度
  40. int length(List *list);
  41. //9.按值删除
  42. void  delete_val(List *list,ElemType x);
  43. //10.排序
  44. void sort(List *list);
  45. //11.逆置(前后转换
  46. void resver(List *list);
  47. //12.清除单链表 ->只清除数据，保留头结点
  48. void clearList(List *list);
  49. //13.摧毁 ->包括头结点在内一起摧毁
  50. void destroy(List *list);
  52. //生成一个结点
  53. Node* getNode(ElemType x);
  55. #endif /* DList_h */

DList.cpp

  1. #include "DList.h"
  3. //初始化
  4. void InitDList(List *list){ 
  5.     Node *s = (Node *)malloc(sizeof(Node));
  6.     assert(s != NULL);
  8.     list->first = list->last = s;
  9.     list->first->next = NULL;
  10.     list->first->prior = NULL;
  11.     list->size = 0;
  12. }
  14. //1.尾部插入
  15. void push_back(List *list,ElemType x){ 
  16.     //获得一个结点
  17.     Node *s = getNode(x);
  19.     //s的前驱指向最后一个结点
  20.     s->prior = list->last;
  21.     //最后一个结点的后继指向s
  22.     list->last->next = s;
  23.     //重新设置last指针的指向
  24.     list->last = s;
  26.     list->size ++;
  27. }
  29. //2.头部插入
  30. void push_fount(List *list,ElemType x){ 
  31.     Node *s = getNode(x);
  32.     //判断是否是第一个结点
  33.     if (list->first == list->last) { 
  34.         //是第一个结点，s的后继不需要设置
  35.         //s的前驱指向头结点
  36.         //s->prior = list->first;
  37.         //重新设置first指针的指向，使s成为新的首元结点
  38.         //list->first->next = s;
  40.         //重新设置last指针的指向
  41.         list->last = s;
  42.     }else{ 
  43.         //s的后继指向首元结点
  44.         s->next = list->first->next;
  45.         //s的前驱指向头结点
  46.         //s->prior = list->first;
  48.         //首元结点的前驱指向s
  49.         //s->next->prior = s;
  50.         list->first->next->prior = s;
  51.         //重新设置first指针的指向，使s成为新的首元结点
  52.         list->first->next = s;
  54.     }
  55.     //if-else语句中有重复的部分，可以提出来
  56.     //s的前驱指向头结点
  57.     s->prior = list->first;
  58.     //重新设置first指针的指向，使s成为新的首元结点
  59.     list->first->next = s;
  61.     list->size ++;
  62. }
  64. //3.展示
  65. void show_list(List *list){ 
  66.     Node *p = list->first->next;
  68.     while (p != NULL) { 
  69.         printf("%4d",p->data);
  70.         p = p->next;
  71.     }
  72.     printf("\n");
  73. }
  74. //4.尾部删除
  75. void pop_back(List *list){ 
  76.     if (list->size == 0) { 
  77.         printf("链表已空！\n");
  78.         return;
  79.     }
  81.     //方法1
  82.     Node *p = list->first;
  83.     //循环到链表的最后一位
  84.     while (p->next != NULL) { 
  85.         p = p->next;
  86.     }
  88.     //将last指针指向倒数第二位(即p的前一位
  89.     list->last = p->prior;
  90.     //释放该结点的空间
  91.     free(p);
  92.     //此时链表最后一位的后继为空
  93.     list->last->next = NULL;
  95.     list->size --;
  97.     /* //方法2 Node *p = list->first; //循环到链表倒数第二位 while (p->next != list->last) { p = p->next; } //释放最后一个结点的空间 free(p->next); p->next = NULL; //重新设置last指针的指向 list->last = p; list->size --; */
  98. }
  100. //5.头部删除
  101. void pop_fount(List *list){ 
  102.     if (list->size == 0) { 
  103.         printf("链表已空!\n");
  104.         return;
  105.     }
  107.     Node *s = list->first->next;
  109.     //判断是否是最后一个结点
  110.     if (s->next == NULL) { 
  111.         //是，则s没有后继,不需要修改后继的指针
  112.         //修改last指针的指向
  113.         list->last = list->first;
  114.         list->last->next = NULL;
  115.     }else{ 
  117.         //s的后继的prior指针指向头结点
  118.         s->next->prior = list->first;
  119.         //头结点的next指针指向s的后继
  120.         list->first->next = s->next;
  121.     }
  123.     //释放该结点
  124.     free(s);
  125.     list->size --;
  126. }
  128. //6.按值插入(要求插入前的链表是有序的(此处为顺序
  129. void insert_val(List *list,ElemType x){ 
  130.     Node *p = list->first;
  131.     //寻找插入位置
  132.     while (p->next != NULL && p->next->data<x) { 
  133.         p = p->next;
  134.     }
  136.     //判断是否是最后一个
  137.     if (p->next == NULL) { 
  138.         //是，直接进行尾部插入
  139.         push_back(list, x);
  140.     }else{ 
  141.         Node *s = getNode(x);
  143.         //s的后继指向p的后继
  144.         s->next = p->next;
  145.         //s的前驱指向p
  146.         s->prior = p;
  147.         //p后继的前驱指向s
  148.         p->next->prior = s;
  149.         //p的后继指向s
  150.         p->next = s;
  152.         list->size ++;
  153.     }
  154. }
  156. //7.按值查找
  157. Node* find(List *list,ElemType x){ 
  158.     Node *p = list->first->next;
  159.     while (p != NULL && p->data != x) { 
  160.         p = p->next;
  161.     }
  162.     return p;
  163. }
  165. //8.获取长度
  166. int length(List *list){ 
  167.     return list->size;
  168. }
  170. //9.按值删除
  171. void  delete_val(List *list,ElemType x){ 
  172.     if (list->size == 0) { 
  173.         printf("链表已空！\n");
  174.         return;
  175.     }
  177.     Node *p = find(list, x);
  178.     if (p == NULL) { 
  179.         printf("要删除的值不存在！\n");
  180.         return;
  181.     }
  182.     //判断是否是最后一个节点
  183.     if (p == list->last) { 
  184.         //直接进行尾部删除
  185.         pop_back(list);
  186.     }else{ 
  187.         //p后继的前驱指向p的前驱
  188.         p->next->prior = p->prior;
  189.         //p前驱的后继指向p的后继
  190.         p->prior->next = p->next;
  191.         //释放结点空间
  192.         free(p);
  193.         list->size --;
  194.     }
  195. }
  197. //10.排序
  198. void sort(List *list){ 
  199.     if (list->size <= 1) { 
  200.         //不需要排序
  201.         return;
  202.     }
  204.     Node *s = list->first->next;
  205.     Node *q = s->next;
  206.     //将链表断开
  207.     list->last = s;
  208.     list->last->next = NULL;
  210.     while (q != NULL) { 
  211.         //取出后续结点
  212.         s = q;
  213.         q = q->next;
  214.         //进行按值插入
  215.         insert_val(list, s->data);
  216.         //释放原来的结点
  217.         free(s);
  218.         list->size --;
  220. // Node *p = list->first;
  221. // //寻找插入位置
  222. // while (p->next != NULL && p->next->data<s->data) { 
  223. // p = p->next;
  224. // }
  225. //
  226. // //判断是否是最后一个
  227. // if (p->next == NULL) { 
  228. // //是，直接进行尾部插入
  229. // s->next = NULL;
  230. // s->prior = list->last;
  231. // list->last->next = s;
  232. // list->last = s;
  233. // }else{ 
  234. //
  235. // //s的后继指向p的后继
  236. // s->next = p->next;
  237. // //s的前驱指向p
  238. // s->prior = p;
  239. // //p后继的前驱指向s
  240. // p->next->prior = s;
  241. // //p的后继指向s
  242. // p->next = s;
  243. // }
  245.     }
  246. }
  248. //11.逆置(前后转换
  249. void resver(List *list){ 
  250.     if (list->size <= 1) { 
  251.         //不需要逆置
  252.         return;
  253.     }
  255.     Node *s = list->first->next;
  256.     Node *q = s->next;
  258.     //将链表断开
  259.     list->last = s;
  260.     list->last->next = NULL;
  262.     while (q != NULL) { 
  263.         s = q;
  264.         q = q->next;
  265.         //直接进行头部插入
  266.         push_fount(list, s->data);
  267.         //释放原有结点
  268.         free(s);
  269.         list->size --;
  270.     }
  271. }
  272. //12.清除单链表 ->只清除数据，保留头结点
  273. void clearList(List *list){ 
  274.     if (list->size == 0) { 
  275.         printf("链表已空！\n");
  276.         return;
  277.     }
  279.     Node *s = list->first;
  280.     Node *p = s->next;
  281.     //遍历整个链表
  282.     while (p != NULL) { 
  283.         s = p;
  284.         p = p->next;
  285.         //释放结点
  286.         free(s);
  287.         list->size --;
  288.     }
  290.     list->last = list->first;
  291.     list->last->next = NULL;
  292. }
  293. //13.摧毁 ->包括头结点在内一起摧毁
  294. void destroy(List *list){ 
  295.     clearList(list);
  296.     free(list->first);
  297.     list->first = list->last = NULL;
  298. }
  301. //生成一个结点
  302. Node* getNode(ElemType x){ 
  303.     Node *s = (Node *)malloc(sizeof(Node));
  304.     assert(s != NULL);
  306.     s->data = x;
  307.     s->prior = NULL;
  308.     s->next = NULL;
  310.     return s;
  311. }

Main.cpp

  1. #include "DList.h"
  3. int main(int argc, const char * argv[]) { 
  5.     List myList;
  6.     InitDList(&myList);
  8.     //保存要输入的数据
  9.        ElemType item;
  10.        //保存要查找的地址
  11.        Node *p = NULL;
  12.        int select = 1;
  13.        while (select) { 
  14.            printf("**************************************\n");
  15.            printf("* [1] push_back [2] push_front *\n");
  16.            printf("* [3] show_list [4] pop_back *\n");
  17.            printf("* [5] pop_front [6] insert_val *\n");
  18.            printf("* [7] find [8] length *\n");
  19.            printf("* [9] delete_val [10] sort *\n");
  20.            printf("* [11] resver [12] clear *\n");
  21.            printf("* [13*] destroy [0] quit_system*\n");
  22.            printf("**************************************\n");
  23.            printf("请选择:");
  24.            scanf("%d",&select);
  25.            if (select == 0) { 
  26.                break;
  27.            }
  28.            switch (select) { 
  29.                case 1:
  30.                    //尾部插入
  31.                    printf("请输入要插入的数据(-1结束):");
  32.                    scanf("%d",&item);
  33.                    while (item != -1) { 
  34.                        push_back(&myList, item);
  35.                        scanf("%d",&item);
  36.                    }
  37.                    break;
  38.                case 2:
  39.                    //头部插入
  40.                    printf("请输入要插入的数据(-1结束):");
  41.                    scanf("%d",&item);
  42.                    while (item != -1) { 
  43.                        push_fount(&myList, item);
  44.                        scanf("%d",&item);
  45.                    }
  46.                    break;
  47.                case 3:
  48.                    //展示单链表
  49.                    show_list(&myList);
  50.                    break;
  51.                case 4:
  52.                    //尾部删除
  53.                    pop_back(&myList);
  54.                    break;
  55.                case 5:
  56.                    //头部删除
  57.                    pop_fount(&myList);
  58.                    break;
  59.                case 6:
  60.                    //按值插入
  61.                    printf("请输入要插入的数据:\n");
  62.                    scanf("%d",&item);
  63.                    insert_val(&myList, item);
  64.                    break;
  65.                case 7:
  66.                    //按值查找
  67.                    printf("请输入要查找的值:\n");
  68.                    scanf("%d",&item);
  69.                    p = find(&myList, item);
  70.                    if (p == NULL) { 
  71.                        printf("要查找的数据不存在!\n");
  72.                    }else{ 
  73.                        printf("地址为:%p\n",p);
  74.                    }
  75.                    break;
  76.                case 8:
  77.                    //展示链表长度
  78.                    printf("链表的长度为:%d\n",length(&myList));
  79.                    break;
  80.                case 9:
  81.                    //按值删除
  82.                    printf("请输入要删除的值：\n");
  83.                    scanf("%d",&item);
  84.                    delete_val(&myList, item);
  85.                    break;
  86.                case 10:
  87.                    //排序
  88.                    sort(&myList);
  89.                    break;
  90.                case 11:
  91.                    //逆置(前后转换
  92.                    resver(&myList);
  93.                    break;
  94.                case 12:
  95.                    //清除
  96.                    clearList(&myList);
  97.                    break;
  98.                case 13:
  99.                    destroy(&myList);
  100.                    break;
  101.                default:
  102.                    printf("输入的命令有误，请重新插入\n");
  103.                    break;
  104.            }
  105.        }
  107.     return 0;
  108. }

发表评论

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

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

相关阅读