C++数据结构之约瑟夫环

2009级数据结构实验报告实验名称：实验线性表实现约瑟夫问题求解学生姓名：桂柯易班级：2009211120班内序号：07学号：09210580日期：2010年10月31日1.实验要求【实验目的】1．熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法；2．学习指针、模板类、异常处理的使用；3．掌握线性表的操作实现方法；4．培养使用线性表解决实际问题的能力。【实验内容】利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：已知n个人（n=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列。他的下一个人又从1开始报数，数到m的那个人又出列。依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。2.程序分析2.1存储结构存储结构：循环链表2.2关键算法分析123n……first【设计思想】首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：structNode{intnumber;Node*next;};其次，建立一个不带头结点的循环链表并由头指针first指示。最后，设计约瑟夫环问题的算法。【伪代码】1、工作指针first，r，s，p，q初始化2、输入人数（n）和报数（m）3、循环n次，用尾插法创建链表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);}4、输入报数的起始人号数k;5、Node*q=newNode;计数器初始化i=1;6、循环n次删除结点并报出位置（其中第一个人后移k个）当in时移动指针m-2次p=p-next;删除p结点的后一结点qq=p-next;p-next=q-next;*L=p-next;报出位置后Deleteq;计数器i++;【复杂度】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;}时间复杂度：O（n）if(i==1)i+=LengthList(*L);Node*p;p=*L;intj=0;while(ji-2){p=p-next;j++;}q=p-next;p-next=p-next-next;*L=p-next;return(q);时间复杂度：O（n2）算法的空间复杂度：O（n2）2.3其他程序源代码：#includeiostreamusingnamespacestd;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()//主函数{Node*L;L=NULL;//初始化尾指针intn,m;cout请输入人数N：;cinn;//环的长度if(n1){cout请输入正整数!;}//人数异常处理else{cout请输入所报数M：;cinm;if(m1){cout请输入正整数!;}//号数异常处理else{L=CreateList(L,n,m);//重新给尾指针赋值Joseph(L,n,m);}}system(pause);}Node*CreateList(Node*L,int&n,int&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尾指针异常!endl;//尾指针异常处理}voidJoseph(Node*L,intn,intm)//输出每次出列的人{intk;cout请输入第一个报数人：;cink;if(k1||kn){cout请输入1-n之间的数endl;}else{cout\n出列顺序:\n;for(inti=1;in;i++){Node*q=newNode;if(i==1)q=DeleteList(&L,k+m-1,q);//第一个出列人的号数elseq=DeleteList(&L,m,q);cout号数：q-numberendl;deleteq;//释放出列人的存储空间}cout最后一个出列号数是：L-numberendl;;//输出最后出列人的号数}}Node*DeleteList(Node**L,inti,Node*q)//寻找每次出列的人{if(i==1)i+=LengthList(*L);//顺序依次出列情况的处理方式Node*p;p=*L;intj=0;while(ji-2){p=p-next;j++;}q=p-next;p-next=p-next-next;*L=p-next;return(q);}intLengthList(Node*L)//计算环上的人数{if(L){cout尾指针错误!endl;}//异常处理else{inti=1;Node*p=L-next;while(p!=L){i++;p=p-next;}return(i);}}3.程序运行结果1.测试主函数流程：开始输入m和n创建链表kn-1移动指针p删除p后一结点q指针p后移，k++输出n结束YN2.测试条件：如上图所示，人数为20人，所报数为6，第一个报数的人是1号。3.测试结论：得出最后出列的人是20号，与算得的结果一致，证明程序正常运行，能够解决一般的约瑟夫环问题。4.总结1.调试时出现的问题及解决办法：利用带头结点的尾插法建立链表求解的时候，头节点的作用无法确定，导致编译通过，但是运行之后的结果都不是正确的运行结果。苦苦思索，包括和同学讨论，一直没能解决，最后决定改用另一种存储方法，将头节点直接改成NULL，最终测试的结果是正确的。（但是还未能完全理解原因是什么）用函数返回存储节点的地址的时候，函数中的一句没有问题的语句出现访问错误，更改函数从而解决了问题。2.心得体会：这次做数据结构作业，不仅对开学一段时间内所学的知识有了更好的理解，而且很好地锻炼了自己的编程能力。发现心中了解程序的主要算法和真正写出来完全不是一回事，一开始做多项式的时候就是先写函数，后定义存储结构等，结果编译报错很多，不知道怎么修改，无奈只好改成做约瑟夫环问题了。在编程和写报告的过程中曾多次遇到各种各样的问题，通过与同学的交流以及自己独立思考，最终得到解决并顺利的完成了此次作业。总之一句话，获益良多。3.下一步的改进：下次作业如果时间允许的话，我要选择最难的，而且要全程独立去编，实在解决不了的问题才去请教老师或者同学。