循环链表示例：求解约瑟夫问题

短命女 2022-06-07 00:12 94阅读 0赞

错误：Debug Assertion Failed！
这里写图片描述
今天花了好久才解决了本篇文章中的一个错误，代码bug当然是不可避免的，但是我们可以尽可能的优化他，减少他。
错误分析：主要原因是求解约瑟夫环的问题时，使用了我上一篇文章的循环单链表的模板类，但是我在实际求解中并没有用模板类中的Remove（删除）这个成员函数（不用是因为我定义的删除函数本身的局限性造成的），直接是
preNode = currNode;
currNode =currNode->link;
也就是直接把前后两个节点建立连接，再释放要删除的节点，那么问题来了，这个时候私有成员last（即始终指向循环单链表尾节点的指针）并没有得到更新，也就是说last指向的节点在早已经被delete（释放）了，在主函数main返回的时候，系统调用析构函数的时候会对last指向的节点再一次释放，图中错误就应运而生了！（这是我一个多小时的分析结果，如有不当，希望大牛指正！）。下面贴出错误处的代码：
析构函数
约瑟夫处理函数中的错误
好了，现在贴出整个约瑟夫问题的处理（包括循环单链表的模板类和主函数），约瑟夫环是循环单链表的一个重要应用，也是一个很实用的问题，希望大家都能够掌握，如有不当，万望指正、批评！
//模板类

  1. //循环链表模板class
  2. #include <iostream>
  3. using namespace std;
  5. template<class T>
  6. struct CircleLinkNode {
  7.     T data;
  8.     CircleLinkNode<T> *link;
  9.     //构造函数
  10.     CircleLinkNode(CircleLinkNode<T> * next = NULL) : link(next) {}
  11.     CircleLinkNode(T d, CircleLinkNode<T> * next = NULL) : data(d), link(next) {}
  12. };
  14. template<class T>
  15. class CircleList {
  16. public:
  17.     CircleList(const T & x);                        //构造函数
  18.     CircleList(CircleList<T> & L);                  //复制构造函数
  19.     ~CircleList();                                 //析构函数
  20.     int Length() const;                             //计算循环链表的长度
  21.     bool IsEmpty()
  22.     {
  23.         return first->link == first ? true : false; //判断是否是空表
  24.     }
  25.     CircleLinkNode<T> * getHead() const;            //返回附加头节点的地址
  26.     void setHead(CircleLinkNode<T> * p);            //设置附加头节点的地址
  27.     CircleLinkNode<T> * Search(T x);                //搜索含数据x的节点
  28.     CircleLinkNode<T> * Locate(int i);              //搜索第i个元素的地址
  29.     T getData(int i);                               //取出第i个元素的值
  30.     void setData(int i, T & x);                     //用修改第i个元素的值
  31.     bool Insert(int i, T & x);                      //在第i个元素后插入x
  32.     bool Remove(int i, T & x);                      //删除第i个元素，用x保存删除的数据
  33.     void createList(T endFlag);                     //创建单链表
  34.     void outputList(int stopSequence);
  35. protected:
  36.     CircleLinkNode<T> *first, *last;                //头指针、尾指针
  37. };
  39. //函数定义
  40. template<class T>
  41. CircleList<T>::CircleList(const T & x) {
  42.     //构造函数: 开辟头节点并赋值
  43.     first = new CircleLinkNode<T>(x);
  44.     first->link = first;
  45.     last = first;
  46. } 
  48. template<class T> 
  49. CircleList<T>::~CircleList() {
  50.     //释放相应的资源
  51.     //if (last != first) {
  53.     //  delete last;
  54.     //}
  55.     delete first;
  56. }
  58. template<class T>
  59. CircleLinkNode<T> * CircleList<T>::getHead() const {
  60.     //得到函数的头指针
  61.     return first;
  62. }
  64. template<class T>
  65. int CircleList<T>::Length() const {
  66.     //计算链表的长度
  67.     CircleLinkNode<T> *calculLen = NULL;
  68.     int Len = 0;
  69.     calculLen = first->link;
  70.     while (calculLen != first) {                    //当再一次循环到first时，返回计数长度
  71.         Len++;
  72.         calculLen = calculLen->link;
  73.     }
  74.     return Len;
  75. }
  77. template<class T>
  78. CircleList<T>::CircleList(CircleList<T> &L) {
  79.     //复制构造函数
  80.     int Len = Length();                             //得到当前链表的长度
  81.     CircleLinkNode<T> *create = NULL, *destData, *srcData;
  82.     create = new CircleLinkNode<T>(0);
  83.     if (!create) {
  84.         cerr << "内存分配错误" << endl;
  85.         exit(1);
  86.     }
  87.     last = create;                                  //标记尾节点
  88.     for (int i = 0; i < Len - 1; i ++) {
  89.         create->link = first->link;
  90.         first->link = create;
  91.         create = new CircleLinkNode<T>(0);
  92.         if (!create) {
  93.             cerr << "内存分配错误" << endl;
  94.             exit(1);
  95.         }
  96.     }
  97.     //将L中的data域逐一copy到当前链表中
  98.     copyData = first->link;
  99.     srcData = L.first->link;
  100.     while (srcData == L.first) {
  101.         destData->data = srcData->data;
  102.         destData = destData->link;
  103.         srcData = srcData->link;
  104.     }
  105.     //构建循环链表
  106.     last->link = first;
  107. }
  109. template<class T>
  110. CircleLinkNode<T> * CircleList<T>::Search(T x) {
  111.     //查找数据域为x的节点并返回其地址
  112.     CircleLinkNode<T> * current = NULL;
  113.     current = first->link;
  114.     while (current != first) {
  115.         if (current->data == x) {
  116.             break;
  117.         }
  118.         current = current->link;
  119.     }
  120.     return current;
  121. }
  123. template<class T>
  124. CircleLinkNode<T> * CircleList<T>::Locate(int i) {
  125.     //定位函数， 返回第i个节点的地址，可供插入与删除函数用
  126.     if (i < 0 || i > Length()) {
  127.         cout << "数据不合法" << endl;
  128.         cin >> i;
  129.         return NULL;
  130.     }
  131.     CircleLinkNode<T> * current = NULL;
  132.     current = first;
  133.     for (int j = 0; j < i; j ++) {
  134.         current = current->link;
  135.     }
  136.     return current;
  137. }
  139. template<class T>
  140. void CircleList<T>::createList(T endFlag) {
  141.     //逆序创建单链表
  142.     T inputData = 0;
  143.     CircleLinkNode<T> *create = NULL;
  144.     cin >> inputData;
  145.     create = new CircleLinkNode<T>(inputData);      //在循环外侧创建尾节点
  146.     if (!create) {
  147.         cerr << "内存分配错误" << endl;
  148.         exit(1);
  149.     }
  150.     last = create;                                  //标记尾节点
  151.     while (inputData != endFlag) {                  //是否满足结束条件
  152.         create->link = first->link;                 //建立链接
  153.         first->link = create;
  154.         cin >> inputData;
  155.         create = new CircleLinkNode<T>(inputData);  //依次建立其他节点
  156.         if (!create) {
  157.             cerr << "内存分配错误" << endl;
  158.             exit(1);
  159.         }
  160.     }
  161.     //单链表建立完成
  162.     last->link = first;                             //构建循环链表
  163. }
  165. template<class T>
  166. T CircleList<T>::getData(int i) {
  167.     CircleLinkNode<T> * current;
  168.     current = Locate(i);                            //定位函数调用
  169.     return current->data;
  170. }
  172. template<class T>
  173. void CircleList<T>::setData(int i, T & x) {
  174.     //设置第i个节点的数据域为x
  175.     CircleLinkNode<T> * current = NULL;
  176.     current = Locate(i);
  177.     current->data = x;                              //完成修改
  178. }
  180. template<class T>
  181. bool CircleList<T>::Insert(int i, T & x) {
  182.     //在第i个节点后插入新的节点，并使其数据域赋值为x
  183.     CircleLinkNode<T> * flagPtr;
  184.     CircleLinkNode<T> * newNode = new CircleLinkNode<T>(x);
  185.     if (!newNode) {                                 //内存分配错误
  186.         return false;
  187.     }
  188.     if (0 == i) {                                   //插入在首位置
  189.         newNode->link = first->link;
  190.         first->link = newNode;
  191.     }
  192.     else {
  193.         flagPtr = Locate(i);
  194.         newNode->link = flagPtr->link;
  195.         flagPtr->link = newNode;
  196.     }
  197.     //更新last指向的节点
  198.     last = Locate(Length());
  199.     return true;
  200. }
  202. template<class T>
  203. bool CircleList<T>::Remove(int i, T & x) {
  204.     //删除第i个节点并将删除的数据存储在x当中
  205.     CircleLinkNode<T> *preNode = NULL, *delNode = NULL;
  206.     preNode = Locate(i - 1);
  207.     delNode = Locate(i);
  208.     preNode->link = delNode->link;
  209.     delete delNode;
  210.     return true;
  211. }
  213. template<class T>
  214. void CircleList<T>::outputList(int stopSequence) {
  215.     if (first == first->link) {
  216.         cout << "此为空表" << endl;
  217.         return;
  218.     }
  219.     //输出循环链表,直到指定序号停止输出(方便测试循环特性)
  220.     CircleLinkNode<T> * current = NULL;
  221.     current = first->link;
  222.     for (int i = 0; i < stopSequence; i ++) {
  223.         cout << current->data << " ";
  224.         current = current->link;
  225.         if (current == first) {
  226.             current = current->link;                //跳过first的输出
  227.         }
  228.     }
  229.     cout << endl;
  230. }

