交通图咨询查询系统数据结构培训资料(doc 53页).doc

信息科学与工程学院结构数据课 程 设 计 报 告课程设计名称： 交通咨询系统 专 业 班 级 ： 计算机xxx 学 生 姓 名 ： xxx 学 号 ： 2015xxxx 指 导 教 师 ： xx 课程设计时间： 2016.07.042016.07.08 II 计算机应用技术 专业课程设计任务书学生姓名Xxx专业班级学号题 目交通咨询系统课题性质A课题来源D指导教师白浩同组姓名无主要内容1. 建立交通网络图的存储结构。2. 某个城市到达其余各城市的最短路径。3. 实现两个城市之间最短路径的问题。4. 主要目的是给用户提供路径咨询任务要求5. 根据需求分析给出概要设计，本系统包括以下功能模块：添加信息、查询信息、删除信息、修改信息、退出和保存信息；6. 结合课题利用数据结构相关知识，利用C语言实现该系统的所有上述功能，要求界面友善，程序运行正常；7. 提交课程设计报告1份（具体写作要求参考样例），可运行的系统和源代码电子版一套。参考文献严蔚敏.数据结构（C语言版）.北京：清华大学出版社谭浩强.C语言程序设计.（第三版）北京：清华大学出版社审查意见指导教师签字：xx教研室主任签字：xx 2016 年 06 月 27 日 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页填 表 说 明1“课题性质”一栏：A工程设计；B工程技术研究；C软件工程（如CAI课题等）；D文献型综述；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 迪杰斯特拉算法的实现85.2.1 迪杰斯特拉算法函数85.2.2 提取迪杰斯特拉函数信息85.2.3 求多源最短路径86 程序编码97 运行结果418 心得体会469参考文献471 需求分析本系统中的数据来源于标准输入设备（如键盘）和文件，可以实现对交通图城市、城市到其余城市的距离的操作，根据需要可查询某两个城市之间的最短距离、城市到各城市的最短距离，各个城市到各个城市的最短距离，以及路径。本系统要实现的功能有：添加城市和城市间距离，删除城市及城市间距离，修改城市间距离，查询城市间的最短路径，查询某个城市到某个城市的最短路径。具体如下： 1.1 添加交通图信息能录入新数据（城市和路径）。当录入了重复的城市和路径时，则提示数据录入重复并取消录入；当交通图中超过15个城市时，存储空间已满，不能再录入新数据；录入的新数据能按递增的顺序自动进行条目编号。1.2 查询单源最短路径能够实现输入起点城市名后，查询出其到各个城市的最短路径，输出该城市到的其他所有的城市的最短路径。1.3 查询多源最短路径 输入起点城市名和终点城市名，查询出两个城市的最短路径，并输出该最短路径。1.4 更新交通图信息根据给定的城市名能够修改该城市的名字。或者输入两个城市，修改一条路径的距离。 1.5 删除交通图信息 根据输入的城市名 ，删除与该城市有关的所有路径。输入两个城市可以删除一条路径。 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；/下一个路径 PathNode,*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 功能模块结构图根据需求分析，为了满足用户的功能需求，按照软件开发方法学中的模块划分原则，我将本系统主要划分为如下模块：操作交通图信息，和查询交通图路径两大模块。各模块之间的关系如图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 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)功能为：管理员端界面函数。 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；硬盘500G2. 软件环境：操作系统：windows104 开发工具和编程语言开发环境：CodeBlocks 、Dev C+编程语言：C语言5 详细设计在概要设计的基础上，对每个模块进行内部逻辑处理部分详细设计。下面分别列出各个模块具体实现流程图：5.1 图结构的基本操作 观察了数据对象后，我选择用一个邻接表用来存储图2信息，则数据结构的基本操作也就确定了，分别为图的添加、删除、更新。 图 2 模拟交通图5.1.1添加城市结点和路径结点 和图的基本操作相同，只是该城市每增加一个城市结点要在弧的邻接点对应的城市上也增加一条弧。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 提取迪杰斯特拉函数信息 根据P函数与D函数，可以将V0到每个终点的经过结点和最终路径求出，利用Print函数打印出V0和V，再调用FindPath函数，打印经过的结点。最后打印出距离，便可在屏幕上打印出单源最短路径。5.2.3 求多源最短路径 对每个结点循环调用便可打印出每个结点到其他结点的最短路径，通过改变Print函数的形参，便可以求出两点间的最短路径。 6 程序编码根据详细设计转化为如下代码，下面列出部分代码：#include#include #include#define OVERFLOW 0#define MAX_CITIES 15#define INFINITY 999#define FALSE 0#define TRUE 1typedef struct _path int adjcity;/邻接点域 int distance;/距离 struct _path *nextpath;/下一个路径 PathNode,*PListMAX_CITIES;typedef struct _city char name10;/城市名 struct _path *firstpath;/第一个路径 AdjList15,CityNode;typedef struct int cities; int paths; AdjList list; Graph;PList head;typedef int PathMatrix;typedef int ShortPathTable;PathMatrix PMAX_CITIESMAX_CITIES;ShortPathTable DMAX_CITIES;int CreatAdjList(Graph *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); 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置为NULL while(p) p-nextpath=(PathNode *)malloc(sizeof(PathNode); pre=p; p=p-nextpath; printf(请输入城市下一条路径的邻接城市（-1表示结束）n); scanf(%d,&p-adjcity); if(p-adjcity=-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(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置为NULL break; else fscanf(fp,%d,&p-distance); while(1) p-nextpath=(PathNode *)malloc(sizeof(PathNode); pre = p; p=p-nextpath; fscanf(fp,%d,&p-adjcity); if(p-adjcity=-1) free(p); p=NULL; pre-nextpath = NULL;/置pre为弧链表结束的节点 break; else fscanf(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); 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(sizeof(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-); 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置为NULL else 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,&p-adjcity); printf(请输入城市下一条路径的距离n); scanf(%d,&p-distance); if(p-adjcity=-1) free(p); p=NULL; pre-nextpath = NULL;/置pre为弧链表结束的节点 else ADD_PATH(G,p-adjcity,i,*p); void UPDATE_CITY(Graph *G,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; while(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; while(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-nextpath=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); 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(ttt5：创建交通图n); printf(tt6：退出n); printf(o)oBINGO!=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)oBINGO!=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(%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(修改完成！n); else break; 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(G,name1); printf(删除完成！n); else break; 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(%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); 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-listleft.firstpath; 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 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; i+) min=INFINITY; for(w=0; wcities; w+) if(!finalw) if(Dwmin) v=w