devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构学习-循环链表：处理约瑟夫环问题_循环链表约瑟夫环

作者：Gausst松鼠会 | 2024-05-07 21:01:35

赞

踩

循环链表约瑟夫环

目录

问题描述

一、基本概念

 1.普通链表

2.单向循环链表 

二、问题处理

1.创建链表

2.查找

3.删除

 4.其他

 三.实验环节

四.总结

问题描述

约瑟夫环问题的一种描述是：编号为1，2，...，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。

基本要求：利用链表模拟此过程，按照出列的顺序印出各人的编号。

一、基本概念

链表是一种链式存储的线性表，用一组地址任意的存储单元存放线性表的数据元素，称存储单元为一个结点（节点）。单向循环链表与普通链表的区别在于：普通链表的最后一个链表的next指向NULL，而单向循环链表的最后一个节点的next指向头结点

 1.普通链表

2.单向循环链表 

 

二、问题处理

1.创建链表

首先因为处理问题时，链表元素的访问并不是从头开始的，而是采用“接力棒”的方式进行访问。所以应该使用不带有头结点的单向循环链表。

代码如下： 

  1. typedef struct Data
  2. {
  3.     int number; // 编号
  4.     int code;   // 密码
  5.     /*
  6.         存放数据
  7.     */
  8. } Data;
  9. typedef struct SqList
  10. {
  11.     Data data;    // 数据域
  12.     SqList *next; // 指针域
  13. } SqList;
  14.  
  15. SqList *CreateList(int n) // 生成一个不带头节点的n个元素的循环链表
  16. {
  17.     if (n < 1) // 输入的n不合法
  18.     {
  19.         printf("输入不合法！");
  20.         system("pause");
  21.         return NULL;
  22.     }
  23.     SqList *end = new SqList; // 尾指针
  24.     for (int i = 1; i < n + 1; i++)
  25.     {
  26.         SqList *newNode = (SqList *)malloc(sizeof(SqList *));
  27.         if (i == 1) // 链表为空时输入首元节点的密码
  28.         {
  29.             newNode->next = newNode;
  30.             cout << "请输入成员" << i << "的密码：";
  31.             cin >> newNode->data.code;
  32.             newNode->data.number = 1;
  33.             end = newNode;
  34.             continue;
  35.         }
  36.         // 链表不为空时输入newNode数据的密码
  37.         cout << "请输入成员" << i << "的密码：";
  38.         cin >> newNode->data.code;
  39.         newNode->data.number = i;
  40.         // 尾插法构建链表
  41.         newNode->next = end->next;
  42.         end->next = newNode;
  43.         end = newNode;
  44.     }
  45.     return end->next;
  46. }

这里需要注意的是因为编号是有序的——按顺时针方向，所以采用尾插法。

2.查找

代码如下：

  1. SqList *ListSearch(SqList *L, int k) // 返回链表中的第k个元素
  2. {
  3.     if (!L || k < 1 || k > ListLength(L)) // 链表为空或输入的k值不合法
  4.     {
  5.         cout << "Error3!" << endl;
  6.         system("pause");
  7.         exit(0);
  8.     }
  9.     for (int i = 0; i < k - 1; i++)
  10.     {
  11.         L = L->next;
  12.     }
  13.     return L;
  14. }

3.删除

代码如下：

  1. SqList *ListDelete(SqList *L, int n) // 删除链表L中指定的第n个元素
  2. {
  3.     if (!L || n < 1) // 链表为空或删除位置不合法
  4.     {
  5.         cout << "Error2!" << endl;
  6.         system("pause");
  7.         exit(0);
  8.     }
  9.     SqList *front = L;
  10.     SqList *temp = nullptr;         // 暂时储存要删除的元素
  11.     for (int i = 0; i < n - 1; i++) // 移动指针到要删除的位置上
  12.     {
  13.         L = L->next;
  14.     }
  15.     while (front->next != L) // 寻找要删除的元素前面的一个元素
  16.     {
  17.         front = front->next;
  18.     }
  19.     front->next = L->next; // 将要删除的元素移出链表
  20.     temp = L;
  21.     L = L->next;
  22.     free(temp); // 释放内存
  23.     return L;
  24. }

