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

1、信息科学与工程学院结构数据课程设计报告课程设计名称： 交通咨询系统专 业 班 级 ： 计算机 xxx学 生 姓 名 ： xxx学 号 ： 2015xxxx指 导 教 师 ： xx课程设计时间： 2016.07.04 2016.07.08计算机应用技术 专业课程设计任务书学生姓名Xxx专业班级学号题目交通咨询系统课题性质A课题来源D指导教师白浩同组姓名无1.建立交通网络图的存储结构。2.某个城市到达其余各城市的最短路径。主要内容3.实现两个城市之间最短路径的问题。4.主要目的是给用户提供路径咨询5.根据需求分析给出概要设计，本系统包括以下功能模块：添加信息、查询信息、删除信息、修改信息、退出和保

2、存信息；任务要求6.结合课题利用数据结构相关知识， 利用 C 语言实现该系统的所有上述功能，要求界面友善，程序运行正常；7.提交课程设计报告 1 份（具体写作要求参考样例），可运行的系统和源代码电子版一套。参考文献严蔚敏 .数据结构（ C 语言版） .北京：清华大学出版社谭浩强 .C 语言程序设计 .（第三版）北京：清华大学出版社审查意见指导教师签字： xx教研室主任签字： xx2016 年 06 月 27 日说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页填表说明1 “课题性质” 一栏：A工程设计；B工程技术研究；C软件工程（如 CAI 课题等）；D文献型综

3、述；E其它。2 “课题来源” 一栏：A自然科学基金与部、省、市级以上科研课题；B企、事业单位委托课题；C校、院（系、部）级基金课题；D自拟课题目录1 需求分析 11.1 添加交通图信息 11.2 查询单源最短路径 11.3 查询多源最短路径 11.4 更新交通图信息 21.6 读取、保存信息 22 概要设计 32.1 数据类型的定义 32.2 功能模块结构图 43 运行环境 64 开发工具和编程语言 65 详细设计 75.1 图结构的基本操作 75.1.1 添加城市结点和路径结点 85.1.2 修改城市结点和路径结点 85.1.3 删除城市结点和路径结点 85.1.4 退出保存 85.2 迪杰

4、斯特拉算法的实现 85.2.1 迪杰斯特拉算法函数 85.2.2 提取迪杰斯特拉函数信息 85.2.3 求多源最短路径 86 程序编码 97 运行结果 4.18 心得体会 4.69 参考文献 4.71 需求分析本系统中的数据来源于标准输入设备（如键盘）和文件，可以实现对交通 图城市、城市到其余城市的距离的操作， 根据需要可查询某两个城市之间的最短 距离、城市到各城市的最短距离，各个城市到各个城市的最短距离，以及路径。 本系统要实现的功能有： 添加城市和城市间距离， 删除城市及城市间距离， 修改 城市间距离， 查询城市间的最短路径， 查询某个城市到某个城市的最短路径。 具 体如下：1.1 添加交

5、通图信息能录入新数据（城市和路径） 。当录入了重复的城市和路径时，则提示数据 录入重复并取消录入；当交通图中超过 15 个城市时，存储空间已满，不能再录 入新数据；录入的新数据能按递增的顺序自动进行条目编号。1.2 查询单源最短路径能够实现输入起点城市名后， 查询出其到各个城市的最短路径， 输出该城市 到的其他所有的城市的最短路径。1.3 查询多源最短路径输入起点城市名和终点城市名， 查询出两个城市的最短路径，并输出该最短路径。1.4 更新交通图信息根据给定的城市名能够修改该城市的名字。 或者输入两个城市， 修改一条路 径的距离。1.5 删除交通图信息根据输入的城市名 ，删除与该城市有关的所有

6、路径。 输入两个城市可以 删除一条路径。1.6 读取、保存信息能够实现退出系统时把交通图中的信息保存在一个文件中， 在程序瑕疵运行 时能够读取出来。2 概要设计2.1 数据类型的定义1. 定义交通图城市的元素类型typedef struct_citychar name10; 城市名struct _path * firstpath ； / 第一个路径 AdjList15,CityNode;2. 定义交通图的路径元素类型typedef struct _pathint adjcity/ 邻接点域int distance ； / 距离struct _path *nextpath ；/ 下一个路径 Pa

7、thNode,*PathPtr;3. 定义交通图类型typedef struct int cities;int paths;AdjList list ；Graph ;4. 全局变量PList head;typedef int PathMatrix;typedef int ShortPathTable;PathMatrix PMAX_CITIESMAX_CITIES;ShortPathTable DMAX_CITIES;2.2 功能模块结构图根据需求分析， 为了满足用户的功能需求， 按照软件开发方法学中的模块划 分原则，我将本系统主要划分为如下模块： 操作交通图信息， 和查询交通图路径 两大模块

