最短路径导航查询系统(图)

数据结构课程设计

一、课程设计目的

数据结构课程设计要求能综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。

通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

二、设计要求

从课程设计的目的出发，通过设计课题的各个环节，达到以下教学要求：

1.从所给题目中任选一个，每个学生必须独立完成课程设计，不能相互抄袭；

2.设计完成后，将所完成的工作交由老师检查；

3.要求写出一份详细的设计报告。

三、设计题目(以下题目任选一个)

1.学生成绩管理系统(线性表)

能完成每位学生某门课程的成绩录入、删除、修改、查找、统计（即成绩为“优”的学生信息、成绩为“良”的学生信息、成绩为“中”的学生信息、成绩为“及格”的学生信息、成绩为“不及格”的学生信息）。

2.停车场管理系统(栈和队列)

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

3.迷宫问题(栈和队列)

求迷宫问题就是求出从入口到出口的所有路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。

4.家谱管理系统(树)

本课题的实质是完成对家谱成员信息的建立、查找、插入、修改、删除等功能。可以首先定义家族成员的数据结构，然后将每个功能作为一个成员函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行的结果。

5.公交路线管理模拟系统(图)

本课题是对公交路线信息的简单模拟，以完成建立公交路线信息、修改公交路线信息和删除公交路线信息等功能。课题的实质是完成对公交路线信息的建立、查找、插入、修改、删除等功能。可以首先定义公交路线的数据结构，然后将每个功能作为一个成员函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行的结果。

6.最短路径导航查询系统(图)

设计一个交通导航质询系统，能让旅客质询从任一个城市顶点到另一个城市顶点之间的最短路径问题。设计分为三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。

7.链表综合算法设计

设有一个职工文件，其结构为：职工号（no）、姓名（name）部门号（depno）、工资数（salary）、职工号指针（pno）和工资数指针（psalary）。设计一个程序，从该文件中读取记录到一个单链表中。

8.复杂表达式的值

设计一个程序计算含有如下标识符的表达式的值。（1）数值包括整数和实数，数值可带正负号。（2）一般运算符：正号负号、加减乘除和求模乘方，其中可以包含括号。（3）单词（即运算函数）

四、课程设计需提交内容

1．提交“课程设计报告”打印版，其内容详见 “课程设计报告书”。

2. 提交已调试通过的完整的相关源程序和“课程设计报告”电子版，将两者压缩为一个文件包，文件名为:“11位学号+姓名”(如2009**********小强)。

3．提交时间：6月24日(18周五)12:00前。

2

设计题目：最短路径导航查询系统(图)

一． 实习目的

通过学习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、编码集成以及调试分析，熟练掌握数据结构的选择、设计、实现、以及操作方法，为进一步的开发应用打好基础。

二． 问题描述

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

三． 需求分析

该程序所做的工作是给司机们提供最佳路线，来提高能源和时间的合理利用。

此程序规定：

1.把城市交通线路转化为图，从而对图进行相应的结构存储；

2.程序的输出信息主要为：起始城市到目的城市的最短路径；

3.程序的功能主要包括：城市之间路径的存储，最短路径的计算，以及最短路径和邻接矩阵的输出；

四．概要设计

对于这样的问题，先假设有四个城市甲乙丙丁，甲乙相距2千米，且只有从乙到甲的单程线路。甲丙相距7千米，且只有从甲到丙的单程线路。甲丁相距4千米，且只有从甲到丁的单程线路。乙丙相距5千米，且只有从丙到乙的单程线路。乙丁相距3千米，且只有从丁到乙的单程线路。丙丁相距3千米，且只有从丁到丙的单程线路。戊甲相距6千米，且只有从戊到甲的单程线路。戊丁相距2千米，且只有从丁到戊的单程线路。乙己相距8千米，且只有从乙到己的单程线路。丙己相距6千米，且只有从己到丙的单程线路。

编程出能求出个一点到任一点的最短路经。

图G为：

甲

6

戊

4

2

2

乙

8

己

3

3

7

5

6

丙

丁

3

则图G的邻接矩阵为：

甲 乙 丙 丁 戊 己

甲 ∞ ∞ 7 4 ∞ ∞

