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

数据结构约瑟夫环的课程设计报告 武汉工业学院数学与计算机学院 数据结构课程设计 设计题目：约瑟夫环 专业大类计算机 班级计算机6班 学号 100702129 姓名王元 指导教师李禹生 2022年9月3 日 一选题背景： 题目：约瑟夫环 问题描述： 编号为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;inext=(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 #include typedef 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(mnext=(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");