数据结构实验约瑟夫问题实验报告

1、数据结构实验报告课程名称数据结构实验名称数据结构试验专业班级姓名学号实验日期第11周星期日 节2012 2013学年度第 一 学期一、实验目的1、用数组来实现约瑟夫问题二、实验内容1、试分别用线性表的向量存储结构和数组存储结构来实现约瑟夫(Josephu)问题。约瑟夫问题如下：设有n个人围坐圆桌周围。从某个位置上的人开始从1报数，数到m的人便出列，下一个人(第m+1个)又从1报数开始，数到m的人便是第2个出列的人，依次类推，直到最 后一个人出列为止，这样就可以得到一个人员排列的新次序。例如，n=8,m=4,从第1个人数起，得到的新次序为 48521376.三、实验环境1、硬件配置：Pentiu

2、m (R) Dual-Core9 CUP E6500 2.93GHz , 1.96 的内存2、软件环境：Microsoft Windows XPProfessional Service Pack 3, Microsoft Visual C+ 6.0四、需求分析1、输入的形式和输入值的范围：根据题目要求与提示输入数据的总数，间隔数和开始 计数的位置2、输出的形式：输出每个挑选的数据3、程序所能达到的功能： 从开始计数的位置起，每隔间隔数， 就把该位置的数字输出， 同时此数被释放掉， 然后从继续此操作， 若到数据结束位置， 则重新开始进行。程序结束的 条件是所有的数据输出，释放掉。4、测试数据：输

3、入一个链表，首先输入数据总数，然后输入间隔数，再输入起始位置， 若起始位置大于数据总数， 会提示错误，要求重新输入起始位置， 直至起始位置不大于总数。 然后开始输入数据，数据以空格隔开，最后输出结构。如：输入数据总数8,间隔数4,起始位置1 ,输入数据1 2 3 4 5 6 7 8输出的链表为：4 8 5 2 1 3 7 6五、概要设计为了实现上述操作，应以数组结构。1、本程序包含二个模块：(1)主程序模块；3、流程图输入数据的总数num间隔数count起始位直start当 Start>num输入总数num输入起始位直start当 I<num按输入顺序将输入的数字存进a数组中设定这

4、个循环是死循环I+_I=num .一一 是否I=i%numJ" _A_i!=0 一_是否I+一 .j二count. 一, 一 一是否Bk+=aiAi=0J=0_一K=num是否跳出循环当 K<num输出数组B六、详细设计主函数详解#include"stdio.hvoid main()int a10,b10,i,j,k,count,num,start;printf(" 请输入总数：")；scanf("%d",&num);printf("请输入间隔数：")；scanf("%d",&am

5、p;count);printf("请输入起始位置：")；scanf("%d",&start);printf("n");while(start>num)printf("请重新输入：n");printf("请输入总数：")；scanf("%d",&num);printf("请输入起始位置：")；scanf("%d",&start);printf("请输入数据：n");for (i=0;i&l

6、t;num;i+)scanf("%d”,&ai);printf("n");i=start-1;/为了保持起始条件匹配k=0;for(j=1;)/为死循环i+；if (i=num)为了实现每次i的循环遍历A数组i=i%num;if (ai!=0)只有ai不为零时，才能j+j+;if (j=count)达至U间隔数bk+=ai; 将a数组的彳I赋给b数组ai=0；j=0;/使记录间隔的重新开始计数if (k=num)/ 当b数组有了 a数据全部数据时，结束循环 break;printf(" 标准顺序为：n");for(k=0;k<nu

7、m;k+)printf(" %d",bk);printf("n");3、完整的程序：#include"stdio.h"void main()int a10,b10,i,j,k,count,num,start;printf("请输入总数：")；scanf("%d",&num);printf(" 请输入间隔数：")；scanf("%d",&count);printf("请输入起始位置：")；scanf("%d&qu

8、ot;,&start);printf("n");while(start>num)printf("请重新输入：n");printf("请输入总数：")；scanf("%d",&num);printf("请输入起始位置：");scanf("%d",&start);printf("请输入数据：n");for (i=0;i<num;i+)scanf("%d”,&ai);printf("n")

9、;i=start-1;k=0;for(j=1；)i+；if (i=num)i=i%num;if (ai!=0)j+；if (j=count)bk+=ai；ai=0；j=0；if (k=num)break;printf("标准顺序为：n");for(k=0;k<num;k+)printf(" %d",bk);printf("n");七、程序使用说明及测试结果1、程序使用说明(1)本程序的运行环境为 VC6.0。(2)进入演示程序后即显示提示信息：输入一个链表，首先输入数据总数， 然后输入间隔数，再输入起始位置，若起始位置大 于数据

10、总数，会提示错误，要求重新输入起始位置，直至起始位置不大于总数。然后开始输 入数据，数据以空格隔开，最后输出结构。2.数据输入如：输入数据总数8,间隔数4,起始位置1,输入数据1 2 3 4 5 6 7 8输出的链表为：4 8 5 2 1 3 7 63、调试中的错误及解决办法。开始遇到很多问题，但是重新改善一下编程的思路，通过逐步的调试可以看到正确的结 果。数据输入的流程如下运行界面先输入8后，回车：XDociuent s再输入间隔数4后回车:输入起始位置。:Dacuen*w and 5Mtin/Adaim区teton桌面'实用二罅表表示茯 法DeL. ht输人总市"C:D&

11、#187;cii»ents 叼口 5Mtin/'ASini品泉面'实用二'蹿表表示茯 法DeL._*H:4置 ,数位二 莪隔始据 莒向起致 R人入入 二1一二* .), 鬻请胃输入数据1 2 3 4 5 6 7 8,回车:一"C; Dacu*ents and 5近11小号人（1>1也3七工事t0工泉面实用二罅表表示津 法1Deb. . .1 2 3 4 S a 71 2 3 4 5 fc 7 师选后的结果为4 8 S 2 1 3 7Press an/ kevcont i nue筛选后的结果就如屏幕所示若中途输入的起始位置为 9,回车，会提示如下"C: D»cii*enTs and 5Mtin/'ASini品tmtoi'泉面'实用二'罅表表示茯 法DeL总.问起啕 人入入位新t 9蜘4位置小篇髓下输入n八、实验小结：你在编程过程中花时多少？总共用来将近2小时多少时间在纸上设计？大约有半个小时在纸上设计多少时间上机输入和调试？45 分钟左右多少