数据结构实践报告.docx

数据结构实践报告.docx

《数据结构实践报告.docx》由会员分享，可在线阅读，更多相关《数据结构实践报告.docx（7页珍藏版）》请在冰点文库上搜索。

数据结构实践报告

数据结构实践报告

学号：

*********

******

班级：

NET2班

*******

时间：

2016-12-21

项目名称

一、项目构思

程序由三个模块组成：

（1）输入模块：

无提示语句，直接输入总人数n和报数次数m，中间用逗号隔开。

（2）处理模块：

将元素储存于顺序表中。

在主函数中根据报数间隔确定需要删除的元素的位置，在顺序表中设置该位置并删除该位置，同时输出该位置的值。

反复设置并删除直到表空。

（3）输出模块：

分别在DOS下和文件中，按移除元素的顺序依次显示其位置。

约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。

由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。

核心算法主要分为两步：

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

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

然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。

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

程序主要功能模块

1、输入的形式和输入值的范围：

每一次输入的值为两个正整数，中间用逗号隔开。

若分别设为n,m，则输入格式为：

“n,m”。

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

2、输出的形式：

输出格式1：

在字符界面上输出这n个数的输出序列

输出格式2：

将这n个数的输出序列写入到文件中

3、程序所能达到的功能：

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

4、测试数据：

包括正确的输入及其输出结果和含有错误的输入及其输出结果。

正确：

输入：

10,3

输出：

36927185104

输入：

41,3

输出：

3691215182124273033363915101419232832374171320263440817293811252224351631

错误：

输入：

103

输出：

68713429510

二、程序清单

1、抽象数据类型的定义：

为实现上述程序的功能，可以用整数存储用户的输入。

并将用户输入的值存储于线性表中。

线性表ADT定义如下：

ADTlist

数据对象：

整形

数据关系：

线性关系，即（0≤a＜n）。

基本操作：

boolremove（int&elem）//移除一个元素，被移除的元素赋给elem

//如果操作成功，返回true,否则返回false

boolisEmpty（）//判断数组的元素是否清空，空返回true,否则返回false

boolsetPos（intplace）//设置当前元素的位置，设置成功返回true,否则返回false

intgetLength（）//获取数组的实际长度

2、各程序模块之间的层次（调用）关系：

主函数会按设计的方法调用顺序表中“获取实际长度”、“设置需要删除元素的位置”、“移除该位置元素”和“判断是否为空表”四种方法方法，使元素依次出列，并正确结束程序。

用整形存储用户输入的整数。

用顺序表实现线性表：

classAList

{

private:

int*listArray;//指向数组的指针

intrealSize;//数组中含有元素的实际长度

intfence;//指向当前元素下标

public:

AList（ints）//构造函数，初始化数组

{

listArray=newint[s];

for（inti=0;i

listArray[i]=i+1;//数组值等于数组下标+1

realSize=s;

fence=0;//指向首元素

}

boolremove（int&elem）//移除一个元素

{

if（isEmpty（））returnfalse;//如果数组为空返回false

elem=listArray[fence];

for（inti=fence;i

{

listArray[i]=listArray[i+1];

}

realSize--;

returntrue;

}

boolisEmpty（）//判断数组的元素是否清空

{

if（realSize==0）returntrue;

elsereturnfalse;

}

boolsetPos（intplace）//设置当前元素的位置

{

if（place>=0&&place<=realSize）

{

fence=place;

returntrue;

}

returnfalse;

}

intgetLength（）//获取数组长度

{

returnrealSize;

}

};

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

ofstreamfout;//文件流

fout.open（"C:

\\Josephus.txt"）;//设置文件路径

intn,m,elem,point=0;

scanf（"%d,%d",&n,&m）;//获得用户输入

AListalist（n）;//创建顺序表对象

while（!

alist.isEmpty（））//如果顺序表不为空，继续删除

{

m=m%alist.getLength（）;//调整计数的长度

if（m==0）m=alist.getLength（）;

if（point+m-1

else{point=point+m-alist.getLength（）-1;}

alist.setPos（point）;//设置当前需要删除的位置

alist.remove（elem）;//删除元素

cout<

fout<

四、测试结果（截图显示）

五、遇到的问题及解决方法

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

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

（1），所以时间复杂度为Θ（n）。

但是用顺序表实现时，每次其移除的方法是时间复杂度为Θ（k）的（k与实际长度有关），所以处理部分总的结果是（

）的，化简后时间复杂度仍然为Θ（n2）。

综上，该算法的时间代价为Θ（n2）。

（PS：

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

）

事实上要用线性表来完成这道题，其复杂度最好也是Θ（n2）的，毕竟对于n个数据，每个都要进行时间复杂度为Θ（n）的删除工作。

欲到达Θ（n）的效率除非不用线性表来实现。

六、体会

主程序

输入和输出的格式：

输入：

10,3

输出：

36927185104

（文本中的输出）：

36927185104