东北大学数据结构实验

《东北大学数据结构实验》由会员分享，可在线阅读，更多相关《东北大学数据结构实验（10页珍藏版）》请在金锄头文库上搜索。

1、数据结构实验报告 东北大学软件学院- 1 -课程编号：课程编号：B080101050B0801010501. 实验目的实验一： 1.理解队列的概念以及用法 2.掌握 queue 类的使用 3.熟练运用队列先进先出，模拟打印机的工作过程实验二： 1.理解图的概念 2.理解并掌握图的存储，并利用邻接表来存储图的信息 3.理解并掌握 Dijkstra 算法 4.运用 Dijkstra 算法解决最短路径的问题针对每次实验，写出你认为比较重要的实验目的2. 实验内容与实验步骤2.1 打印机模拟程序的内容与步骤(1) 简短明确地写出实验的内容 模拟打印机打印的过程，以先来先服务的策略来完成打印工作。先从一

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

3、 队列，一个是等待执行队列。Workload 队列中存 放的是所有的打印任务，通过文件读取并保存。而等待执行队列则是为了实现 FIFO 功能的队列，即时间小的就先被压入等待执行队列，自然也就先被 pop 并执 行。 解决设想： 利用一个 int 型变量模拟时间的流逝，然后当等待执行队列为空的时候，就 不断循环检查 workload 队列中是否有任务到达，若有则将其弹出并 push 进等待 执行队列。而当等待执行队列中有任务时则执行它，并且同时判断 workload 队列数据结构实验报告 东北大学软件学院- 2 -中是否有任务到达。若 workload 和等待执行队列同时为空了，则程序结束。(3

4、) 简短明确地写出你实验所采用的存储结构及其用途，详细说明其中的属性的含 义。job 类封装了一个任务的所有属性。包括任务的大小和该任务的用户：任务 的大小即为该打印任务一共需要打印的页数，而该任务来自哪个计算机。event 类封装了一个打印事件的所有属性。任务本身并不包含打印的信息， 而一个打印事件则需要包含一个待执行的任务和该任务到达的时间。打印的时候 就是根据这些信息来执行它。而待执行的任务属性即是一个任务对象，而该任务 到达的时间即是该任务在某个时间到达打印机，并等待被执行。simulator 类封装了所有打印机的操作，包括加载任务文件，执行打印任务 等。该类将从文件中加载的任务封装成

5、对象，并存储于 workload 队列中。然后待 时间到时，将该任务 pop 并 push 到等待执行队列中。在该队列中自然就按 FIFO 的策略来执行。2.2 欧洲旅行实验的内容与步骤(1) 简短明确地写出实验的内容该实验就是在互相连接的城市中寻找给定两个城市之间的费用最小的路径。用 邻接表来存储整个图的信息，并用一个 map 对象来存储各个城市的信息，包括它 上一个城市，从起点到该城市的费用和距离。最后利用 Dijkstra 算法来对任意给定 的两个城市，计算他们之间的费用最小的路径。(2) 简短描述你在实验中使用的数据结构及算法的基本原理。在本实验中，使用了邻接表，map 集合，list

6、 集合。邻接表是用于存储整个图的 信息的，即它用于存储每一个点，有多少个点与它相连。即对于每一个点，它的名 称作为键，而有一个包含了与它相连的所有点的信息的 list 对象作为值。这样就完 全保存了该图的全部信息。然后有了该图，就可以利用 Dijkstra 算法来计算任意两 点之间的距离。而 Dijkstra 算法的基本思想就是，循环找出下一个离起点距离最短 的点，并标上标记，纳入以找出最短路径的点的集合。而当找到的下一个里起点最 近的点就是目的地，则循环结束，最短路径则通过 map 集合中每一个 City 对象的 from_city 属性来找到。(3)描述你采用 STL 中的什么容器或者类实

7、现图的存储，在算法应用过程中使用什么 数据结构或算法提高算法的效率。 我们使用 STL 中的 map 对象来存储图。即 map 中的每一个键都为一个城市名， 然后它的值为与该城市直接相连的所有城市所形成的 list 对象。 我们使用了邻接表的数据结构，并使用了优先级队列来实现下一个最短路径 的点的快速查找，极大地提高了算法的效率。并且使用了 Dijkstra 算法，利用优先 级队列逐渐寻找下一个里起点最短的点，并将它的 visited 属性标记为 true，表示 已经访问过，并在每一次访问后，都会更新剩余点的费用和距离的值。然后再利 用优先级队列计算新一轮的距离最短的点。数据结构实验报告 东北