乙 2 ∞ ∞ ∞ ∞ 8

丙 ∞ 5 ∞ ∞ ∞ ∞

丁 ∞ 3 3 ∞ 2 ∞

戊 6 ∞ ∞ ∞ ∞ ∞

己 ∞ ∞ 6 ∞ ∞ ∞

∞表示无穷大

系统用到的数据有：

int which;

int v ;

int endv;

用到的主要函数：

1）void DispMat(MGraph g) //输出邻接矩阵g

2）void ppath(int path[][MAXV],int v,int endv) //输出相应选择的起点和终点的最短路

3）void DisPath(int A[][MAXV],int path[][MAXV],int n,int v,int endv)//由path计算最短

路径

4）void Floyd(MGraph g,int v,int endv) //采用弗洛伊德算法求没对顶点之间的最

路径

5）int main（） //主函数

各程序模块之间的调用关系：

函数3）可以调用函数2）。

函数4）可以调用函数3）。

函数5）可以调用函数1）和函数4）。

五．详细设计

①typedef struct

{int no; //顶点编号

InfoType info; //顶点其他信息，这里用于存放边的权值

}VertexType; //顶点类型

typedef struct //图的定义

{int edges[MAXV][MAXV]; //邻接矩阵

int n,e; //顶点数，弧数

VertexType vexs[MAXV]; //存放顶点信息

}MGraph; //图的邻接矩阵类型

//以下定义邻接表类型

4

typedef struct ANode //弧的结点结构类型

{int adjvex; //该弧的终点位置

struct ANode *nextarc; //指向下一个弧的指针

InfoType info; //该弧的相关信息，这里用于存放权值

}ArcNode;

typedef int Vertex;

typedef struct Vnode //邻接表头结点的类型

{Vertex data; //顶点信息

ArcNode *firstarc[MAXV]; //指向第一条弧

}VNode;

typedef VNode AdjList[MAXV];//AdjList是邻接表类型

typedef struct

{AdjList adjlist; //邻接表

int n,e; //图中顶点数n和边数e

}ALGraph; //图的邻接表类型

②void DispMat(MGraph g) //输出邻接矩阵g