主函数及约瑟夫处理函数测试

  1. //循环链表实例，求解约瑟夫问题
  2. #include <iostream>
  3. #include "CircleList.cpp"
  4. using namespace std;
  5. template<class T>
  6. void Josephus(CircleList<T> & js, int n, int m);
  7. int main()
  8. {
  9.     CircleList<int> circle(0);
  10.     int nodesAmount = 0, delSequence = 0, data = 0, sotre;
  11.     cout << "输入游戏人数和报数间隔 ：" << endl;
  12.     cin >> nodesAmount >> delSequence; 
  13.     for (int i = 0; i < nodesAmount; i ++) {                    //形成约瑟夫环
  14.         data = i + 1;
  15.         circle.Insert(i, data);
  16.     }
  17.     Josephus(circle, nodesAmount, delSequence);                 //解决约瑟夫问题
  19.     system("pause");
  20.     return 0;
  21. } 
  22. template<class T>
  23. void Josephus(CircleList<T> & js, int n, int m) {
  24.     //用来求解约瑟夫问题
  25.     //参数 ： 循环链表、节点数、节点的删除间隔
  26.     CircleLinkNode<T> *preNode = NULL, *currNode = NULL;        //定义两个标志节点
  27.     preNode = js.getHead();
  28.     currNode = preNode->link;
  29.     for (int i = 0; i < n - 1; i ++) {                          //循环n - 1次，最后只剩下一个节点
  30.         for (int j = 0; j < m - 1; j ++) {                      //每次进行一个报数循环
  31.             if (currNode == js.getHead()) {
  32.                 preNode = currNode;
  33.                 currNode = currNode->link; 
  34.             }
  35.             //开始删除报数后的节点
  36.             preNode = currNode;
  37.             currNode = currNode->link;
  38.             if(currNode == js.getHead()) {
  39.                 preNode = currNode;
  40.                 currNode = currNode->link;
  41.             }
  42.         }
  43.         cout << "删除的数据是 ： " << currNode->data << endl;
  44.         preNode->link = currNode->link;
  45.         delete currNode;
  46.         currNode = preNode->link;                               //这步毋漏
  47.     }
  48. }

正常运行结果显示：这里写图片描述
数据结构需要大量的时间实践与研究，希望我们能够多花点时间练习，珍惜当前的时间，做任何一件事都应该有目标！

发表评论

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

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

相关阅读