8、。各模块之间的关系如图 1 所示。图 1 模块结构图 为了实现上述功能模块，分别在顺序表和单链表物理结构上定义了多个函 数，本系统定义的函数和功能如下：1. 数据结构部分部分void initalize_graph(Graph *G)功能为：图初始化，即生成一个空图。int CreatAdjList(Graph *G)/初始化交通图功能为：图的创建，用图存储数据。void ADD_CITY(Graph *G)功能为：往图 G 中插入一个城市结点。void ADD_PATH(Graph *G,int ori,int add,PathNode *p) 功能为：往图 G 中插入一个路径结点。void

9、 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 c

10、ity,char *name) 功能为：更新图 G 中的一个城市信息 。Status SqListSearchByName(SqList *L,char *phone) ; 功能为：通过电话号码查找顺序表中 ,返回值为其在通讯录中的位置2. 程序功能部分void MODE_CLIENT(Graph *G) 功能为：客户端界面函数。void MODE_ADMIN(Graph *G)功能为：管理员端界面函数int ReadAdjList(Graph *G) 功能为：从文件中读取交通图。int WriteAdjList(Graph *G) 功能为：在文件中存储交通图。void menu(int i)

11、 功能为：各种的端界面打印。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) 功能为：返

12、回指定路径的距离。3 运行环境1. 硬件环境 :PC 机内存 4G；硬盘 500G2. 软件环境：操作系统： windows104 开发工具和编程语言开发环境： CodeBlocks 、Dev C+编程语言： C 语言5 详细设计在概要设计的基础上， 对每个模块进行内部逻辑处理部分详细设计。 下面分 别列出各个模块具体实现流程图：5.1 图结构的基本操作观察了数据对象后，我选择用一个邻接表用来存储图 2 信息，则数据结构的基本操作也就确定了，分别为图的添加、删除、更新。图 2 模拟交通图5.1.1 添加城市结点和路径结点和图的基本操作相同，只是该城市每增加一个城市结点要在弧的邻接点对应的城市上

13、也增加一条弧。5.1.2 修改城市结点和路径结点和图的基本操作相同。5.1.3 删除城市结点和路径结点和图的基本操作相同， 只是该城市每删除一个城市结点要在弧的邻接点对应的城市上也 删除那条弧。5.1.4 退出保存在主函数的开始部分添加 Read 函数， 在管理员修改模式添加 Write 函数。实现对图结 构的读取保存。5.2 迪杰斯特拉算法的实现把算法实现得到不仅仅是一系列数组，而是将这些数组的信息提炼成有用的信息输出 出来，将抽象的数据转换为具象的信息。5.2.1 迪杰斯特拉算法函数定义了若干个全局辅助变量，如路径矩阵 P 和距离数组 D ， final 用来标记是否找 到了点的最短路径在

14、函数的初始阶段进行对个辅助变量的初始化， 第一趟把 V0 相邻的路径 距离保存下来。 选择一个最小的用 final 记录下来， 记录下最终的 D 和 P 值。再遍历其他结 点，如果出现新的路径，且路径小于最大值 INFINITY ，则保存路径和距离以便下次比较。 循环 n-1 次得到 V0 到各结点的最短距离和路径。5.2.2 提取迪杰斯特拉函数信息根据 P 函数与 D 函数，可以将 V0 到每个终点的经过结点和最终路径求出，利用 Print 函数打印出 V0 和 V，再调用 FindPath 函数，打印经过的结点。最后打印出距离，便可在 屏幕上打印出单源最短路径。5.2.3 求多源最短路径对

15、每个结点循环调用便可打印出每个结点到其他结点的最短路径，通过改变 Print 函数 的形参，便可以求出两点间的最短路径。6 程序编码根据详细设计转化为如下代码，下面列出部分代码：#include#include #include#define OVERFLOW 0#define MAX_CITIES 15#define INFINITY 999#define FALSE 0#define TRUE 1typedef struct _pathint adjcity;/ 邻接点域int distance;/ 距离struct _path *nextpath;/ 下一个路径 PathNode,*PL

