数据结构约瑟夫环问题.docx
数据构造实验报告题目：约瑟夫环问题-设计内容问题描述约瑟夫环问题的一种描述是：编号为1,2,3,，n的n个人按顺时针方向围坐一圈，每人手持一个密码(正整数)。一开场任选一个整数作为报数上限值，从第一人开场顺时针自1开场顺序报数，报到m时停顿报数。报m的人出列，将它的密码作为新的m值，从他在顺时针方向上的下一个人开场重新从1报数，如此下去直到所有人全部出列为止。试设计程序实现之。基本要求利用循环链表存储构造模拟此过程，按照出列的顺序打印各人的编号。实验提示程序运行后首先要求用户指定初始报数上限值。然后读取各人的密码。设n<=30°程序执行后，要求用户在计算机终端上显示“提示信息”后，用键盘输入“提示信息中规定的命令，以“回车符为完毕标志。相应的输入数据和运算结果显示在其后。二、设计目的1 .到达熟练掌握C+语言的基本知识和技能；2 .能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题。3 .把课本上的知识应用到实际生活中，到达学以致用的目的。三、系统分析与设计(确定程序功能模块)1、为实现上述程序的功能，应以有序链表表示集合。基本操作：InitList(&L)操作结果：构造一个空的有序表LDestroyList(&L)初始条件：有序表L已存在。操作结果：销毁有序表L1.istEmpty(L)初始条件：有序表L已存在。操作结果：假设L为空表，那么返回TRUE,否那么返回FALSE。1.istLength(L)初始条件：有序表L已存在。操作结果：返回L中数据元素个数。GetElem(L,i)初始条件：有序表L已存在，并且IWiWLiStLength(L)。操作结果：返回L中第i个数据元素。1.ocatePos(L,e)初始条件：有序表L已存在，e和有序表中元素同类型的值。操作结果：假设L中存在和e一样的元素，那么返回位置；否那么返回0。InsertElem(&L,e)初始条件：有序表L已存在操作结果：在L中，按有序关系插入值和e一样的数据元素。DeleteElem(&L,i)初始条件：有序表L已存在。操作结果：删除L中第i个数据元素。1.istTraverse(L,visit()初始条件：有序表L已存在。操作结果:依次对L的每个数据元素调用函数ViSit()。一旦visit()失败，那么操作失败。ADTOrderedList2、本程序包含两个模块：(1)主程序模块：voidmain()初始化；调用函数(承受命令，处理命令)(2)有序表单元模块一一实现有序表的抽象数据类型。(3)输出函数模块一一有序表的输出。四、源程序代码ftincludez,stdio. hftinclude,malloc. hL元素类型，结点类型和指针类型typedef struct LNodeint num, pwd;定义构造体，nUm用来存储人的序号，pwd用来存储人的密码struct LNode *next;struct LNode *head, *p, *pt;定义结点2、 创立循环链表函数int CreatLinkList(int n)参数n传递人数,inti;head=(structLNode*)malIoc(sizeof(structLNode);创立一个带头结点的链表if(!head)return0;创立不成功，返回Op=head;for(i=l;i<n;i+)pt=(structLNode*)malIoc(sizeof(structLNode);if(!pt)return0;p->next-pt;P三Pt；p->next=head;构成循环链表pt=head;returnO;/3.创立输入密码函数int enterPwd(int n)参数n传递人数int i, j;printf (z, 请输入密码：n)；for( i=l;i<=n;i+) (scanf&j);pt->num=i;pt->pwd=j;/num存储人的序号/pwd存储人的密码pt=pt->next;pt=p;return j;4、创立输出函数int OUtList(int m, intn)参数m、n传递报数上限值和人数int i, a;for(i=l;i<=n;i+)用一个for循环搜索循环链表for(a=l;a<m;a+)删除结点pt=pt->next;p=pt->next;m=p->pwcl;printf(,%dz,p->num);输出人的序号pt->next=p->next;free(p);释放动态申请的结点空间return0;)主函数voidmain()i11tm,n;m为报数上限值，n为人数printf(n参数m>n传递报数上限值和人数;n)；Printf("n请输入m和n:n)；scanf(,z%d%d,&m,&n);CreatLinkList(n);调用创立链表函数enterPwd(n);调用输入密码函数printf(zzn出队的人依次是:n);outList(m,n);调用输出链表函数)五、测试结果及功能说明输入报数上限值为m为6,人数n为7；7个人数密码依次是1,2,3,4,5,6,7；出队的人号码依次是：6,5,4,3,2,1,7六、设计体会数据构造是一门比较抽象的课程，但是也是一门最根基的课程学的过程。在现实生活的应用也非常广泛通过设计该实验让我更加深刻的掌握了掌握了，有关链表的知识，同时也认识到了自己在平时学习当中的盲点，通过这次实验发现了自己在数据构造这门功课上存在严重的缺乏。链表中的指针理解不够，运用不够熟练，常常出现一些莫名其妙的问题，调试费时太多。今后一定会多编程，多思索。在以后的学习过程中还需要不断的完善学习，希望能把数据构造这门课学习的更加深入，更加透彻。最后，非常感谢教师在实验的过程所提供的帮助和指导。