8、大学软件学院- 3 -3. 实验环境操作系统、调试软件名称、版本号，上机地点，机器台号 操作系统：Windows 8.1 调试软件名称：Codeblocks 12.114. 实验过程与分析4.1 打印机模拟程序的过程分析(1) 描述你在进行实现时，主要的函数或操作内部的主要算法，分析这个算法的时、 空复杂度，并说明你设计的巧妙之处。simulate 函数为主要的执行 FIFO 打印的函数。该算法首先是一个 while 循环，该循 环中的部分，由三个判断与语句组成，如果 workload 队列和等待执行队列都为空，则可 以断定所有任务全部执行完；而如果等待执行队列为空，则表名现在还没有任务到达打

9、 印机，此时需要循环判断是否有任务到达，并且计数器也循环+1；而如果等待执行队列 不为空，就意为着，需要执行任务，那么则立即执行当前队列顶部任务，计算该任务的 等待时间，加到总等待时间上，并把当前计数器时间加上该任务执行的时间。然后在 workload 队列中把任务的执行时间的变量，然后把 outgoing_servicesfrom赋值给它，然后在调用该变量的 push_back 方法。而这样永远找 不出最短路径。解决之道：直接调用 outgoing_servicesfrom的 push_back 方法将 Service 对象 push 进去。(3) 你的实验在解决类似问题时是否具有灵活的可修

10、改性、可扩展性？ 具有可扩展性，因为可以在优先级队列的比较方法中设置不同的比较算法。这样权值 的比较具有任意性，只要更改此比较方法，就可以求出任意形式的最短的路径了。5.实验结果总结5.1 打印机模拟程序的结果总结回答以下问题： (1) 你的测试充分吗？为什么？你是怎样考虑的？ 充分。不管是任意顺序的任务，还是大的任务先执行，都可以得到正确的结果。(2) 为什么你要选用队列作为你应用的数据结构？ 因为该题是 FIFO，而队列也正是先入先出的数据结构。(3) 用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。 while (1)/*如果两个队列同时为空，则退出*/ if (workl

11、oad.empty() / 如果等待执行队列为空，则循环判断是否有任务到达数据结构实验报告 东北大学软件学院- 5 -else if (print.empty() while (!workload.empty() if (workload.front().arrival_time() = count_time)/*如果时间到了则 pop*/ break; else count_time+; else/ 执行任务 while (!workload.empty() if (workload.front().arrival_time() visited = false)f_city-visited

12、= true; list f_city_service = outgoing_servicesf_city-name; list:iterator iter = f_city_service.begin(); / 循环遍历与该点相连的所有的点，并重新计算它的距离和费用属性，并将 其 push 到优先级队列中。 for (; iter != f_city_service.end(); iter+) if (cities(*iter)-destination-visited = false) cities(*iter)-destination-total_fee = f_city-total_fe

13、e + (*iter)-fee; cities(*iter)-destination-total_distance = f_city- total_distance + (*iter)-distance; cities(*iter)-destination-from_city = f_city-name; candidates.push(cities(*iter)-destination); 数据结构实验报告 东北大学软件学院- 8 -/ 将已经遍历过的点弹出优先级队列。 candidates.pop(); (4) 在你的图中使用了怎么样数据结构来优化算法的性能？使用了链接表来存储图的结构，并

14、使用了优先级队列来将其它城市到起点城市 的距离进行排序，然后选取出距离最短的那个城市，作为下一个标记为已访问过 的那个城市。这样极大的简化了代码。 (5) 源程序的大致的执行过程是怎样的？load_services / 读取数据初始化所有城市的信息息Reset / 初始化所有城市的属性，将总 费用和总路程都置为 0把起点 push 进优先级队列While 循环 For 循环遍历与优先级队列顶部 的相连的点，并重新计算与起 点的距离和费用 把它 push 到优先级队列把该顶部的点弹出 根据终点城市回退，推算出整个 最短路径所包括的城市数据结构实验报告 东北大学软件学院- 9 -6.附录(1) 回

15、答思考题 a)栈和队列在计算机系统中有哪些应用？写出你知道的系统中，这两种抽象数 据类型的应用。 Android 系统中的 Activity 是用栈来管理的。 Linux 的 CPU 调度算法就是用队列来完成的。b)在程序调用的时侯，需要进行函数的切换，你认为函数在进行切换时系统要 做那些工作？ 把此时运行的位置进栈 跳转到函数的位置，执行函数 弹出与栈顶元素，回到原来的执行位置，继续执行c)队列在系统的设计中都起到什么样的作用？举出你所熟悉的一些队列的应用 例子。 能够保持程序的执行顺序。 在 Linux 的 CPU 调度的时候，就是采用多级队列反馈调度，每次都从队头抽 取出一个进程来执行。d)在你的两次实验中分别使用了 STL 中的哪些容器？有什么用途？ Queue：队列完成先进先出的功能，即打印的 FIFO 策略 Map：用来存储图 List：用