数据结构（4）线性表之单循环链表

喜欢ヅ旅行 2023-08-17 16:50 273阅读 0赞

数据结构（4）线性表之单循环链表

      • 前言
      • 尾指针
      • 注
      • 全部代码
        • SCList.h
        • SCList.cpp
        • Main.cpp

前言

所谓单循环链表，实际上就是在单链表的基础上，使最后一个结点的next指针再指向头结点，形成循环的效果。这样，从表中任何一个结点出发都可以找到其他结点的位置。

尾指针

顾名思义，尾指针是指向链表的最后一个结点。在单循环链表中，设立尾指针能使得一些操作简化，例如两个单循环链表的合并。

img\_2

img\_3

注

我们之前所写的管理结构，是既包括头指针又包括尾指针的，因此在实现某些操作时就很方便了。

单循环链表和单链表的实现思路、注意事项都是一样的，只是需要额外注意的是，在我们的管理结构中要注意保持last的next指针始终指向头结点，达到循环的效果。

附：单链表的实现思路及注意事项
数据结构（2.1）线性表之单链表的表示和实现
数据结构（2.2）线性表之单链表的具体实现

  • 链表为空

链表为空

  • 链表非空

链表非空

全部代码

单循环链表的各项操作与单链表并无差别，只是在判断链表结束的条件有差别，之前是判断next指针是否为空，现在需要判断是否为头结点。因此实现代码并没有巨大的改变，只是在一些判断条件上做出改变。

SCList.h

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

