1. 首页
  2. IT资讯

Josephus问题解决方法二

前面文章写了关于Josephus问题解决的一种方法http://blog.itpub.net/29876893/viewspace-1815055/,但是由于前面的程序有两处错误已改正(红色字体),由于本人写文章时太粗心!导致运行结果错误,下面修正:(原文已经修正,下面指出已对自己粗心的教训)

点击(此处)折叠或打开

  1. ...
  2.   ...
  3. Note *InitNote(Note *first, int n) {
  4.     Note *head, *p;
  5.     head = first;
  6.     p = NULL;
  7.     cout << “同学开始座次: << endl;
  8.     for (int i = 1; i <= n; i++) { //利用尾插法,构造链表
  9.         p = new Note;
  10.         head>next = p;
  11.         p>data = i;
  12.         cout << p>data << “–> “;
  13.         head = p;
  14.     }
  15.     p>next = first>next; //形成换
  16.     return first; //返回头结点
  17. }
  18. void Search(Note *q, int m) {
  19.      
  20.       ...
  21.     for (int i = 1; q != q>next; q = q>next, i++) {
  22.         if (i == m) { //当i = m时,执行其中的语句,并初始化i = 1,至于原因,读者画图便可知
  23.          ....
  24.         }
  25.     }
  26.    ...
  27. }
  28. int main() {
  29. ...
  30. }

我认为该问题难点在于构造单向循环链表和对链表结点的删除(如何判断删除间隔),下面给出另一种构造单向循环链表的方法:

点击(此处)折叠或打开

  1. #include<iostream>
  2. //#include<stdlib.h>
  3. using namespace std;
  4. struct Note {
  5.     int data;
  6.     struct Note *next;
  7. };
  8. Note *CreateNote() {
  9.     Note *first;
  10.     first = new Note; //first = (Note *)malloc(sizeof(Note));
  11.     //first>data = NULL;
  12.     first>next = new Note;
  13.     return first;
  14. }
  15. void InitNote(Note *first, int n) {
  16.     Note *p;
  17.     p = first;
  18.     cout << “同学开始座次:” << endl;
  19.     for (int i = 1; i <= n; i++) {
  20.         p>next = new Note;
  21.         p = p>next;
  22.         p>data = i;
  23.         cout << p>data << “–>”;
  24.         
  25.     }
  26.     p>next = first>next;
  27.     
  28. }
  29. void Search(Note *first, int m) {
  30.     cout << “依次出列同学:”;
  31.     if (m == 1) {
  32.         cout << “游戏太无聊!”;
  33.         exit(1);
  34.     }
  35.     int i;
  36.     Note *q;
  37.     for (i=1,q = first; q != q>next; q = q>next,i++) {
  38.         if (i == m) {
  39.             i = 1;
  40.             Note *n;
  41.             n = q>next;
  42.             cout<<n>data << “–>”;
  43.             q>next = n>next;
  44.             delete n;
  45.         }
  46.     }
  47.     cout << q>data;
  48.     cout << endl;
  49.     cout << “获胜的是:” << q>data << “号同学” << endl;
  50. }
  51. int main() {
  52.     Note *p;
  53.     p = CreateNote();
  54.     InitNote(p, 5);
  55.     cout << endl;
  56.     Search(p, 2);
  57. }

关于构造单向循环链表,画出图后,会变的简单些,下面简单给出上面的构造循环单链表的示意图(图画的不是太美观~_~):
Josephus问题解决方法二

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/29876893/viewspace-1850077/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:℅傍ㄖ免沦陷dε鬼,转转请注明出处:http://www.cxybcw.com/191806.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code