数据结构实践报告.pdf

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

1、数据结构实践报告 学号： 150906112 姓名：武锦蓉 班级： NET2班 指导老师：田喜平 时间： 2016-12-21 项目名称 一、 项目构思 程序由三个模块组成： （1）输入模块：无提示语句，直接输入总人数n 和报数次数 m，中间用逗 号隔开。 （2）处理模块：将元素储存于顺序表中。在主函数中根据报数间隔确定需 要删除的元素的位置，在顺序表中设置该位置并删除该位置，同时输出该位 置的值。反复设置并删除直到表空。 （3）输出模块：分别在DOS 下和文件中，按移除元素的顺序依次显示其位 置。 约瑟夫环问题中的数据是人所在的位置，而这种数据是存在 “第一元素、 最后元素”，并且存在“唯一

2、的前驱和后继的” ，符合线性表的特点。由于需 要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序 的输出。 核心算法主要分为两步： 1、确定需要删除的位置，2、设置并删除该位置。 已知报数间隔 m，我们可以把当前位置加上m 获得需要删除的位置，如 果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际 长度来修正（即模拟环状计数） 。然后把顺序表中的当前指向位置设置为该 位置，继而删掉该位置。 反复进行上述确定位置和删除位置的操作，直到顺序表为空。 程序主要功能模块 1、输入的形式和输入值的范围： 每一次输入的值为两个正整数，中间用逗号隔开。 若分别设为 n,m，则

3、输入格式为：“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

