东北大学数据结构实验报告_第1页
东北大学数据结构实验报告_第2页
东北大学数据结构实验报告_第3页
东北大学数据结构实验报告_第4页
东北大学数据结构实验报告_第5页
已阅读5页,还剩3页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、课程编号:B080101050数据结构实验报告姓名郝伟学号20144805班级软工1409指导教师张莉实验名称数据结构综合实验开发与总结开设学期2014-2015第二学期开设时间第4周第18周报告日期评定成绩评定人张莉评定日期2015-07-15东北大学软件学院数据结构实验报告 东北大学软件学院1. 实验目的针对每次实验,写出你认为比较重要的实验目的实验一:1、了解和掌握队列的数据类型描述及其特点。2、掌握队列初始化、入队、出队等相关基本操作的实现方法,从而达到能灵活运用队列解决应用问题的目的实验二:1、加深对图的表示法和图的基本操作的理解,并可初步使用及操作;2、掌握用图对实际问题进行抽象方

2、法,可以解决基本的问题;3、掌握利用邻接表求解非负权值、单源最短路径的方法,即利用迪杰斯特拉算法 求最短路径,同时掌握邻接表的建立以及使用方法,能够解决相关的问题。4、学会使用STL中的map抽象实际问题,掌握map,List的应用。2. 实验内容与实验步骤2.1打印机模拟程序的内容与步骤(1) 简短明确地写出实验的内容仿真一个网络打印过程(2) 简短描述抽象数据类型或设计的函数描述,说明为什么要使用这种抽象数据类型,并说明你的解决设想使用队列存放等待打印的作业序列 queue<event> wait; 因为队列的特点就是先进先出十分适合打印机的需求首先判断作业是否到达,若到达输出

3、相关信息,最后加入到wait中然后判断打印机是否空闲,若空闲且wait中有作业的话,按照先后顺序打印 (3) 简短明确地写出你实验所采用的存储结构及其用途,详细说明其中的属性的含义。存储结构:queue<event> wait;用途:存放等待打印的作业序列主要属性:2.2欧洲旅行实验的内容与步骤(1) 简短明确地写出实验的内容求两个城市之间的最便宜的乘车路线(2) 简短描述你在实验中使用的数据结构及算法的基本原理。数据结构使用Map来实现图的存贮 键:城市名,值:该城市与相邻城市的边的链表使用Map实现城市的存贮,键:城市名,值:该城市所对应的实体类使用priority_queue

4、存放未被标记为最短路径的城市算法:使用 Dijkstra's shortest path algorithm 。1)待用户输入起点与终点城市后,调用reset方法重置Map中city中的信息 2) 首先将起点城市的标记为最短路径的城市,然后将它的相邻城市加入priority_queue.3)开始循环,更新最短路径信息选出priority_queue中路径最短的城市 a,。然后将它从priority_queue删除。遍历城市a的邻接城市 如果该相邻城市b不在最短路径节点中, 则判断 若起点城市到b城市原本无路可走,则添加此路径,通 过a城市中转 若原路径费用更大则修改为通过a城市中转 最

5、后将此城市加入优先级队列中 直到priority_queue为空为止(3) 描述你采用STL中的什么容器或者类实现图的存储,在算法应用过程中使用什么数据结构或算法提高算法的效率。使用Map来实现图的存贮 键:城市名,值:该城市与相邻城市的边的链表在计算最小路时使用priority_queue存放未被标记为最短路径的城市,因为priority_queue可以根据你写的排序算法自动将最小路径的城市放在队首的位置3. 实验环境操作系统、调试软件名称、版本号,上机地点,机器台号操作系统:Windows 10调试软件:Dev C+ 版本号5.9.2上机地点:信息楼A415 机器台号:自带笔记本4. 实验

6、过程与分析4.1打印机模拟程序的过程分析(1) 描述你在进行实现时,主要的函数或操作内部的主要算法,分析这个算法的时、空复杂度,并说明你设计的巧妙之处。主要操作:首先判断作业是否到达,若到达输出相关信息,最后加入到wait队列中然后判断打印机是否空闲,若空闲且wait中有作业的话,按照先后顺序打印由于等待与打印并发执行:故空间复杂度为O(n)使用队列存贮,故空间复杂度为O(n)(2) 你在调试过程中发现了怎样的问题?又做了怎样的改进(要求写出具体的事例)一些打印任务是同时到达的,一开始只取出一个任务后计时器便加一,由此漏掉了一些打印任务,经过调试后,在一个while循环中加入打印任务,这样便可

