数据结构约瑟夫环问题.docx

数据结构实验报告题目：约瑟夫环问题一．设计内容[问题描述]约瑟夫环问题的一种描述是：编号为1,2,3,…，n的n个人按顺时针方向围坐一圈，每人手持一个密码(正整数)一开始任选一个整数作为报数上限值，从第一人开始顺时针自1开始顺序报数，报到m时停止报数报m的人出列，将它的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去直到所有人全部出列为止试设计程序实现之[基本要求]利用循环链表存储结构模拟此过程，按照出列的顺序打印各人的编号[实验提示]程序运行后首先要求用户指定初始报数上限值然后读取各人的密码设n<=30程序执行后，要求用户在计算机终端上显示“提示信息”后，用键盘输入“提示信息”中规定的命令，以“回车符”为结束标志相应的输入数据和运算结果显示在其后二、设计目的1 .达到熟练掌握C+钠言的基本知识和技能；2 .能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题3 .把课本上的知识应用到实际生活中，达到学以致用的目的三、系统分析与设计(确定程序功能模块)1、为实现上述程序的功能，应以有序链表表示集合基本操作：InitList(&L)操作结果：构造一个空的有序表L。

DestroyList(&L)初始条件：有序表L已存在操作结果：销毁有序表LListEmpty(L)初始条件：有序表L已存在操作结果：若L为空表，则返回TRUE否则返回FALSEListLength(L)初始条件：有序表L已存在操作结果：返回L中数据元素个数GetElem(L,i)初始条件：有序表L已存在，并且10i&ListLength(L)操作结果：返回L中第i个数据元素LocatePos(L,e)初始条件：有序表L已存在，e和有序表中元素同类型的值操作结果：若L中存在和e相同的元素，则返回位置；否则返回0InsertElem(&L,e)初始条件：有序表L已存在操作结果：在L中，按有序关系插入值和e相同的数据元素DeleteElem(&L,i)初始条件：有序表L已存在操作结果：删除L中第i个数据元素ListTraverse(L,visit())初始条件：有序表L已存在操作结果：依次对L的每个数据元素调用函数visit()一旦visit()失败，则操作失败}ADTOrderedList2、本程序包含两个模块：(1)主程序模块：voidmain(){初始化；调用函数(接受命令，处理命令)}(2)有序表单元模块——实现有序表的抽象数据类型。

3)输出函数模块——有序表的输出四、源程序代码#include""#include""素类型，结点类型和指针类型typedefstructLNode建输入密码函数intenterPwd(intn)//参数n传递人数{inti,j;printf("\n请输入密码:\n");for(i=1;i<=n;i++){scanf("%d",&j);pt->num=i;pt->pwd=j;pt=pt->next;}pt=p;return j;}//4、创建输出函数int outList(int m,int n){int i,a;//num 存储人的序号//pwd 存储人的密码// 参数 m 、 n 传递报数上限值和人数for(i=1;i<=n;i++)// 用一个 for 循环搜索循环链表{for(a=1;anext;}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);//调用输出链表函数}五、测试结果及功能说明参数*n传递报数上限值和人数,j青输入E和H上67请输入密码:1234567出队的人.依次是士6543217Pressanykeytocontinue输入报数上限值为m为67个人数密码依次是1, 23, 4, 5, 6, 7;出队的人号码依次是：65, 4, 3, 2, 1, 7六、设计体会数据结构是一门比较抽象的课程，但是也是一门最基础的课程学的过程。

在现实生活的应用也非常广泛通过设计该实验让我更加深刻的掌握了掌握了，有关链表的知识，同时也认识到了自己在平时学习当中的盲点，通过这次实验发现了自己在数据结构这门功课上存在严重的不足链表中的指针理解不够，运用不够熟练，常常出现一些莫名其妙的问题，调试费时太多今后一定会多编程，多思索在以后的学习过程中还需要不断的完善学习，希望能把数据结构这门课学习的更加深入，更加透彻最后，非常感谢老师在实验的过程所提供的帮助和指导。