16、istMAX_CITIES;typedef struct _citychar name10;/ 城市名struct _path *firstpath;/第一个路径 AdjList15,CityNode;typedef structint cities;int paths;AdjList list; Graph;PList head;typedef int PathMatrix;typedef int ShortPathTable;PathMatrix PMAX_CITIESMAX_CITIES;ShortPathT able DMAX_CITIES;int CreatAdjList(Graph

17、 *G)/ 初始化交通图PathNode *p,*p1,*pre;int i=0;printf( 请输入交通路径数目 n);scanf(%d,&G-paths);printf( 请输入城市数目 n);scanf(%d,&G-cities);for(i=0; icities; i+)printf( 请输入第 %d 个城市名称 n,i+1); getchar();scanf(%s,G-);G-listi.firstpath=(PathNode*)malloc(sizeof(PathNode);-1 表示p=G-listi.firstpath;printf( 请输入城市第一条路径

18、的邻接城市的位置(结束) n);scanf(%d,&p-adjcity);printf( 请输入城市第一条路径的距离 n);scanf(%d,&p-distance);if(p-adjcity=-1)free(p);p=NULL;G-listi.firstpath = NULL;/ 把弧链表的 first 置为 NULLwhile(p)p-nextpath=(PathNode*)malloc(sizeof(PathNode);pre=p;p=p-nextpath;printf( 请输入城市下一条路径的邻接城市( -1 表示结 束) n);scanf(%d,&p-adjcity);if(p-ad

19、jcity=-1)free(p);p=NULL;pre-nextpath = NULL;/ 置 pre 为弧链表结束的节点break;printf( 请输入城市下一条路径的距离 n); scanf(%d,&p-distance);return 0;int ReadAdjList(Graph *G)/ 读取交通图FILE *fp;int r,i;PathNode *p,*p1,*pre;if( fp=fopen(graph.txt,r)=NULL)printf( 文件打开失败 );exit(0);r=fscanf(fp,%d %d ,&G-paths,&G-cities);if(r=2)for(

20、i=0; icities; i+)fscanf(fp,%s,G-);G-listi.firstpath=(PathNode*)malloc(sizeof(PathNode);p=G-listi.firstpath;fscanf(fp,%d,&p-adjcity); if(p-adjcity=-1)free(p);p=NULL;G-listi.firstpath = NULL;/把弧链表的 first 置为 NULLbreak;elsefscanf(fp,%d,&p-distance);while(1)p-nextpath=(PathNode*)malloc(sizeof(P

21、athNode);pre = p;p=p-nextpath;fscanf(fp,%d,&p-adjcity);if(p-adjcity=-1)free(p);p=NULL;pre-nextpath = NULL;/ 置 pre 为弧链表 结束的节点break;elsefscanf(fp,%d,&p-distance);fclose(fp);return 0;int WriteAdjList(Graph *G)/ 读取交通图FILE *fp;int r,i;PathNode *p,*p1;if( fp=fopen(graph.txt,w)=NULL)printf( 文件打开失败 );exit(0

22、);fprintf(fp,%d %d ,G-paths,G-cities);for(i=0; icities; i+)fprintf(fp,%s ,G-);p=G-listi.firstpath;while(p)fprintf(fp,%d %d ,p-adjcity,p-distance);p=p-nextpath;fprintf(fp,-1 );fclose(fp); return 0;添加路void ADD_PATH(Graph *G,int ori,int add,PathNode p)/ 径PathNode *pr; pr=(PathNode *)malloc(si

23、zeof(PathNode); pr-adjcity=add;pr-distance=p.distance; pr-nextpath=G-listori.firstpath;G-listori.firstpath=pr;void ADD_CITY(Graph *G)/ 添加城市int i=0;PathNode *p,*pre; if(G-cities=MAX_CITIES) return ;while(strcmp(G-,0)!=0)i+;G-cities+;printf( 请输入%d 城市的名称 n,i+1);getchar();scanf(%s,G-

24、);G-listi.firstpath=(PathNode *)malloc(sizeof(PathNode); p=G-listi.firstpath;printf( 请输入城市第一条路径的邻接城市的位置 ( -1 表示结束) n);scanf(%d,&p-adjcity);printf( 请输入城市第一条路径的距离 n); scanf(%d,&p-distance);if(p-adjcity=-1)free(p);p=NULL;G-listi.firstpath = NULL;/ 把弧链表的 first 置为 NULLelseADD_PATH(G,p-adjcity,i,*p);while

25、(p)p-nextpath=(PathNode *)malloc(sizeof(PathNode);pre = p;p=p-nextpath;printf( 请输入城市下一条路径的邻接城市( -1 表示结束) n);scanf(%d,&p-adjcity);printf( 请输入城市下一条路径的距离 n);scanf(%d,&p-distance);if(p-adjcity=-1)free(p);p=NULL;pre-nextpath = NULL;/ 置 pre 为弧链表结束的节elseADD_PATH(G,p-adjcity,i,*p);void UPDATE_CITY(Graph *G,

26、int city,char *name) strcpy(G-,name);int FindCity(Graph *G,char name)/ 返回城市的序号 int i;for(i=0; icities; i+)if(strcmp(name,G-)=0) return i;return -1;void UPDATE_PATH(Graph *G,int left,int right) PathNode *p;int dis;printf( 请输入修改后的路径距离 n); scanf(%d,&dis);p=G-listleft.firstpath;wh

27、ile(1)if(right=p-adjcity)p-distance=dis;break;p=p-nextpath;p=G-listright.firstpath;while(1)if(left=p-adjcity)p-distance=dis;break;p=p-nextpath;return ;void DELETE_PATH(Graph *G,int left,int right)PathNode *p,*pre;int dis;p=G-listleft.firstpath;pre=p;while(p)if(right=p-adjcity)break;p=p-nextpath;whil

28、e(1)if(p=G-listleft.firstpath)G-listleft.firstpath=p-nextpath;free(p);break;if(pre-nextpath=p)pre-nextpath=p-nextpath;free(p);break;p=G-listright.firstpath;pre=p;while(p)if(left=p-adjcity)break;p=p-nextpath;while(1)if(p=G-listright.firstpath)G-listright.firstpath=p-nextpath;free(p);break;if(pre-next

29、path=p)pre-nextpath=p-nextpath;free(p);break;return ;void DELETE_CITY(Graph *G,int city)int i;while(G-listcity.firstpath)DELETE_PATH(G,city,G-listcity.firstpath-adjcity); G-cities-;for(i=city+1; icities; i+)G-listi-1=G-listi;void menu(int i)switch(i)case 0:printf(= =- ( - ) 乾杯 n);printf( 欢迎进入交通咨询系统n

30、); printf(ttttt1 ：任意键进入客户模式 n); printf(tttt2 ：输入密码进入管理员模式 n);printf(ttt3 ：输入 0 退出系统 n);printf(o)oBINGO!=n);break;case 1:printf(=- ( - ) 乾杯 n);printf( 欢迎进入交通咨询系统管理员模式 n);printf(tttttttt输入： n);printf(ttttttt1：初始化交通图 n);printf(tttttt2：更新交通图信息 n);printf(ttttt3：删除交通图信息 n);printf(tttt4 ：添加交通图信息 n); printf

31、(ttt5 ：创建交通图 n); printf(tt6 ：退出 n);printf(o )o BINGO!=n);break;case 2:printf(=- ( - ) 乾杯 n);printf( 欢迎进入交通咨询系统客户模式 n);printf(tttttttt输入： n);printf(ttttttt1：咨询某城市到其他所有城市的最短路径n);printf(tttttt2：咨询所有城市间的最短路径 n);printf(ttttt3：咨询两城市间的最短路径 n);printf(tttt4：浏览地图的邻接表表示 n);printf(ttt5 ：退出 n);printf(o )o BINGO!

32、=n);break;void initalize_graph(Graph *G)int i;for(i=0; ,0);G-listi.firstpath=NULL;void MODE_ADMIN(Graph *G)int i=0,j;char name20,name120;PathNode *p;while(1)menu(1);scanf(%d,&i);switch(i)case 1:initalize_graph(G);printf( 初始化完成！ n);break;case 2:printf(1 ：修改城市名 n2 ：修改路径距离 n3: 返回上 一层n);scanf

33、(%d,&j);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( 修改完成！

34、 n);elsebreak;break;case 3:printf(1 ：删除城市 n2 ：删除路径 n3: 返回上一层 n); scanf(%d,&j);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

35、(G,name1);printf( 删除完成！ n);elsebreak;break;case 4:printf(1 ：添加城市 n2 ：添加路径 n3: 返回上一层 n); scanf(%d,&j);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(%

36、d,p-adjcity);ADD_PATH(G,FindCity(G,name),FindCity(G,name1),*p);ADD_PATH(G,FindCity(G,name1),FindCity(G,name),*p);printf( 添加完成！ n);elsebreak;break;case 5:CreatAdjList(G);printf( 创建完成！ n);break;default :return ;WriteAdjList(G);int dis(Graph *G,int left,int right)PathNode *p;p=G-listleft.firstpath;whil

37、e(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 finalMAX_CITIES;/Dijkstra tool for(v=0; vcities; v+)finalv=FALSE;Dv=dis(G,v0,v); for(w=0; wcities; w+)Pvw=FALSE;if(DvINFINITY)Pvv0=1;Pvw=1;Dv0=0;finalv0=TRUE;for(i=1; icities

38、; i+)min=INFINITY;for(w=0; wcities; w+)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=TRUE;for(w=0; wcities; w+)if(!finalw&(min+dis(G,v,w)Dw) Dw=min+dis(G,v,w);strcpy(char*)Pw,(char *)Pv);Pwv=TRUE;void FindPath(Graph *G,int v)int i=0;for(i=0; iMAX_CITIES; i+) if(Pvi=1)if(dis(G,v,i),G-);void Print(G

39、raph *G,int v0)int i;PathNode *p,*pre;for(i=0; icities; i+)if(i!=v0)路径如下：printf(%s 到%s 的最短距离为%d ，n,G-,G-,Di);printf(%s,G-);Piv0=0;Pii=0;FindPath(G,i);printf(%sn,G-);void Print2(Graph *G,int v1,int v2)printf(%s 到 %s 的 最 短 距 离 为 %d ， 路 径 如 下 ：n,G-,G

40、-,Dv2);printf(%s,G-);Pv2v1=0;Pv2v2=0;FindPath(G,v2);printf(%sn,G-);void Print3(Graph *G)int i;PathNode *p;for(i=0; icities; i+)p=G-listi.firstpath-nextpath;printf(|%-2d%-12s-%-12s%-3d|,i+1,G-,G-listG-,G-listi.firstpath-distance);

41、while(p)printf(-%-12s%-3d|,G-, p-distance);p=p-nextpath;printf();putchar(10);void MODE_CLIENT(Graph *G)int i,j;int v0,v1,v2;char name120,name220,name20;while(1) menu(2);scanf(%d,&i);switch(i)case 1:printf( 请输入城市的名称： n); scanf(%s,name);v0=FindCity(G,name);if(v0=-1)printf( 输入有误或者没有该城

42、市！ );break;ShortestPath(G,v0);Print(G,v0);break;case 3:printf( 请输入第一个城市的名称： n);scanf(%s,name1);v1=FindCity(G,name1);printf( 请输入第二个城市的名称： n);scanf(%s,name2);v2=FindCity(G,name2);if(v1=-1|v2=-1)printf( 输入有误或者没有该城市！ ); break;ShortestPath(G,v1);Print2(G,v1,v2);break;case 2:for( j=0; jcities; j+)Shortest

43、Path(G,j);Print(G,j);break;case 4:Print3(G);getchar();getchar();break;default: return ;int main()Graph G;int password=123;initalize_graph(&G);ReadAdjList(&G);while(1)menu(0); scanf(%d,&password); if(password=123)MODE_ADMIN(&G);else if(password=0) return 0;elseMODE_CLIENT(&G);return 0;7 运行结果 插入城市函数测试

44、： 输入：TextCity03-1输出结果：添加完成！查看邻接表结果：删除城市函数测试：输入：LaSa输出结果：删除完成！查看邻接表结果对比：删除前：删除后：更新城市函数测试：略；修改城市函数测试：略；退出保存函数测试：略；单源多终点函数测试：输入：TextCity输出结果：单源单终点函数测试：输入：TextCityGuangzhou输出结果：输入有误或者没有该城市！输入：TextCityGuangZhou输出结果：TextCity 到 GuangZhou 的最短距离为 13 ，路径如下：TextCityBeiJingGuangZhou多源多终点函数测试：BeiJingShangHaiBeiJ

45、ing 到 ZhengZhou 的最短距离为 5 ，路径如下：BeiJingHanDanZhengZhouBeiJing 到 XiAn 的最短距离为 5，路径如下：BeiJingXiAnBeiJing 到 WuHan 的最短距离为 7，路径如下：BeiJingHanDanWuHanBeiJing 到 GuangZhou 的最短距离为 10 ，路径如下：BeiJingGuangZhouBeiJing 到 ShenYang 的最短距离为 4 ，路径如下：BeiJingTianJinShenYangBeiJing 到 LaSa 的最短距离为 25 ，路径如下：BeiJingXiAnLaSaBeiJing 到 HanDan 的最短距离为 3 ，路径如下：BeiJingHanDanBeiJing 到 TextCity 的最短距离为 3 ，路径如下：BeiJingTextCityTianJin 到 BeiJing 的最短距离为 1 ，路径如下：TianJinBeiJingTianJin 到 ShangHai 的最短距离为 8 ，路径如下：TianJinShangHaiTianJin 到 ZhengZh