4、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 数据对象：整形 数据关系：线性关系，即(0an)。 基本操作： bool remove(int / 指向数组的指针 int realSize;/数组中含有元素的实际长度 int fence;/指向当前元素下标 public: AList(int s)/ 构造函数，初始化数

5、组 listArray=new ints; for(int i=0;i=0 return true; return false; int getLength()/获取数组长度 return realSize; ; 在主函数中调用上述模块的方法： ofstream fout;/文件流 fout.open(“C:Josephus.txt“);/设置文件路径 int n,m,elem,point=0; scanf(“%d,%d“,/ 获得用户输入 AList alist(n);/ 创建顺序表对象 while(!alist.isEmpty()/ 如果顺序表不为空，继续删除 m=m%alist.getL

6、ength();/调整计数的长度 if(m=0)m=alist.getLength(); if(point+m-1alist.getLength()point=point+m-1; / 设置偏移位置 elsepoint=point+m-alist.getLength()-1; alist.setPos(point);/ 设置当前需要删除的位置 alist.remove(elem);/删除元素 coutelem“ “;/DOS 输出 foutelem“ “;/ 文件输出 四、测试结果（截图显示） 五、遇到的问题及解决方法 1、初始化部分为循环赋值，时间复杂度为(n)。 2、处理部分，我为了提高效

7、率没有采用循环寻找的方法，直接利用数学关 系通过当前位置获得下一位置， 因此对于长度为 n 的约瑟夫环，只做了 n 次定位， 每次定位的复杂度为 (1)，所以时间复杂度为 (n)。 但是用顺序表实现时， 每次其移除的方法是时间复杂度为(k)的(k 与实际长 度有关 )， 所以处理部分总的结果是 ( 2 )1(nn )的， 化简后时间复杂度仍然为 (n 2)。 综上，该算法的时间代价为(n2)。 （PS：如果是用循环查找，在n 次定位中每次都使用了m 次的循环，至少 是(n*m)，然后再用顺序表的移除方法，总的复杂度应该是(m*n 2)的。 ） 事实上要用线性表来完成这道题，其复杂度最好也是(n

8、2)的，毕竟对于n 个数据，每个都要进行时间复杂度为(n)的删除工作。欲到达 (n)的效率除非 不用线性表来实现。 六、体会 输入人数n,报数间隔m，创建顺序表对象。 主程序 输入和输出的格式： 输入：10,3 输出：3 6 9 2 7 1 8 5 10 4 （文本中的输出）：3 6 9 2 7 1 8 5 10 4 个人工作业务总结 本人于 2009 年 7 月进入新疆中正鑫磊地矿技术服务有限公司(前身为“西安中正矿业信息咨询有限公司”)，主要从事测量技术工作，至今已有三年。 在这宝贵的三年时间里，我边工作、边学习测绘相专业书籍，遇到不懂得问题积极的请教工程师们，在他们耐心的教授和指导下，我

9、的专业知识水平得到了很到的提高，并在实地测量工 作中加以运用、总结，不断的提高自己的专业技术水平。同时积极的参与技术培训学习，加速自身知识的不断更新和自身素质的提高。努力使自己成为一名合格的测绘技术人员。 在这三年中，在公司各领导及同事的帮助带领下，按照岗位职责要求和行为规范，努力做好本职工作，认真完成了领导所交给的各项工作，在思想觉悟及工作能力方面有了很大的提高。 在思想上积极向上，能够认真贯彻党的基本方针政策，积极学习政治理论，坚持四项基本原则，遵纪守法，爱岗敬业，具有强烈的责任感和事业心。积极主动学习专业知识，工作态度端 正，认真负责，具有良好的思想政治素质、思想品质和职业道德。 在工作

10、态度方面，勤奋敬业，热爱本职工作，能够正确认真的对待每一项工作，能够主动寻找自己的不足并及时学习补充，始终保持严谨认真的工作态度和一丝不苟的工作作风。 在公司领导的关怀以及同事们的支持和帮助下，我迅速的完成了职业角色的转变。 一、回顾这四年来的职业生涯，我主要做了以下工作： 1、参与了新疆库车县新疆库车县胡同布拉克石灰岩矿的野外测绘和放线工作、点之记的编写工作、1:2000 地形地质图修测、1:1000勘探剖面测量、测绘内业资料的编写工作，提交成果 新疆库车县胡同布拉克石灰岩矿普查报告已通过评审。 2、参与了库车县城北水厂建设项目用地压覆矿产资源评估项目的室内地质资料编写工作，提交成果为库车县

11、城北水厂建设项目用地压覆矿产资源评估报告，现已通过评审。 3、参与了新疆库车县巴西克其克盐矿普查项目的野外地质勘查工作，参与项目包括：1:2000 地质测图、 1:1000勘查线剖面测量、测绘内业资料的编写工作；最终提交的新疆库车 县康村盐矿普查报告已通过评审。 4、参与了新疆哈密市南坡子泉金矿2009 年度矿山储量监测工作，项目包括：野外地质测量与室内地质资料的编写，提交成果为新疆哈密市南坡子泉金矿2009年度矿山储量年报， 现已通过评审。 6、参与了新疆博乐市五台石灰岩矿9 号矿区勘探项目的野外地质勘查工作，项目包括：1:2000地质测图、 1:1000勘探剖面测量、测绘内业资料的编写工作

12、，并绘制相应图件。 7、参与了新疆博乐市托特克斜花岗岩矿详查报告项目的野外地质勘查工作，项目包括：1:2000地质测图、1:1000 勘探剖面测量、测绘内业资料的编写工作，并绘制相应图件。 通过以上的这些工作，我学习并具备了以下工作能力： 1、通过实习，对测绘这门学科的研究内容及实际意义有了系统的认识。加深对测量学基本理论的理解，能够用有关理论指导作业实践，做到理论与实践相统一，提高分析问题、解决问 题的能力，从而对测量学的基本内容得到一次实际应用，使所学知识进一步巩固、深化。 2、熟悉了三、四等控制测量的作业程序及施测方法，并掌握了全站仪、静态GPS、RTK 等测量仪器的工作原理和操作方法。

13、 3、掌握了GPS 控制测量内业解算软件（南方测绘Gps 数据处理）以及内业成图软件（南方cass）的操作应用。能够将外业测量的数据导入软件进行地形图成图和处理。 4、在项目技术负责的指导下熟悉了测量技术总结的编写要求和方法，并参与了部分项目测量技术总结章节的编写工作。 5、在项目负责的领导下参与整个测量项目的组织运作，对项目的实施过程有了深刻理解。通过在项目组的实习锻炼了自己的组织协调能力，为以后的工作打下了坚实基础。 二、工作中尚存在的问题 从事测绘工作以来，深深感受到工作的繁忙、责任的重大，也因此没能全方位地进行系统地学习实践，主要表现为没有足够的经验，对于地形复杂的地段理解不够深刻；理论知识掌握不够 系统，实践能力尚为有限。以上问题，在今后工作中自己将努力做到更好。 三、今后的工作打算 通过总结四年来的工作，我无论从工作技术上，还是从世界观、人生观、价值观等各个方面，都有了很大的提高。今后，我会在此基础上，刻苦钻研，再接再厉，使自己在业务知识水平 更上一层楼，为测绘事业的发展，贡献自己的力量。 ！isEmpty () / 顺序表不为空 确定需要删除的位置 Remove（） /调用删除方法