《数据结构约瑟夫环的课程设计报告.doc》由会员分享，可在线阅读，更多相关《数据结构约瑟夫环的课程设计报告.doc（7页珍藏版）》请在三一办公上搜索。
1、数学与计算机学院数据结构课程设计设计题目：约瑟夫环一选题背景：题目：约瑟夫环问题描述：编号为1,2，.，n的n个人按顺时针方向围坐圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新重新从1报数，如此下去，直至所有人全部出列为止。基本要求： 建立模型，确定存储结构； 对任意 n个人，密码为 m ，实现约瑟夫环问题； 出圈的顺序可以依次输出，也可以用一个数组存储。设计指导思想：首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环
2、性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。 其次，建立一个不带头结点的循环链表并由头指针 first 指示。 最后，设计约瑟夫环问题的算法。下面给出伪代码描述，操作示意图如图 2-1 所示。 二方案论证：本方案通过建立单循环链表模拟了约瑟夫问题；首先，建立一个结构体node，然后给他开辟一个储存空间；利用头指针head标记链表，利用尾指针向后移将建立的结点连接成我们需要的单循环链表，过程如下：约瑟夫问题中的人数个数即为链表的长度，链表中node-num 编号n，node-data为每个人的密码。建立单循环链表后，通过初始报数上限找到出列的结点，输出该结点的nod
3、e-num值，将该结点中的data中数作为新密码开始下一个步的开始，将该结点从链表中删除，并释放该结点的空间。重复此过程，直到剩下最后一个结点，就直接将该结点中的num值输出，删除该结点，并释放该结点的空间。输出的num值即为约瑟夫中人的编号。三过程论述：typedef struct nodeint data;int num;struct node *next;listnode;定义一个结构体用来储存学生的编号和所携带的密码for(i=1;inext=(listnode*)malloc(sizeof(listnode);/建立一个新的空间，并将它的地址赋给p1-next p1=p1-next;
4、 p1-data=j; p1-num=i;/对结点的num和data成员赋值p1-next=head-next;/构成单循环链表定义指针p1，然后建立一个新结点并将p1-next指向它的地址，然后将这个地址赋给p1，最后将head-next赋给p1-next,构成一个单循环链表，并不断在尾部插入新的结点，直至所有人都进入循环链表中，而且在循环的过程中给结点的num和data成员赋值do k=1; while(k!=m)/当k=m时一轮报数结束 p1=p1-next; k+; /报数过程中将指针p1指向下一位 p2=p1-next; p1-next=p2-next;/将报m的人的结点从链表中删去
5、 printf(编号为%d的人出列，他的密码%d作为新的m值n,p2-num,p2-data);/报数为m的人出列 m=p2-data;/报数为m的人的密码作为新的m值 free(p2);/释放报m的人的结点while(p1-next!=p1);/当p1-next指向的地址是它自己的地址，所有报数结束定义指针p1用以循环链表，定义变量k计数，指针p1每移动一次，k加1，直到k=m时，输出指针p1所指向的节点序号，也就是令这个“人”出列，p2指向该节点上一节点，令上一节点next域指向该节点下一节点，然后删除该节点，令头节点p1指向该节点下一节点作为再次报数初始“人”，再令k归1，继续循环。知道
6、p1-next= =p1时，表示所有“人”出列完毕，删除最后的节点后跳出循环四结果分析：测试数据：n=4, 4个人的密码依次为4, 3，8, 6, 首先m=6输出结果： 测试数据：n=7，7个人的密码依次为3，1，7，2，48，4，首先m=20输出结果： 五课程设计总结：为期一周的课程设计快结束了，通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一
7、个结点等。在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现。在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要
8、能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。六附录：完整程序代码#include#includetypedef struct nodeint data;int num;struct node *next;listnode;typedef listnode *linklist;void main()int n,m,i,j,k;linklist head=(listnode*)malloc(sizeof(listnode);/开辟一个空间，并将它的起始地址赋给头指针headlistnode *p1,*p2;printf(输入总人数:);scanf(%d,&n);/输入
9、总人数printf(输入报数上限m:);scanf(%d,&m);/输入初始报数上限if(m=0)printf(输入错误);/初始报数上限必须大于0p1=head;/将头指针head所指地址赋给p1for(i=1;inext=(listnode*)malloc(sizeof(listnode);/建立一个新的空间，并将它的地址赋给p1-next p1=p1-next; p1-data=j; p1-num=i;/对结点的num和data成员赋值p1-next=head-next;/构成单循环链表 do k=1; while(k!=m)/当k=m时一轮报数结束 p1=p1-next; k+; /报
10、数过程中将指针p1指向下一位 p2=p1-next; p1-next=p2-next;/将报m的人的结点从链表中删去 printf(编号为%d的人出列，他的密码%d作为新的m值n,p2-num,p2-data);/报数为m的人出列 m=p2-data;/报数为m的人的密码作为新的m值 free(p2);/释放报m的人的结点while(p1-next!=p1);/当p1-next指向的地址是它自己的地址，所有报数结束 printf(编号为%d的人出列，至此所有人出列完毕n,p1-num);/至此所有人出列完毕 free(p1);/释放最后一个人的结点 free(head);/释放头结点 printf(程序结束n);
