欢迎来到天天文库
浏览记录
ID:59629114
大小:13.07 KB
页数:8页
时间:2020-11-16
《约瑟夫环数据结构实验报告.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
此文档下载收益归作者所有