7、解决。(3) 你的实现是否具有可扩展性,如针对多个打印队列的仿真程序?不能,程序中没有涉及过同步的有关内容4.2欧洲旅行实验的过程分析(1) 描述你在进行实现时,主要的函数或操作内部的主要算法,分析这个算法的时、空复杂度,并说明你设计的巧妙之处。void RailSystem:reset(void):遍历map类cities中的对象,将以前产生的信息清除,重新初始化。时间复杂度O(n),空间复杂度O(1)。 void RailSystem:load_services(string const &filename):导入文件,构建铁路系统的模拟图。时间复杂度O(n),空间复杂度O(1)。

8、pair<int, int> RailSystem:calc_route(string from, string to):实现最小路径算法,把信息存储在map<string,City*>中。时间复杂度O(n2),空间复杂度O(1)。string RailSystem:recover_route(const string& city):还原从from到to的最小费用路径的路线。时间复杂度O(n),空间复杂度O(1)(2) 你在调试过程中发现了怎样的问题?又做了怎样的改进?一开始没想明白 reset()的作用,后来仔细研究了一下实际应用,就想明白了。(3) 你的实验

9、在解决类似问题时是否具有灵活的可修改性、可扩展性?有一定的可修改性,因为我的程序都是一步步的解决问题,较好的实现了模块化,并且关键步骤都有注释5.实验结果总结5.1打印机模拟程序的结果总结回答以下问题:(1) 你的测试充分吗?为什么?你是怎样考虑的?充分,与给出的实验结果一模一样(2) 为什么你要选用队列作为你应用的数据结构?因为队列的特点就是先进先出十分适合打印机的需求(3) 用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。(4) 用结构化图表或者结构化代码描述源程序的大致的执行过程。等待作业到达,若到达输出相关信息,并加入到等待列表中若打印机空闲且wait中有作业的话,打印,

10、然后更新所有作业等待的总时间,并且计算出下一次的空闲时间 计时器加一5.2欧洲旅行实验的的结果总结回答以下问题:(1) 你的测试充分吗?为什么?你是怎样考虑的?我测试了多个城市,结果都正确(2) 在你的问题解决方案中,为图选取了顺序的还是链式的存储结构?为什么要选取这种存储结构?链式的存储,因为存储数量未知,链式支持动态存储(3) 用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。(4) 在你的图中使用了怎么样数据结构来优化算法的性能?在计算最小路时使用priority_queue存放未被标记为最短路径的城市,因为priority_queue可以根据你写的排序算法自动将最小路径的城

11、市放在队首的位置(5) 源程序的大致的执行过程是怎样的?Reset(刷新)>load(载入文件,构建铁路系统模拟图)>cac_route(计算两城市之 间最短路径)>print(打印总费用和总距离,以及路线)6.附录(1) 回答思考题a) 栈和队列在计算机系统中有哪些应用?写出你知道的系统中,这两种抽象数据类型的应用。队列:处理机调度中的fifo算法栈:递归时,将函数状态压入中b) 在程序调用的时侯,需要进行函数的切换,你认为函数在进行切换时系统要做那些工作?当调用一个函数时,将把本函数的参数、返回位置、返回值打包压入栈中。这样,每退出一个函数的调用,就会从栈中弹出一条工作记

12、录,里面记录了返回值和返回位置,可以使函数使用完毕后回到本次调用语句的后继语句中。类似递归工作栈c) 队列在系统的设计中都起到什么样的作用?举出你所熟悉的一些队列的应用例子。处理机调度中的fifo算法d) 在你的两次实验中分别使用了STL中的哪些容器?有什么用途?Map存放键值对List 相当于动态数组quene 一种先到先出的存贮结构prority_quene 堆结构e) 假设一个图采用邻接表存储结构进行存储,在某一个结点的邻接结点链表中,结点的顺序是否会影响到最短路径算法的结果?不会,迟早都要被遍历到,只要路径不是最短就一定会被改动(2) 列出实验参考的资料一些网上资料以及C+ API(3) 如果你对这两次实验还有其他的解决方案或设想,或对我们的实验方案有什么意见,请在此描述。 实验二中图也可以试试用矩阵存放。- 5 -附录 数据结构实验成绩评定表 附录:数据结构实验成绩评定表评价内容具 体 要 求分值得分平时表现实验过程中,无缺勤现象,态度积极,具有严谨的学习态度和认真、踏实、一丝不苟的科学作风。10提交材料能够按时规范提交实验要求的所有材料(要求在以“学号-姓

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论