数据结构实验一约瑟夫问题.doc

HUNAN UNIVERSITY 课程实习报告 题 目： 约 瑟 夫 问 题 学生姓名 刘 海 龙 学生学号 201326010115 专业班级 软 件1 3 0 1 指导老师 李 晓 鸿 完 成 日 期 2 0 1 4 年 11 月 18 日 一、需求分析 输入的形式和输入值的范围 本程序中，输入的人数n和报数值m均为整数，n、m均大于0，输入的形式为：n，m （n、m输入时用逗号隔开） 程序功能 提供用户从键盘输入约瑟夫环的关键数据，人数n和报数值m，并显示出列顺序。 3.输出的形式 在DOS界面上输出这n个数的输出序列。 4.测试数据 ① 输入（n，m均为正整数，且nm） 10，3 输出 3 6 9 2 7 1 8 5 10 4 ② 输入 （n，m均为正整数，且nm） 4，6 输出 2 1 4 3 ③ 输入 （n，m均为正整数，且n=m） 7，7 输出 7 1 3 6 2 4 5 ④ 输入 (n,m中有浮点数) 8，5.56 输出 输入有误，请重新输入！ ⑤ 输入 （n,m中有负数） -3，-8 输出 输入有误，请重新输入！ ⑥ 输入 （n,m未按格式输入） aA2，3asf 输出 输入有误，请重新输入！ 二、概要设计 抽象数据类型 n（n为正整数）个人的编号为1~n，1相当于唯一的“第一元素”，n相当于唯一的“最后元素”，除最后元素n外，剩下的n-1个编号均有唯一的后继，除第一元素1外，剩下的n-1个编号均有唯一的前驱，符合线性结构，故应以线性表实现该结构。 ADT alist { 数据对象： D={ai | ai∈int，i=1，2，…，n，n≥0}. 数据关系： Rl={ai-1，ai | ai-1，ai∈D，i=2，…，n} 基本操作： InitList（L，size）//构造一个空线性表L。 Append(L，e) //新元素e入表 Remove(L，i) //删除表中第i个元素，即将i之后的元素往前移一位。 DesList（L）//销毁线性表，释放内存空间 } 无论选择哪种数据结构都应有一个结构初始化操作及相应的结构销毁操作，本程序的结构初始化操作为：InitList（L，size），结构销毁操作为DesList（L）。 在将n个人的编号存进线性表时，需要一个添加操作，故设计Append(L，e)，其用于向线性表表尾添加新元素e。 “出列”相当于删除线性表中某个指定的元素，这就需要一个删除操作，故设计Remove(L，i)，其根据下标索引需要删除的元素，“删除”即相当于将该元素之后的所有元素向前移动一位。 算法的基本思想 n个人的编号为1,2,3,…,n(n0)，并且这n个人根据编号大小依序排列，即将这n 个编号依序存入线性表中，报数值m为正整数。 ①．编号为1的人从1开始依序报数，即从线性表的第一个元素起开始访问，并依序逐个访问它的下一个元素。 ②．当轮到剩余人群中编号最大的人报数时，剩余人中编号最小的作为他的下一位，继续报数，即当线性表的表尾元素访问完后，将表头元素作为下一个访问对象。 ③．数到m时报数停止，并且数到m的人出列，他的下一位从1开始重新报数。 即访问进行到第m次时停止，将第m次访问到的元素从表中删除，并在DOS界 面上输出对应的编号，然后从它的下一个元素开始新一轮的访问（每轮m次）。 ④．重复步骤2、3，直到出列n个人为止，即当表内元素均被删除为止，此时， 整个出列序列已经输出在DOS界面上。 程序的流程 程序由三个模块组成： （1）输入模块：完成人数和报数值的输入，存入变量n，m中。 （2）功能模块：设计一个实现约瑟夫问题的函数Joseph(L,m），模拟循环报数，每 出列一个元素，通过输出模块将其显示在屏幕上。 （3）输出模块：屏幕上显示出列的元素。 三、详细设计 物理数据类型 输入的人数n与报数值m均应为正整数，为了能够存储和处理，变量n，m采用C语言中的int定义变量。 因为线性表是对n个人的编号1~n进行操作(编号1~n符合线性结构)，过程中无需添加新的元素，即表内元素最多只有n个，为了减小空间上的开销，线性表采用顺序表来实现其物理结构。线性表的每个元素存储的是n个人的编号1~n中的一个，所以线性表中元素类型定义为整型。 #define De