数据结构实践报告剖析

职教20条

数据结构实践报告

学号： 150906112

姓：武锦蓉

类： NET2类

指导老师：田喜平

时间： 2016-12-21

项目名称

一.项目构想

程序由三个模块组成。

(1)输入模块)在没有提示句的情况下，直接输入总人数n和报告次数m，用逗号隔开。

(2)处理模块)将要素收纳在顺序表中。 在主函数中，根据通知间隔决定要删除的要素的位置，在顺序表中设定该位置并删除，同时输出该位置的值。 重复设置和删除，直到桌子空了。

(3)输出模块)在DOS下和文件中，按照删除要素的顺序依次表示其位置。

约瑟夫环问题的数据是人所处的位置，但该数据存在“第一元素、最后元素”，存在“唯一的前体和后继者”，符合线性表的特征。 由于需要模拟约瑟夫林的输出问题，可以利用顺序表实现线性表，完成输出顺序。

算法主要分为两个阶段：

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

因为知道申报间隔m，所以可以在当前位置上加上m得到应该删除的位置。 如果得到的位置超过了顺序表中实际元素的全长，可以通过减去数组的实际长度进行修改。 也就是说，是伪环计数。 然后，将顺序表中当前的指向位置设定在该位置，删除该位置。

重复上述定位和删除位置操作，直到顺序表为空。

程序的主要功能模块

1、输入格式和输入值范围：

一次输入的值是两个正整数，之间用逗号分隔。

全国教育信息化

假设不处理非法输入，也就是输入全部合法。

2、输出格式：

输出格式1 :将这n个输出序列输出到文字界面

输出格式2 :将这n个输出序列写入文件

3、程序能达到的功能：

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

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

正确：

输入： 10，3

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

输入： 41，3

输出： 369121518212427303363911014192328374171320263440817281125224351631

错误：

输入： 10 3

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

二.程序清单

1、抽象数据类型定义：

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

ADT list

数据对象：格式

数据关系：线性关系，即(0a<； n )。

基本操作：

删除BOLremove(intelem ) /元素，并将删除的元素分配给elem

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

bool isEmpty ()//判断数组的元素是否为空，如果为空，则返回true；否则返回false

boolsetpos(intplace ) /设置当前元素的位置，设置正常返回true，否则返回false

intgetlength(//获取数组的实际长度

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

主函数用设计的方法调用序列图中的“获取实际长度”、“设置删除元素的位置”、“删除该位置的元素”、“判断是否为空表”四种方法，按顺序列出元素，然后进行设置

保存用户在整形中输入的整数。

用顺序表实现线性表：

class AList

{

私有：

int *listArray；

国家职业教育

int fence； //指当前元素的下标

公共：

初始化alist(ints )//构造函数和数组

{

listArray=new int[s]；

for(intI=0； i=0place=realSize )

{

fence=place；

返回真；

}

返回假；

}

intgetlength(//获取数组的长度

{

return realSize；

}

(；

如何在主函数中调用上述模块：

流浮； //文件流

fut.open(c:(JosePhus.txt ) )； //设定文件路径

int n，m，elem，point=0；

scanf('%d，%d '，n，m )； //获得用户输入

alistalist(n； //创建顺序表对象

while (！

m=m%alist.getLength (； //调整计数的长度

if(m==0) m=alist.getLength )；

pointm-1