《程序设计课程设计》指导书2013

3．停车场管理

专业： 班级： 姓名： 学号： 完成日期：

3.1【问题描述】

设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端）,若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

3.2【设计需求及分析】

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。

3.3【设计功能的实现】（用C或C++语言描述）

//说明：此内容由学生自己设计完成。

3.4【实例测试及运行结果】

设n=2，输入数据为：（‘A’,1,5）,（‘A’,2,10）,（‘D’,1,15）,（‘A’,3,20）,（‘A’,4,25）,（‘A’5,30）,（‘D’,2,35）,（‘D’,4,40）,（‘E’,0,0）。其中：‘A’表示到达（arrival）；‘D’表示离去（departure）；‘E’表示输入结束（end）。

3.5【实现提示】

需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。

//说明：要求由学生来补充。

- 14 -

4．交通咨询系统设计（最短路径问题）

专业： 班级： 姓名： 学号： 完成日期：

4.1【问题描述】

在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点A到顶点B的所含边数目最少的路径。我们只需要从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径。路径上A与B之间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路径选择问题。

设计一个交通咨询系统，为出差、旅游或做其他出行的客人提供各种路径选择信息查询服务。

4.2【设计需求及分析】

设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。

本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。

4.2.1建立图的存储结构

邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方阵： 设G=（V，E）是一个图，结点集为

V??v1,v2,?,vn?。

??(wij)n?n，当（vi,vj）或?vi,vj??E, G的邻接矩阵A?(aij)n?n,aij????0或?，当（vi,vj）或?vi,vj??E

当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。

图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下： #definf MVNum 50 //最大顶点数 typedef struct { VertexType vexs[MVNum]; //顶点数组，类型假定为char型 Adjmatrix arcs[MVNum][MVNum]; //邻接矩阵，假定为int型 }MGraph; - 15 -

4.2.2单源最短路径

最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望找出从某个源点S?V到G中其余各顶点的最短路径。

为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。

那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。

迪杰斯特拉算法求最短路径的实现思想是：设G=（V，E）是一个有向图，结点集为，

V?{v1,v2,?,vn}，cost是表示G的邻接矩阵，cost[i][j]表示有向边的权。若不存在有

向边，则cost[i][j]的权为无穷大（这里取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含一个元素，即顶点v1。数组dist记录从源点到其他顶点当前的最短距离，其初值为dist[i]=cost[v1][i],i=1,2,??,n。从S之外的顶点集合V-S中选出一个顶点w，使dist[w]的值最小。于是从源点到达w只通过S中顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v]和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到V-S为空。

最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i]表示从源点到顶点i之间的最短路径的前驱顶点。

因此，迪杰斯特拉算法可用自然语言描述如下： 初始化S和D，置空最短路径终点集，置初始的最短路径值； S[v1]=TRUE; D[v1]=0； //S集初始时只有源点，源点到源点的距离为0； While (S集中顶点数

任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V，E），要对G中任意一对顶点有序对“v,w(v?w)”,找出v到w的最短路径。

要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。

这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。

费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点 vi到vj的最短路径。如果从vi到vj存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径和是否存在。如果存在，则比较和< vi,v1,vj >的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么可分解为和,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求出的从vi到vj的中间顶点序号不大于1的最短路

- 16 -

径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推，直到顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。

4.3【设计功能的实现】（用C或C++语言描述） 4.3.1 建立有向图的存储结构

//说明：要求由学生来完成代码的编写。

4.3.2 迪杰斯特拉算法

//说明：要求由学生来完成代码的编写。

4.3.3 费洛伊德算法

//说明：要求由学生来完成代码的编写。

4.3.4 运行主控程序

//说明：要求由学生来完成代码的编写。

4.4【实例测试及运行结果】 4.4.1 运行实例一

（求给定有向图4-1的最短路径）

a209g151810b图4-1 一个有向图

具体要求之一：求顶点a到其余顶点的最短路径；分别求顶点b到顶点d之间的最短路径、顶点a到顶点d之间的最短路径。

提示：为了操作方便，对于图的顶点都是用序号来表示的，所以顶点的字母就用其对应的序号来操作：如a用1来代替，??。

4.4.2 运行实例二

（求给定有向图4-2的最短路径）

- 17 -

12de8 3010cf5