欢迎来到天天文库
浏览记录
ID:18018078
大小:267.55 KB
页数:6页
时间:2018-09-12
《数据结构课程设计约瑟夫环》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、约瑟夫环课程设计题目约瑟夫环学院专业年级已知参数和设计要求:[问题描述]约瑟夫(Joeph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。学生应完成的工作:[基本要求]利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。[测试数据]m的初
2、值为20;密码:3,1,7,2,4,8,4(正确的结果应为6,1,4,7,2,3,5)。[实现提示]程序运行后首先要求用户指定初始报数上限值,然后读取各人的密码。设n≤30。目前资料收集情况(含指定参考资料):[1]RobertL.KruseAlexanderJ.Ryba编著.《数据结构与程序设计——C++语言描述》(影印版).高等教育出版社.2001年5月[2]郑慧范忠诚等编著.《零基础学VisualC++》.机械工业出版社.2009年1月课程设计的工作计划:2014.6.6---2014.6.10思考完成此文档的问题描述、基本要求、算法思
3、想、模块划分、数据结构内容,形成一个初步设计架构。2014.6.11---2014.6.22李嘉诚完成此任务各模块功能的编码和实现。2014.6.22---2014.7.2李嘉诚负责对此任务程序进行测试,并记录测试内容。2014.7.2---2014.7.10李嘉诚完成此任务界面设计与实现,做相应修改、并完成此任务的文档编写。任务下达日期2014年6月6日完成日期2014年7月10日指导教师(签名)学生(签名)说明:1、学院、专业、年级均填全称,如:光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够,可另附页,但应
4、在页脚添加页码。6约瑟夫环【问题描述】约瑟夫(Joeph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。【基本要求】利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号【算法思想】游戏实现的关键是游戏信息的储存。包括玩家座位信息,玩家所报数
5、信息以及密码信息。我们通过自定义单向循环链表Joeph_list存储结构来实现游戏过程的模拟。链表以结点连接。结点Node存储的信息包括每个人手中的密码、每个人的位置以及下一个结点在计算机中的存储位置,及指向下一个结点的指针。值得注意的是,信息“每个人的位置”是必不可少的,因为他不等同于结点在链表中的位置——但一个玩家被移除之后,链表后的元素位置会“前进”,而我们需要的玩家的位置始终是不变的。玩家的报数,我们通过循环中计数器的递增实现,当顺序递增到链表中最后一个结点,而循环仍没有结束时,我们继续从第一个元素开始递增——及相当于最后一个玩家仍没
6、有报数到m我们就从第一个玩家重头开始报数。直到计数器累加到m,则发现我们要移除的结点,记录并输出移出结点的信息,继续游戏。直到链表中元素被清空,程序结束。算法的关键是将实际游戏场景抽象到链表中的元素的查找和移除上,要掌握清楚哪些数据代表哪些信息,并熟悉程序运行中各种判断的流程。具体流程图见下一页。【模块划分】6【数据结构】Member*Joseph::Index(inti){if(i==0)returnfrist;Member*p=frist->next;intj=1;6while(jnext;j++;}returnp;}i
7、ntJoseph::Delete(inti){Member*s,*p=Index(i-1);s=p->next;p->next=p->next->next;intx=s->number;cout<password;deletes;size--;returny;}【源程序清单】ysfh.cpp【测试数据】输入给定数字:N=7,测定数据为3,1,7,2,4,8,4,m=20【测试情况】1.输入玩儿游戏的总人数m:62.输入作为队首的人的初值m:3.依次输入每个人的密码:4.出列的结果为:66
此文档下载收益归作者所有