还剩5页未读,继续阅读
文本内容:
数据结构实验报告题目约瑟夫环问题一.设计内容[问题描述]约瑟夫环问题的一种描述是编号为1,2,3,n的n个人按顺时针方向围坐一圈,每人手持一个密码正整数一开始任选一个整数作为报数上限值,从第一人开始顺时针自1开始顺序报数,报到m时停止报数报m的人出列,将它的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去直到所有人全部出列为止试设计程序实现之[基本要求]利用循环链表存储结构模拟此过程,按照出列的顺序打印各人的编号[实验提示]程序运行后首先要求用户指定初始报数上限值然后读取各人的密码设〈=n30程序执行后,要求用户在计算机终端上显示“提示信息”后,用键盘输入“提示信息”中规定的命令,以“回车符”为结束标志相应的输入数据和运算结果显示在其后
二、设计目的
1.达到熟练掌握C++语言的基本知识和技能;
2.能够利用所学的基本知识和技能,解决简单的面向对象程序设计问题
3.把课本上的知识应用到实际生活中,达到学以致用的目的
三、系统分析与设计确定程序功能模块
1、为实现上述程序的功能,应以有序链表表示集合基本操作InitListL操作结果构造一个空的有序表LDestroyListL初始条件有序表L已存在操作结果销毁有序表LListEmptyL初始条件有序表L已存在操作结果若L为空表,则返回TRUE,否则返回FALSEListLengthL初始条件有序表L已存在操作结果返回L中数据元素个数GetElem L,i初始条件有序表L已存在,并且IWiWListLengthL操作结果返回L中第i个数据元素LocatePos L,e初始条件有序表L已存在,e和有序表中元素同类型的值操作结果若L中存在和e相同的元素,则返回位置;否则返回0InsertElemL,e初始条件有序表L已存在操作结果在L中,按有序关系插入值和e相同的数据元素DeleteElemL,i初始条件有序表L已存在操作结果删除L中第i个数据元素ListTraverseL,visit初始条件有序表L已存在操作结果:依次对L的每个数据元素调用函数visit一旦visit失败,则操作失败}ADT OrderedList
2、本程序包含两个模块1主程序模块void main{初始化;调用函数接受命令,处理命令}2有序表单元模块一一实现有序表的抽象数据类型3输出函数模块——有序表的输出
四、源程序代码#include〃stdio.h〃ftinclude^malloc.h〃typedef struct LNode〃定义结构体,int num,pwd;//num用来存储人的序号,pwd用来存储人的〃
1.元素类型,结点类型和指针类型密码struct LNode*next;struct LNode*head,*p,*pt;〃定义结点〃
2、创建循环链表函数int creatLinkListint n〃参数n传递人数,int i;head=struct LNode*mallocsizeofstruct LNode;〃创建一个带头结点的链表if!head{return0;〃创建不成功,返回0p=head;for i=l;in;i++pt=structLNode*mallocsizeofstruct LNode;if!pt{return0;}p-next=pt;P=pt;p-next=head;〃构成循环链表pt=head;return0;int enterPwdintn//参数n传递人数//
3.创建输入密码函数int i,j;printf〃\n请输入密码:\n〃;for i=l;i=n;i++pt-num=i;//num存储人的序号pt-pwd=j;//pwd存储人的密码pt=pt-next;Pt=p;return j;〃
4、创建输出函数int outListint m,intn〃参数隈n传递报数上限值和人数int i,a;fori=l;i=n;i++〃用一个for循环搜索循环链表for a=l;am;a++//删除结点pt=pt-next;p=pt-next;m=p-pwd;printf〃%d〃,p-num;〃输出人的序号pt-next=p-next;〃释放动态申请的结点空间freep;return0;〃主函数void main{intm,n;〃m为报数上限值,n为人数printf〃\n参数m、n传递报数上限值和人数;\n〃;printf\n请输入m和n:\n;scanf,z%d%d”,m,n;creatLinkListn;〃调用创建链表函数enterPwd n;〃调用输入密码函数printf\n出队的人依次是\n;outListm,n;〃调用输出链表函数
五、测试结果及功能说明■F Debu g傲据.exew参教、传递报数上限值和人数m n请输入和m n67请输入密码1234567出队的人依次是6543217Press anykey tocontinue输入报数上限值为m为6,人数n为7;7个人数密码依次是1,2,3,4,5,6,7;出队的人号码依次是6,5,4,3,2,1,7
六、设计体会数据结构是一门比较抽象的课程,但是也是一门最基础的课程学的过程在现实生活的应用也非常广泛通过设计该实验让我更加深刻的掌握了掌握了,有关链表的知识,同时也认识到了自己在平时学习当中的盲点,通过这次实验发现了自己在数据结构这门功课上存在严重的不足链表中的指针理解不够,运用不够熟练,常常出现一些莫名其妙的问题,调试费时太多今后一定会多编程,多思索在以后的学习过程中还需要不断的完善学习,希望能把数据结构这门课学习的更加深入,更加透彻最后,非常感谢老师在实验的过程所提供的帮助和指导。