版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
约瑟夫环(Joseph)问题
姓名:学号:
系别:指导老师:目录1.程序设计目标2.问题描述3.概要设计4.详细设计5.测试报告6.总结1.程序设计目标约瑟夫(Joseph)环问题是数据结构中的经典问题,在学习线性表的时候常用到约瑟夫环问题,通过学习约瑟夫环问题能提高对线性表的理解和应用能力。约瑟夫环问题可利用多种方法求解,本设计主要利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号。同时,通过查找C语言相关知识,分析约瑟夫环问题与循环链表之间的联系,然后形成算法的思想对约瑟夫环问题用C语言进行编译实现。2.问题描述编号是1,2,……,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。设计一个程序来求出出列顺序。2.问题描述图1Joseph环示意图3.概要设计本设计实现约瑟夫环问题主要由三个模块构成:主模块、链表的创建、输出序列。图2各模块调用关系3.概要设计单向循环链表:将单链表尾节点的指针端由空指针改为指向头节点,使整个单链表形成一个环。图3所示为带头节点的循环单链表。
图3循环单链表
4.详细设计链表的创建主要用到CreateLinkList()函数,首先从主函数main()函数中读取个人信息,包括人数、每个人持有的密码以及第一个报数值,然后开始创建循环单链表来存储每个人的密码,创建完成后返回main()函数。
4.详细设计图4链表的生成
4.详细设计输出出对序列主要用到Joseph()函数,首先从创建好的循环链表中按初始密码依次找出对应出列序列,然后依次输出每个人持有的密码c,当所有密码输出后,删除相应的节点,并释放所占有的存储空间,返回主函数。
4.详细设计图5输出序列的实现5.测试报告//尾插入法创建链表voidCreateLinkList(LinkList*&L,intn){ LinkList*s,*c; inti; L=(LinkList*)malloc(sizeof(LinkList));//创建头节点
c=L; printf("请输入第1个元素的密码:"); scanf("%d",&(c->cipher)); c->data=1; for(i=2;i<=n;i++) { s=(LinkList*)malloc(sizeof(LinkList)); printf("请输入第%d个元素的密码:",i); scanf("%d",&(s->cipher)); s->data=i; c->next=s; c=s; } c->next=L;}5.测试报告voidJoseph(LinkList*&L,intm,intn)//出列{ LinkList*s,*c; inti=1; c=L; printf("输出出对序列:"); while(n) { while(i!=m) { s=c; c=c->next; i++; } printf("%-3d",c->data); m=c->cipher; s->next=c->next; free(c); c=s->next; i=1; n--; } printf("\n");}5.测试报告图6Joseph环编译结果
6.总结通过本次的课程设计,我了解到约瑟夫环问题是由古罗马著名的史学家Josephus提出的问题基础上演变而来,所以也称为Josephus问题。Jo
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年繁华商圈店铺租赁合同3篇
- 2024年跨国保险业务分销合同
- 2024年版:项目合作风险共担协议
- 2024黄山旅游纪念品设计合同
- 2025年度大理石石材进出口贸易承包合同规范3篇
- 2024艺术品代理销售与艺术品展览策划合同3篇
- 2024蔬菜产地直供与电商平台合作意向协议书3篇
- 2025年度物业费收取与调整协议3篇
- 2024甲乙双方共建智慧城市战略合作合同
- 西南大学《特殊儿童运动康复》2023-2024学年第一学期期末试卷
- 2023年项目申报专员年终总结及年后展望
- 普通高中思想政治课程标准
- 假发项目市场营销与品牌管理方案
- 1-6年级健康教育课程安排表
- 《石墨类负极材料检测方法 第1部分:石墨化度的测定》
- 红色经典影片与近现代中国发展期末考试答案
- 建设工程设计文件质量检查报告范例
- 施工图审查要点-全专业
- 千字文毛笔楷书描红字帖-米字格A4版
- 男人来自火星女人来自金星
- 医院病案科绩效考核标准
评论
0/150
提交评论