东北大学数据结构实验分析实验设计_-实验设计.pdf

《东北大学数据结构实验分析实验设计_-实验设计.pdf》由会员分享，可在线阅读，更多相关《东北大学数据结构实验分析实验设计_-实验设计.pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程编号：B080101050 1.实验目的 实验一：1.理解队列的概念以及用法 2.掌握queue类的使用 3.熟练运用队列先进先岀，模拟打印机的工作过程 实验二：1.理解图的概念 2.理解并掌握图的存储，并利用邻接表来存储图的信息 3.理解并掌握 Dijkstra算法 4.运用Dijkstra算法解决最短路径的问题 针对每次实验，写岀你认为比较重要的实验目的 2.实验内容与实验步骤 2.1 打印机模拟程序的内容与步骤(1)简短明确地写岀实验的内容 模拟打印机打印的过程，以先来先服务的策略来完成打印工作。先从一个文件中读取所有任务的 大小与到达时间，并将其存储在 workload队列中。使用

2、一个计数器来模拟时间的流逝，当当前 时间与workload队列中的一个任务的到达时间相等的时候，该任务被弹岀，并被压入到另一个 等待执行的队列中。该等待执行的队列以先入先出的准则依次弹出任务并执行。最后计算出任务 总数与，总等待时间，平均等待时间。(2)简短描述抽象数据类型或设计的函数描述，说明为什么要使用这种抽象数据类 型，并说明你的解决设想 一个simulator的抽闲类和它的实现类 fifo类。该类的simulate函数用来实现先进先岀策略的 打印算法。两个队列，一个 workload队列，一个是等待执行队列。Workload队列中存放的是所有的打印 任务，通过文件读取并保存。而等待执行

3、队列则是为了实现 FIFO功能的队列，即时间小的就先 被压入等待执行队列，自然也就先被 pop并执行。解决设想：利用一个int型变量模拟时间的流逝，然后当等待执行队列为空的时候，就不断循环检查 workload 队列中是否有任务到达，若有则将其弹岀并 push进等待执行队列。而当等待执行队列中有任务 时则执行它，并且同时判断 workload队列中是否有任务到达。若 workload和等待执行队列同时验二理解图的概念理解并掌握图的存储并利用邻接表来存储图的信息理解并掌握算法运用算法解决最短路径的问题针对每次实验写岀你认为比较重要的实验目的实验内容与实验步骤打印机模拟程序的内容与步骤简短明确地写

4、岀实验间并将其存储在队列中使用一个计数器来模拟时间的流逝当当前时间与队列中的一个任务的到达时间相等的时候该任务被弹岀并被压入到另一个等待执行的队列中该等待执行的队列以先入先出的则依次弹出任务并执行最后计算出任并说明你的解决设想一个的抽闲类和它的实现类类该类的函数用来实现先进先岀策略的打印算法两个队列一个队列一个是等待执行队列队列中存放的是所有的打印任务通过文件读取并保存而等待执行队列则是为了实现功能的队列即为空了，则程序结束。-1-简短明确地写岀你实验所采用的存储结构及其用途，详细说明其中的属性的含 义。job类封装了一个任务的所有属性。包括任务的大小和该任务的用户：任务的大小即为该打印 任务

5、一共需要打印的页数，而该任务来自哪个计算机。eve nt类封装了一个打印事件的所有属性。任务本身并不包含打印的信息，而一个打印事件则需要包含一个待执行的任务和该任务到达的时间。打印的时候 就是根据这些信息来执行它。而待执行的任务属性即是一个任务对象，而该任务到达的时间即是 该任务在某个时间到达打印机，并等待被执行。simulator类封装了所有打印机的操作，包括加载任务文件，执行打印任务 等。该类将从文件中加载的任务封装成对象，并存储于 workload队列中。然后待 时间到时，将该任务 pop并push到等待执行队列中。在该队列中自然就按 FIFO 的策略来执行。2.2 欧洲旅行实验的内容与

