顺序表实现约瑟夫环的问题-C语言

1、算法与数据结构试验报告一专业班级10级计算机工程02试验地点计算机大楼计工教研室学生学号1005080222指导教师蔡琼学生姓名肖宇博试验时间20GG-2-29试验项目算法与数据结构试验类别基础性（） 设计性（） 综合性（2）其它（）试 验 目 的 及 要 求（1）掌握用VC+上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。成绩评定表类另S评分标准分值得分合计上机表现积极出勤、遵守纪律主动完成设计任务30分程序与报告程序代码规范、功能止确报告详实完整、体现收获70分备注：评阅教师：日期：年 月 日试验内容一、实验目的和要求1、实验目的：（1）掌握用VC+上机调试线性表的

2、基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。2、实验内容约瑟夫环问题：设编号为1 , 2, 3,n的n（n0）个人按顺时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针方向自1起顺序报数，报到m时停止并且报m的人出列，再从 他的下一个人开始重新从1报数，报到m时停止并且报m的人出 列。如此下去，直到所有人全部出列为止。要求设计一个程序模拟 此过程，对任意给定的 m和n,求出出列编号序列。3、实验要求：用顺序表实现。二、设计分析根据实验要求，采用顺序表来完成本次实验。实验中定义了两个顺序表，一个用来存储n个人的序号，另一个用来存储 n个人的出队顺序及序号。程序中充分考虑了如果

3、出队的元素大于队列的元素个数时应该有的情况，如果出现这样的错误就提示！否则继续出队！三、源程序代码#i nclude#i nclude#define MAGSIZE 10/宏替换最大值typedef structint dataMAGSIZE;int len gth;Sqlist;void CreatList(Sqlist G&L,int a,int n)/ 创建顺序表L=(Sqlist G)malloc(sizeof(Sqlist);for(int i=0;idatai=ai;L-le ngth=n;void InitList(Sqlist G&L)/ 初始化顺序表L=(Sqlist G)m

4、alloc(sizeof(Sqlist);L-le ngth=O;/释放顺序表空间/约瑟夫环的核心代码void DestoryList(Sqlist G&L) free(L);void josephus(Sqlist G&L)int t=0;int m=0;printf（请输入数到几个人出来）;prin tf(n);sca nf(%d,&m);if（mL-le ngth）printf（没有这么多人呀！、（丿_产）;elseprin tf(出列顺序为：);for(i nt q=L-le ngth;q=1;q-)t=(t+m-1)%q;prin tf(n);prin tf(t%dt,L-datat

5、);for(i nt j=t+1;jdataj-1=L-dataj;prin tf(n);void mai n()Sqlist Gs;In itList(s);int aMAGSIZE;int n=0;printf(请键入要输入几个数);prin tf(n);sca nf(%d,&n);for(int i=0;in;i+)ai=i+1;CreatList(s,a, n);josephus(s);DestoryList(s);prin tf(n);四、测试用例(尽量覆盖所有分支)1.当输入1 , 2 , 3, 4。n的这些数字范围以内的话，可以得到正确的结五、实验总结先后学习了 C/C+,对编程

6、语言基本上有一些了解，但在数据结构试验程序 设计过程中还是学到了很多。经过两天的设计，在不断翻阅以前资料的情况下，有针对性的复习了C/C+中指针、循环的相关理论知识和 VC6.0的基础知识和应用技巧，最后比 较成功的完成了本次的设计。本次设计是运用已学的线性表中顺序表的相关内容，由于以前的指针方面 知识没有学好，刚开始时有些措手不及，尤其是运用指针申请动态内存，遇到 了不小的麻烦，程序检查时没有错误，但运行不了，经过仔细的思考，终于发 现了问题所在，特别高兴。程序运行后，开始考虑各种BUG，比如输入的数大于数组定义的最大值的 时候抑或是数组的数小于应该输入的最小值（比如 0），比如输入的要出列的元 素大于队列中已有的元素抑或是小于数组中应该出现的元素，比如一些错误输 入等等之内的BUG都考虑之后的问题。然后思考与反思后，发现程序还是有美中不足的地方，算法的核心存在一 些不足，比如依次从后往前挪动一个元素的时候存在一些效率上的问题，当元 素较多时，效率不高！考虑到可以采用标记法，把出队元素标记为 0，以后的出 队的时候跳过0，而不是进行挪动，这样程序的效率就大大提高了！本次实验运用的是C语言，大一时就学过了，在今后的试验中应该多尝试 其他的语言