数据结构（6）线性表之双循环链表

矫情吗；* 2023-06-08 03:18 119阅读 0赞

数据结构（6）线性表之双循环链表

      • 前言
      • 双循环链表的插入与删除
      • 全部代码
        • DCList.h
        • DCList.cpp
        • Main.cpp

前言

同单链表一样，双向链表也可以是循环表。链表最后一个结点的next指针指向头结点，头结点的Prior指针指向最后一个结点，形成循环。

带头结点的空链表

img\_1

带头结点的非空链表

img\_2

添加管理结构

img\_3

双循环链表的插入与删除

实际上，在循环链表中，无论是头部插入还是尾部插入，都可以理解为按位置插入(就是在两个结点中间进行插入)：头部插入是在头结点和首元结点之间进行插入，尾部插入则是在最后一个结点和头结点之间进行插入。这样，我们只需要知道如何在两个结点中间进行插入，就可以实现双循环链表诸多的插入操作。而如何在两个结点中间进行插入，跟在双链表中是一致的，也就是需要考虑四个指针的指向

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

这样，本来区分开的头部插入、尾部插入操作可以整合为按位置插入，参数传要插入的位置即可。但是考虑到我们的双链表增加了管理结构，还需要保证管理结构指针的正确性，所以在代码中仍是区分实现的。

img\_4

尾部插入也是两个结点中的插入

img\_6

实际上

img\_5

插入与删除类似

img\_7
img\_8
其他操作同双链表一致，只是判断循环结束的条件有区别罢了，不细说

全部代码

DCList.h

  1. #ifndef DCList_h
  2. #define DCList_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 InitDCList(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 /* DCList_h */

