(交通运输)交通图咨询查询系统数据结构(C语言).

(交通运输)交通图咨询查询系统数据结构

(C语言).

-CAL-FENGHAI.-(YICAI)-Company One1

（交通运输）交通图咨询查询系统数据结构(C语言)

I

信息科学与工程学院

《结构数据》

课 程 设 计 报 告

课程设计名称： 交通咨询系统 专 业 班 级 ： 计算机xxx 学 生 姓 名 ： xxx 学 号 ： 2015xxxx 指 导 教 师 ： xx

课程设计时间： 2016.07.04—2016.07.08

II

计算机应用技术 专业课程设计任务书

学生姓名 题 目 课题性质 指导教师 A 白浩 Xxx 专业班级 学号 交通咨询系统 课题来源 同组姓名 D 无 1. 建立交通网络图的存储结构。 2. 某个城市到达其余各城市的最短路径。 主要内容 3. 实现两个城市之间最短路径的问题。 4. 主要目的是给用户提供路径咨询 5. 根据需求分析给出概要设计，本系统包括以下功能模块：添加信息、查询信息、删除信息、修改信息、退出和保存信息； 任务要求 6. 结合课题利用数据结构相关知识，利用C语言实现该系统的所有上述功能，要求界面友善，程序运行正常； 7. 提交课程设计报告1份（具体写作要求参考样例），可运行的系统和源代码电子版一套。 参考文献 严蔚敏.《数据结构（C语言版）》.北京：清华大学出版社 谭浩强.《C语言程序设计》.（第三版）北京：清华大学出版社 指导教师签字：xx 审查意见 教研室主任签字：xx 2016 年 06 月 27 日 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页

I

填 表 说 明

1．“课题性质”一栏：

A．工程设计； B．工程技术研究；

C．软件工程（如CAI课题等）； D．文献型综述； E．其它。 2．“课题来源”一栏：

A．自然科学基金与部、省、市级以上科研课题； B．企、事业单位委托课题； C．校、院（系、部）级基金课题； D．自拟课题。

II

目录

1 需求分析 .........................................................................................................................1

1.1 添加交通图信息 .................................................................................................1 1.2 查询单源最短路径 ............................................................................................1 1.3 查询多源最短路径 ............................................................................................1 1.4 更新交通图信息 .................................................................................................2 1.6 读取、保存信息 .................................................................................................2 2 概要设计 .........................................................................................................................3

2.1 数据类型的定义 .................................................................................................3 2.2 功能模块结构图 .................................................................................................4 3 运行环境 .........................................................................................................................6 4 开发工具和编程语言 ....................................................................................................6 5 详细设计 .........................................................................................................................7

5.1 图结构的基本操作 ............................................................................................7 5.1.1添加城市结点和路径结点 .............................................................................8 5.1.2修改城市结点和路径结点 .............................................................................8 5.1.3删除城市结点和路径结点 .............................................................................8 5.1.4退出保存 ..........................................................................................................8 5.2 迪杰斯特拉算法的实现 ....................................................................................8 5.2.1 迪杰斯特拉算法函数 .....................................................................................8

III

5.2.2 提取迪杰斯特拉函数信息.............................................................................8 5.2.3 求多源最短路径 .............................................................................................8 6 程序编码 .........................................................................................................................9 7 运行结果 ...................................................................................................................... 41 8 心得体会 ...................................................................................................................... 46 9参考文献 ...................................................................................................................... 47

IV

1 需求分析

本系统中的数据来源于标准输入设备（如键盘）和文件，可以实现对交通图城市、城市到其余城市的距离的操作，根据需要可查询某两个城市之间的最短距离、城市到各城市的最短距离，各个城市到各个城市的最短距离，以及路径。本系统要实现的功能有：添加城市和城市间距离，删除城市及城市间距离，修改城市间距离，查询城市间的最短路径，查询某个城市到某个城市的最短路径。具体如下：

1.1 添加交通图信息

