数据结构实践报告




数结构实践报告



学 号：
姓 名：
班 级： 班
指导老师：
时 间： 20161221



项目名称
项目构思
程序三模块组成：
（1）输入模块：提示语句直接输入总数n报数次数m中间逗号隔开
（2）处理模块：元素储存序表中函数中根报数间隔确定需删元素位置序表中设置该位置删该位置时输出该位置值反复设置删直表空
（3）输出模块：分DOS文件中移元素序次显示位置
约瑟夫环问题中数位置种数存第元素元素存唯前驱继符合线性表特点需模拟约瑟夫环出列问题采序表实现线性表完成出列序输出
核心算法分两步：
1确定需删位置2设置删该位置
已知报数间隔m前位置加m获需删位置果获位置超序表中实际元素总长度通减数组实际长度修正（模拟环状计数）然序表中前指位置设置该位置继删掉该位置
反复进行述确定位置删位置操作直序表空
程序功模块
1输入形式输入值范围：
次输入值两正整数中间逗号隔开
分设nm输入格式：nm
非法输入做处理假设输入合法

2输出形式：
输出格式1：字符界面输出n数输出序列
输出格式2：n数输出序列写入文件中

3程序达功：
输入约瑟夫环长度n间隔m输出约瑟夫环出列序

4测试数：包括正确输入输出结果含错误输入输出结果
正确：
输入：103
输出：3 6 9 2 7 1 8 5 10 4

输入：413
输出：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
二 程序清单
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()获取数组实际长度




2程序模块间层次（调）关系：
函数会设计方法调序表中获取实际长度设置需删元素位置移该位置元素判断否空表四种方法方法元素次出列正确结束程序

整形存储户输入整数
序表实现线性表：
class AList
{
private
int *listArray指数组指针
int realSize数组中含元素实际长度
int fence指前元素标

public
AList(int s)构造函数初始化数组
{
listArraynew int[s]
for(int i0i listArray[i]i+1数组值等数组标+1

realSizes
fence0指首元素
}

bool remove(int &elem)移元素
{
if(isEmpty())return false果数组空返回false

elem listArray[fence]
for(int ifencei {
listArray[i]listArray[i+1]
}

realSize
return true

}

bool isEmpty()判断数组元素否清空
{
if(realSize0)return true
else return false
}

bool setPos(int place)设置前元素位置
{
if(place>0&&place {
fenceplace
return true
}

return false
}

int getLength()获取数组长度
{
return realSize
}

}

函数中调述模块方法：
ofstream fout文件流
foutopen(C＼＼Josephustxt)设置文件路径
int nmelempoint0
scanf(dd&n&m)获户输入
AList alist(n)创建序表象

while(alistisEmpty())果序表空继续删
{
mmalistgetLength()调整计数长度
if(m0)malistgetLength()

if(point+m1 else{pointpoint+malistgetLength()1}

alistsetPos(point)设置前需删位置
alistremove(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)效率非线性表实现


六体会

输入数n报数间隔m创建序表象



确定需删位置
程序

isEmpty () 序表空
Remove（）调删方法


输入输出格式：
输入：103
输出：3 6 9 2 7 1 8 5 10 4
（文中输出）：3 6 9 2 7 1 8 5 10 4

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档