数据结构实践报告学 号: 150906112 姓 名: 武锦蓉 班 级: N Ｅ T2 班 指导老师: 田喜平 时 间： 2 ０ 1 ６ -12-21 项目名称 一、 项目构思程序由三个模块组成:(1）输入模块:无提示语句,直接输入总人数ｎ与报数次数 m,中间用逗号隔开。（2）处理模块:将元素储存于顺序表中。在主函数中根据报数间隔确定需要删除得元素得位置，在顺序表中设置该位置并删除该位置,同时输出该位置得值。反复设置并删除直到表空。(3)输出模块:分别在 D Ｏ S 下与文件中,按移除元素得顺序依次显示其位置。约瑟夫环问题中得数据就是人所在得位置,而这种数据就是存在“第一元素、最后元素”,并且存在“唯一得前驱与后继得”,符合线性表得特点。由于需要模拟约瑟夫环得出列问题,可以采纳顺序表来实现线性表,完成出列顺序得输出。核心算法主要分为两步:1、确定需要删除得位置,2、设置并删除该位置。已知报数间隔 m，我们可以把当前位置加上 m 获得需要删除得位置，假如获得得位置超过顺序表中实际元素得总长度,则可以通过减去数组得实际长度来修正（即模拟环状计数)。然后把顺序表中得当前指向位置设置为该位置,继而删掉该位置。反复进行上述确定位置与删除位置得操作,直到顺序表为空。程序主要功能模块1、输入得形式与输入值得范围:每一次输入得值为两个正整数,中间用逗号隔开。若分别设为 n,m,则输入格式为：“ｎ,ｍ”。不对非法输入做处理,即假设输入都就是合法得。2、输出得形式:输出格式 1：在字符界面上输出这ｎ个数得输出序列输出格式２:将这 n 个数得输出序列写入到文件中3、程序所能达到得功能:对于输入得约瑟夫环长度 n 与间隔ｍ，输出约瑟夫环得出列顺序。4、测试数据:包括正确得输入及其输出结果与含有错误得输入及其输出结果。正确:输入:１ 0，3 输出:3 6 9 2 7 1 8 5 10 ４ 输入:41,３输出：3 ６ 9 12 15 18 ２ 1 24 ２７ 30 ３ 3 36 ３９ １ ５ １0 14 1 ９ 2 ３ 28 ３ 2 3 ７ 4 １ 7 1 ３ 20 26 ３ 4 40 8 1 ７ 2 ９ 3８ １ 1 25 ２ 2 ２ ４ 35 16 3 １错误:输入:1 ０ 3输出:6 ８ ７ １ ３ 4 2 ９ 5 10二、程序清单1、 抽象数据类型得定义:为实现上述程序得功能，可以用整数存储用户得输入。并将用户输入得值存储于线性表中。线性表 ADT 定义如下:AD Ｔ list数据对象:整形数据关系:线性关系，即
