没有合适的资源?快使用搜索试试~ 我知道了~
约瑟夫环 数据结构课程设计
5星 · 超过95%的资源 需积分: 9 65 下载量 192 浏览量
2010-05-07
20:51:13
上传
评论 2
收藏 85KB DOC 举报
温馨提示
试读
15页
约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来,所以通常称为Josephus问题。改进约瑟夫问题的描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈, 每人有一个密码Ki(整数),留作其出圈后应报到Ki后出圈。报数方法采用顺时针报数和逆时针报数交替进行,初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景,后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构,就是将一个链表的尾元素指针指向队首元素。 p->link=head解决问题的核心步骤:先建立一个具有n个链结点,无头结点的循环链表,然后确定第一个报数人的位置,并不断地从链表中删除链结点,直到链表为空。
资源推荐
资源详情
资源评论
摘要:
约瑟夫问题是由古罗马著名的史学家 Josephus 提出的问题演变而来,所
以通常称为 Josephus 问题。改进约瑟夫问题的描述是:编号为 1,2,…,n
的 n 个人按顺时针方向围坐一圈, 每人有一个密码 Ki(整数),留作其出圈后
应报到 Ki 后出圈。报数方法采用顺时针报数和逆时针报数交替进行,初始密码
可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景,后
来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随
机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链
表的数据结构,就是将一个链表的尾元素指针指向队首元素。 p->link=head
解决问题的核心步骤:先建立一个具有 n 个链结点,无头结点的循环链表,然
后确定第一个报数人的位置,并不断地从链表中删除链结点,直到链表为空。
关键词:约瑟夫环;双向循环链表;数据结构;删除结点
目 录
........................................................................................3
1 需求分析...........................................................................3
1.1 功能分析.................................................................................3
1.2 设计平台.................................................................................3
2 概要设计...........................................................................3
2.1 类 LinkList............................................................................4
2.2 类 Joseph..............................................................................4
2.3 类异常处理..............................................................................4
3 详细设计和实现...................................................................4
3.1 创建结点 Node........................................................................5
3.2 创建双向循环链表......................................................................5
3.3 从链表中删除结点......................................................................6
4 调试与操作说明..................................................................10
4.1 调试情况...............................................................................10
4.2 操作说明...............................................................................11
总结.................................................................................12
为期一周的课程设计快结束了,通过这次数据结构课程设计,我感受最深的就
是对于循环链表的使用,可以说对循环链表有了比以前更进一步的认识,以前
只是一知半解的,如果只给个题目自己根本不能把程序完整地编写出来,所以
这次课程设计最大的收获就在于对循环链表有了一定的理解,包括其中的一系
列操作,如建立一个循环链表,删除链表中的一个结点,增加一个结点等。 12
致 谢................................................................................13
参 考 文 献.........................................................................14
1 需求分析
1.1 功能分析
本次选做的课程设计是改进约瑟夫(Joseph)环问题。我选择了和薛晶两个人
来完成本次课程设计的作业。约瑟夫环问题是一个古老的数学问题,本次课题
要求用程序语言的方式解决数学问题。此问题仅使用单循环链表就可以解决此
问题。而改进的约瑟夫问题通过运用双向循环链表,同样也能方便地解决。
在建立双向循环链表时,因为约瑟夫环的大小由输入决定。为方便操作,
我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。
进行操作时,用一个指针 current 指向当前的结点,指针 front 始终指向头结点。
然后建立双向循环链表,因为每个人的密码是通过 rand()函数随机生成的,所
以指定第一个人的顺序号,找到结点,不断地从链表中删除链结点,直到链表
剩下最后一个结点,通过一系列的循环就可以解决改进约瑟夫环问题。
1.2 设计平台
Windows2000 以上操作系统;Microsoft Visual C++ 6.0
2 概要设计
已知 n 个人(以编号 1,2,3...n 分别表示)围成一圈。从编号为 1 的人开
始报数,数到 m 的那个人出列;他的下一个人又从 1 开始报数,数到 m 的那
个人又出列;依此规律重复下去,直到一圈的人全部出列。这个就是约瑟夫环
问题的实际场景,有一种是要通过输入 n,m,k 三个正整数,来求出列的序列。
这个问题采用的是典型的循环链表的数据结构,就是将一个链表的尾元素指针
剩余14页未读,继续阅读
资源评论
- xifengrose2012-12-15挺高效的,程序
- jshh19912013-05-04参考下代码,很感谢。
- garybaby2011-12-10执行不成功,程序有错误
- czh3618849472014-12-22代码很有参考价值,多谢
feifei20090407
- 粉丝: 0
- 资源: 48
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- ### 1、项目介绍 本项目Scrapy进行数据爬取,并使用Django框架+PyEcharts实现可视化大屏 效果如下:
- # 微信小程序-健康菜谱 基于微信小程序的一个查找检索菜谱的应用 ### 效果 !动态图(./res/gif/demo
- zabbix-get命令包资源
- 毕业设计,基于PyQt5实现的可视化界面的Python车牌自动识别系统源码
- 26-朴素贝叶斯分类.rar
- 没有安Matlab 也可以 生成FIR抽头系数工具.py
- python烟花代码.rar
- 实验目的: 1.构建基于verilog语言的组合逻辑电路和时序逻辑电路; 2.掌握verilog语言的电路设计技巧 3.完成如
- 扩展卡尔曼滤波matlab仿真
- 3_base.apk.1
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功