搜索
课程编号：B080101050《数据结构》实验报告姓名郝伟学号20144805班级软工1409指导教师张莉实验名称《数据结构》综合实验开发与总结开设学期2014-2015第二学期开设时间第4周——第18周报告日期评定成绩评定人张莉评定日期2015-07-15东北大学软件学院《数据结构》实验报告东北大学软件学院-1-1.实验目的针对每次实验，写出你认为比较重要的实验目的实验一：1、了解和掌握队列的数据类型描述及其特点。2、掌握队列初始化、入队、出队等相关基本操作的实现方法，从而达到能灵活运用队列解决应用问题的目的实验二：1、加深对图的表示法和图的基本操作的理解，并可初步使用及操作；2、掌握用图对实际问题进行抽象方法，可以解决基本的问题；3、掌握利用邻接表求解非负权值、单源最短路径的方法，即利用迪杰斯特拉算法求最短路径，同时掌握邻接表的建立以及使用方法，能够解决相关的问题。4、学会使用STL中的map抽象实际问题，掌握map，List的应用。2.实验内容与实验步骤2.1打印机模拟程序的内容与步骤(1)简短明确地写出实验的内容仿真一个网络打印过程(2)简短描述抽象数据类型或设计的函数描述，说明为什么要使用这种抽象数据类型，并说明你的解决设想使用队列存放等待打印的作业序列queueeventwait;因为队列的特点就是先进先出十分适合打印机的需求首先判断作业是否到达，若到达输出相关信息，最后加入到wait中然后判断打印机是否空闲，若空闲且wait中有作业的话，按照先后顺序打印(3)简短明确地写出你实验所采用的存储结构及其用途，详细说明其中的属性的含义。存储结构：queueeventwait;用途：存放等待打印的作业序列主要属性：2.2欧洲旅行实验的内容与步骤(1)简短明确地写出实验的内容求两个城市之间的最便宜的乘车路线(2)简短描述你在实验中使用的数据结构及算法的基本原理。数据结构《数据结构》实验报告东北大学软件学院-2-使用Map来实现图的存贮键：城市名，值：该城市与相邻城市的边的链表使用Map实现城市的存贮，键：城市名，值：该城市所对应的实体类使用priority_queue存放未被标记为最短路径的城市算法：使用Dijkstra'sshortestpathalgorithm。1）待用户输入起点与终点城市后，调用reset方法重置Map中city中的信息2）首先将起点城市的标记为最短路径的城市，然后将它的相邻城市加入priority_queue.3)开始循环，更新最短路径信息选出priority_queue中路径最短的城市a，。然后将它从priority_queue删除。遍历城市a的邻接城市如果该相邻城市b不在最短路径节点中，则判断若起点城市到b城市原本无路可走，则添加此路径，通过a城市中转若原路径费用更大则修改为通过a城市中转最后将此城市加入优先级队列中直到priority_queue为空为止(3)描述你采用STL中的什么容器或者类实现图的存储，在算法应用过程中使用什么数据结构或算法提高算法的效率。使用Map来实现图的存贮键：城市名，值：该城市与相邻城市的边的链表在计算最小路时使用priority_queue存放未被标记为最短路径的城市，因为priority_queue可以根据你写的排序算法自动将最小路径的城市放在队首的位置3.实验环境操作系统、调试软件名称、版本号，上机地点，机器台号操作系统：Windows10调试软件：DevC++版本号5.9.2上机地点：信息楼A415机器台号：自带笔记本4.实验过程与分析4.1打印机模拟程序的过程分析(1)描述你在进行实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明你设计的巧妙之处。主要操作：首先判断作业是否到达，若到达输出相关信息，最后加入到wait队列中然后判断打印机是否空闲，若空闲且wait中有作业的话，按照先后顺序打印由于等待与打印并发执行：故空间复杂度为O（n）使用队列存贮，故空间复杂度为O（n）(2)你在调试过程中发现了怎样的问题？又做了怎样的改进（要求写出具体的事例）一些打印任务是同时到达的，一开始只取出一个任务后计时器便加一，由此漏掉了一些打印任务，经过调试后，在一个while循环中加入打印任务，这样便可解决。《数据结构》实验报告东北大学软件学院-3-(3)你的实现是否具有可扩展性，如针对多个打印队列的仿真程序？不能，程序中没有涉及过同步的有关内容4.2欧洲旅行实验的过程分析(1)描述你在进行实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明你设计的巧妙之处。①voidRailSystem::reset(void)：遍历map类cities中的对象，将以前产生的信息清除，重新初始化。时间复杂度O(n)，空间复杂度O(1)。②voidRailSystem::load_services(stringconst&filename)：导入文件，构建铁路系统的模拟图。时间复杂度O(n)，空间复杂度O(1)。③pairint,intRailSystem::calc_route(stringfrom,stringto)：实现最小路径算法，把信息存储在mapstring,City*中。时间复杂度O(n2)，空间复杂度O(1)。④stringRailSystem::recover_route(conststring&city)：还原从from到to的最小费用路径的路线。时间复杂度O(n)，空间复杂度O(1)(2)你在调试过程中发现了怎样的问题？又做了怎样的改进？一开始没想明白reset()的作用，后来仔细研究了一下实际应用，就想明白了。(3)你的实验在解决类似问题时是否具有灵活的可修改性、可扩展性？有一定的可修改性，因为我的程序都是一步步的解决问题，较好的实现了模块化，并且关键步骤都有注释5.实验结果总结5.1打印机模拟程序的结果总结回答以下问题：(1)你的测试充分吗？为什么？你是怎样考虑的？充分，与给出的实验结果一模一样(2)为什么你要选用队列作为你应用的数据结构？因为队列的特点就是先进先出十分适合打印机的需求(3)用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。《数据结构》实验报告东北大学软件学院-4-(4)用结构化图表或者结构化代码描述源程序的大致的执行过程。等待作业到达，若到达输出相关信息，并加入到等待列表中若打印机空闲且wait中有作业的话，打印，然后更新所有作业等待的总时间，并且计算出下一次的空闲时间计时器加一5.2欧洲旅行实验的的结果总结回答以下问题：(1)你的测试充分吗？为什么？你是怎样考虑的？我测试了多个城市，结果都正确(2)在你的问题解决方案中，为图选取了顺序的还是链式的存储结构？为什么要选取这种存储结构？链式的存储，因为存储数量未知，链式支持动态存储(3)用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。《数据结构》实验报告东北大学软件学院-5-(4)在你的图中使用了怎么样数据结构来优化算法的性能？在计算最小路时使用priority_queue存放未被标记为最短路径的城市，因为priority_queue可以根据你写的排序算法自动将最小路径的城市放在队首的位置(5)源程序的大致的执行过程是怎样的？Reset（刷新）—load(载入文件，构建铁路系统模拟图)—cac_route(计算两城市之间最短路径)—print(打印总费用和总距离，以及路线)6.附录(1)回答思考题a)栈和队列在计算机系统中有哪些应用？写出你知道的系统中，这两种抽象数据类型的应用。队列：处理机调度中的fifo算法栈：递归时，将函数状态压入中b)在程序调用的时侯，需要进行函数的切换，你认为函数在进行切换时系统要《数据结构》实验报告东北大学软件学院-6-做那些工作？当调用一个函数时，将把本函数的参数、返回位置、返回值打包压入栈中。这样，每退出一个函数的调用，就会从栈中弹出一条工作记录，里面记录了返回值和返回位置，可以使函数使用完毕后回到本次调用语句的后继语句中。类似递归工作栈c)队列在系统的设计中都起到什么样的作用？举出你所熟悉的一些队列的应用例子。处理机调度中的fifo算法d)在你的两次实验中分别使用了STL中的哪些容器？有什么用途？Map存放键值对List相当于动态数组quene一种先到先出的存贮结构prority_quene堆结构e)假设一个图采用邻接表存储结构进行存储，在某一个结点的邻接结点链表中，结点的顺序是否会影响到最短路径算法的结果？不会，迟早都要被遍历到，只要路径不是最短就一定会被改动(2)列出实验参考的资料一些网上资料以及C++API(3)如果你对这两次实验还有其他的解决方案或设想，或对我们的实验方案有什么意见，请在此描述。实验二中图也可以试试用矩阵存放。附录《数据结构》实验成绩评定表附录：《数据结构》实验成绩评定表评价内容具体要求分值得分平时表现实验过程中，无缺勤现象，态度积极，具有严谨的学习态度和认真、踏实、一丝不苟的科学作风。10提交材料能够按时规范提交实验要求的所有材料（要求在以“学号-姓名”命名的文件夹中，包含实验报告电子版、和分别以实验源代码一、二命名的存放两次实验源代码的两个子文件夹，源代码仅包含代码文件，不要包含工程维护文件等），材料完备，格式内容等符合要求。10报告质量实验报告格式规范，体例符合要求；报告内容充实、正确，实验目的归纳合理到位，思考题回答准确。30实验内容能够按实验要求合理设计并开发出程序，认真记录实验数据，原理及实验结果分析准确，归纳总结充分。50总分