1、计算机科学与工程学院算法与数据结构试验报告一专业班级 试验地点学生学号 指导教师学生姓名 试验时间试验项目 算法与数据结构试验类别 基础性（） 设计性（） 综合性（） 其它（ ）试验目的及要求（1）掌握用 VC+上机调试线性表的基本方法； （2）掌握顺序表的存储结构以及基本运算的实现。成 绩 评 定 表类 别 评 分 标 准 分值 得分 合 计上机表现积极出勤、遵守纪律主动完成设计任务30 分程序与报告程序代码规范、功能正确报告详实完整、体现收获70 分计算机科学与工程学院算法与数据结构试验报告 2备注：评阅教师： 日 期： 年 月 日试 验 内 容一、实验目的和要求1、实验目的：（1）掌握用
2、 VC+上机调试线性表的基本方法； （2）掌握顺序表的存储结构以及基本运算的实现。2、实验内容约瑟夫环问题：设编号为 1，2，3，n 的 n(n0)个人按顺时针方向围坐一圈，m 为任意一个正整数。从第一个人开始顺时针方向自 1 起顺序报数，报到 m 时停止并且报 m 的人出列，再从他的下一个人开始重新从 1 报数，报到 m 时停止并且报 m 的人出列。如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，对任意给定的 m 和 n，求出出列编号序列。3、实验要求：用顺序表实现。2、设计分析根据实验要求，采用顺序表来完成本次实验。实验中采用一维数组屁【】 ，先将 n 个人的编号存入到 p0
3、pn-1。从编号为 1 的人 (下标 t=0)开始循环报数，数到 m 的人(下标 t=(t+m-1)%i)pt，输出并将其从数组中删除（即将后面的元素前移一个位置） ，每次报数的起始位置就是上次报数的出列位置。反复执行直到出列 n 个人为止。3、源程序代码#include#include#include #define MaxSize 100typedef struct List计算机科学与工程学院算法与数据结构试验报告 3int dataMaxSize;int length;*Sqlist;void InitList(Sqlist L-length=0;void CreateList(Sql
4、ist printf(“您想输入的人数为:“);scanf(“%d“,printf(“最初的顺序表为:n“);for(int i=0;idatai=i+1;printf(“%d “,L-datai);L-length=n;计算机科学与工程学院算法与数据结构试验报告 4printf(“n“);void josephus(Sqlist t=0;printf(“最后的顺序表为:“);for(i=L-length;i=1;i-) t=(t+m-1)%i;printf(“%d “,L-datat);for(j=t+1;jdataj-1=L-dataj;printf(“n“);void main()int
5、 tt;Sqlist L;InitList( L);CreateList(L);计算机科学与工程学院算法与数据结构试验报告 5printf(“您想出列的序号为:“);scanf(“%d“,josephus(L,tt);四、测试用例（尽量覆盖所有分支）1.当 nm 且 n%m!=0 时，即当 n 不是 m 的倍数时：n=12，m=5 时约瑟夫环的实验结果为2.当 nm 且 n%m=0 时，即当 n 是 m 的倍数时：n=15，m=5 时约瑟夫环的实验结果为计算机科学与工程学院算法与数据结构试验报告 63. 当 nm 且 n%m=0 时，即当 n 是 m 的约数时：n=4，m=12 时约瑟夫环的实验结果为4.当 nm 且 n%m!=0 时，即当 n 不是 m 的约数时：计算机科学与工程学院算法与数据结构试验报告 8n=3，m=7 时约瑟夫环的实验结果为5当 n 或 m 任一个足够大时n=150，m=7 时约瑟夫环的实验结果为计算机科学与工程学院算法与数据结构试验报告 8五、实验总结
