数据结构约瑟夫环问题.doc

袂薈螇蒂数据结构实验报告虿蚇膆节螁聿薆羃螂膇肅螃蕿薀题目:[问题描述]蚈约瑟夫环问题的一种描述是:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人手持一个密码(正整数)。一开始任选一个整数作为报数上限值,从第一人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出列,将它的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去直到所有人全部出列为止。试设计程序实现之。袄[基本要求]膄利用循环链表存储结构模拟此过程,按照出列的顺序打印各人的编号。蚂[实验提示]螇程序运行后首先要求用户指定初始报数上限值。然后读取各人的密码。设n<=30。薇程序执行后,要求用户在计算机终端上显示“提示信息”后,用键盘输入“提示信息”中规定的命令,以“回车符”为结束标志。相应的输入数据和运算结果显示在其后。羄二、++语言的基本知识和技能;,解决简单的面向对象程序设计问题。,达到学以致用的目的。蚅三、系统分析与设计(确定程序功能模块)薁1、为实现上述程序的功能,应以有序链表表示集合。芇基本操作:蒆InitList(&L)膁操作结果:构造一个空的有序表L。蚂DestroyList(&L)蚀初始条件:有序表L已存在。袅操作结果:销毁有序表L。袁ListEmpty(L)蒀初始条件:有序表L已存在。螈操作结果:若L为空表,则返回TRUE,否则返回FALSE。芅ListLength(L)蚂初始条件:有序表L已存在。蒁操作结果:返回L中数据元素个数。袆GetElem(L,i)螄初始条件:有序表L已存在,并且1≤i≤ListLength(L)。莂操作结果:返回L中第i个数据元素。薂LocatePos(L,e)艿初始条件:有序表L已存在,e和有序表中元素同类型的值。膃操作结果:若L中存在和e相同的元素,则返回位置;否则返回0。膂InsertElem(&L,e)莀初始条件:有序表L已存在莇操作结果:在L中,按有序关系插入值和e相同的数据元素。袇DeleteElem(&L,i)袃初始条件:有序表L已存在。莁操作结果:删除L中第i个数据元素。螀ListTraverse(L,visit())芆初始条件:有序表L已存在。蚃操作结果:依次对L的每个数据元素调用函数visit()。一旦visit()失败,则操作失败。膈}ADTOrderedList袈2、本程序包含两个模块:蚆(1)主程序模块:莄voidmain(){芀初始化;羆调用函数(接受命令,处理命令)}膅(2)有序表单元模块——实现有序表的抽象数据类型。膄 (3)输出函数模块——有序表的输出。芁四、源程序代码荿#include""薄#include""袄//,结点类型和指针类型聿typedefstructLNode//定义结构体,蒇{羄intnum,pwd;//num用来存储人的序号,pwd用来存储人的密码薅structLNode*next;膀};衿structLNode*head,*p,*pt;//定义结点蚇//2、 创建循环链表函数肁intcreatLinkList(intn)//参数n传递人数,芁{羈inti;肇head=(structLNode*)malloc(sizeof(structLNode));袁//创建一个带头结点的链表聿if(!head){return0;}//创建不成功,返回0肆p=head;薆for(i=1;i<n;i++)薂{肀pt=(structLNode*)malloc(sizeof(structLNode));葿if(!pt){return0;}羅p->next=pt;莂p=pt;膁}薇p->next=head; //构成循环链表莅pt=head;肃 return0;罿}衿//(intn)//参数n传递人数螃{羀inti,j;肈printf("\n请输入密码:\n");蒇for(i=1;i<=n;i++)薃{肂scanf("%d",&j);膆pt->num=i;//num存储人的序号羇pt->pwd=j;//pwd存储人的密码芄pt=pt->next;衿}蒈pt=p;莆 returnj;肄}袀//4、创建输出函数蚇intoutList(intm,intn)//参数m、n传递报数上限值和人数螆{螅inti,a;羂for(i=1;i<=n;i++)//用一个for循环搜索循环链表罿{膅for(a=1;a<m;a++)//删除结点薅{蝿pt=pt->next;肈}蚄p=pt->next;羁m=p->pwd;袀printf("%d",p->num);//输出人