数据结构约瑟夫环的课程设计报告.doc

数学与计算机学院数据结构课程设计设计题目：约瑟夫环 一．选题背景：题目：约瑟夫环问题描述：编号为1,2，…..，n的n个人按顺时针方向围坐圈，每个人持有一个密码（正整数）一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新重新从1报数，如此下去，直至所有人全部出列为止基本要求：⑴ 建立模型，确定存储结构； ⑵ 对任意 n个人，密码为 m ，实现约瑟夫环问题；⑶ 出圈的顺序可以依次输出，也可以用一个数组存储设计指导思想：首先，设计实现约瑟夫环问题的存储结构由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点   其次，建立一个不带头结点的循环链表并由头指针 first 指示 最后，设计约瑟夫环问题的算法下面给出伪代码描述，操作示意图如图 2-1 所示  二．方案论证：本方案通过建立单循环链表模拟了约瑟夫问题；首先，建立一个结构体node，然后给他开辟一个储存空间；利用头指针head标记链表，利用尾指针向后移将建立的结点连接成我们需要的单循环链表，过程如下：约瑟夫问题中的人数个数即为链表的长度，链表中node->num 编号n，node->data为每个人的密码。

建立单循环链表后，通过初始报数上限找到出列的结点，输出该结点的node->num值，将该结点中的data中数作为新密码开始下一个步的开始，将该结点从链表中删除，并释放该结点的空间重复此过程，直到剩下最后一个结点，就直接将该结点中的num值输出，删除该结点，并释放该结点的空间输出的num值即为约瑟夫中人的编号三．过程论述：typedef struct node{ int data; int num; struct node *next;}listnode;定义一个结构体用来储存学生的编号和所携带的密码for(i=1;i<=n;i++) { printf("输入第%d号同学的密码:",i); scanf("%d",&j);//输入学生所带密码 p1->next=(listnode*)malloc(sizeof(listnode));//建立一个新的空间，并将它的地址赋给p1->next p1=p1->next; 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的人的结点从链表中删去 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，继续循环。

知道p1->next= =p1时，表示所有“人”出列完毕，删除最后的节点后跳出循环四．结果分析：测试数据：n=4, 4个人的密码依次为4, 3，8, 6, 首先m=6输出结果： 测试数据：n=7，7个人的密码依次为3，1，7，2，48，4，首先m=20输出结果： 五．课程设计总结：为期一周的课程设计快结束了，通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。

学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己六．附录：完整程序代码#include#includetypedef struct node{ int data; int num; struct node *next;}listnode;typedef listnode *linklist;void main(){ int n,m,i,j,k; linklist head=(listnode*)malloc(sizeof(listnode));//开辟一个空间，并将它的起始地址赋给头指针head listnode *p1,*p2; printf("输入总人数:"); scanf("%d",&n); //输入总人数 printf("输入报数上限m:"); scanf("%d",&m);//输入初始报数上限 if(m<=0)printf("输入错误");//初始报数上限必须大于0 p1=head;//将头指针head所指地址赋给p1 for(i=1;i<=n;i++) { printf("输入第%d号同学的密码:",i); scanf("%d",&j);//输入学生所带密码 p1->next=(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++; }//报数过程中将指针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");}- 2 -。