SCList.cpp

  1. #include "SCList.h"
  3. //初始化单循环链表
  4. void InitSCList(List *list){ 
  5.     Node *s = (Node *)malloc(sizeof(Node));
  6.     assert(s != NULL);
  7.     list->first = list->last = s;
  9.     //让最后一个结点的next指向头部，形成循环
  10.     list->last->next = list->first;
  11.     list->size = 0;
  12. }
  14. //1.尾部插入
  15. void push_back(List *list,ElemType x){ 
  16.     Node *s = getNode(x);
  18.     //将这个结点接到链表尾部
  19.     list->last->next = s;
  21.     //重新设置last指针的指向
  22.     list->last = s;
  24.     //让最后一个结点的next指向头部，形成循环
  25.     list->last->next = list->first;
  26.     list->size ++;
  27. }
  30. //2.头部插入
  31. void push_fount(List *list,ElemType x){ 
  32.     Node *s = getNode(x);
  34.     s->next = list->first->next;
  35.     list->first->next = s;
  37.     //判断是否是第一个结点
  38.     if (list->last == list->first) { 
  39.         //是，更改last指针的指向
  40.         list->last = s;
  41.     }
  43.     list->size ++;
  44. }
  46. //3.展示
  47. void show_list(List *list){ 
  48.     Node *p = list->first->next;
  50.     while (p != list->first) { 
  51.         printf("%4d",p->data);
  52.         p = p->next;
  53.     }
  54.     printf("\n");
  55. }
  58. //4.尾部删除
  59. void pop_back(List *list){ 
  60.     if (list->size == 0) { 
  61.         printf("无可删除的结点！\n");
  62.         return;
  63.     }
  65.     //寻找倒数第二个结点
  66.     Node *p = list->first;
  67.     while (p->next != list->last) { 
  68.         p = p->next;
  69.     }
  71.     //释放它后一个结点(即最后一个结点)
  72.     free(list->last);
  73.     //更改last指针的指向
  74.     list->last = p;
  75.     //让最后一个结点的next指向头部，形成循环
  76.     list->last->next = list->first;
  77.     list->size --;
  78. }
  80. //5.头部删除
  81. void pop_fount(List *list){ 
  82.     if (list->size == 0) { 
  83.         printf("无可删除的结点！\n");
  84.         return;
  85.     }
  87.     Node *p = list->first->next;
  88.     list->first->next = p->next;
  89.     free(p);
  91.     //判断是否是最后一个结点
  92.     if(list->size == 1){ 
  93.         //重新设置last的指向
  94.         list->last = list->first;
  95.     }
  97.     list->size --;
  98. }
  99. //6.按值插入(要求插入前的链表是有序的(此处为顺序
  100. void insert_val(List *list,ElemType x){ 
  101.     Node *p = list->first;
  103.     //寻找插入位置
  104.     while (p->next != list->last && p->next->data < x) { 
  105.         p = p->next;
  106.     }
  108.     //到达了最后一个结点后，还需要与最后一个结点的值进行比较
  109.     //判断是否比最后一个结点大
  110.     if (p->next == list->last && p->next->data < x) { 
  111.         //是，直接进行尾部插入
  112.         push_back(list, x);
  113.     }else{ 
  114.         //其他状况，直接在该位置进行插入
  115.         Node *s = getNode(x);
  117.         s->next = p->next;
  118.         p->next = s;
  119.         list->size ++;
  120.     }
  121. }
  122. //7.按值查找
  123. Node* find(List *list,ElemType x){ 
  124.     if (list->size == 0) { 
  125.         return NULL;
  126.     }
  128.     //遍历整个链表
  129.     Node *p = list->first->next;
  130.     while (p != list->first && p->data != x) { 
  131.         p = p->next;
  132.     }
  134.     //判断是否回到头部
  135.     if (p == list->first) { 
  136.         //是，说明链表中没有要找的数据
  137.         return NULL;
  138.     }else{ 
  139.             return p;
  140.     }
  141. }
  142. //8.获取长度
  143. int length(List *list){ 
  144.     return list->size;
  145. }
  147. //9.按值删除
  148. void  delete_val(List *list,ElemType x){ 
  149.     if (list->size == 0) { 
  150.         printf("链表为空，无法删除！\n");
  151.         return;
  152.     }
  154.     Node *p = find(list, x);
  155.     if (p == NULL) { 
  156.         printf("要删除的数据不存在!\n");
  157.         return;
  158.     }
  160.     //判断是否是最后一个结点
  161.     if (p == list->last) { 
  162.         //是，直接尾部删除
  163.         pop_back(list);
  164.     }else{ 
  165.         //判断是否是倒数第二个结点
  166.         if (p->next == list->last) { 
  167.             //是，需要修改last指针的指向
  168.             list->last = p;
  169.         }
  170.         Node *s = p->next;
  171.         p->data = s->data;
  172.         p->next = s->next;
  173.         free(s);
  174.         list->size --;
  175.     }
  176. }
  178. //10.排序
  179. void sort(List *list){ 
  180.     if (list->size <= 1) { 
  181.         return;
  182.     }
  184.     Node *s = list->first->next;
  185.     Node *q = s->next;
  187.     //将链表尾部断开
  188.     list->last->next = NULL;
  189.     //重新设置last指针
  190.     list->last = s;
  191.     //让链表再次循环
  192.     list->last->next = list->first;
  194.     while (q != NULL) { 
  195.         s = q;
  196.         q = q->next;
  197.         //进行按值插入
  198.         insert_val(list, s->data);
  199.         free(s);
  200.         list->size --;
  202. // //寻找插入位置
  203. // Node *p = list->first;
  204. // while (p->next != list->last && p->next->data < s->data) { 
  205. // p = p->next;
  206. // }
  207. //
  208. // //判断是否是最后一个结点
  209. // if (p->next == list->last && p->next->data < s->data) { 
  210. // //是，直接进行尾部插入
  211. // s->next = list->last->next;
  212. // list->last->next = s;
  213. // list->last = s;
  214. //
  215. // }else{ 
  216. // s->next = p->next;
  217. // p->next = s;
  218. // }
  220.     }
  221. }
  223. //11.逆置(前后转换
  224. void resver(List *list){ 
  225.     if (list->size <= 1) { 
  226.         return;
  227.     }
  229.     Node *s = list->first->next;
  230.     Node *q = s->next;
  232.     list->last->next = NULL;
  233.     list->last = s;
  234.     list->last->next = list->first;
  236.     while (q != NULL) { 
  237.         s = q;
  238.         q = q->next;
  239.         //进行头部插入
  240.         push_fount(list, s->data);
  241.         free(s);
  242.         list->size--;
  244. // //进行头部插入
  245. // s->next = list->first->next;
  246. // list->first->next = s;
  247.     }
  248. }
  250. //12.清除单链表 ->只清除数据，保留头结点
  251. void clearList(List *list){ 
  252.     Node *p = list->first->next;
  253.     while (p != list->first) { 
  254.         p = p->next;
  255.         pop_fount(list);
  256.     }
  258. }
  259. //13.摧毁 ->包括头结点在内一起摧毁
  260. void destroy(List *list){ 
  261.     clearList(list);
  262.     free(list->first);
  263.     list->first = list->last = NULL;
  264. }
  266. //生成一个结点
  267. Node* getNode(ElemType x){ 
  268.     Node *s = (Node *)malloc(sizeof(Node));
  269.     assert(s != NULL);
  271.     s->data = x;
  272.     s->next = NULL;
  274.     return s;
  275. }

Main.cpp

  1. #include "SCList.h"
  3. int main(int argc, const char * argv[]) { 
  5.     List myList;
  6.     InitSCList(&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 条评论，273人围观）

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

相关阅读