因为采用“接力棒”的方式访问元素，需要记住被删除元素的后一个元素。所以返回指针类型。

 4.其他

代码如下：

  1. int ListLength(SqList *L) // 返回链表长度
  2. {
  3.     if (!L) // 输入空链表时报错并退出函数
  4.     {
  5.         cout << "Error1!";
  6.         system("pause");
  7.         exit(0);
  8.     }
  9.     SqList *F_Node = L;
  10.     int count = 1; // 因为不带头节点的链表，所以非空时链表节点个数至少为1
  11.     while (L->next != F_Node)
  12.     {
  13.         count++;
  14.         L = L->next;
  15.     }
  16.     return count;
  17. }
  18.  
  19. void ListPrint(SqList *L) // 打印链表L中的元素
  20. {
  21.     if (!L)
  22.     {
  23.         return;
  24.     }
  25.     SqList *Node = L;
  26.     do
  27.     {
  28.         if (Node->next == L)
  29.         {
  30.             cout << "成员" << Node->data.number << "的密码：" << Node->data.code << "\t";
  31.             return;
  32.         }
  33.         cout << "成员" << Node->data.number << "的密码：" << Node->data.code << "\t";
  34.         Node = Node->next;
  35.     } while (1);
  36.     return;
  37. }
  38.

 三.实验环节

整体代码：

  1. /*
  2.     整个实验重要的步骤就是创建、查找、删除
  3. */
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. typedef struct Data
  8. {
  9.     int number; // 编号
  10.     int code;   // 密码
  11.     /*
  12.         存放数据
  13.     */
  14. } Data;
  15. typedef struct SqList
  16. {
  17.     Data data;    // 数据域
  18.     SqList *next; // 指针域
  19. } SqList;
  20.  
  21. SqList *CreateList(int n) // 生成一个不带头节点的n个元素的循环链表
  22. {
  23.     if (n < 1) // 输入的n不合法
  24.     {
  25.         printf("输入不合法！");
  26.         system("pause");
  27.         return NULL;
  28.     }
  29.     SqList *end = new SqList; // 尾指针
  30.     for (int i = 1; i < n + 1; i++)
  31.     {
  32.         SqList *newNode = (SqList *)malloc(sizeof(SqList *));
  33.         if (i == 1) // 链表为空时输入首元节点的密码
  34.         {
  35.             newNode->next = newNode;
  36.             cout << "请输入成员" << i << "的密码：";
  37.             cin >> newNode->data.code;
  38.             newNode->data.number = 1;
  39.             end = newNode;
  40.             continue;
  41.         }
  42.         // 链表不为空时输入newNode数据的密码
  43.         cout << "请输入成员" << i << "的密码：";
  44.         cin >> newNode->data.code;
  45.         newNode->data.number = i;
  46.         // 尾插法构建链表
  47.         newNode->next = end->next;
  48.         end->next = newNode;
  49.         end = newNode;
  50.     }
  51.     return end->next;
  52. }
  53. int ListLength(SqList *L) // 返回链表长度
  54. {
  55.     if (!L) // 输入空链表时报错并退出函数
  56.     {
  57.         cout << "Error1!";
  58.         system("pause");
  59.         exit(0);
  60.     }
  61.     SqList *F_Node = L;
  62.     int count = 1; // 因为不带头节点的链表，所以非空时链表节点个数至少为1
  63.     while (L->next != F_Node)
  64.     {
  65.         count++;
  66.         L = L->next;
  67.     }
  68.     return count;
  69. }
  70. void ListPrint(SqList *L) // 打印链表L中的元素
  71. {
  72.     if (!L)
  73.     {
  74.         return;
  75.     }
  76.     SqList *Node = L;
  77.     do
  78.     {
  79.         if (Node->next == L)
  80.         {
  81.             cout << "成员" << Node->data.number << "的密码：" << Node->data.code << "\t";
  82.             return;
  83.         }
  84.         cout << "成员" << Node->data.number << "的密码：" << Node->data.code << "\t";
  85.         Node = Node->next;
  86.     } while (1);
  87. }
  88.  
  89. void ListInsert(SqList *L, Data elem, int a) // 向链表L中第a个位置后面插入数据elem
  90. {
  91.     for (int i = 0; i < a - 1; i++)
  92.     {
  93.         L = L->next;
  94.     }
  95.     if (!L)
  96.     {
  97.         return;
  98.     }
  99.     SqList *newNode = new SqList;
  100.     newNode->data = elem;
  101.     newNode->next = L->next;
  102.     L->next = newNode;
  103. }
  104.  
  105. SqList *ListDelete(SqList *L, int n) // 删除链表L中指定的第n个元素
  106. {
  107.     if (!L || n < 1) // 链表为空或删除位置不合法
  108.     {
  109.         cout << "Error2!" << endl;
  110.         system("pause");
  111.         exit(0);
  112.     }
  113.     SqList *front = L;
  114.     SqList *temp = nullptr;         // 暂时储存要删除的元素
  115.     for (int i = 0; i < n - 1; i++) // 移动指针到要删除的位置上
  116.     {
  117.         L = L->next;
  118.     }
  119.     while (front->next != L) // 寻找要删除的元素前面的一个元素
  120.     {
  121.         front = front->next;
  122.     }
  123.     front->next = L->next; // 将要删除的元素移出链表
  124.     temp = L;
  125.     L = L->next;
  126.     free(temp); // 释放内存
  127.     return L;
  128. }
  129.  
  130. SqList *ListSearch(SqList *L, int k) // 返回链表中的第k个元素
  131. {
  132.     if (!L || k < 1 || k > ListLength(L)) // 链表为空或输入的k值不合法
  133.     {
  134.         cout << "Error3!" << endl;
  135.         system("pause");
  136.         exit(0);
  137.     }
  138.     for (int i = 0; i < k - 1; i++)
  139.     {
  140.         L = L->next;
  141.     }
  142.     return L;
  143. }

