校园导航系统

（

2

）为来访客人提供 图中任意景点相关信息的查询。

（

3

）

为来访客人提供任意景点的问路查询

，

即查询任意两个景点之间的一条最短路径。

（

4

）修改景点信息。

实现提示：

一般情况下，校园的道路 是双向通行的，可设计校园平面图是一个无向网。顶点和边均

含有相关信息。

选做内容：

（

1

）提供图的编辑功能：增、删景点；增、删道路；修改已有信息等。

（

2

）校园 导游图的仿真界面。

2

，设计：

2.1

设计思想：

<1>

< br>，数据结构设计

：

（

1

）图。采用邻接矩阵存储，其中图所用到的 结构体为：

typedef struct

{

SeqList vertices;

//

表示图中的顶点

int Edge[MaxVertices][MaxVertices];

//

表示图中的边

int numOfEdge;

//

表示图中边的数目

}AdjMGraph;

（

2

）景点。用顺序表存储。所用到的结构体为：

typedef struct

{

char name[20];

//

顶点名称

int code;

//

顶点代号

char introduction[50];

//

顶点信息简介

}DataType;

1

（

3

）景点之间的连接描述，所用到的结构 体为：

typedef struct

{

int row;

int col;

int weight;

}RowColWeight; < /p>

用图来存放所提供的所有景点，

然后用线性表来存放每一个景点的 信息，

其

中包括景点的名称，

代号，信 息简介，以及其它的一些信息。

这样就将对景点的

操作，变成对 图中各顶点的操作

。

<2>

，算法设计：

关于本课题的算法，很大部分来源于这学期数据结构课程的学 习，其中包括：

图的创建，线性表 的一些操作。对于具体的问题实现，都有不同的算法，在下面的分析中，

我将详细说明< /p>

2.2

设计表示：

<1>,

函数调用关系及函数说明

：

首先，

main()

函数调用

< br>Creat()

函数，用来创建图，

然后调用

函数来选择用户所要

进行的操作。其 中

menu()

函数就是一个菜单供使用者来选择他所要进行的 相关操作，比如

信息的查询，最短路径查询之类。

main()

Creat()

menu()

对于要 求

1

：以图中顶点表示校园内各景点，存放景点名称、代号、简 介等信

息；以边表示路径，存放路径长度等有关信息。图的创 建设计流程图为：

main()

Creat()

Creat()

函数原型为：

void Creat(AdjMGraph *G

, DataType v[], RowColWeight E[], int n,int e)

G

为所创建的图结构体对象，

v[]

为所有顶点的集合，它是

DataType

型，

这个类型前面已经介绍过；

E[]

存放着各顶点之间的连接关系，

它是

R owColWeight

型，

前面也介绍过；

< br>n

表示顶点的个数；

e

表示边数 。

Creat()

函数的功能就是实 现图的创建，

将已知的景点的一些信息，

转换成图的

信息，并进行存储。

对于要求

2

：为来访客人提供图中任意 景点相关信息的查询。流程图为：

menu()

Information1()

Information()

menu()

函数的原型为：

2

void menu()

他就是一个菜单，供用户选择他们所要进行的操作。

Information1()

函数 原型为：

void

Information1()

它 的功能就是输入查询景点的信息，并调用

Information()

Information()

函数原 型为：

void Information(AdjMGraph G

, char scenery[])

G

依然是所创建的图的结构

体对象，后面所有的

G

都是表示这个意思；

scenery[]

是在

Information1()

中输入的景点的

名称。此函数的功能 就是根据输入的景点的名称来查询其相关的信息。

对于要求

3

：为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条

最短路径。流程图为：

Path1()

Path()

Floyd()

menu()

Path1()

函数原型为：

void

Path1()

它的功能就是输入查询景点的名称，并调用

Path()

Path ()

函数原型为：

v

oid

Path(AdjMGraph G

,char sceneryname[], char sceneryname1[])

其中

sceneryname[],

sceneryname1[]

就是在

Path1()

函数中所输入的景点的名称，

这

个函数的功能就是通过这两个景点的名称找到它们在线性表中的位置，然后 调用

Floyd()

函数，查找出它们的最短路径，并输出所要的信息。

Floyd()

函数原型为：

void

Floyd (int cost[][ MaxVertices],int n,int weight[][MaxVertices],int path[][MaxVertices])

其中参数

cost[][ MaxVertices]

即是图中边的邻接存储矩阵，

weight[][MaxVertice s]

用来存放经

此算法后的各顶点间 的最短路径的值，

path[][MaxVertices]

就 是每两个顶点之间最短路径中

到达目的顶点的前一个顶点的位 置。

Path()

函数中的输出信息就是据此而来。

对于要求

4

：修改景点信息。流程图为：< /p>

menu()

Modify()

Modify()

函数原型为：

void

Modify()

它不带任何参数，功能是通过手动输入景点名称，然后找到景点的

存储空间， 然后在修改相应的信息。

对于选做要求：增加景点。其工作流程图为：

menu()

AddVertic()

ListInsert()

AddVertic()

函数原型为：

void

AddVertic()

他不带任何参数，该函数的功能是在这个函数里面输入景点的 信

息，然后调用

ListInsert()

函数，将所要增加的顶点信息插入到线性表中。

ListInsert()

函数原型为：

void

ListInsert(SeqList *L, int i, DataType x)

参数

L

表示顶点存储的线性表，

i

表示

要插 入的位置

,x

表示要插入的景点的信息。

同时我在插入顶点时也将他与其他顶点之间的距

离设置为

Ma xWeight

，这样做主要是为了方便在

Floyd