数据结构实践报告Word格式.docx
- 文档编号:7973766
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:7
- 大小:63.42KB
数据结构实践报告Word格式.docx
《数据结构实践报告Word格式.docx》由会员分享,可在线阅读,更多相关《数据结构实践报告Word格式.docx(7页珍藏版)》请在冰点文库上搜索。
在主函数中根据报数间隔确定需要删除的元素的位置,在顺序表中设置该位置并删除该位置,同时输出该位置的值。
反复设置并删除直到表空。
(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
数据对象:
整形
数据关系:
线性关系,即<
ai,ai+1>
(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<
s;
i++)
listArray[i]=i+1;
//数组值等于数组下标+1
realSize=s;
fence=0;
//指向首元素
}
boolremove(int&
elem)//移除一个元素
if(isEmpty())returnfalse;
//如果数组为空返回false
elem=listArray[fence];
for(inti=fence;
realSize-1;
i++)//从当前位置开始循环向前赋值
listArray[i]=listArray[i+1];
realSize--;
returntrue;
boolisEmpty()//判断数组的元素是否清空
if(realSize==0)returntrue;
elsereturnfalse;
boolsetPos(intplace)//设置当前元素的位置
if(place>
=0&
&
place<
=realSize)
fence=place;
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<
alist.getLength()){point=point+m-1;
}//设置偏移位置
else{point=point+m-alist.getLength()-1;
}
alist.setPos(point);
//设置当前需要删除的位置
alist.remove(elem);
//删除元素
cout<
<
elem<
"
"
;
//DOS输出
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
(文本中的输出):
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实践 报告