约瑟夫环数据结构实验报告.docx

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

1、约瑟夫环课程设计实验报告【约瑟夫环数据结构实验报告】　　数据结构实验报告　　实习1线性表及其应用　　题目：编制一个演示约瑟夫环的程序　　班级：班姓名：付尧学号：[1**********]完成日期：　　一．需求分析　　1．本程序中，人数n为任意整数，首先输入一个报数上限值整数m，程序应能自动将出列的人所持的密码赋给m，再次作为报数上限，如此循环，直至所有人都出列为止。　　2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据，每个人的序号由程序自动分配。　　3．程序执行的命令包括

2、：　　构造线性表；输入数据；执行报数，删除出列人的信息以及把出列人的密码赋给m；结束。　　4．测试数据　　m初值为20，n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则正确的出列顺序为6，1，4，7，2，3，5。　　二．概要设计　　为了实现程序上述功能，应以单向循环链表为存储结构。　　1.基本操作：　　voidcreateList　　操作结果：构造单向循环链表，初始化每个人的密码并分配序号。　　voidJosephus　　初始条件：链表存在。　　操作结果：删除出列人的节点并重新报数。　　2．本程序包含三个

3、模块：　　主程序模块；　　构造链表并输入信息模块；　　执行约瑟夫环函数模块；　　三．详细设计　　1.元素类型，结点类型和指针类型：　　structnode{　　intnum;　　intcode;　　structnode*next;　　};　　typedefstructnodeNODE;　　NODE*head,*tail;　　intm,n;　　2．每个模块的分析：　　主程序模块：　　intmain{　　createList;　　Josephus;　　return0;　　}　　构造链表模块：　　voidcreateList{　　//

4、申请头结点空间　　//生成头结点　　printf;　　//读取m，n　　printf;　　//创建节点并写入密码分配相应序号。　　//形成循环链表　　}　　约瑟夫环函数模块：　　voidJosephus{　　NODE*q;　　intcount=0;//报数计数器　　q=tail;//q为尾结点　　p=p->next;//p为第一个数据　　while{　　count++;//当循环链表所剩元素大于1时　　if{　　//输出当前出列者的序号　　//更新m为出列者的密码　　//删除p节点　　//令p指向下一个数据结点　　count=0

5、;　　}　　else{　　//维护p和q到下一个结点　　}　　}　　//打印最后剩下的人的序号　　}　　四．调试分析　　设计过程中对函数结束的条件感到疑惑，经过考虑，采取p==p->next来判断，非常简捷方便　　算法的时间复杂度为n^2，空间复杂度为n，时间复杂度偏高，如果遇到数据过多可能会变得很慢。可以将m转化为m除以当前人数的余数，可以减少时间复杂度。　　这道题第一眼看觉得十分复杂，但编写中就会发现并不难。调试过程中我对链表的建立和插入删除操作更加熟练，也加深了对算法的认识。　　五．用户使用说明　　本程序的运行环境为VS2

6、0XX。　　进入演示程序后即显示提示信息：　　请输入m和n：　　输入m和n　　请输入每个人的密码：　　输入密码　　输入完毕后就进行报数操作：　　六．测试结果　　当输入m＝20，n＝7，每个人所持密码一次为：3，1，7，2，4，8，4时，则输出正确的出列顺序为：6，1，4，7，2，3，5。　　七．附录　　#include　　#include　　structnode{　　//建立链表数据类型　　intnum;　　intcode;　　structnode*next;　　};　　typedefstructnodeNODE;//定义NOD

7、E为链表数据类型　　NODE*head,*tail;//声明头指针，尾指针　　intm,n;　　voidcreateList{　　//建立链表函数　　NODE*p,*q;　　inti;　　p=newNODE;//申请头结点空间　　p->next=NULL;　　head=p;//生成头结点　　printf;　　scanf;//读取m，n　　printf;　　for;//记录该节点密码　　p->next=q;//插入节点P　　p=q;　　}　　tail=p;//保存尾指针　　tail->next=head->next;//形成循环链

8、表　　}　　voidJosephus{　　//约瑟夫函数　　NODE*q;　　intcount=0;//报数计数器　　q=tail;//q为尾结点　　p=p->next;//p为第一个数据　　while{　　count++;//当循环链表所剩元素大于1时　　if