欢迎来到天天文库
浏览记录
ID:27203669
大小:47.50 KB
页数:4页
时间:2018-12-01
《约瑟夫环问题实验报告》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、天津理工大学实验报告学院(系)名称:计算机与通信工程学院姓名黄雅娇学号20145777专业信息安全班级四班实验项目约瑟夫环问题课程名称数据结构与算法课程代码0661013实验时间2016年03月01日实验地点主校区软件实验室7-215批改意见成绩教师签字:一、实验目的 本实验的目的是进一步理解线性表的逻辑结构和存储结构,进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 设编号为1,2,···,n的n个人围坐一圈,约定编号为k(1≤k≤n)的人从1开始报数,数到m的那个人出列,他的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号
2、的序列。 三、实验步骤 1、实验问题分析 ①由于当某个人退出圆圈后,报数的工作要从下一个人开始继续,剩下的人仍要是围成一个圆圈,可以使用循环表;由于退出圆圈的工作对应着表中结点的删除操作,对于这种删除操作频繁的情况,应该选用效率较高的链表结构;为了程序指针每一次都指向一个具体的代表一个人的结点而不需要进行判断,链表不带表头结点。所以,对于所有人围成的圆圈所对对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p,并根据具体情况移动 可以采用数据类型定义: Typedef struct node { int number; struct node *next; }Lnode,
3、*Linklist; ②为了记录退出的人的先后顺序,采用一个顺序表进行存储,程序结束后再输入依次退出的人的编号顺序。由于只记录各个结点的number值就可以,所以定义一个整型一维数组。如“int quite[N];”N为一个根据实际问题定义的一个足够大的整数。 2、功能(函数)设计 根据上述分析,该算法可以由3个功能函数实现。Main()用做数据的输入和 函数的调用,Init()做链表的初始化工作,使用Josephus()做删除结点和保存输出顺序的工作,OutRing()完成序列的输出工作。 1.建立单循环链表函数 LinkList InitRingList(int n);
4、 2.产生Josephus顺序函数第4页共4页 void Josephus(LinkList L,int n,int k,int m,int quit[N]) 3.输出顺序表void Print(int n,int quit[N])四、实验程序及分析#includeusingnamespacestd;typedefstructLNode{intdata;structLNode*link;}LNode,*LinkList;voidJosephus(intn,intk,intm)//n个人,从第k个人开始报数,m为
5、出列者喊到的数{LinkListp,r,cur;//p为当前结点,r为p的前驱p=newLNode;if(!p){cout<<"Thefailureofmemoryallocated!"<data=n;p->link=p;//循环链表cur=p;for(inti=1;idata=i;t->link=cur->link;cur->link=t;cur=t;}//移动当前指针到kwhile(k--){r=p;p=
6、p->link;}第4页共4页//报数为m的人出列while(n--){for(ints=m-1;s--;r=p,p=p->link);cout<<"Theoutputis:"<data<link=p->link;LinkListd=newLNode;if(!d){cout<<"Thefailureofmemoryallocated!"<link;deleted;}}intmain(){Josephus(13,4,1);return0;}第4页共4页心得体会:通过对该题目的设计,我加深了对数据结构及存储结构的理解,进一步地理解和掌
7、握了课本中所学的各种数据结构,尤其是对单循环链表上基本运算的实现,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。 通过这次数据结构课程设计,我感受最深的就是对于循环链表的使用,可以说对循环链表有了比以前更进一步的认识,以前只是一知半解的,如果只给个题目自己根本不能把程序完整地编写出来,所以这次课程设计最大的收获就在于对循环链表有了一定的理解,包括其中的一系列操作,如建立一个循环链表,删除链表中的一个结点,增加一个结点
此文档下载收益归作者所有