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