数据机构实验报告.doc

题目：约瑟夫环问题 班级：网络工程2班 姓名：赵文龙 学号：2220111650 实验日期：2012年12月6日 1、 需求分析 输入的形式和输入值的范围： 每一次输入的值为两个正整数，中间用逗号隔开。 若分别设为n,m,则输入格式为： 不对非法输入做处理，即假设输入都是合法的。 输出的形式： 输出格式1：在字符界而上输出这n个数的输出序列 输出格式2：将这n个数的输出序列写入到文件中 程序所能达到的功能： 对于输入的约瑟夫环长度n和间隔m,输出约瑟夫环的出列顺序。 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 正确： 输入:10,3 输出1()4 输入：41,3 输出：3 6 9 12 15 1821 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 1631 错误： 输入:103 输岀：687134295 10 2、 概要设计 抽象数据类型的定义： 为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线 性表中。线性表ADT定义如下： ADT list 数据对象：整形 数据关系：线性关系，即ai,ai+l(0^an)o 基本操作： bool remove(int elem)//移除一个元素,被移除的元素赋给elem 〃如果操作成功，返回true,否则返1h| false bool isEmpty()//判断数组的元素是否清空，空返回tme,否则返回false bool setPos(int place)//设置当前元素的位置，设置成功返回true,否则返回false int getLength()//获取数组的实际长度 算法的基本思想: 约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”, 并且存在“唯一的前驱和后继的”，符合线性表的特点。由于需要模拟约瑟夫环的出列 问题，可以采用顺序表来实现线性表，完成出列顺序的输出。 核心算法主要分为两步： 1、确定需要删除的位置，2、设置并删除该位置。 已知报数间隔m,我们可以把当前位置加上m获得需要删除的位置，如果获得的 位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模 拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。 反复进行上述确定位置和删除位置的操作，直到顺序表为空。 （3） 主程序的流程： 程序由三个模块组成： （1） 输入模块：无提示语句，直接输入总人数n和报数次数中间用逗号隔开。 （2） 处理模块：将元素储存于顺序表中。在主函数中根据报数间隔确定需要删除的元 素的位置，在顺序表中设置该位置并删除该位置，同时输出该位置的值。反复设置并 删除直到表空。 （3） 输出模块：分别在DOS下和文件中，按移除元素的顺序依次显示其位置。 （4） 各程序模块之间的层次（调用）关系： 主函数会按设计的方法调用顺序表中“获取实际长度”、“设置需要删除元素的位置”、 “移除该位置元素”和“判断是否为空表”四种方法方法，使元素依次出列，并正确结束 程序。 3、详细设计 （1）实现概要设计屮定义的所有数据类型（物理数据结构）： 1、 用整形存储用户输入的整数。 2、 用顺序表实现线性表： class AList { private: int *listArray;//指向数组的指针 int realSize;//数组中含有元素的实际长度 int fence;//指向当前元素下标 public: AList（int s）//构造函数，初始化数组 { listArray=new int[s]; for（int i=0;is;i++） listArray[i]=i+l;//数组值等于数组下标+1 realSize=s; fence=0;〃指向首元素 bool remove(int elem)//移除一个元素 { if(isEmpty())return false;//如果数组为空返回 false elem = listArray[fence]; for(int i=fence;irealSize-l;i++)〃从当前位置开始循环向前赋值 { listArray[i]=listArray[i+l]; } realSize--; return true; } bool isErnpty()//判断数组的元素是否清空 { if(realSi ze==())return true; else return false; } bool setPos(int place)//设置当前元素的位置 { if(place=0place=realSize) {