数据结构约瑟夫环课程设计报告书

《数据结构约瑟夫环课程设计报告书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》课程设计报告书《数据结构》课程设计报告书设计题目：约瑟夫环专业：班级：姓名：指导教师：完成日期：9《数据结构》课程设计报告书目录一、问题描述1二、基本要求1三、测试数据1四、算法思想2五、模块划分3六、数据结构4七、源程序4八、界面设计6九、运行与测试6十、总结8十一、思考与感悟99《数据结构》课程设计报告书课程设计设计报告书一、问题描述约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈,

2、每人有一个密码（整数），留作其出圈后应报到后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p->link=head解决问题的核心步骤：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。二、基本

3、要求(1)输入的形式和输入值的范围：输入的形式是以数字的形式输入，输入范围为-2147483648～2147483648(2)输出的形式：字符串形式输出(3)程序所能达到的功能：达到符合约瑟夫环要求的响应功能。三、测试数据进入程序，显示“1.开始游戏0.退出游戏”输入非0数进入游戏，输入0退出游戏。进入游戏后显示“输入总人数”，输入大于0的整数；若输入错误，则光标处清空，重新输入。后提示“输入开始人的序号”；范围是大于零，小于总人数的整数，若输入错误，则光标处清空，重新输入。后提示“输入间隔数字”，范围是任意正整数；若输入

4、错误，则光标处清空，重新输入。按回车键，显示结果，并重新询问“1.开始游戏0.退出游戏”。9《数据结构》课程设计报告书四、算法思想首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：typedefstructnode{intdata;structnode*next;}LNode;其次，建立一个不带头结点的循环链表并由头指针p指示。最后，设计约瑟夫环问题的算法。1、工作指针first，r，s，p，q初始化2、

5、输入人数（n）和报数（m）3、循环n次，用尾插法创建链表intstart=k-1;LNode*s,*p,*L=0,*t;if(start==0)start=n;while(n!=0){s=(LNode*)malloc(sizeof(LNode));if(L==0)p=s;if(n==start)t=s;s->data=n;s->next=L;L=s;n--;}p->next=L;returnt;}LNode*GetNode(LNode*p)/*出队函数*/{LNode*q;for(q=p;q->next!=p;q=q->n

6、ext);q->next=p->next;free(p);return(q);}4、输入报数的起始人号数k;9《数据结构》课程设计报告书5、循环n次删除结点并报出位置（其中第一个人后移k个）当inext=L;删除p结点的后一结点qq=p;q->next!=p;q=q->nextq->next=p->next;报出位置后freeq;计数器i++;五、模块划分报数过程输入总人数n创建并初始化n个结点输入第一个报的数kn==0输出出列者的编号及密码结束n--图5-1流程关系图9《数据结构》课程设计报告

7、书六、数据结构通过对问题的分析，给出该课程设计需要使用的数据结构的类型定义，并阐述定义理由。存储结构：循环链表123n……first图6-1循环链表七、源程序#include#includetypedefstructnode{intdata;structnode*next;}LNode;main(){LNode*Create(int,int);LNode*GetNode(LNode*);intPrint(LNode*,int);LNode*p;intn,k,m;intflag;whil

8、e(1){printf("1.开始游戏0.退出游戏");scanf("%d",&flag);if(!flag)break;do{printf("输入总人数");scanf("%d",&n);}while(n<=0);9《数据结构》课程设计报告书do{printf("输入开始人的序号(1~%d)",n