约瑟夫环问题 实验报告

数学与计算机学院约瑟夫环问题实验报告年级10级学号2010434062姓名成绩专业电气信息（计算机类）实验地点主楼402指导教师史青宣实验项目约瑟夫环问题实验日期2011年12月26日一、实验目的本实验的目的是进一步理解线性表的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。二、实验问题描述设编号为1，2，···，n的n个人围坐一圈，约定编号为k（1≤k≤n）的人从1开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。三、实验步骤1、实验问题分析①由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍要是围成一个圆圈，可以使用循环表；由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，应该选用效率较高的链表结构；为了程序指针每一次都指向一个具体的代表一个人的结点而不需要进行判断，链表不带表头结点。所以，对于所有人围成的圆圈所对对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动可以采用数据类型定义：Typedefstructnode{intnumber;structnode*next;}Lnode,*Linklist;②为了记录退出的人的先后顺序，采用一个顺序表进行存储，程序结束后再输入依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一个整型一维数组。如“intquite[N];”N为一个根据实际问题定义的一个足够大的整数。2、功能（函数）设计根据上述分析，该算法可以由3个功能函数实现。Main（）用做数据的输入和函数的调用，Init()做链表的初始化工作，使用Josephus()做删除结点和保存输出顺序的工作，OutRing()完成序列的输出工作。1.建立单循环链表函数LinkListInitRingList(intn)；2.产生Josephus顺序函数voidJosephus(LinkListL,intn,intk,intm,intquit[N])3.输出顺序表voidPrint(intn,intquit[N])四、实验结果（程序）及分析1.实验的的源代码：//约瑟夫环问题.cpp:Definestheentrypointfortheconsoleapplication.////#include"stdafx.h"#include"iostream.h"#defineN34typedefstructNode{ intdata; structNode*next;}Lnode,*LinkList;LinkListInitRingList(intn)//尾插法建立单循环链表{ Lnode*L,*r,*s; L=newLnode;//不带头结点 r=L; for(inti=1;i<n;i++) { s=newLnode; r->data=i; r->next=s; r=s; } r->data=n; r->next=L;//链表首尾相连 L=r;//L指向循环链表的尾结点 returnL;}voidJosephus(LinkListL,intn,intk,intm,intquit[N]){ inti,j; Lnode*p,*q; p=L; for(intr=1;r<m;r++) p=p->next; for(i=0;i<n;i++) { for(j=1;j<=k-1;j++) p=p->next; q=p->next; p->next=q->next; quit[i]=q->data; deleteq; }}voidPrint(intn,intquit[N]){ inti; for(i=0;i<n;i++) cout<<quit[i]<<""; cout<<endl;}intmain(intargc,char*argv[]){ LinkListL; intn; intk; intm; cout<<"请输入围坐一圈的人数n的值:"<<endl; cin>>n; L=InitRingList(n); intquit[N]; cout<<"约定从编号为m的值开始数，请输入m的值:"<<endl;cin>>m; while(m>n||m<1) {cout<<"输入错误，请重新输入："<<endl; cin>>m; } cout<<"要求数到k的人出列，请输入k的值:"<<endl; cin>>k; cout<<"顺序为:";Josephus(L,n,k,m,quit); Print(n,quit); return0;}2.测试数据A．当n的初始值为7，k的值为5，m的值为1时，正确的出列顺序为：5、3、2、4、7、1、6，经程序运行测试，结果如下：可知程序运行正确。B．程序的容错性测试，当输入m的值不符合问题约定时，应有错误提示给用户，指导用户正确输入，并做出相应处理，保证程序运