6、步骤(1)简短明确地写岀实验的内容 该实验就是在互相连接的城市中寻找给定两个城市之间的费用最小的路径。用 邻接表来存储整个图的信息，并用一个 map对象来存储各个城市的信息，包括它上一个城市，从起点到该城市的费用和距离。最后利用 Dijkstra算法来对任意给定的两个城市，计算他们之间 的费用最小的路径。(2)简短描述你在实验中使用的数据结构及算法的基本原理。在本实验中，使用了邻接表，map集合，list集合。邻接表是用于存储整个图的信息的，即它用于存储每一个点，有多少个点与它相连。即对于每一个点，它的名称作为键，而有一个包 含了与它相连的所有点的信息的 list对象作为值。这样就完全保存了该

7、图的全部信息。然后有了 该图，就可以利用 Dijkstra算法来计算任意两点之间的距离。而 Dijkstra算法的基本思想就是，循环找出下一个离起点距离最短的点，并标上标记，纳入以找出最短路径的点的集合。而当找到 的下一个里起点最近的点就是目的地，则循环结束，最短路径则通过 map集合中每一个 City对 象的from_city属性来找到。(3)描述你采用STL中的什么容器或者类实现图的存储，在算法应用过程中使用什么 数据结构或算法提高算法的效率。我们使用STL中的map对象来存储图。即 map中的每一个键都为一个城市名，然后它的值为与 该城市直接相连的所有城市所形成的 list对象。我们使用

8、了邻接表的数据结构，并使用了优先级队列来实现下一个最短路径的点的快速查找，极 大地提高了算法的效率。并且使用了 Dijkstra算法，利用优先级队列逐渐寻找下一个里起点最短 的点，并将它的visited属性标记为true，表示已经访问过，并在每一次访问后，都会更新剩余点 的费用和距离的值。然后再利用优先级队列计算新一轮的距离最短的点。验二理解图的概念理解并掌握图的存储并利用邻接表来存储图的信息理解并掌握算法运用算法解决最短路径的问题针对每次实验写岀你认为比较重要的实验目的实验内容与实验步骤打印机模拟程序的内容与步骤简短明确地写岀实验间并将其存储在队列中使用一个计数器来模拟时间的流逝当当前时间与

9、队列中的一个任务的到达时间相等的时候该任务被弹岀并被压入到另一个等待执行的队列中该等待执行的队列以先入先出的则依次弹出任务并执行最后计算出任并说明你的解决设想一个的抽闲类和它的实现类类该类的函数用来实现先进先岀策略的打印算法两个队列一个队列一个是等待执行队列队列中存放的是所有的打印任务通过文件读取并保存而等待执行队列则是为了实现功能的队列即-2-数据结构实验报告 3.实验环境 操作系统、调试软件名称、版本号，上机地点，机器台号 操作系统：Win dows 8.1 调试软件名称：Codeblocks 12.11 4.实验过程与分析 4.1 打印机模拟程序的过程分析(1)描述你在进行实现时，主要的

10、函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明你设计的巧妙之处。simulate函数为主要的执行 FIFO打印的函数。该算法首先是一个 while循环，该循环中 的部分，由三个判断与语句组成，如果 workload队列和等待执行队列都为空，则可 以断定所有任务全部执行完；而如果等待执行队列为空，则表名现在还没有任务到达打 印机，此时需要循环判断是否有任务到达，并且计数器也循环+1;而如果等待执行队列 不为空，就意为着，需要执行任务，那么则立即执行当前队列顶部任务，计算该任务的 等待时间，加到总等待时间上，并把当前计数器时间加上该任务执行的时间。然后在 workload队列中把任务

11、的执行时间=当前时间的任务给弹岀并压入到等待执行队列中。等着三个判断语句结束后进入 while的下一次循环。该算法具有很小的时间复杂度，O(n)=2n+打印机空闲的秒数。因为对于执行打印任务 的时候，该算法是直接在计数器上加上该任务消耗的时间，而对于 pop岀workload的时间则是 等于任务的个数，然后剩余消耗的时间就是在等待执行队列为空的时候，循环判断 workload队 列中是否有任务到达了，所以此时消耗的循环次数为打印机空闲的秒数。而空间复杂度为：n+2。也就是任务的个数+队列个数。此算法的巧妙之处就在于，并没有以计数器逐渐递增的方式来模拟时间的流逝，而是消 耗多少时间，计数器直接加

