约瑟夫问题算法及数据结构课程设计报告.pdfVIP

约瑟夫问题算法及数据结构课程设计报告.pdf

  1. 1、本文档共13页,可阅读全部内容。
  2. 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多

约瑟夫问题算法及数据结构课程设计报告--第1页

....

线性表的操作及其应用

一、问题描述

线性表、队列是一种常用的数据结构,有顺序和链式两种存储结构,在实际中应用十分

广泛,而链表又分为单链表和循环链表,队列又分为链式队列和循环队列。这些数据结构都

可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题,是顺序编号的一组

n个人围坐一圈,从第1个人按一定方向顺序报数,在报到m时该人出列,然后按相同方

法继续报数,直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。

二、基本要求

1、选择合适的存储结构,建立线性表;

2、利用顺序存储结构求解约瑟夫环问题;

3、利用单链表和循环链表分别求解约瑟夫环问题;

4、利用队列求解约瑟夫环问题。

三、测试数据

约瑟夫环的测试数据为7,报数为1至3。

四、算法思想

由于用到四种不同的存储结构,它们的算法思想依次是:

1、首先建立一个顺序表模拟整个约瑟夫环,手动输入顺序表长(即参加约瑟夫循环的

人数)和循环的次数和表元素。用已经输出总人数和顺序表长作比较,作为外层循环条件。

并对每一个输出后的元素重新赋值以为标记。对于每次循环,首先检查顺序表此次是不是我

们设立的标记,如果不是则循环次数加1,当达到要求的循环次数时就将循环次数设置为0,

输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置,作为新

的判断条件,每次报到表尾的时候,我们都将重新设置到表尾,作为下次循环的表元素。

2、首先采用链式循环链表建立整个约瑟夫环,手动输入第一次的循环次数和每个人所

持下一个循环次数。设立判断指针指向表头,并将该指针是否为空作为外层循环条件。做一

个内层循环,将判断指针移动到循环要输出的数,并设立一个前指针指向该指针的前一个位

置,输出该元素后,将循环次数重新赋值成该元素。接着判断前指针和判断指针比较,如果

相等说明整个表已经输出完毕,否则将删除该位置的元素。

3、用链式队列建立循环约瑟夫环,手动输入人数,第一次的循环次数和每个人所持下

一个循环次数。并将每一个元素依次入队列,根据第一次循环次数,建立一个for循环,每

一次循环都出队列,如果达到要求的循环次数就输出,否则进队列,这样这个数字就出现在

队尾。第一个数输出后,以队列的非空作为循环条件,判断方式如上。

4、用循环队列建立约瑟夫环,将1-7个元素依次进入循环队列,以队列的长度作为与

已输出的元素作为判断条件,对每一个输出后的元素重新赋值以为标记。对于每次循环,首

先检查该该位置的元素是不是我们设立的标记-1,如果不是则循环次数加1,将队首指针移

.资料....

约瑟夫问题算法及数据结构课程设计报告--第1页

约瑟夫问题算法及数据结构课程设计报告--第2页

....

到队列的下一个元素,结束此次循环,当达到要求的循环次数时就将重新循环次数设置为0,

输出该元素到屏幕并将总输出元素加1。

五、模块划分

1、voidInitQueue(SqQueue*Q)

初始化循环队列

2、voidDestroyQueue(SqQueue*Q)

文档评论(0)

175****9697 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档