数据结构实验报告.docx

《数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告.docx（8页珍藏版）》请在第一文库网上搜索。

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

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

3、。1ist1ength(1)初始条件：有序表1已存在。操作结果：返回1中数据元素个数。GetE1em(1,i)初始条件：有序表1已存在，并且IWiW1iSt1ength(1)。操作结果：返回1中第i个数据元素。1ocatePos(1,e)初始条件：有序表1已存在，e和有序表中元素同类型的值。操作结果：若1中存在和e相同的元素，则返回位置；否则返回0。InsertE1em(&1,e)初始条件：有序表1已存在操作结果：在1中，按有序关系插入值和e相同的数据元素。De1eteE1em(&1,i)初始条件：有序表1已存在。操作结果：删除1中第i个数据元素。1istTraverse(1,visit()初

4、始条件：有序表1已存在。操作结果:依次对1的每个数据元素调用函数ViSit()。一旦visit()失败，则操作失败。ADTOrdered1ist2、本程序包含两个模块：(1)主程序模块：voidmain()初始化；调用函数(接受命令，处理命令)(2)有序表单元模块一一实现有序表的抽象数据类型。(3)输出函数模块有序表的输出。四、源程序代码#inc1udestdio.hftinc1ude,ma11oc.h1元素类型，结点类型和指针类型typedefstruct1Nodeintnum,pwd;密码定义结构体，nUm用来存储人的序号，PWd用来存储人的struct1Node*next;）；struc

5、t1Node*head,*p,*pt;定义结点2、创建循环链表函数intCreat1ink1ist(intn)参数n传递人数,inti;head-(struct1Node*)ma1Ioc(sizeof(struct1Node);创建一个带头结点的链表if(!head)return0;创建不成功，返回Op=head;for(i=1;inext=pt;P=Pt；)p-next=head;构成循环链表pt=head;returnO;/3.创建输入密码函数intenterPwd(intn)参数n传递人数inti,j;printf(z,请输入密码：for(i=1;inum=i;pt-pwd=j;pt=p

6、t-next;)pt=p;returnj;)4、创建输出函数intout1ist(intm,intn)inti,a;for(i=1;i=n;i+)(for(a=1;anext;p-t-next;m=p-pwd;printf(z,%d,p-num)pt-next=p-next;n）；/num存储人的序号/pwd存储人的密码参数m、n传递报数上限值和人数用一个for循环搜索循环链表删除结点输出人的序号free(p);释放动态申请的结点空间return0;)主函数voidmain()itm,n;m为报数上限值，n为人数printf(z,参数m、n传递报数上限值和人数;n);Printf(n请输入m和

7、n:n)；scanf(%d%d,&m,&n);Creat1ink1ist(n);调用创建链表函数enterPwd(n);调用输入密码函数printf(,zn出队的人依次是：n);out1ist(m,n);调用输出链表函数)五、测试结果及功能说明t叶:Debug击UeXe-参数m、n传递报数上限值和人数I请输入m和n:67请输入密码：1234567出队的人依次是：6543217Pressanykeytocontinue输入报数上限值为m为6,人数n为7；7个人数密码依次是1,2,3,4,5,6,7；出队的人号码依次是：6,5,4,3,2,1,7六、设计体会数据结构是一门比较抽象的课程，但是也是一门最基础的课程学的过程。在现实生活的应用也非常广泛通过设计该实验让我更加深刻的掌握了掌握了，有关链表的知识，同时也认识到了自己在平时学习当中的盲点，通过这次实验发现了自己在数据结构这门功课上存在严重的不足。链表中的指针理解不够，运用不够熟练，常常出现一些莫名其妙的问题，调试费时太多。今后一定会多编程，多思索。在以后的学习过程中还需要不断的完善学习，希望能把数据结构这门课学习的更加深入，更加透彻。最后，非常感谢老师在实验的过程所提供的帮助和指导。