




已阅读5页,还剩2页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据结构课程设计实验学校: 江西农业大学 班级: 软 件1115班 姓名: 朱 利 斌 学号: 20111976 课程: 数据结构课程设计 指导教师: 彭玉莹 2012.1.2实验一:约瑟夫问题问题简述: 约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3.n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来,所以通常称为Josephus问题。改进约瑟夫问题的描述是:编号为1,2,n的n个人按顺时针方向围坐一圈, 每人有一个密码Ki(整数),留作其出圈后应报到Ki后出圈。报数方法采用顺时针报数和逆时针报数交替进行,初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景,后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构,就是将一个链表的尾元素指针指向队首元素。 p-link=head解决问题的核心步骤:先建立一个具有n个链结点,无头结点的循环链表,然后确定第一个报数人的位置,并不断地从链表中删除链结点,直到链表为空。一、题目内容及要求【问题描述】编号是1,2,,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。设计一个程序来求出出列顺序。【要求】利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号。2)掌握线性表的基本操作,如插入、删除、检索等在链式存储结构上的运算。二、实验环境(硬/软件要求): Windows XP + VC6.0三、概要设计利用单向循环链表存储结构模拟此过程,因为循环链表最后一个结点的指针域指向头结点,整个链表形成一人环,刚好和题中的“n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数)”内容要求一致,而且,循环链表中任一结点出发均可找到表中其他结点,利用这一优点可较容易地找出报数的人及下一个报数的人,最后按照出列的顺序用一个for语句实现。循环链表的存储结构如下:struct Joseph /定义josephint num;struct Joseph *next;int n,s,m;void print(struct Joseph *head) /打印链对中的信息 struct Joseph *p; /p指针p=head; /将p指向头指针四、实验设计思想1.在实践约瑟夫问题时的关键是用两个指针把一个移动的,一个指向要删除的节点,另外要注意保留头指针。第一步是建立一个循环的单向链表。第二步是运用指针遍历链表同时计数到第m个时将其删除。此时指针指向不变。其格式如下:void output(struct Joseph *head) /输出出列情况int i,j=1;struct Joseph *p1,*p2;p1=p2=head; /p1 p2都指向头指针for(i=1;inext; /从第M个人开始报数,所以p1指针依次后移,指向第m个人while(n0)for(i=1;inext; /开始报数,报到s前p1、p2依次后移printf(第%d个出列的人是:%dn,j,p1-num);p2-next=p1-next; p1=p2-next; /此人出列,将p1-next赋给p2-next,将p1所指向的结点删掉n-; /人数减少1j+; / 出列人数加12创建单循环链表 创建一个空单循环链表,双向循环链表和每个结点包括两个域:元素域和指针域。形成单循环链表的原理:定义三个指针变量H,r,s,三指针开始全部指向头结点,在插入操作开始后,H不变仍指向头结点,s指针在插入过程中始终指向新插入的节点,而r指针紧随其后,用于将新插入的节点和前一个节点连接起来,最后通过r指向头指针H,来完成环的操作。关键代码实现如下:if(H=NULL) H=s,r=H;/从链表的第一个节点插入else r-next=s,r=s;/r后移/链表的其余节点插入结束for循环后结成环的操作:r-next=H;/*生成循环单链表*/return H;3查找并删除节点 每当结点计数到某一结点时,将他的前驱结点接到他的后继结点,然后将他的密码值cipher赋给计数变量,再将此结点删除。如此循环下去,直到最后变为空的单循环链表为止。函数通过代码:p=H; pre=p; p=p-next;pre-next=p-next; p=pre-next;来删除当前的那个结点q,通过循环来一次次删除当前的结点,直到链表中剩下最后一个结点。 五、程序清单/*运行环境VC*/#include #include#include #define LEN sizeof(struct Joseph)struct Joseph /定义josephint num;struct Joseph *next;int n,s,m;void print(struct Joseph *head) /打印链对中的信息 struct Joseph *p; /p指针p=head; /将p指向头指针printf(%d个人的代号如下:n,n);doprintf(%d ,p-num);p=p-next;while(p!=head); /依次输入每个人的代号printf(n);void output(struct Joseph *head) /输出出列情况int i,j=1;struct Joseph *p1,*p2;p1=p2=head; /p1 p2都指向头指针for(i=1;inext; /从第M个人开始报数,所以p1指针依次后移,指向第m个人while(n0)for(i=1;inext; /开始报数,报到s前p1、p2依次后移printf(第%d个出列的人是:%dn,j,p1-num);p2-next=p1-next; p1=p2-next; /此人出列,将p1-next赋给p2-next,将p1所指向的结点删掉n-; /人数减少1j+; / 出列人数加1struct Joseph *create() /建立链队列int i;struct Joseph *head;struct Joseph *p1,*p2;printf(请输入总人数(输入0退出程序):n);scanf(%d,&n);if(n=0)exit(0);/退出for(i=1;inum=i;if(i=1)head=p1;elsep2-next=p1;p2=p1;p2-next=head; /将整个链队构成一个环形print(head);printf(请输入从第几个人开始报数:n);scanf(%d,&m);printf(数到第几个人出列:n);scanf(%d,&s);return head;main()struct Joseph *head;while(1)head=create();output(head);system(pause);system(cls);六、运行结果七、实验心得在约瑟夫问题中,着重训练的是链表的应用,尤其是链表中结点的删除、检索等。由于单向链表等线性表的操作基本思想是一致的,因此通过对单向链表的练习来加深对线性表的理解。在本实验中,需要解决的问题的重点是怎样找到要删除的结点。因此,我首先考虑解决这个问题,即应用循环语句来找到满足条件的结点,我选用了if循环语句。然后应用指针实现查找过程。在弄清出这些之后,在建立一个单向链表即形成程序。在经过调试改正一些细节即可。在编辑的过程中,将所学的知识充分应用于实践,虽然遇到
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 光大银行盐城市亭湖区2025秋招小语种岗笔试题及答案
- 执业药师之《药事管理与法规》预测复习及答案详解(典优)
- 平安银行深圳市罗湖区2025秋招无领导模拟题角色攻略
- 2025年江苏宿迁市广播电视总台招聘4人笔试备考题库参考答案详解
- 招商银行南通市海门区2025秋招无领导小组面试案例库
- 华夏银行太原市万柏林区2025秋招无领导小组面试案例库
- 2024-2025学年度自考专业(行政管理)真题及完整答案(夺冠)
- 2024-2025学年度辅警招聘考试试题含答案详解【突破训练】
- 浦发银行哈尔滨市南岗区2025秋招笔试综合模拟题库及答案
- 2025年工程硕士高频难、易错点题及参考答案详解(预热题)
- 2023年安康市交通建设投资集团有限公司招聘笔试模拟试题及答案解析
- Be-Safe-on-the-Way课件(省一等奖)
- 大学生心理健康优秀说课-比赛课件
- 高中英语词汇3500词(含音标)
- 凝结水泵解体检修课件
- TDTG提升机说明书
- 度基本公卫工作整改台账
- 大宗商品贸易业务风险管理指引
- 公务员第二批
- 阳宅风水培训讲义课件
- 1《材料科学基础》第一章晶体学基础课件
评论
0/150
提交评论