数据结构约瑟夫环问题

1、数据结构实验报告题目：约瑟夫环问题一、设计内容问题描述约瑟夫环问题的一种描述是：编号为 1, 2, 3,，n的n个人按顺时针方向围 坐一圈，每人手持一个密码（正整数）。一开始任选一个整数作为报数上限值， 从第一人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列， 将它的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从 1报数， 如此下去直到所有人全部出列为止。试设计程序实现之。基本要求利用循环链表存储结构模拟此过程，按照出列的顺序打印各人的编号。实验提示程序运行后首先要求用户指定初始报数上限值。然后读取各人的密码。设n=30。程序执行后，要求用户在计算机终端上显示“提示信息”

2、后，用键盘输入“提示信息” 中规定的命令，以“回车符”为结束标志相应的输入数据和运算结果显示在其后。二、设计目的1. 达到熟练掌握C+语言的基本知识和技能；2. 能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题。3. 把课本上的知识应用到实际生活中，达到学以致用的目的。三、系统分析与设计（确定程序功能模块）1、为实现上述程序的功能，应以有序链表表示集合。基本操作：In itList（&L）操作结果：构造一个空的有序表L 初始条件：有序表L已存在。操作结果：销毁有序表L。ListEmpty(L)初始条件：有序表L已存在。操作结果：若L为空表，则返回TRUE否则返回FALSEListL

3、e ngth(L)初始条件：有序表L已存在。操作结果：返回L中数据元素个数。GetElem(L,i)初始条件：有序表L已存在，并且 K i ListLength(L)。操作结果：返回L中第i个数据元素。LocatePos(L,e)初始条件：有序表L已存在，e和有序表中元素同类型的值。操作结果：若L中存在和e相同的元素，则返回位置；否则返回0。In sertElem(&L,e)初始条件：有序表L已存在操作结果：在L中，按有序关系插入值和e相同的数据元素。DeleteElem(&L,i)初始条件：有序表L已存在。操作结果：删除L中第i个数据元素。ListTraverse(L,visit()初始条件

4、：有序表L已存在。操作结果：依次对L的每个数据元素调用函数 visit()。一旦visit()失 败，则操作失败。 ADT OrderedList2、本程序包含两个模块:(1) 主程序模块：void mai n()初始化;调用函数(接受命令，处理命令)(2) 有序表单元模块一一实现有序表的抽象数据类型(3) 输出函数模块一一有序表的输出。四、源程序代码#i ncludestdio.h#i ncludemalloc.h1.元素类型，结点类型和指针类型/定义结构体,typedef struct LNodeint nu m,pwd;密码struct LNode *n ext;struct LNode

5、 *head,*p,*pt;2、创建循环链表函数int creatL in kList(i nt n)/num用来存储人的序号,/定义结点II参数n传递人数，pwd用来存储人的int i;head=(struct LNode*)malloc(sizeof(struct LNode);II创建一个带头结点的链表if(!head) return 0;II 创建不成功，返回 0p=head;for(i=1;i n ext=pt;P=Pt；p- next=head;/构成循环链表pt=head;return 0;3.创建输入密码函数int en terPwd(i nt n)/参数n传递人数int i,

6、j;printf(n 请输入密码:n);for( i=1;inum=i; pt-pwd=j;pt=pt- n ext;pt=p; return j;4、创建输出函数int outList(i nt m,i nt n) /num存储人的序号pwd存储人的密码/参数m、n传递报数上限值和人数int i,a;for(i=1;i=n ;i+)/用一个for循环搜索循环链表for(a=1;an ext;p=pt- n ext;m=p-pwd;printf(%d ,p-num);/ 输出人的序号pt- n ext=p-n ext;free(p);/释放动态申请的结点空间return 0;/主函数void

7、mai n() int m,n; /m为报数上限值，n为人数printf(n参数m、n传递报数上限值和人数;n);printf(n 请输入 m 和 n: n);sea nf(%d %d,&m,&n);creatLi nkList( n); /调用创建链表函数 en terPwd( n);/调用输入密码函数printf(n出队的人依次是:n);outList( m,n);/调用输出链表函数五、测试结果及功能说明F；蟲霍洁构Oubug斶揭绅| =回sf数叽口传連报数上限値和人数，请输入e .和n 6 7请输入密码：1 2 3 4 5 6 7M队的人依次是:；6 53217 Press any key to contioue输入报数上限值为m为6 ,人数n为7;7个人数密码依次是1, 2, 3, 4, 5, 6, 7;出队的人号码依次是：6, 5, 4, 3, 2, 1 , 7六、设计体会数据结构是一门比较抽象的课程，但是也是一门最基础的课程学的过程。在现实生活的应用也非常广泛通过设计该实验让我更加深刻的掌握了掌握了，有关链表的知识，同时也认识到了自己在平时学习当中的盲点， 通过这次实验发现 了自己在数据结构这门功课上存在严重的不足。 链表中的