数据结构约瑟夫环问题

..数据结构实验报告题目：约瑟夫环问题一．设计内容[问题描述]约瑟夫环问题的一种描述是：编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人手持一个密码〔正整数。一开始任选一个整数作为报数上限值,从第一人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出列,将它的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去直到所有人全部出列为止。试设计程序实现之。[基本要求]利用循环链表存储结构模拟此过程,按照出列的顺序打印各人的编号。[实验提示]程序运行后首先要求用户指定初始报数上限值。然后读取各人的密码。设n<=30。程序执行后,要求用户在计算机终端上显示"提示信息"后,用键盘输入"提示信息"中规定的命令,以"回车符"为结束标志。相应的输入数据和运算结果显示在其后。二、设计目的1.达到熟练掌握C++语言的基本知识和技能；2.能够利用所学的基本知识和技能,解决简单的面向对象程序设计问题。3.把课本上的知识应用到实际生活中,达到学以致用的目的。三、系统分析与设计〔确定程序功能模块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<>失败,则操作失败。}ADTOrderedList2、本程序包含两个模块：〔1主程序模块：voidmain<>{初始化；调用函数〔接受命令,处理命令}〔2有序表单元模块——实现有序表的抽象数据类型。 〔3输出函数模块——有序表的输出。四、源程序代码#include"stdio.h"#include"malloc.h"//1.元素类型,结点类型和指针类型typedefstructLNode//定义结构体,{intnum,pwd;//num用来存储人的序号,pwd用来存储人的密码structLNode*next;};structLNode*head,*p,*pt;//定义结点//2、 创建循环链表函数intcreatLinkList<intn>//参数n传递人数,{inti;head=<structLNode*>malloc<sizeof<structLNode>>; //创建一个带头结点的链表if<!head>{return0;}//创建不成功,返回0p=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;}//3.创建输入密码函数intenterPwd<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>;//输出人的序号pt->next=p->next;free<p>;//释放动态申请的结点空间}return0;}//主函数voidmain<>{intm,n;//m为报数上限值,n为人数 printf<"\n参数m、n传递报数上限值和人数;\n">;printf<"\n请输入m和n:\n">;scanf<"%d%d",&m,&n>;creatLinkList<n>;//调用创建链表函数enterPwd<n>;//调用输入密码函数printf<"\n出队的人依次是:\n">;outList<m,n>;//调用输出链表函数}五、测试结果及功能说明输入报数上限值为m为6,人数n为7；7个人数密码依次是1,2,3,4,5,6,7；出队的人号码依次是：6,5,4,3,2,1,7六、设计体会数据结构是一门比较抽象的课程,但是也是一门最基础的课程学的过程。在现实生活的应用也非常广泛通过设计该实验让我更加深刻的掌握了掌握了,有关链表的知识,同时也认识到了自己在平时学习当中的盲点,通过这次实验