能录入新数据（城市和路径）。当录入了重复的城市和路径时，则提示数据录入重复并取消录入；当交通图中超过15个城市时，存储空间已满，不能再录入新数据；录入的新数据能按递增的顺序自动进行条目编号。

1.2 查询单源最短路径

能够实现输入起点城市名后，查询出其到各个城市的最短路径，输出该城市到的其他所有的城市的最短路径。

1.3 查询多源最短路径

输入起点城市名和终点城市名，查询出两个城市的最短路径，并输出该最短路径。

1

1.4 更新交通图信息

根据给定的城市名能够修改该城市的名字。或者输入两个城市，修改一条路径的距离。

1.5 删除交通图信息

根据输入的城市名 ，删除与该城市有关的所有路径。输入两个城市可以删除一条路径。

1.6 读取、保存信息

能够实现退出系统时把交通图中的信息保存在一个文件中，在程序瑕疵运行时能够读取出来。

2

2 概要设计

2.1 数据类型的定义

1.

定义交通图城市的元素类型

typedef struct _city{

char name[10];城市名

struct _path * firstpath；//第一个路径

}AdjList[15],CityNode; 2.

定义交通图的路径元素类型

typedef struct _path{

int adjcity//邻接点域 int distance；//距离

struct _path *nextpath；//下一个路径 }PathNode,*PathPtr; 3.

定义交通图类型

typedef struct {

int cities;

3

int paths;

AdjList list； }Graph ; 4.

全局变量

PList head;

typedef int PathMatrix; typedef int ShortPathTable;

PathMatrix P[MAX_CITIES][MAX_CITIES]; ShortPathTable D[MAX_CITIES];

2.2 功能模块结构图

根据需求分析，为了满足用户的功能需求，按照软件开发方法学中的模块划分原则，我将本系统主要划分为如下模块：操作交通图信息，和查询交通图路径两大模块。各模块之间的关系如图1所示。

图 1模块结构图

为了实现上述功能模块，分别在顺序表和单链表物理结构上定义了多个函数，本系统定义的函数和功能如下：

1. 数据结构部分部分

void initalize_graph(Graph *G) 功能为：图初始化，即生成一个空图。

4

int CreatAdjList(Graph *G)//初始化交通图 功能为：图的创建，用图存储数据。 void ADD_CITY(Graph *G)

功能为：往图G中插入一个城市结点。

void ADD_PATH(Graph *G,int ori,int add,PathNode *p) 功能为：往图G中插入一个路径结点。 void DELETE_CITY(Graph *G,int city)

功能为：删除图G中的指定的城市及其相关的路径。 void DELETE_PATH(Graph *G,int left,int right) 功能为：删除图G中一条指定的路径。

void UPDATE_PATH(Graph *G,int left,int right) 功能为：更新图G中的一个路径信息 。

Status SqListSearchByName(SqList *L,char *name) ;

功能为：通过姓名查找顺序表中,返回值为其在通讯录中的位置 。 void UPDATE_CITY(Graph *G,int city,char *name) 功能为：更新图G中的一个城市信息 。

Status SqListSearchByName(SqList *L,char *phone) ;

功能为：通过电话号码查找顺序表中,返回值为其在通讯录中的位置。 2.程序功能部分

void MODE_CLIENT(Graph *G) 功能为：客户端界面函数。 void MODE_ADMIN(Graph *G)

5

功能为：管理员端界面函数。 int ReadAdjList(Graph *G) 功能为：从文件中读取交通图。 int WriteAdjList(Graph *G) 功能为：在文件中存储交通图。

void menu(int i)

功能为：各种的端界面打印。 3.算法实现部分

void ShortestPath(Graph *G,int v0)

功能为：迪杰斯特拉算法，求出对V0单源最短路径。 void Print(Graph *G,int v0)

功能为：根据迪杰斯特拉算法，打印出V0单源最短路径。 void Print2(Graph *G,int v1,int v2)

功能为：根据迪杰斯特拉算法，打印出V1和V2的最短路径。 void FindPath(Graph *G,int v) 功能为：打印出V1到V2的经过路径。 int dis(Graph *G,int left,int right) 功能为：返回指定路径的距离。

3

运行环境

1. 硬件环境:PC机内存 4G；硬盘500G

6

2. 软件环境：操作系统：windows10

4 开发工具和编程语言

开发环境：CodeBlocks 、Dev C++ 编程语言：C语言

7

5

详细设计

在概要设计的基础上，对每个模块进行内部逻辑处理部分详细设计。下面

分别列出各个模块具体实现流程图：

5.1 图结构的基本操作

观察了数据对象后，我选择用一个邻接表用来存储图2信息，则数据结构的基本操作也就确定了，分别为图的添加、删除、更新。

图 2 模拟交通图

5.1.1添加城市结点和路径结点

和图的基本操作相同，只是该城市每增加一个城市结点要在弧的邻接点对应的城市上也增加一条弧。

8

5.1.2修改城市结点和路径结点

和图的基本操作相同。

5.1.3删除城市结点和路径结点

和图的基本操作相同，只是该城市每删除一个城市结点要在弧的邻接点对应的城市上也删除那条弧。

5.1.4退出保存

在主函数的开始部分添加Read函数，在管理员修改模式添加Write函数。实现对图结构的读取保存。

5.2 迪杰斯特拉算法的实现

把算法实现得到不仅仅是一系列数组，而是将这些数组的信息提炼成有用的

信息输出出来，将抽象的数据转换为具象的信息。

5.2.1 迪杰斯特拉算法函数

定义了若干个全局辅助变量，如路径矩阵P[][]和距离数组D[]，final用来标

记是否找到了点的最短路径在函数的初始阶段进行对个辅助变量的初始化，第一趟把V0相邻的路径距离保存下来。选择一个最小的用final记录下来，记录下最终的D和P值。再遍历其他结点，如果出现新的路径，且路径小于最大值INFINITY，则保存路径和距离以便下次比较。循环n-1次得到V0到各结点的最短距离和路径。

5.2.2 提取迪杰斯特拉函数信息

9

根据P函数与D函数，可以将V0到每个终点的经过结点和最终路径求出，

利用Print函数打印出V0和V，再调用FindPath函数，打印经过的结点。最后打印出距离，便可在屏幕上打印出单源最短路径。

5.2.3 求多源最短路径

对每个结点循环调用便可打印出每个结点到其他结点的最短路径，通过改变

Print函数的形参，便可以求出两点间的最短路径。

10

6 程序编码

根据详细设计转化为如下代码，下面列出部分代码：

#include #include #include #define OVERFLOW 0 #define MAX_CITIES 15 #define INFINITY 999 #define FALSE 0 #define TRUE 1

typedef struct _path {

int adjcity;//邻接点域 int distance;//距离

struct _path *nextpath;//下一个路径 } PathNode,*PList[MAX_CITIES];

typedef struct _city

11

{

char name[10];//城市名

struct _path *firstpath;//第一个路径 } AdjList[15],CityNode;

typedef struct {

int cities; int paths; AdjList list; } Graph;

PList head;

typedef int PathMatrix;

typedef int ShortPathTable;

PathMatrix P[MAX_CITIES][MAX_CITIES];

ShortPathTable D[MAX_CITIES];

12

int CreatAdjList(Graph *G)//初始化交通图 {

PathNode *p,*p1,*pre; int i=0;

printf(\"请输入交通路径数目\\n\"); scanf(\"%d\ printf(\"请输入城市数目\\n\"); scanf(\"%d\

for(i=0; icities; i++) {

printf(\"请输入第%d个城市名称\\n\ getchar();

scanf(\"%s\ G->list[i].firstpath=(PathNode *)malloc(sizeof(PathNode)); p=G->list[i].firstpath;

printf(\"请输入城市第一条路径的邻接城市的位置（-1表示结束）\\n\");

scanf(\"%d\

printf(\"请输入城市第一条路径的距离\\n\");

13

scanf(\"%d\ if(p->adjcity==-1) {

free(p); p=NULL;

G->list[i].firstpath = NULL;//把弧链表的first置为NULL } while(p) {

p->nextpath=(PathNode *)malloc(sizeof(PathNode)); pre=p;

p=p->nextpath;

printf(\"请输入城市下一条路径的邻接城市（-1表示结束）\\n\");

scanf(\"%d\ if(p->adjcity==-1) {

free(p); p=NULL;

pre->nextpath = NULL;//置pre为弧链表结束的节点 break; }

14

printf(\"请输入城市下一条路径的距离\\n\"); scanf(\"%d\ } } return 0; }

int ReadAdjList(Graph *G)//读取交通图 {

FILE *fp; int r,i;

PathNode *p,*p1,*pre;

if(( fp=fopen(\"graph.txt\ {

printf(\"文件打开失败\"); exit(0); }

r=fscanf(fp,\"%d %d \ if(r==2) {

for(i=0; icities; i++)

15

{

fscanf(fp,\"%s\ G->list[i].firstpath=(PathNode *)malloc(sizeof(PathNode)); p=G->list[i].firstpath; fscanf(fp,\"%d\ if(p->adjcity==-1) {

free(p); p=NULL;

G->list[i].firstpath = NULL;//把弧链表的first置为NULL

break; } else

fscanf(fp,\"%d\ while(1) {

p->nextpath=(PathNode *)malloc(sizeof(PathNode)); pre = p;

16

p=p->nextpath;

fscanf(fp,\"%d\ if(p->adjcity==-1) {

free(p); p=NULL;

pre->nextpath = NULL;//置pre为弧链表结束的节点

break; } else

fscanf(fp,\"%d\ } } }

fclose(fp); return 0; }

int WriteAdjList(Graph *G)//读取交通图 {

FILE *fp;

17

int r,i;

PathNode *p,*p1;

if(( fp=fopen(\"graph.txt\ {

printf(\"文件打开失败\"); exit(0); }

fprintf(fp,\"%d %d \

for(i=0; icities; i++) {

fprintf(fp,\"%s \ p=G->list[i].firstpath; while(p) {

fprintf(fp,\"%d %d \ p=p->nextpath; }

fprintf(fp,\"-1 \"); }

18

fclose(fp); return 0; }

void ADD_PATH(Graph *G,int ori,int add,PathNode p)//添加路径 {

PathNode *pr;

pr=(PathNode *)malloc(sizeof(PathNode)); pr->adjcity=add; pr->distance=p.distance;

pr->nextpath=G->list[ori].firstpath; G->list[ori].firstpath=pr; }

void ADD_CITY(Graph *G)//添加城市 {

int i=0;

PathNode *p,*pre;

if(G->cities>=MAX_CITIES) return ;

while(strcmp(G->list[i].name,\"0\")!=0) i++;

19

G->cities++;

printf(\"请输入%d城市的名称\\n\

getchar();

scanf(\"%s\

G->list[i].firstpath=(PathNode *)malloc(sizeof(PathNode)); p=G->list[i].firstpath;

printf(\"请输入城市第一条路径的邻接城市的位置（-1表示结束）\\n\");

scanf(\"%d\

printf(\"请输入城市第一条路径的距离\\n\"); scanf(\"%d\ if(p->adjcity==-1) {

free(p); p=NULL;

G->list[i].firstpath = NULL;//把弧链表的first置为NULL } else

20

{

ADD_PATH(G,p->adjcity,i,*p); }

while(p) {

p->nextpath=(PathNode *)malloc(sizeof(PathNode)); pre = p; p=p->nextpath;

printf(\"请输入城市下一条路径的邻接城市（-1表示结束）\\n\");

scanf(\"%d\

printf(\"请输入城市下一条路径的距离\\n\"); scanf(\"%d\ if(p->adjcity==-1) {

free(p); p=NULL;

pre->nextpath = NULL;//置pre为弧链表结束的节点 } else {

21

ADD_PATH(G,p->adjcity,i,*p); } } }

void UPDATE_CITY(Graph *G,int city,char *name) {

strcpy(G->list[city].name,name); }

int FindCity(Graph *G,char name[])//返回城市的序号 { int i;

for(i=0; icities; i++) {

if(strcmp(name,G->list[i].name)==0) return i; }

return -1; }

void UPDATE_PATH(Graph *G,int left,int right) {

PathNode *p; int dis;

22

printf(\"请输入修改后的路径距离\\n\"); scanf(\"%d\ p=G->list[left].firstpath; while(1) {

if(right==p->adjcity) {

p->distance=dis; break; }

p=p->nextpath; }

p=G->list[right].firstpath; while(1) {

if(left==p->adjcity) {

p->distance=dis; break; }

p=p->nextpath; }

23

return ; }

void DELETE_PATH(Graph *G,int left,int right) {

PathNode *p,*pre; int dis;

p=G->list[left].firstpath; pre=p; while(p) {

if(right==p->adjcity) {

break; }

p=p->nextpath; } while(1) {

if(p==G->list[left].firstpath) {

G->list[left].firstpath=p->nextpath;

24

free(p); break; }

if(pre->nextpath==p) {

pre->nextpath=p->nextpath; free(p); break; } }

p=G->list[right].firstpath; pre=p; while(p) {

if(left==p->adjcity) { break; }

p=p->nextpath; } while(1) {

25

if(p==G->list[right].firstpath) {

G->list[right].firstpath=p->nextpath; free(p); break; }

if(pre->nextpath==p) {

pre->nextpath=p->nextpath; free(p); break; } } return ; }

void DELETE_CITY(Graph *G,int city) { int i;

while(G->list[city].firstpath) {

DELETE_PATH(G,city,G->list[city].firstpath->adjcity); }

26

G->cities--;

for(i=city+1; i<=G->cities; i++) G->list[i-1]=G->list[i]; }

void menu(int i) {

switch(i) { case 0:

printf(\"==================================================================- ( ゜- ゜)つロ 乾杯~ \\n\");

printf(\"★★★欢迎进入交通咨询系统★★★\\n\"); printf(\"\\\\\1：任意键进入客户模式\\n\"); printf(\"\\\\2：输入密码进入管理员模式\\n\"); printf(\"\\\3：输入0退出系统\\n\"); printf(\"(o゜▽゜)o☆

[BINGO!]==================================================================\\n\"); break;

27

case 1:

printf(\"==================================================================- ( ゜- ゜)つロ 乾杯~ \\n\");

printf(\"★★★欢迎进入交通咨询系统管理员模式★★★\\n\"); printf(\"\\\\\\\\输入：\\n\"); printf(\"\\\\\\\1：初始化交通图\\n\"); printf(\"\\\\\\2：更新交通图信息\\n\"); printf(\"\\\\\3：删除交通图信息\\n\"); printf(\"\\\\4：添加交通图信息\\n\"); printf(\"\\\5：创建交通图\\n\"); printf(\"\\6：退出\\n\"); printf(\"(o゜▽゜)o☆

[BINGO!]==================================================================\\n\"); break; case 2:

printf(\"===================================

28

===============================- ( ゜- ゜)つロ 乾杯~ \\n\");

printf(\"★★★欢迎进入交通咨询系统客户模式★★★\\n\"); printf(\"\\\\\\\\输入：\\n\");

printf(\"\\\\\\\1：咨询某城市到其他所有城市的最短路径\\n\");

printf(\"\\\\\\2：咨询所有城市间的最短路径\\n\"); printf(\"\\\\\3：咨询两城市间的最短路径\\n\"); printf(\"\\\\4：浏览地图的邻接表表示\\n\"); printf(\"\\\5：退出\\n\"); printf(\"(o゜▽゜)o☆

[BINGO!]==================================================================\\n\"); break; } }

void initalize_graph(Graph *G) { int i;

for(i=0; istrcpy(G->list[i].name,\"0\");

29

G->list[i].firstpath=NULL; } }

void MODE_ADMIN(Graph *G) {

int i=0,j;

char name[20],name1[20]; PathNode *p; while(1) {

menu(1); scanf(\"%d\ switch(i) { case 1:

initalize_graph(G); printf(\"初始化完成！\\n\"); break; case 2:

printf(\"1：修改城市名\\n2：修改路径距离\\n3:返回上一层\\n\");

30

scanf(\"%d\ if(j==1) {

printf(\"请输入要修改的城市名称\\n\"); gets(name);

printf(\"请输入要修改后的城市名称\\n\"); gets(name1);

UPDATE_CITY(G, FindCity(G,name),name1); printf(\"修改完成！\\n\"); }

else if(j==2) {

printf(\"请输入要修改的两个中第一个城市的名称\\n\"); gets(name);

printf(\"请输入要修改的两个中第二个城市的名称\\n\"); gets(name1);

UPDATE_PATH(G,FindCity(G,name),FindCity(G,name1)); printf(\"修改完成！\\n\"); } else break;

31

break; case 3:

printf(\"1：删除城市\\n2：删除路径\\n3:返回上一层\\n\"); scanf(\"%d\ if(j==1) {

printf(\"请输入要删除的城市名称\\n\"); gets(name);

DELETE_CITY(G,FindCity(G,name)); printf(\"删除完成！\\n\"); }

else if(j==2) {

printf(\"请输入要删除的路径中第一个城市的名称\\n\"); gets(name);

printf(\"请输入要修改的两个中第二个城市的名称\\n\"); gets(name1);

DELETE_PATH(G,FindCity(G,name),FindCity(G,name1)); printf(\"删除完成！\\n\"); } else

32

break; break; case 4:

printf(\"1：添加城市\\n2：添加路径\\n3:返回上一层\\n\"); scanf(\"%d\ if(j==1) {

ADD_CITY(G); printf(\"添加完成！\\n\"); }

else if(j==2) {

p=(PathNode *)malloc(sizeof(PathNode)); printf(\"请输入要添加的路径中第一个城市的名称\\n\"); gets(name);

printf(\"请输入要添加的两个中第二个城市的名称\\n\"); gets(name1);

printf(\"请输入要添加的路径的距离\\n\"); scanf(\"%d\

ADD_PATH(G,FindCity(G,name),FindCity(G,name1),*p);

33

ADD_PATH(G,FindCity(G,name1),FindCity(G,name),*p); printf(\"添加完成！\\n\"); } else break; break; case 5:

CreatAdjList(G); printf(\"创建完成！\\n\"); break; default : return ; }

WriteAdjList(G); } }

int dis(Graph *G,int left,int right) {

PathNode *p;

p=G->list[left].firstpath;

34

while(p) {

if(right==p->adjcity) {

return p->distance; }

p=p->nextpath; }

return INFINITY; }

void ShortestPath(Graph *G,int v0) {

int i,w,v,min,l=0;

int final[MAX_CITIES];//Dijkstra tool for(v=0; vcities; v++) {

final[v]=FALSE; D[v]=dis(G,v0,v);

for(w=0; wcities; w++) P[v][w]=FALSE; if(D[v]35

{

P[v][v0]=1; P[v][w]=1; } } D[v0]=0; final[v0]=TRUE;

for(i=1; icities; i++) {

min=INFINITY;

for(w=0; wcities; w++) {

if(!final[w]) {

if(D[w]final[v]=TRUE;

36

for(w=0; wcities; w++) {

if(!final[w]&&(min+dis(G,v,w)D[w]=min+dis(G,v,w);

strcpy((char*)P[w],(char *)P[v]); P[w][v]=TRUE; } } } }

void FindPath(Graph *G,int v) {

int i=0;

for(i=0; iif(dis(G,v,i)printf(\"%s---->\ }

void Print(Graph *G,int v0) {

37

int i;

PathNode *p,*pre; for(i=0; icities; i++) {

if(i!=v0) {

printf(\"%s到%s的最短距离为%d，路径如下：\\n\>list[v0].name,G->list[i].name,D[i]); printf(\"%s---->\ P[i][v0]=0; P[i][i]=0; FindPath(G,i);

printf(\"%s\\n\ } } }

void Print2(Graph *G,int v1,int v2) {

38

printf(\"%s到%s的最短距离为%d，路径如下：\\n\>list[v1].name,G->list[v2].name,D[v2]); printf(\"%s---->\ P[v2][v1]=0; P[v2][v2]=0; FindPath(G,v2);

printf(\"%s\\n\}

void Print3(Graph *G) {

int i;PathNode *p; for(i=0; icities; i++) {

p=G->list[i].firstpath->nextpath; printf(\"|%-2d%-12s-->%-12s~%-3d|\ i+1,

G->list[i].name,

G->list[G->list[i].firstpath->adjcity].name, G->list[i].firstpath->distance); while(p) {

printf(\"-->%-12s~%-3d|\

39

G->list[p->adjcity].name, p->distance); p=p->nextpath; }

printf(\"<<\"); putchar(10); } }

void MODE_CLIENT(Graph *G) { int i,j; int v0,v1,v2;

char name1[20],name2[20],name[20]; while(1) {

menu(2); scanf(\"%d\ switch(i) { case 1:

printf(\"请输入城市的名称：\\n\");

40

scanf(\"%s\ v0=FindCity(G,name); if(v0==-1) {

printf(\"输入有误或者没有该城市！\"); break; }

ShortestPath(G,v0); Print(G,v0); break; case 3:

printf(\"请输入第一个城市的名称：\\n\"); scanf(\"%s\ v1=FindCity(G,name1);

printf(\"请输入第二个城市的名称：\\n\"); scanf(\"%s\ v2=FindCity(G,name2); if(v1==-1||v2==-1) {

printf(\"输入有误或者没有该城市！\"); break; }

41

ShortestPath(G,v1); Print2(G,v1,v2); break; case 2:

for(j=0; jcities; j++) {

ShortestPath(G,j); Print(G,j); } break; case 4: Print3(G); getchar(); getchar(); break; default: return ; } } }

int main()

42

{

Graph G;

int password=123; initalize_graph(&G); ReadAdjList(&G); while(1) {

menu(0);

scanf(\"%d\ if(password==123) MODE_ADMIN(&G); else if(password==0) return 0; else

MODE_CLIENT(&G); }

return 0; }

43

7 运行结果

插入城市函数测试： 输入： TextCity 0 3 -1

输出结果： 添加完成！

查看邻接表结果：

删除城市函数测试： 输入： LaSa

44

输出结果： 删除完成！

查看邻接表结果对比： 删除前： 删除后： 更新城市函数测试： 略；

修改城市函数测试： 略；

退出保存函数测试： 略；

45

单源多终点函数测试： 输入： TextCity

输出结果：

单源单终点函数测试： 输入： TextCity Guangzhou 输出结果：

输入有误或者没有该城市！ 输入： TextCity GuangZhou 46

输出结果：

TextCity到GuangZhou的最短距离为13，路径如下： TextCity---->BeiJing---->GuangZhou

多源多终点函数测试： BeiJing---->ShangHai BeiJing到ZhengZhou的最短距离为5，路径如下： BeiJing---->HanDan---->ZhengZhou BeiJing到XiAn的最短距离为5，路径如下： BeiJing---->XiAn BeiJing到WuHan的最短距离为7，路径如下： BeiJing---->HanDan---->WuHan BeiJing到GuangZhou的最短距离为10，路径如下： BeiJing---->GuangZhou BeiJing到ShenYang的最短距离为4，路径如下： BeiJing---->TianJin---->ShenYang BeiJing到LaSa的最短距离为25，路径如下： BeiJing---->XiAn---->LaSa BeiJing到HanDan的最短距离为3，路径如下： BeiJing---->HanDan BeiJing到TextCity的最短距离为3，路径如下： BeiJing---->TextCity TianJin到BeiJing的最短距离为1，路径如下： TianJin---->BeiJing TianJin到ShangHai的最短距离为8，路径如下： TianJin---->ShangHai TianJin到ZhengZhou的最短距离为6，路径如下： TianJin---->BeiJing---->HanDan---->ZhengZhou TianJin到XiAn的最短距离为6，路径如下： TianJin---->BeiJing---->XiAn 47

TianJin到WuHan的最短距离为8，路径如下： TianJin---->HanDan---->WuHan TianJin到GuangZhou的最短距离为11，路径如下： TianJin---->BeiJing---->GuangZhou TianJin到ShenYang的最短距离为3，路径如下： TianJin---->ShenYang TianJin到LaSa的最短距离为26，路径如下： TianJin---->XiAn---->LaSa TianJin到HanDan的最短距离为4，路径如下： TianJin---->BeiJing---->HanDan TianJin到TextCity的最短距离为4，路径如下： TianJin---->BeiJing---->TextCity ShangHai到BeiJing的最短距离为8，路径如下： ShangHai---->BeiJing ShangHai到TianJin的最短距离为8，路径如下： ShangHai---->TianJin

（部分输出结果）

8 心得体会

通过完成此次实验，学到了很多东西，也收获了解决问题的幸福。学到

的东西有很多，一是数据结构方面的知识；二是算法方面的知识；三是编程思想的升华；四是解决问题的思路更加明晰。

48

数据结构方面，我学会了灵活运用链表和数组，并学会运用了将二者合二为一的邻接表。邻接表是一个常见的图的存储结构。然而它也有很多方面的不足。如：寻找特定的弧结点，需要遍历弧链表，比较麻烦。因此在操作图的结构方面出现了很多的问题，我耐心得针对每个问题，想出每一种不同的解决方法。虽然邻接表在操作上很复杂，但是便于理解，在构造一个又一个函数之后，各种基本操作也变得简单了。尤其是书上迪杰斯特拉算法的C语言描述，用的是邻接矩阵，而我的又是无向图，所以非常难以理解。好在我不断的琢磨算法，不断的改造，以适应我的程序和存储结构，最终完成了算法的实现，令我十分欣喜。鼓舞了我学习算法和编程的信心。

算法方面，通过改造迪杰斯特拉算法，我了解了算法并不是固定不变的，只要了解算法的精髓，便可更好利用。

编程思想和解决问题方面，我学会了耐心，学会了理性的用逻辑图的方式解决问题。更加端正了我解决问题态度，以及学会了解决问题的套路。

49

50

9参考文献

[1] [2]

严蔚敏.《数据结构（C语言版）》.北京：清华大学出版社

谭浩强.《C语言程序设计》.（第三版）北京：清华大学出版社

[3] 崔.《数据结构（C语言版）》.北京：清华大学出版社

51

[4] 信息科学与工程 学院课程设计成绩评价表

课程名称：数据结构课程设计 设计题目：交通咨询系统

专业：计算机 班级：xxx 姓名：xxx 学号：xxx

序号 评审项目 分 数 满分标准说明 思路清晰；语言表达准确，概念清楚，论点正确；实验方法科1 内 容 20 学，分析归纳合理；结论严谨，设计有应用价值。任务饱满，做了大量的工作。 内容新颖，题目能反映新技术，对前人工作有改进或突破，或有独特见解 整体构思合理，理论依据充分，设计完整，实用性强 2 创 新 10 3 完整性、实用性 10 4 数据准确、可靠 10 数据准确，公式推导正确 设计格式、绘图、图纸、实验数据、标准的运用等符合有关标准和规定 能很好的遵守各项纪律，设计过程认真； 准备工作充分，回答问题有理论依据，基本概念清楚。主要问题回答简明准确。在规定的时间内作完报告。 5 规 范 性 10 6 纪 律 性 20 7 答 辩 20 总 分 52

综 合 意 见 指导教师：xx 2016 年7月6日

53