{int i,j;

for(i=0;i

{for(j=0;j

if([i][j]==INF)

cout<<"∞"<<" ";

else

cout<<[i][j]<<" ";

cout<<"n";

}

}

③void ppath(int path[][MAXV],int v,int endv) //输出相应选择的起点和终点的最短路线

{int k;

k=path[v][endv];

if(k==-1)return;

ppath(path,v,k);

cout<

ppath(path,k,endv);

}

④void DisPath(int A[][MAXV],int path[][MAXV],int n,int v,int endv)//由path计算最短路径

{

cout<<"从"<

cout<

5

ppath(path,v,endv);

cout<

cout<

cout<<"路线长度为："<

⑤void Floyd(MGraph g,int v,int endv) //采用弗洛伊德算法求没对顶点之间的最短路径

{int A[MAXV][MAXV],path[MAXV][MAXV];

int i,j,k,n=g.n;

for(i=0;i

for(j=0;j

{A[i][j]=[i][j];

path[i][j]=-1;

}

for(k=0;k

{

for(i=0;i

{

for(j=0;j

{

if(A[i][j]>(A[i][k]+A[k][j]))

{A[i][j]=(A[i][k]+A[k][j]);

path[i][j]=k;

}

}

}

}

cout<<"n"<<"输出最短路线："<<"n";

DisPath(A,path,n,v,endv); //输出最短路线

}

六．测试分析

6

七．使用说明

首先运行程序，包括三个选项，a.需要求最短路径请按：1.

b.输出有向图G的邻接矩阵：2.

c.退出系统请按：3 .

然后可以根据不同的需要选择不同的选项进行操作

最后按3退出程序。

八．附录：测试数据

起点为：地点丁（3）

终点为：地点己（5）

7

九．C++实现

#include

#include

using namespace std;

#define MAXV 6 //最大顶点个数

#define INF 32767 //用32767表示∞

typedef int InfoType; //最大顶点个数

typedef struct

{int no; //顶点编号

InfoType info; //顶点其他信息，这里用于存放边的权值

}VertexType; //顶点类型

typedef struct //图的定义

{int edges[MAXV][MAXV]; //邻接矩阵

int n,e; //顶点数，弧数

VertexType vexs[MAXV]; //存放顶点信息

}MGraph; //图的邻接矩阵类型

//以下定义邻接表类型

typedef struct ANode //弧的结点结构类型

{int adjvex; //该弧的终点位置

struct ANode *nextarc; //指向下一个弧的指针

InfoType info; //该弧的相关信息，这里用于存放权值

}ArcNode;

typedef int Vertex;

typedef struct Vnode //邻接表头结点的类型

{Vertex data; //顶点信息

ArcNode *firstarc[MAXV]; //指向第一条弧

}VNode;

typedef VNode AdjList[MAXV];//AdjList是邻接表类型

typedef struct

{AdjList adjlist; //邻接表

int n,e; //图中顶点数n和边数e

}ALGraph; //图的邻接表类型

void DispMat(MGraph g) //输出邻接矩阵g

8

{int i,j;

for(i=0;i

{for(j=0;j

if([i][j]==INF)

cout<<"∞"<<" ";

else

cout<<[i][j]<<" ";

cout<<"n";

}

}

void ppath(int path[][MAXV],int v,int endv) //输出相应选择的起点和终点的最短路径

{int k;

k=path[v][endv];

if(k==-1)return;

ppath(path,v,k);

cout<

ppath(path,k,endv);

}

void DisPath(int A[][MAXV],int path[][MAXV],int n,int v,int endv)//由path计算最短路径{

cout<<"从"<

cout<

ppath(path,v,endv);

cout<

cout<

cout<<"路线长度为："<

}

void Floyd(MGraph g,int v,int endv) //采用弗洛伊德算法求没对顶点之间的最短路径{int A[MAXV][MAXV],path[MAXV][MAXV];

int i,j,k,n=g.n;

for(i=0;i

for(j=0;j

{A[i][j]=[i][j];

path[i][j]=-1;

}

for(k=0;k

{

for(i=0;i

{

for(j=0;j

9

{

if(A[i][j]>(A[i][k]+A[k][j]))

{A[i][j]=(A[i][k]+A[k][j]);

path[i][j]=k;

}

}

}

}

cout<<"n"<<"输出最短路线："<<"n";

DisPath(A,path,n,v,endv); //输出最短路线

}

int main()

{int i,j,u=0;

MGraph g;

int A[MAXV][6]={{INF,INF,7 ,4 ,INF,INF},

{2 ,INF,INF,INF,INF,8 },

{INF,5 ,INF,INF,INF,INF},

{INF,3 ,3 ,INF,2 ,INF},

{6 ,INF,INF,INF,INF,INF},

{INF,INF,6 ,INF,INF,INF}};

g.n=6;

g.e=10;

for(i=0;i

for(j=0;j

[i][j]=A[i][j];

cout<<"t 欢迎使用 n"

<<"t 交通导航系统 n";

cout<<"地点名称:"<

cout<<"0.地点甲"<<" "<<"1.地点乙"<<" "<<"2.地点丙"<

cout<<"3.地点丁"<<" "<<"4.地点戊"<<" "<<"5.地点己"<

int which;

while(1)

{

cout<<" 请选择所需要的服务:"<

cout<<"a."<<"需要求最短路线请按:"<<"1" <<"n";

cout<<"b."<<"输出有向图G的邻接矩阵："<<"2"<<"n";

cout<<"c."<<"退出系统请按:"<<"3"<

cout<<"请输入整数1到3:";

cin>>which;

if(which>3){cout<<"请重新输入"<

switch(which)

{

10

case 1:

{int v,endv;

cout<<"输入起点代号:";

cin>>v;

if(v>=6)

{cout<<"输入错误"<

break;

}

cout<<"输入终点代号:";

cin>>endv;

if(endv>=6)

{cout<<"输入错误"<

break;

}

while(1)

{

Floyd(g,v,endv);

break;

}

break;

}

case 2:cout<<"有向图G的邻接矩阵:"<<"n";

DispMat(g);

break;

case 3: return 0;

}

}

return 0;

}

11