约瑟夫环问题源代码(C语言).doc

《约瑟夫环问题源代码(C语言).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、约瑟夫环问题如下：已知n个人(n>=1)围桌一园桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列。他的下一个人又从1开始报数，数到m的那个人又出列。依此规则重复下去，直到所有人全部出列。求解最后一个出列的人的编号。本次实验是以顺序表求解约瑟夫环问题，程序流程图及程序运行结果如下：存储并建立一个约瑟夫环通过循环结构依次查找每次出列的人的编号并输出输入人数、所报数、第一个报数人编号输出最后一个出列的人的编号程序代码如下：#include#include#include<

2、stdlib.h>usingnamespacestd;structNode//循环节点的定义{intnumber;//编号Node*next;};Node*CreateList(Node*L,int&n,int&m);//建立约瑟夫环函数voidJoseph(Node*L,intn,intm);//输出每次出列号数函数Node*DeleteList(Node**L,inti,Node*q);//寻找每次出列人的号数intLengthList(Node*L);//计算环上所有人数函数voidmain()//主函数{system("co

3、lor75");//设置颜色以美观Node*L;L=NULL;//初始化尾指针intn,m;cout<<"请输入人数N：";cin>>n;//环的长度if(n<1){cout<<"请输入正整数!";}//人数异常处理else{cout<<"请输入所报数M：";cin>>m;if(m<1){cout<<"请输入正整数!";}//号数异常处理else{L=CreateList(L,n,m);//重新给尾指针赋值Joseph(L,n,m);}}system("pause");}Node*CreateList(Node*L,int&n,in

4、t&m)//建立一个约瑟夫环（尾插法）{Node*q;for(inti=1;i<=n;i++){Node*p;p=newNode;p->number=i;p->next=NULL;if(i==1)L=q=p;//工作指针的初始化else{q->next=p;q=q->next;}}q->next=L;if(L!=NULL){return(L);}//返回尾指针elsecout<<"尾指针异常!"<

5、入第一个报数人：";cin>>k;if(k<1

6、

7、k>n){cout<<"请输入1-"<number<number<

8、next;j++;}q=p->next;p->next=p->next->next;*L=p->next;return(q);}intLengthList(Node*L)//计算环上的人数{if(L){cout<<"尾指针错误!"<

9、/异常处理else{inti=1;Node*p=L->next;while(p!=L){i++;p=p->next;}return(i);}}实验体会：通过对本问题的分析，我进一步熟悉了对各种逻辑表达式的判断和指针的使用。本程序分为输入模块、处理模块、输出模块，主函数按运行流程依次调用各方法。本程序可以很好地运行，还具有一定的排错能力，稳定性好，如下图所示：