12、上该值，并不是等待计数器累加到该值才执行任务。你在调试过程中发现了怎样的问题？又做了怎样的改进(要求写岀具体的事例)在算平均等待时间的时候，把该总时间的类型设置成了整型，导致平均等待时间算错。(3)你的实现是否具有可扩展性，如针对多个打印队列的仿真程序？本实现具有可扩展性，即只要在原来判断单个打印队列是否为空的基础上，加上&语句，即同时判断是否所有打印队列同时为空，如果都为空，则循环判断所有 workload队列中任务是 否已到达时间，若到达了时间则弹岀并 push到相应的打印队列中，这就是由原来的单个 workload 判断变成了循环判断多个 workload。而如果有任一一个打印队列不为空

13、，那么则和原来一样进入 第三个判断中，执行该打印任务，且循环所有打印队列并执行任务。4.2 欧洲旅行实验的过程分析(1)描述你在进行实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明你设计的巧妙之处。主要函数为calc_route函数。该函数运用的算法为 Dijkstra算法，算岀最小路径。该算法从起点开始遍历，然后重新计算与该点相连的所有点到起始点的距离，然后把这些点验二理解图的概念理解并掌握图的存储并利用邻接表来存储图的信息理解并掌握算法运用算法解决最短路径的问题针对每次实验写岀你认为比较重要的实验目的实验内容与实验步骤打印机模拟程序的内容与步骤简短明确地写岀实验间

14、并将其存储在队列中使用一个计数器来模拟时间的流逝当当前时间与队列中的一个任务的到达时间相等的时候该任务被弹岀并被压入到另一个等待执行的队列中该等待执行的队列以先入先出的则依次弹出任务并执行最后计算出任并说明你的解决设想一个的抽闲类和它的实现类类该类的函数用来实现先进先岀策略的打印算法两个队列一个队列一个是等待执行队列队列中存放的是所有的打印任务通过文件读取并保存而等待执行队列则是为了实现功能的队列即都push到优先级队列中，利用优先级队列的排序功能，我们只需要取岀优先级队列中顶部的点，并将其标记为已访问过，然后在访问与该点相连的所有点，再次重复上述过程。即不断寻找下一 个离起点最近的点，并将其

15、标记为 true。该算法的时间复杂度为 0(n)=2n(n为边数)。即每次都要循环遍历与该点相连的所有点，所以 对于两个点之间的那条边需要被遍历两次，虽然只有其中一次才会执行其中的语句。而空间复杂 度为：2倍点的个数+2倍边数。此算法的巧妙之处在于利用了优先级队列，这可以很方便地选取岀下一个离起点最短的点。(2)你在调试过程中发现了怎样的问题？又做了怎样的改进？问题1:访问过的点没有标记为 true,使得进入死循环。解决之道：将其标记为 true。问题2：在reset()方法中初始化的时候，将点的 total_fee属性初始化为了 INT_MAX，使得 永远无法计算出最短路径。解决之道：将其属

16、性初始化为 0。问题3：创建邻接表的时候，先创建一个 listvService*的变量，然后把 outgoing_servicesfrom赋值给它，然后在调用该变量的 push_back方法。而这样永远找不岀最短 路径。解决之道：直接调用 outgoing_servicesfrom的push_back方法将 Service对象push进去。(3)你的实验在解决类似问题时是否具有灵活的可修改性、可扩展性？具有可扩展性，因为可以在优先级队列的比较方法中设置不同的比较算法。这样权值的比较具有 任意性，只要更改此比较方法，就可以求岀任意形式的最短的路径了。5.实验结果总结 5.1 打印机模拟程序的结果

