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

I信息科学与工程学院《结构数据》课程设计报告课程设计名称：交通咨询系统专业班级：计算机xxx学生姓名：xxx学号：2015xxxx指导教师：xx课程设计时间：2016.07.04—2016.07.08I计算机应用技术专业课程设计任务书学生姓名Xxx专业班级学号题目交通咨询系统课题性质A课题来源D指导教师白浩同组姓名无主要内容1.建立交通网络图的存储结构。2.某个城市到达其余各城市的最短路径。3.实现两个城市之间最短路径的问题。4.主要目的是给用户提供路径咨询任务要求5.根据需求分析给出概要设计，本系统包括以下功能模块：添加信息、查询信息、删除信息、修改信息、退出和保存信息；6.结合课题利用数据结构相关知识，利用C语言实现该系统的所有上述功能，要求界面友善，程序运行正常；7.提交课程设计报告1份（具体写作要求参考样例），可运行的系统和源代码电子版一套。参考文献严蔚敏.《数据结构（C语言版）》.北京：清华大学出版社谭浩强.《C语言程序设计》.（第三版）北京：清华大学出版社审查意见指导教师签字：xx教研室主任签字：xx2016年06月27日说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页II填表说明1．“课题性质”一栏：A．工程设计；B．工程技术研究；C．软件工程（如CAI课题等）；D．文献型综述；E．其它。2．“课题来源”一栏：A．自然科学基金与部、省、市级以上科研课题；B．企、事业单位委托课题；C．校、院（系、部）级基金课题；D．自拟课题。III目录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参考文献...................................................................................................................4711需求分析本系统中的数据来源于标准输入设备（如键盘）和文件，可以实现对交通图城市、城市到其余城市的距离的操作，根据需要可查询某两个城市之间的最短距离、城市到各城市的最短距离，各个城市到各个城市的最短距离，以及路径。本系统要实现的功能有：添加城市和城市间距离，删除城市及城市间距离，修改城市间距离，查询城市间的最短路径，查询某个城市到某个城市的最短路径。具体如下：1.1添加交通图信息能录入新数据（城市和路径）。当录入了重复的城市和路径时，则提示数据录入重复并取消录入；当交通图中超过15个城市时，存储空间已满，不能再录入新数据；录入的新数据能按递增的顺序自动进行条目编号。1.2查询单源最短路径能够实现输入起点城市名后，查询出其到各个城市的最短路径，输出该城市到的其他所有的城市的最短路径。1.3查询多源最短路径输入起点城市名和终点城市名，查询出两个城市的最短路径，并输出该最短路径。21.4更新交通图信息根据给定的城市名能够修改该城市的名字。或者输入两个城市，修改一条路径的距离。1.5删除交通图信息根据输入的城市名，删除与该城市有关的所有路径。输入两个城市可以删除一条路径。1.6读取、保存信息能够实现退出系统时把交通图中的信息保存在一个文件中，在程序瑕疵运行时能够读取出来。32概要设计2.1数据类型的定义1.定义交通图城市的元素类型typedefstruct_city{charname[10];城市名struct_path*firstpath；//第一个路径}AdjList[15],CityNode;2.定义交通图的路径元素类型typedefstruct_path{intadjcity//邻接点域intdistance；//距离struct_path*nextpath；//下一个路径}PathNode,*PathPtr;3.定义交通图类型typedefstruct{intcities;intpaths;AdjListlist；}Graph;4.全局变量4PListhead;typedefintPathMatrix;typedefintShortPathTable;PathMatrixP[MAX_CITIES][MAX_CITIES];ShortPathTableD[MAX_CITIES];2.2功能模块结构图根据需求分析，为了满足用户的功能需求，按照软件开发方法学中的模块划分原则，我将本系统主要划分为如下模块：操作交通图信息，和查询交通图路径两大模块。各模块之间的关系如图1所示。图1模块结构图为了实现上述功能模块，分别在顺序表和单链表物理结构上定义了多个函5数，本系统定义的函数和功能如下：1.数据结构部分部分voidinitalize_graph(Graph*G)功能为：图初始化，即生成一个空图。intCreatAdjList(Graph*G)//初始化交通图功能为：图的创建，用图存储数据。voidADD_CITY(Graph*G)功能为：往图G中插入一个城市结点。voidADD_PATH(Graph*G,intori,intadd,PathNode*p)功能为：往图G中插入一个路径结点。voidDELETE_CITY(Graph*G,intcity)功能为：删除图G中的指定的城市及其相关的路径。voidDELETE_PATH(Graph*G,intleft,intright)功能为：删除图G中一条指定的路径。voidUPDATE_PATH(Graph*G,intleft,intright)功能为：更新图G中的一个路径信息。StatusSqListSearchByName(SqList*L,char*name);功能为：通过姓名查找顺序表中,返回值为其在通讯录中的位置。voidUPDATE_CITY(Graph*G,intcity,char*name)功能为：更新图G中的一个城市信息。StatusSqListSearchByName(SqList*L,char*phone);功