DCList.cpp

  1. #include "DCList.h"
  3. //初始化
  4. void InitDCList(List *list){ 
  5.     //申请头结点
  6.     Node *s = (Node *)malloc(sizeof(Node));
  7.     assert(s != NULL);
  8.     list->first = list->last = s;
  10.     //使链表循环
  11.     list->first->prior = list->last;
  12.     list->last->next = list->first;
  14.     list->size = 0;
  15. }
  17. //1.尾部插入
  18. void push_back(List *list,ElemType x){ 
  19.     Node *s = getNode(x);
  21.     //s的前驱指向最后一个结点
  22.     s->prior = list->last;
  23.     //s的后继指向头结点
  24.     s->next = list->last->next;
  25.     //头结点的前驱指向s
  26.     //list->last->next->prior = s;
  27.     s->next->prior = s;
  28.     //最后一个结点的后继指向s
  29.     list->last->next = s;
  31.     //重新设置last指针的值
  32.     list->last = s;
  34.     list->size ++;
  35. }
  37. //2.头部插入
  38. void push_fount(List *list,ElemType x){ 
  39.     Node *s = getNode(x);
  41.     //s的后继是头结点的后继
  42.     s->next = list->first->next;
  43.     //s的前驱是头结点
  44.     s->prior = list->first;
  45.     //原先第一个结点的前驱改为s
  46.     //list->first->next->prior = s;
  47.     s->next->prior = s;
  48.     //头结点的后继改为s
  49.     list->first->next = s;
  51.     //判断是否是第一个结点
  52.     if (list->first == list->last) { 
  53.         //是，需要修改last指针的指向
  54.         list->last = s;
  55.     }
  57.     list->size ++;
  58. }
  60. //3.展示
  61. void show_list(List *list){ 
  62.     Node *s = list->first->next;
  64.     while (s != list->first) { 
  65.         printf("%4d",s->data);
  66.         s = s->next;
  67.     }
  69.     printf("\n");
  70. }
  72. //4.尾部删除
  73. void pop_back(List *list){ 
  75.     if (list->size == 0) { 
  76.         printf("链表已空！\n");
  77.         return;
  78.     }
  80.     Node *s = list->last;
  81.     //last指针修改为s的前驱
  82.     //list->last = list->last->prior;
  83.     list->last = s->prior;
  85.     //s前驱的next指针指向s的后继(即头结点)
  86.     //list->last->next = s->next;
  87.     s->prior->next = s->next;
  89.     //s后继的prior指针(即头结点的prior指针)指向s的前驱(即新的最后一个结点)
  90.     //s->next->prior = list->last;
  91.     s->next->prior = s->prior;
  92.     //释放s
  93.     free(s);
  95.     list->size --;
  96. }
  98. //5.头部删除
  99. void pop_fount(List *list){ 
  100.     if (list->size == 0) { 
  101.         printf("链表已空！\n");
  102.         return;
  103.     }
  105.     Node *s = list->first->next;
  106.     //s前驱的后继指向s的后继(即头结点的next指向s的next)
  107.     //list->first->next = s->next;
  108.     s->prior->next = s->next;
  110.     //s后继的前驱指向s的前驱(即s的后继的prior指针指向头结点)
  111.     //s->next->prior = list->first;
  112.     s->next->prior = s->prior;
  113.     //释放s
  114.     free(s);
  116.     //判断删除的是否是最后一个结点
  117.     if (list->size == 1) { 
  118.         //是，重新修改last指针的指向
  119.         list->last = list->first;
  120.     }
  121.     list->size -- ;
  123. }
  125. //6.按值插入(要求插入前的链表是有序的(此处为顺序
  126. void insert_val(List *list,ElemType x){ 
  128.     Node *p = list->first;
  130.     //寻找插入位置
  131.     while (p->next != list->first && p->next->data < x) { 
  132.         p = p->next;
  133.     }
  136.     //在p结点之后进行插入
  137.     //判断插入位置
  138.     if (p->next == list->first) { 
  139.         //尾部插入
  140.         push_back(list, x);
  141.     }else{ 
  142.         Node *s = getNode(x);
  144.         //s的前驱为p
  145.         s->prior = p;
  146.         //s的后继为p的后继
  147.         s->next = p->next;
  148.         //p后继的前驱改为s
  149.         p->next->prior = s;
  150.         //p的后继改为s
  151.         p->next = s;
  153.         list->size ++;
  154.     }
  156. }
  158. //7.按值查找
  159. Node* find(List *list,ElemType x){ 
  160.     Node *s = list->first->next;
  161.     while (s != list->first && s->data != x) { 
  162.         s = s->next;
  163.     }
  164.     if (s == list->first) { 
  165.         //循环结束，没找到
  166.         return NULL;
  167.     }
  168.     return s;
  169. }
  170. //8.获取长度
  171. int length(List *list){ 
  172.     return list->size;
  173. }
  175. //9.按值删除
  176. void  delete_val(List *list,ElemType x){ 
  177.     if (list->size == 0) { 
  178.         printf("链表已空！\n");
  179.         return;
  180.     }
  182.     Node *p = find(list, x);
  184.     if (p == NULL) { 
  185.         printf("要删除的数据不存在！\n");
  186.         return;
  187.     }
  189.     //找到结点位置
  190.     if (p == list->last) { 
  191.         //如果是最后一个，直接进行尾部删除
  192.         push_back(list, x);
  193.     }else{ 
  194.         //p后继的前驱指向p的前驱
  195.         p->next->prior = p->prior;
  196.         //p前驱的后继指向p的后继
  197.         p->prior->next = p->next;
  199.         list->size --;
  200.     }
  201. }
  203. //10.排序
  204. void sort(List *list){ 
  205.     if (list->size <= 1) { 
  206.         printf("无须排序！\n");
  207.         return;
  208.     }
  210.     //将链表分为两个部分,s单独作为一个链表，p指向后续结点
  211.     Node *s = list->first->next;
  212.     Node *p = s->next;
  213.     //将后续结点的最后一个结点的next指针标记为空
  214.     list->last->next = NULL;
  216.     //重新设置last指针的值
  217.     list->last = s;
  219.     //让链表循环
  220.     //s的后继指向头结点
  221.     //list->last->next = list->first;
  222.     s->next = list->first;
  223.     //头结点的前驱指向s
  224.     //list->first->prior = list->last;
  225.     list->first->prior = s;
  227.     while (p != NULL) { 
  228.         s = p;
  229.         p = p->next;
  231.         //直接进行按值插入
  232.         insert_val(list, s->data);
  233.         free(s);
  234.         list->size --;
  235.     }
  238. }
  239. //11.逆置(前后转换
  240. void resver(List *list){ 
  241.     if (list->size <= 1) { 
  242.         printf("无须逆置！\n");
  243.         return;
  244.     }
  246.     //将链表分为两个部分,s单独作为一个链表，p指向后续结点
  247.     Node *s = list->first->next;
  248.     Node *p = s->next;
  249.     //将后续结点的最后一个结点的next指针标记为空
  250.     list->last->next = NULL;
  252.     //重新设置last指针的值
  253.     list->last = s;
  255.     //让链表循环
  256.     //s的后继指向头结点
  257.     //list->last->next = list->first;
  258.     s->next = list->first;
  259.     //头结点的前驱指向s
  260.     //list->first->prior = list->last;
  261.     list->first->prior = s;
  263.     while (p != NULL) { 
  264.         s = p;
  265.         p = p->next;
  267.         //直接进行头部插入
  268.         push_fount(list, s->data);
  269.         free(s);
  270.         list->size --;
  271.     }
  272. }
  273. //12.清除单链表 ->只清除数据，保留头结点
  274. void clearList(List *list){ 
  275.     if (list->size == 0) { 
  276.         return;
  277.     }
  279.     Node *s = list->first;
  280.     Node *p = s->next;
  281.     //遍历整个链表，释放结点
  282.     while (p != list->first) { 
  283.         s = p;
  284.         p = p->next;
  285.         free(s);
  286.         list->size --;
  287.     }
  289.     //重新设置last指针
  290.     list->last = list->first;
  291.     //使链表循环
  292.     list->first->prior = list->last;
  293.     list->last->next = list->first;
  295. }
  296. //13.摧毁 ->包括头结点在内一起摧毁
  297. void destroy(List *list){ 
  298.     clearList(list);
  299.     free(list->first);
  301.     list->first = list->last = NULL;
  302. }
  305. //生成一个结点
  306. Node* getNode(ElemType x){ 
  307.     //申请空间
  308.     Node *s = (Node *)malloc(sizeof(Node));
  309.     assert(s != NULL);
  311.     //赋初值
  312.     s->data = x;
  313.     s->prior = s->next = NULL;
  315.     //返回
  316.     return s;
  317. }

Main.cpp

  1. #include "DCList.h"
  3. int main(int argc, const char * argv[]) { 
  5.     List myList;
  6.     InitDCList(&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.        }
  106.     return 0;
  107. }

发表评论

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

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

相关阅读