数据结构实践报告
更新时间:2023-12-27 19:29:01 阅读量: 教育文库 文档下载
数据结构实践报告
学 号: 150906112 姓 名: 武锦蓉 班 级: 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 输出: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
二、 程序清单
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)//构造函数,初始化数组 {
listArray=new int[s]; for(int i=0;i
listArray[i]=i+1;//数组值等于数组下标+1 realSize=s;
fence=0;//指向首元素 }
bool remove(int &elem)//移除一个元素 {
if(isEmpty())return false;//如果数组为空返回false
elem = listArray[fence];
for(int i=fence;i listArray[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; } }; 在主函数中调用上述模块的方法: ofstream fout;//文件流 fout.open(\设置文件路径 int n,m,elem,point=0; scanf(\获得用户输入 AList alist(n);//创建顺序表对象 while(!alist.isEmpty())//如果顺序表不为空,继续删除 { m=m%alist.getLength();//调整计数的长度 if(m==0)m=alist.getLength(); if(point+m-1 alist.setPos(point);//设置当前需要删除的位置 alist.remove(elem);//删除元素 cout< fout< 四、测试结果(截图显示) 五、遇到的问题及解决方法 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)的效率除非不用线性表来实现。 六、体会 输入人数n,报数间隔m,创建顺序表对象。 主程序 确定需要删除的位置 !isEmpty () //顺序表不为空 Remove()//调用删除方法 输入和输出的格式: 输入:10,3 输出:3 6 9 2 7 1 8 5 10 4 (文本中的输出):3 6 9 2 7 1 8 5 10 4
正在阅读:
数据结构实践报告12-27
ARM 《IQ》中文杂志 2009 Spring -5-ARM快速模型用于嵌入式软件开发的虚拟平台07-26
伊宁学前教育2017-2018年第二学期05-18
手机可以买彩票啦!——即日起湖南移动用户可以使用手机购买体育彩票。05-03
(审核版)2017-2018学年高二语文上学期期末试题(含解析)(新人教版 第132套)05-05
化学必修一方程式总结05-05
125例唐氏综合征高危孕妇中筛查出1例9qh +、2例inv(9)05-19
新闻本科毕业生论文范文 -10-21
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 数据结构
- 实践
- 报告
- 化妆培训学校推荐,哪个比较好 - 图文
- 加强和创新基层社会管理与做好新时期群众工作的辩证关系
- 全年一次性奖金的个税筹划
- 美沙拉嗪联合加味甘草泻心汤治疗溃疡性结肠炎临床观察
- 关爱进城务工子女工作总结
- 体育活动策划书(呼啦圈比赛、乒乓球赛)
- 统计学期考试题1(附答案)
- 人教版六年级语文下册期中试卷
- 中等职业学校体育与健康课程标准
- 河南省洛阳市2017届高三历史三模试题(含解析)
- 万士伟 水利水电工程地质勘测分析
- 浅谈小学语文课堂教学中的互动交流-精选教育文档
- 浅谈答复审查意见通知书及修改申请文件应注意的问题
- 配套K12北师大版五年级数学上册全册教案1
- 2018-2019年初中语文中考模拟真卷含答案考点及解析
- 关于水的创意图片
- 沙河镇中心小学二年级美术集体备课12
- (上海)高一物理第二学期期中考试题
- 四代移动通信及其技术(4G)
- 学习《毕业后的五年拉开大家差距的原因在哪里》有感