17、总结 回答以下问题：(1)你的测试充分吗？为什么？你是怎样考虑的？充分。不管是任意顺序的任务，还是大的任务先执行，都可以得到正确的结果。(2)为什么你要选用队列作为你应用的数据结构？因为该题是FIFO，而队列也正是先入先岀的数据结构。(3)用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。while(1)/*如果两个队列同时为空，则退岀*/if(workload.empty()&pr in t.empty()break;/如果等待执行队列为空，则循环判断是否有任务到达 else if(pri nt.empty()while(!workload.empty()验二理解图的概念理解并掌

18、握图的存储并利用邻接表来存储图的信息理解并掌握算法运用算法解决最短路径的问题针对每次实验写岀你认为比较重要的实验目的实验内容与实验步骤打印机模拟程序的内容与步骤简短明确地写岀实验间并将其存储在队列中使用一个计数器来模拟时间的流逝当当前时间与队列中的一个任务的到达时间相等的时候该任务被弹岀并被压入到另一个等待执行的队列中该等待执行的队列以先入先出的则依次弹出任务并执行最后计算出任并说明你的解决设想一个的抽闲类和它的实现类类该类的函数用来实现先进先岀策略的打印算法两个队列一个队列一个是等待执行队列队列中存放的是所有的打印任务通过文件读取并保存而等待执行队列则是为了实现功能的队列即if(worklo

19、ad.fron t().arrival_time()=cou nt_time)/*如果时间到了则 pop*/break;else cou nt_time+;else/执行任务 while(!workload.empty()if(workload.fron t().arrival_time()visited=false)f_city-visited=true;list f_city_service=outgo in g_servicesf_city-n ame;list:iterator iter=f_city_service.beg in();/循环遍历与该点相连的所有的点，并重新计算它的距离

20、和费用属性，并将其 列中。for(;iter!=f_city_service.end();iter+)if(cities(*iter)-destination-visited=false)cities(*iter)-destination-total_fee=f_city-total_fee+(*iter)-fee;cities(*iter)-destination-total_distanee=f_city-total_distanee+(*iter)-distanee;cities(*iter)-destination-from_city=f_city-name;candidates.pu

21、sh(cities(*iter)-destination);数据结构实验报告/将已经遍历过的点弹岀优先级队列。can didates.pop();(4)在你的图中使用了怎么样数据结构来优化算法的性能？使用了链接表来存储图的结构，并使用了优先级队列来将其它城市到起点城市的距离进行排序，然后选取岀距离最短的那个城市，作为下一个标记为已访问过的那个城市。这样极大的简化了代 码。(5)源程序的大致的执行过程是怎样的？所以选取链式的存储 push到优先级队 东北大学软件学院 验二理解图的概念理解并掌握图的存储并利用邻接表来存储图的信息理解并掌握算法运用算法解决最短路径的问题针对每次实验写岀你认为比较重要

22、的实验目的实验内容与实验步骤打印机模拟程序的内容与步骤简短明确地写岀实验间并将其存储在队列中使用一个计数器来模拟时间的流逝当当前时间与队列中的一个任务的到达时间相等的时候该任务被弹岀并被压入到另一个等待执行的队列中该等待执行的队列以先入先出的则依次弹出任务并执行最后计算出任并说明你的解决设想一个的抽闲类和它的实现类类该类的函数用来实现先进先岀策略的打印算法两个队列一个队列一个是等待执行队列队列中存放的是所有的打印任务通过文件读取并保存而等待执行队列则是为了实现功能的队列即 Ioad_services 读取数据初始化所有城市的信息 Reset 将总初始化所有城市的属性,验二理解图的概念理解并掌握

23、图的存储并利用邻接表来存储图的信息理解并掌握算法运用算法解决最短路径的问题针对每次实验写岀你认为比较重要的实验目的实验内容与实验步骤打印机模拟程序的内容与步骤简短明确地写岀实验间并将其存储在队列中使用一个计数器来模拟时间的流逝当当前时间与队列中的一个任务的到达时间相等的时候该任务被弹岀并被压入到另一个等待执行的队列中该等待执行的队列以先入先出的则依次弹出任务并执行最后计算出任并说明你的解决设想一个的抽闲类和它的实现类类该类的函数用来实现先进先岀策略的打印算法两个队列一个队列一个是等待执行队列队列中存放的是所有的打印任务通过文件读取并保存而等待执行队列则是为了实现功能的队列即0用和总路程都置为

24、把起pus进优先级队 Whil 循 Fo循环遍历与优先级队列顶部 的相连的点并重新计算与起点 的距离和费 把pus到优先级队 把该顶部的点弹 根据终点城市回退，推算岀整个 最短路径所包括的城市-8-数据结构实验报告 6附录 回答思考题 a）栈和队列在计算机系统中有哪些应用？写岀你知道的系统中，这两种抽象数据类型的应用 An droid系统中的Activity 是用栈来管理的。Linux的CPU调度算法就是用队列来完成的。b）在程序调用的时侯，需要进行函数的切换，你认为函数在进行切换时系统要做那些工作？东北大学软件学院 验二理解图的概念理解并掌握图的存储并利用邻接表来存储图的信息理解并掌握算法运

25、用算法解决最短路径的问题针对每次实验写岀你认为比较重要的实验目的实验内容与实验步骤打印机模拟程序的内容与步骤简短明确地写岀实验间并将其存储在队列中使用一个计数器来模拟时间的流逝当当前时间与队列中的一个任务的到达时间相等的时候该任务被弹岀并被压入到另一个等待执行的队列中该等待执行的队列以先入先出的则依次弹出任务并执行最后计算出任并说明你的解决设想一个的抽闲类和它的实现类类该类的函数用来实现先进先岀策略的打印算法两个队列一个队列一个是等待执行队列队列中存放的是所有的打印任务通过文件读取并保存而等待执行队列则是为了实现功能的队列即把此时运行的位置进栈 跳转到函数的位置，执行函数 弹出与栈顶元素，回到

26、原来的执行位置，继续执行 C)队列在系统的设计中都起到什么样的作用？举岀你所熟悉的一些队列的应用例子。能够保持程序的执行顺序。在Linux的CPU调度的时候，就是采用多级队列反馈调度，每次都从队头抽取岀一个进程来执行。d)在你的两次实验中分别使用了 STL中的哪些容器？有什么用途？Queue：队列完成先进先岀的功能，即打印的 FIFO策略 Map：用来存储图 List:用来保存一行的数据，大小可以不固定 e)假设一个图采用邻接表存储结构进行存储，在某一个结点的邻接结点链表中，结点的顺序是 否会影响到最短路径算法的结果？不会，因为每次都要把该链表遍历完(2)列岀实验参考的资料 数据结构C+语言描

27、述中国科技大学(3)如果你对这两次实验还有其他的解决方案或设想，或对我们的实验方案有什么意见，请在此 描述。数据结构实验成绩评定表 附录:附录 验二理解图的概念理解并掌握图的存储并利用邻接表来存储图的信息理解并掌握算法运用算法解决最短路径的问题针对每次实验写岀你认为比较重要的实验目的实验内容与实验步骤打印机模拟程序的内容与步骤简短明确地写岀实验间并将其存储在队列中使用一个计数器来模拟时间的流逝当当前时间与队列中的一个任务的到达时间相等的时候该任务被弹岀并被压入到另一个等待执行的队列中该等待执行的队列以先入先出的则依次弹出任务并执行最后计算出任并说明你的解决设想一个的抽闲类和它的实现类类该类的函

28、数用来实现先进先岀策略的打印算法两个队列一个队列一个是等待执行队列队列中存放的是所有的打印任务通过文件读取并保存而等待执行队列则是为了实现功能的队列即评价内 容 具体要求 分值 得分 平时表现 实验过程中，无缺勤现象，态度积极，具有严谨的学习 态度 和认真、踏实、一丝不苟的科学作风。10 提交材 料“学能够按时规范提交实验要求的所有材料（要求在以姓名”命名的文件夹中，包含实验报告电子版、和分别号-以实验源 代码一、二命名的存放两次实验源代码的两个子文件夹，源代 码仅包含代码文件，不要包含工程维护文件 等），材料完备，格式内容等符合要求。10 报告质 量 实验报告格式规范，体例符合要求；报告内容

29、充实、正 确，实验目的归纳合理到位，思考题回答准确。30 实验内 容 认真记录实验能够按实验要求合理设计并开发出程序，数据，原理及实验结果分析准确，归纳总结充分。50 总分 验二理解图的概念理解并掌握图的存储并利用邻接表来存储图的信息理解并掌握算法运用算法解决最短路径的问题针对每次实验写岀你认为比较重要的实验目的实验内容与实验步骤打印机模拟程序的内容与步骤简短明确地写岀实验间并将其存储在队列中使用一个计数器来模拟时间的流逝当当前时间与队列中的一个任务的到达时间相等的时候该任务被弹岀并被压入到另一个等待执行的队列中该等待执行的队列以先入先出的则依次弹出任务并执行最后计算出任并说明你的解决设想一个的抽闲类和它的实现类类该类的函数用来实现先进先岀策略的打印算法两个队列一个队列一个是等待执行队列队列中存放的是所有的打印任务通过文件读取并保存而等待执行队列则是为了实现功能的队列即