数据结构实验报告一-约瑟夫环问题

1． 需求分析

（1） 输入的形式和输入值的范围：

每一次输入的值为两个正整数，中间用逗号隔开。 若分别设为n,m，则输入格式为：“n,m”。

不对非法输入做处理，即假设输入都是合法的。

（2） 输出的形式：

输出格式1：在字符界面上输出这n个数的输出序列 输出格式2：将这n个数的输出序列写入到文件中

（3） 程序所能达到的功能：

对于输入的约瑟夫环长度n和间隔m，输出约瑟夫环的出列顺序。

（4） 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

正确：

输入：10,3 输出：3 6 9 2 7 1 8 5 10 4

输入：41,3

输出：3 6 9 12 15 18 21 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 16 31

错误：

输入：10 3

输出：6 8 7 1 3 4 2 9 5 10

2． 概要设计

（1）抽象数据类型的定义：

为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线性表中。线性表ADT定义如下：

ADT list

数据对象：整形

数据关系：线性关系，即(0≤a＜n)。 基本操作：

bool remove(int &elem)//移除一个元素，被移除的元素赋给elem //如果操作成功，返回true,否则返回false

bool isEmpty()//判断数组的元素是否清空，空返回true,否则返回false

bool setPos(int place)//设置当前元素的位置，设置成功返回true,否则返回false

int getLength()//获取数组的实际长度

－ 1 －

（2）算法的基本思想：

约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。

核心算法主要分为两步：

1、确定需要删除的位置，2、设置并删除该位置。

已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。

反复进行上述确定位置和删除位置的操作，直到顺序表为空。

（3）主程序的流程：

程序由三个模块组成：

（1）输入模块：无提示语句，直接输入总人数n和报数次数m，中间用逗号隔开。 （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;ilistArray[i]=i+1;//数组值等于数组下标+1 realSize=s;

fence=0;//指向首元素 }

－ 2 －

bool remove(int &elem)//移除一个元素 {

if(isEmpty())return false;//如果数组为空返回false

elem = listArray[fence];

for(int i=fence;ilistArray[i]=listArray[i+1]; } realSize--; return true; }

bool isEmpty()//判断数组的元素是否清空 {

if(realSize==0)return true; else return false; }

bool setPos(int place)//设置当前元素的位置 {

if(place>=0&&place<=realSize) {

fence=place; return true; }

return false; }

int getLength()//获取数组长度 {

return realSize; } };

－ 3 －

（2） 算法的具体步骤：

在主函数中调用上述模块的方法：

ofstream fout;//文件流

fout.open(\"C:\\\\Josephus.txt\");//设置文件路径 int n,m,elem,point=0;

scanf(\"%d,%d\获得用户输入 AList alist(n);//创建顺序表对象

while(!alist.isEmpty())//如果顺序表不为空，继续删除 {

m=m%alist.getLength();//调整计数的长度 if(m==0)m=alist.getLength();

if(point+m-1alist.setPos(point);//设置当前需要删除的位置 alist.remove(elem);//删除元素

cout<fout<（3） 算法的时空分析和改进设想：

1、初始化部分为循环赋值，时间复杂度为Θ(n)。

2、处理部分，我为了提高效率没有采用循环寻找的方法，直接利用数学关系通过当前位置获得下一位置，因此对于长度为n的约瑟夫环，只做了n次定位，每次定位的复杂度为Θ(1)，所以时间复杂度为Θ(n)。

但是用顺序表实现时，每次其移除的方法是时间复杂度为Θ(k)的(k与实际长度有关)，

(1n)n所以处理部分总的结果是()的，化简后时间复杂度仍然为Θ(n2)。

2

综上，该算法的时间代价为Θ(n2)。

（PS：如果是用循环查找，在n次定位中每次都使用了m次的循环，至少是Θ(n*m)，然后再用顺序表的移除方法，总的复杂度应该是Θ(m*n2)的。）

事实上要用线性表来完成这道题，其复杂度最好也是Θ(n2)的，毕竟对于n个数据，每个都要进行时间复杂度为Θ(n)的删除工作。欲到达Θ(n)的效率除非不用线性表来实现。

－ 4 －

（4） 画出函数的调用关系图：

主程序

输入人数n,报数间隔m，创建顺序表对象。 确定需要删除的位置 ！isEmpty () //顺序表不为空 Remove（）//调用删除方法 DOS和文本输出显示结果

（5） 输入和输出的格式：

输入：10,3

输出：3 6 9 2 7 1 8 5 10 4 （文本中的输出）：3 6 9 2 7 1 8 5 10 4

4、测试结果

－ 5 －