测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4

（正确的出列顺序应为6，1，4，7，2，3，5）。 

测试如下：

  1. #define N 7 // 约瑟问题中的人数
  2.  
  3. int main(void)
  4. {
  5.     SqList *List = CreateList(N);
  6.     int res[N]; // 存放出列顺序
  7.     int m, i = 0, code = 0;
  8.     cout << "请输入初始的正整数密码m" << endl;
  9.     cin >> m;
  10.     while (ListLength(List) != 1)
  11.     {
  12.         int k = 0;
  13.         m = m % (N - i);
  14.         // cout << "当前m的值是：" << m << endl;
  15.         /*
  16.             注意在这里m的取值是[0,N-i-1],
  17.             而实际上m应该属于[1,N-i]。
  18.             所以需要对求模后的m进行条件判断
  19.         */
  20.         if (m == 0)        
  21.         {
  22.             k = N - i;
  23.         }
  24.         else
  25.             k = m;
  26.         code = ListSearch(List, k)->data.code;
  27.         res[i] = ListSearch(List, k)->data.number;
  28.         List = ListDelete(List, k); // 返回新的起始访问位置
  29.         m = code;
  30.         i++;
  31.     }
  32.     res[i] = ListSearch(List, 1)->data.number; //此时链表中仅有一个元素
  33.     cout << "出列顺序为:";
  34.     for (int i = 0; i < N; i++)
  35.         cout << res[i] << "\t";
  36.     free(List); // 释放内存
  37.     return 0;
  38. }

 

四.总结

该问题的难点就在于元素的访问是采取“接力棒”的方式进行访问，需要对循环链表有足够的的理解，同时对密码的处理上也需要小心。对于本次实验来说，还有许多能改进的地方，比如非法输入的检测，可以把它包装成一个函数，这样处理的话，代码会更简洁并且更容易阅读。

如有错误，欢迎在评论区指正。以上内容若涉及侵权请联系作者进行删改。 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/551217
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号