正式英文-bj是什么意思
《数据结构》实验报告
东北大学软件学院
课程编号：
B080101050
1.
实验目的
实验一：
1.
理解队列的概念以及用法
2.
掌握
q
ueue
类的使用
3.
熟练运用队列先进先出，模拟打印机的工作过程
实验二：
1.
理解图的概念
2.
理解并掌握图的存储，并利用邻接表来存储图的信息
3.
理解并掌握
Dijkstra
算法
4.
运用
D
ijkstra
算法解决最短路径的问题
针对每次实验，写出你认为比较重要的实验目的
2.
实验内容与实验步骤
2.1
打印机模拟程序的内容与步骤
(1)
简短明确地写出实验的内容
模拟打印
机打印的过程，以先来先服务的策略来完成打印工作。先从一个文件
中读取所有任务的大
小与到达时间，
并将其存储在
workload
队列中。
使用一个计数
器来模拟时间的流逝，
当当前时间与
workload
队列中的一个任
务的到达时间相等的
时候，该任务被弹出，并被压入到另一个等待执行的队列中。该等待
执行的队列以
先入先出的准则依次弹出任务并执行。最后计算出任务总数与，总等待时间
，平均
等待时间。
(2)
简短描述抽象数据类型或设计
的函数描述，说明为什么要使用这种抽象数据类
型，并说明你的解决设想
①一个
simulator
的抽闲类和它的实现类
fifo
类。
该类的
simulate
函数用来实现
先进先出策略的打印算法。
②两个队列，一个
workload
队列，一个是等待执行队列。
Workload
队列中存
放的是所有的打印任务，
通过文件读取并保存。
而等待执行队列则是为了实现
FIFO
功能的队列，即时间
小的就先被压入等待执行队列，自然也就先被
pop
并执行。<
/p>
解决设想：
利用一个
int
型变量模拟时间的流逝，然后当等待执行队列为
空的时候，就不
断循环检查
workload
< br>队列中是否有任务到达，
若有则将其弹出并
push
进等待执行
队列。而当等待执行队列中有任务时则执行它，并且同时
判断
workload
队列中是
否有任
务到达。若
workload
和等待执行队列同时为空了，则程
序结束。
- 1 -
《数据结构》实验报告
东北大学软件学院
(3)
简短明确地写出你实验所采用
的存储结构及其用途，详细说明其中的属性的含
义。
①
jo
b
类封装了一个任务的所有属性。包括任务的大小和该任务的用户：任务
的大小即为该打印任务一共需要打印的页数，而该任务来自哪个计算机。
②
event
类封装了一个打印事件的所有
属性。任务本身并不包含打印的信息，
而一个打印事件则需要
包含一个待执行的任务和该任务到达的时间。打印的时候
就是
根据这些信息来执行它。
而待执行的任务属性即是一个任务对象，
而该任务到
达的时间即是该任务在某个时间到达打印机，并等待被执行。
③
simulator
类
封装了所有打印机的操作，包括加载任务文件，执行打印任务
等。该类将从文件中加载的任务封装成对象，并存储于
workload
队列中。然后待
时间到时，将该任务
pop
并
push
到等待执行
队列中。在该队列中自然就按
FIFO
的策略来执行。
2.2
欧洲旅行实验的内容与步骤
(1)
简短明确地写出实验的内容
该实验
就是在互相连接的城市中寻找给定两个城市之间的费用最小的路径。用
邻接表来存储整个图的信息，并用一个
map
对象来存
储各个城市的信息，包括它上
一个城市，从起点到该城市的费用和距离。最后利用
Dijkstra
算法来对任意给定的
两个城
市，计算他们之间的费用最小的路径。
(2)
简短描述你在实验中使用的数据结构及算法的基本原理。
在本实验中，使用了邻接表，
map
集合，
list
集合。邻接表是用于存储整个图的
信息的，即它用于存储每一个点，有多少个点与它
相连。
即对于每一个点，
它的名称
作为
键，而有一个包含了与它相连的所有点的信息的
list
对象作
为值。这样就完全保
存了该图的全部信息。然后有了该图，就可以利用
< br>Dijkstra
算法来计算任意两点之间
的距离。而<
/p>
Dijkstra
算法的基本思想就是，循环找出下一个离起点距
离最短的点，并
标上标记，
纳入以找出最短路径的点的集合。<
/p>
而当找到的下一个里起点最近的点就是
目的地，
< br>则循环结束，
最短路径则通过
map
集合中每一个
City
对象的
fr
om_city
属性
来找到。
(3)
描述你采用
< br>STL
中的什么容器或者类实现图的存储，在算法应用过程中使用什么
数据结构或算法提高算法的效率。
我们使用
STL
中的
ma
p
对象来存储图。
即
map
中的每一个键都为一个城市名，
然后它的值为与该城市直接相连的所有城市
所形成的
list
对象。
我们使用了邻接表的数据结构，
并使用了优先级队列来实现下一个最短路径
的
点的快速查找，极大地提高了算法的效率。并且使用了
Dij
kstra
算法，利用优先级
队列逐渐寻找下一个里起点最短的
点，并将它的
visited
属性标记为
true
，表示已经
访问过，并在每一次访问后，都会更新剩
余点的费用和距离的值。然后再利用优先
级队列计算新一轮的距离最短的点。
- 2 -
《数据结构》实验报告
东北大学软件学院
3.
实验环境
操作系统、调试软件名称、版本号，上机地点，机器台号
操作系统：
Windows 8.1
调试软件名称：
Codeblocks 12.11
4.
实验过程与分析
4.1
打印机模拟程序的过程分析
(1)
描述你在进行实现时，主要的
函数或操作内部的主要算法，分析这个算法的时、空
复杂度，并说明你设计的巧妙之处。
simulate
函数为主要的执行
FIF
O
打印的函数。该算法首先是一个
while
< br>循环，该循
环中的部分，由三个判断与语句组成，如果
w
orkload
队列和等待执行队列都为空，则可
以断定所有任务全部执行完；而如
果等待执行队列为空，则表名现在还没有任务到达打
印机，此
时需要循环判断是否有任务到达，并且计数器也循环
+1
；而如
果等待执行队列
不为空，就意为着，需要执行任务，那么则立即执行当前队列顶部任务，计算该任务的
< br>
等待时间，加到总等待时间上，并把当前计数器时间加上该任务执行的时间。然
后在
workload
队列中把任务
的执行时间
<=
当前时间的任务给弹出并压入到等待执行队列中
。
等着三个判断语句结束后进入
wh
ile
的下一次循环。
该算法具有很小的时间复杂度，
O(n) = 2n +
打印机空闲的秒数。因为对于执行打印
任务的时候，该算法是直接在
计数器上加上该任务消耗的时间，而对于
pop
出
workload
的
时间则是等于任务的个数，
然后剩余消耗的时间就是在等待执行队列为空的时候，
循环判断
workload
队列中是否有任务到达了，所以此时消耗的循环次
数为打印机空闲的秒数。
而空间复杂度为：
n+2
。也就是任务的个数
+
队列个数。
此算法的巧妙之处就在于，并没有以计数器逐渐递增的方式来模拟时间的流逝，而
是消耗多少时间，计数器直接加上该值，并不是等待计数器累加到该值才执行任务。
(2)
你在调试过程中发现了怎样的问题？又做了怎样的改进（要求写出具体的事例）
在算平均等待时间的时候，把该总时间的类型设置成了整型，
导致平均等待时间
算错。
(3)
你的实现是否具有可扩展性，如针对多个打印队列的仿真程序？
本实现具有可扩展性，即只要在原来判断单个打印队列是否为
空的基础上，加上
&&
语句，即同时判断是否所有打印队列同时
为空，如果都为空，则循环判断所有
workload
队列中任
务是否已到达时间，若到达了时间则弹出并
push
到相应的打
印队列
中，这就是由原来的单个
workload
判断变成了循环判断多个
workload
。而如果
有任一
一个打印队列不为空，
那么则和原来一样进入第三个判断
中，
执行该打印任务，
且循环
所有打印
队列并执行任务。
4.2
欧洲旅行实验的过程分析
(1)
描述你在进行实现时，主要的函数或操作内部的主要算
法，分析这个算法的时、空
复杂度，并说明你设计的巧妙之处。
主要函数为
calc_route
函数
。该函数运用的算法为
Dijkstra
算法，算出最小路径。
该算法从起点开始遍历，
然后重新计
算与该点相连的所有点到起始点的距离，
然后把这些点
- 3
-
《数据结构》实验报告
东北大学软件学院
都
push
到优先级队列中，利用优先级队列的排序功能，我们只需要取出优先级
队列中顶部
的点，
并将其标记为已访问过，
然后在访问与该点相连的所有点，
再次重复上述过程。
即不
断寻找下一个离起点最近的点，并将其标记为
true
。
该算法的时间复杂度为
O(n) = 2n
（
n
为边数）
。
< br>即每次都要循环遍历与该点相连的所有
点，
所以对于两个
点之间的那条边需要被遍历两次，
虽然只有其中一次才会执行其中的语句。
而空间复杂度为：
2
倍点的个数
+2
倍边数。
此算法的巧妙之处
在于利用了优先级队列，这可以很方便地选取出下一个离起点最短
的点。
(2)
你在调试过程中发现了怎样的问题？又做了怎样的改进？
问题<
/p>
1
：访问过的点没有标记为
true
，使得进入死循环。
解决之道：将其标记为
true
。
问题
2
：
在
reset()
方法中初始化的时候，
将点的
total_fee
属性初始化为了
I
NT_MAX
，
使得永远无法计算出最短路径。
解决之道：将其属性初始化为
0
。
问题<
/p>
3
：创建邻接表的时候，先创建一个
li
st
的变量，然后把
outgoing_services[from]
赋值给它，然后在调用该变
量的
push_back
方法。而这样永远找不
出最短路径。
解决之道：直接调用
outgoing_services[fro
m]
的
push_back
方法将
Service
对象
push
进去。
(3)
你的实验在解决类似问题时是否具有灵活的可修改性、可扩展性？
<
/p>
具有可扩展性，因为可以在优先级队列的比较方法中设置不同的比较算法。这样权值
的比较具有任意性，只要更改此比较方法，就可以求出任意形式的最短的路径了。
5.
实验结果总结
5.1
打印机模拟程序的结果总结
回答以下问题：
(1)
你的测试充分吗？为什么？你是怎样考虑的？
充分。不管是任意顺序的任务，还是大的任务先执行，都可以得到正确的结果。
(2)
为什么你要选用队列作为你应用的数据结构？
因为该题是
FIFO
，而队列也正是先入先出的数据结
构。
(3)
用一段简短的代码及说明论述
你的应用中主要的函数的主要处理部分。
while
(1){
/**
*
如果两个队列同时为空，则退出
*/
if (() && ()){
break;
}
//
如果等待执行队列为空，则循环判断是否有任务到达
- 4 -
《数据结构》实验报告
东北大学软件学院
else if
(()){
while (!()){
if
(().arrival_time() == count_time){
/**
*
如果时间到了则
pop
*/
break;
}else{
count_time++;
}
}
}else{
//
执行任务
while (!()){
if
(().arrival_time() <= count_time){
//
把
workload
中的任务添加到等待执行队列
}else{
break;
}
}
}
}
(4)
用结构化图表或者结构化代码描述源程序的大致的执行过程。
- 5 -
正式英文-bj是什么意思
正式英文-bj是什么意思
正式英文-bj是什么意思
正式英文-bj是什么意思
正式英文-bj是什么意思
正式英文-bj是什么意思
正式英文-bj是什么意思
正式英文-bj是什么意思
-
上一篇：浦东新区2016高三英语一模
下一篇：八年级下册文言文对比阅读训练答案