资源描述：
《《数据结构课程设计》实习报告——约瑟夫环》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构实习报告题目：程序求解约瑟夫环问题出列顺序一、需求分析1.以单项循环链表存储结构模拟约瑟夫环问题。即编号为1、2、3…、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺吋针方向自1开始报数，报到m吋停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。按出列顺序印出各人的编号。2.演示程序以用户与计算机的对话方式执行，用户输入相应的数据，输出结果显示在其后。3.测试数据
2、：（1）n=77个人的密码依次为：3,1,7,2,4,&4；首先m值为6（正确的输出顺序为：6,1,4,723,5）⑵n=55个人的密码依次为：1,2,3,4,5首先m值为1（正确的输出顺序为：124,3,5）（3）n=5首先m值为・2（输入的人数和初始密码不能为负数!）二、概要设计为实现上述程序功能，应利用单向循环链表存储结构模拟此过程。1.单向循环链表的抽象数据类型定义为：ADTCircularListj数据对象：D二{ai
3、aiwLNode,i=l,2,...,n,n20}数据关系：Rl={
4、
5、ai-lWD,i=2,...,n}基本操作：StatusListDelete_L（LinkList&L,intI,ElemType&e）操作结果：在带头结点的单链表L中，删除第i个元素，并用e返回其值}2.本程序屮包括的三个基本模块：1）主程序模块：Voidmain（）{初始化；do{接受命令；处理命令；}while（"命令〃二〃退出〃）}2）线性表模块：实现线性表的抽象数据结构3）元素结构单元模块：定义线性表中每个元素的结构三、详细设计1.结点类型typedefstructLNodeintdata;//密码in
6、ti;〃编号structLNode*next;}LNode,*LinkList;2.用循环链表存储约瑟夫环，没有头结点，基本操作函数如下:intCreateList(LinkList&L,intal],intn){//创建循环链表结构的约瑟夫环LinkLists,r;inti;r=L;for(i=l;i<=n;i++){s=(LinkList)malloc(sizeof(LNode));s->data=a[i];s->i=i;if(i==l){L=s;s->next=s;r=s;〃尾指针指向当前元素}else{s-
7、>next=r->next;r->next=s;r=s;}}return1;}intListDelete_L(LNode*L){〃删除表中一个结点if(L->next==L)//只剩一个结点{printf("%d",L->i);free(L);return0;}LNode*p;p=L->next;//p指向要删除元素的下一个结点while(p->next!=L)p=p->next;LNode*q=L;//q指向需要被删除的元素结点inte=L->i;p・>next=L->next;free(q);printf(
8、n%d”,e);return1;}intFindNode(LinkListLJntx){〃查找表中某个结点LinkListp=L;LinkListq;for(inti=l;inext;q二p・>next;〃下一次循坏的起始位置x=p->data;if(ListDelete_L(p))FindNode(q,x);returnp->i;1.主函数:intmain()intn,m;LinkListL;printf(n请输入人数和初始密码:“)；scanf("%d%d”,&n,&m);if(n<0
9、
10、
11、m<0){printfC输入的人数和初始密码不能为负数!”);return0;inta[100];printf(n请输入每个人的密码:“)；for(inti=l;i<=n;i++)scanf(”％d“,&a[i]);if(CreateList(L,a,n)){printf(HH);printf(“正确的岀列顺序为：”);FindNode(L,m);printf(,,H);}return0;2.函数的调用关系图反映了演示程序的层次结构:mainCreateListFindNodeListDelete_L
12、四、调试分析1.刚开始时，忽略了题目要求的没有头结点这一项，没有把第一个结点单独拿出來建立，出现了逻辑上的错误。2.程序在编译时，有很多错误，主要是指针与引用概念不清导致。3.查找下一个吋候采用求余数的方法，减少了循环次数。4.程序的算法复杂度为0((),不过虽然是C++写的，但还有很大的面向过程的思想，函数间的调用显得不好。五、用户手册1.本程序的运行环境
