下载文档原格式
太原工业学院计算机工程系数据结构课程设计设计题目：全国交通网络咨询系统1班级：计算机科学与技术学号：**********名：**指导教师：***年月日目录一、课程设计题目 (1)二、需求分析 (1)三、测试数据 (2)四、概要设计 (2)五、调用关系图 (3)六、程序代码 (3)七、测试结果 (14)八、心得体会及总结 (14)数据结构课程设计一、课程设计题目全国交通网络咨询系统二、需求分析1、实现功能对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能；对城市间的交通工具：火车。
对列车时刻表进行编辑：里程、和列车班次的添加、修改、删除；提供两种最优决策：最快到达或最省钱到达。
全程只考虑一种交通工具，可以不考虑回程；咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。
由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间，并详细说明依次于何时何地乘坐哪一趟列车何时到达何地。
2、设计思路（1) 数据存储。
城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件。
在实验中本想用文本储存数据，但操作不熟悉，而是改用图的邻接矩阵储存原始信息，而后用数组进行添加删改(2) 数据的逻辑结构。
根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为无向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的时间）或旅费。
(3) 数据的存储结构。
采用邻接表和邻接矩阵都可作为数据的存储结构，这里建议采用邻接矩阵作为数据的存储结构。
(4) 用不同的功能模块对城市信息和交通信息进行编辑。
添加、修改、删除功能可用菜单方式或命令提示方式。
只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面，具体实现由学生自行设计，也可参考有关程序(届时在网上提供)。
这些工作有不小的工作量。
适用标准文案设计题目<二>：交通咨询系统设计P160一、设计要求1．问题描绘依据不一样目的的游客对交通工拥有不一样的要求。
比如，因公出差的游客希望在旅途中的时间尽可能的短，出门旅游的游客希望旅费尽可能的少，而老年人则要求中转次数少。
模拟一个全国城市之间的咨询交通程序，为游客供给两种或三种最优的交通路线。
2．需求剖析二、纲要设计1．主界面设计（图“交通咨询系统”主菜单）2．储存构造设计本系统采纳图构造种类储存抽象交通咨询系统的信息。
typedefstructTrafficNode{charname[MAX_STRING_NUM];//班次//MAX_STRING_NUM 最为10intStartTime,StopTime;//起止时间intEndCity;//该有向边指向的极点在数组中的地点，即该城市编号intCost;//票价出色文档}TrafficNodeDat;typedefstructVNode{CityTypecity;intTrainNum,FlightNum;//标志下边Train数组和Flight数组里元素个数TrafficNodeDatTrain[MAX_TRAFFIC_NUM];//数构成员为构造体，记录了到达城市、起止时间、票价和班次TrafficNodeDatFlight[MAX_TRAFFIC_NUM];intCost;//遍历时抵达该城市的耗资（时间或许花费）}VNodeDat;typedefstructPNode{intCity;intTraNo;}PNodeDat;3．系统功能设计1）增添城市。
增添一个城市的名称2）删除城市。
输入一个城市名称，删除该城市。
3）增添交通路线。
输入开端城市、终点城市、航班或火车、车次、开端时间、终点时间和票价4）删除交通路线。
输入火车或飞机的班次删除该交通路线。
5）查问最小花费路线。
输入开端城市、终点城市、航班或火车、车次、开端时间、终点时间查问最小花费路线。
数据结构设计报告姓名：专业：指导教师：目录摘要 (3)第1章概述 (4)1.1系统实现的目标 (4)1.2系统实现方案 (4)1.3系统实现环境 (4)1.4具体的开发方法 (4)第2章系统设计 (5)2.1系统功能设计 (5)2.2数据设计 (5)2.3界面的设计 (5)第3章系统实现 (9)参考文献 (15)摘要设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：一是建立交通网络图的存储结构，二实现两个城市间的最短路经问题。
程序所具有的功能特色本程序主要目的是为了给用户提供路径咨询。
实现了帮助用户了解全国各大城市间往来的最短路径问题，第二，可以提供用户查询各大城市的相关信息。
本程序最大的特点是支持用户自己添加城市信息及城市，或添加城市的路径，既就有可扩展性该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。
此程序规定：（1）在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。
（2）程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。
（3）程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。
第1章概述1.1 系统实现的目标通过进行课程设计，了解并初步掌握设计、实现较大系统的完整过程，包括：系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。
应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。
信息科学与工程学院课程设计任务书题目：交通咨询系统设计学号： 201112220141姓名：年级：专业：计算机应用与技术课程：数据结构指导教师：职称：完成时间：课程设计任务书及成绩评定一、需求分析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。
对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。
本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。
1.1.1建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。
图的邻接矩阵是定义如下的n 阶方阵：设G=（V ，E ）是一个图，结点集为{}n v v v V ,,,21 =。
G 的邻接矩阵,E,,0E,,)(,)(⎪⎩⎪⎨⎧>∉<∞>∈<==⨯⨯j i j i j i j i n n j i ij n n ij v v v v v v v v w a a A ）或当（，或）或当（， 当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。
图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n 个元素的一维数组来存储顶点信息，其中下标为i 的元素存储顶点i 的信息。
因此，图的邻接矩阵的存储结构定义如下：1.1.2 单源最短路径最短路径的提法很多。
在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望找出从某个源点S ∈V 到G 中其余各顶点的最短路径。
为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。
那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra ）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。
迪杰斯特拉算法求最短路径的实现思想是：设G=（V ，E ）是一个有向图，结点集为，}v ,,v ,{v V n 21⋯=，cost 是表示G 的邻接矩阵，cost[i][j]表示有向边<i,j>的权。
.郑州工业应用技术学院课程设计任务书题目全国交通资询系统主要内容：设计了一个方便用户查询交通咨询系统。
该系统所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。
该系统可以进行城市，列车车次和飞机航班的编辑的基本信息输入操作。
程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。
程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。
基本要求：1、掌握C语言的变量及函数的灵活使用；2、熟练掌握图的深度、广度优先遍历算法思想及其程序实现；3、掌握C语言中文件的基本操作；4、掌握VC++6.0软件的熟练使用。
主要参考资料：[1] 李春葆.数据结构程序设计[M].北京:清华大学出版社,2002,03[2] 王黎,袁永康战略[M].北京:清华大学出版社,2002,01[3] 谭浩强.C程序设计第二版[M].北京:清华大学出版社,2003,03[4] 任哲.MFC Windows程序设计[M].北京:清华大学出版社,2004,06完成期限：2016.12.05—2017.01.05指导教师签名：课程负责人签名：随着高科技的飞速发展，列车、飞机、动车、高铁的出现极大的减少了人们花在旅途上的时间。
对于城市间错综复杂交通网的管理，是一项庞大而复杂的工作。
在此基础上，如何实现交通网智能化的管理达到帮助乘客选择经济高效的交通工具是目前仍处空白。
尤其乘客交通工具的择优选择是一个令人懊恼的工作，一个原因就是各种交通工具的查询十分分散和繁琐。
即使有互联网的帮忙，但是没有一个统一的归类、没有一个精细的算法、系统的软件帮助，人们仍然无法获得最优方式。
为此开发一个交通择优系统是十分必要的。
采用计算机对城市间的交通工具进行系统录入和管理，进一步提高了交通部门针对城市间客运网络的管理效率，实现交通运营网络的系统化、规范化和自动化。
数据结构课程设计—城市道路交通咨询系统榆林学院数据结构课程设计报告题目城市交通咨询系统作者杨朝专业信息管理与信息系统学号 1514210121 指导老师张慧答辩时间 2016.12.18目录1.系统需求分析 (1)1.1用户需求分析 (1)1.2功能需求分析 (2)1.3数据需求分析 (2)1.4 小结 (3)2.系统设计 (3)2.1系统设计功能 (3)2.2每个模块的具体功能。
(4)2.2.1采用C语言定义相关数据类型 (4)2.2.2建立邻接矩阵交通网络： (5)2.2.3查询指定城市到其他城市自己建的最短路程： (6)2.2.4查询任意两个城市之间的一条最短路径： (8)2.3主函数的调用关系图 (9)3.系统测试 (11)3.1操作说明 (11)3.2测试数据 (11)3.2.1用户进入界面： (11)3.2.2、具体功能的实现 (12)3.2.3、结束程序 (14)4.总结 (15)5.致谢 (15)6.附录 (16)1.系统需求分析现如今网络非常发达，无论人们出差，旅游或者做其他的出行之时，都会想到道路问题，切不仅仅关心的是交通费用，而且对于里程和所需要的时间等的问题也是同样的关心，在此系统中，完全面向用户，可以用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。
且在图中，顶点表示城市，边表示城市之间的交通关系。
设计一个交通咨询系统，能够让旅客咨询从任一城市顶点到达另外一个城市之间顶点的最短路径问题（最短里程问题）。
对系统分析，主要从以下几个方面进行分析。
1.用户需求分析2.功能需求分析3.数据需求分析1.1用户需求分析现如今网络非常发达，无论人们出差，旅游或者做其他的出行之时，都会想到道路问题，切不仅仅关心的是交通费用，而且对于里程和所需要的时间等的问题也是同样的关心，在此系统中，完全面向用户，可以用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。
且在图中，顶点表示城市，边表示城市之间的交通关系。
数据结构课程设计全国交通咨询系统数据结构课程设计全国交通咨询系统随着交通工具的快速发展，现代人的出行方式更加灵活便捷，交通行业也变得越来越重要。
然而，随之而来的交通拥堵、安全问题和出行效率等问题亟待解决。
因此，交通咨询系统的开发应运而生。
本文介绍一个数据结构课程设计项目——全国交通咨询系统，该系统旨在为用户提供便捷、全面的交通出行信息和服务。
该系统主要包括以下方面的功能：1. 城市选择及路线查询功能用户可选择目的地城市，系统将返回该城市的基本信息，以及从用户当前位置到目的地的交通路线和方案，并提供相应的时间和费用信息。
2. 交通工具查询功能用户可在系统中查询各种交通工具的班次、价格、车次和到达时间等相关信息，以便用户做出最优出行方案。
3. 路况信息查询该系统可实时获取交通状况信息，并展示给用户最新的路况信息。
此外，当用户选择出行方式时，系统可根据实时路况为用户提供最佳出行方案。
4. 预订和购票该系统可为用户提供方便的预订和购票服务。
用户可在线预订和购买机票、火车票和长途汽车票等交通工具，并选择合适的座位和时间。
5. 旅游景点推荐功能该系统可根据用户的出行方案提供适宜的旅游景点推荐。
用户可在系统中了解这些景点的详细信息和交通时间，以便更好地规划自己的行程。
该全国交通咨询系统的实现需要多种数据结构的支持，例如图、树、堆栈、链表、哈希表等。
下面分别讨论每个功能的实现方法和相关数据结构。
1. 城市选择及路线查询功能城市选择及路线查询功能需要通过图的遍历来实现。
图是由顶点和边组成的集合，可以用来表示城市及它们之间的相互关系。
在本系统中，每个城市可以看做一个顶点，每条连接两个城市的路径被视为一条边。
为了实现城市选择及路线查询功能，需要对图进行遍历。
在这个系统中，广度优先搜索算法（BFS）是最佳选择，因为BFS可以给出最近的解决方案。
2. 交通工具查询功能交通工具查询功能需要通过树来实现。
树是由节点和边组成的集合，可以用来表示各种结构化数据。
数据结构--交通咨询系统数据结构--交通咨询系统一、引言交通咨询系统是为了方便用户获取交通相关信息而设计的一种软件系统。
本文档旨在说明交通咨询系统的设计和实现细节，包括系统的功能需求、系统架构、核心算法以及数据结构的选择等方面内容。
二、功能需求1、用户注册与登录功能a：用户可以通过注册功能创建账户；b：用户可以通过登录功能进行身份验证。
2、交通信息查询功能a：用户可以根据起点和终点查询交通路线；b：用户可以查询公交、地铁、火车、飞机等交通工具的时刻表；c：用户可以查询附近交通站点或机场、车站的详细信息。
3、交通信息推荐功能a：根据用户的历史查询记录和个人偏好，系统可以推荐适合的交通方案；b：根据用户的位置信息，系统可以推荐附近的交通站点或机场、车站。
4、系统设置功能a：用户可以选择系统界面的主题风格；b：用户可以设置提醒功能，以接收相关交通信息的通知。
三、系统架构1、前端设计a：用户界面设计：包括登录、注册、查询、推荐、设置等功能的界面设计；b：用户交互设计：实现用户与系统之间的信息交互。
2、后端实现a：数据库设计：设计用户、交通路线、交通工具、交通站点等相关数据表；b：服务器端设计：负责处理用户请求、数据存储和计算等任务；c：算法设计：设计合适的算法用于交通信息查询和推荐。
四、核心算法1、最短路径算法a：使用Dijkstra算法计算起点到终点的最短路径；b：考虑交通工具的运行时间、换乘时间等因素。
2、推荐算法a：使用协同过滤算法根据用户的历史查询记录和个人偏好进行交通方案推荐；b：使用基于位置的推荐算法根据用户的位置信息推荐附近的交通站点或机场、车站。
五、数据结构选择1、图结构a：使用图结构来表示交通路线和交通站点之间的关系；b：利用图的搜索算法来实现最短路径算法。
2、队列和栈a：使用队列和栈来处理用户的查询请求和系统的任务调度。
六、附件本文档涉及的附件包括系统的界面原型设计图、数据库设计文档、算法设计文档等。
课程设计题目：城市交通咨询系统一、课程设计的原始资料及依据在交通网络非常发达，交通工具和交通方式不断更新的今天，人们的出差、旅游或做其他的出行时，不仅关心节省交通运费问题，而且对里程和所需要时间等问题感兴趣。
可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。
图中顶点表示城市，边表示城市之间的交通关系。
这个交通咨询系统可用回答旅客提出的各种问题。
二、课程设计主要内容及要求1. 建立交通网络图的存储结构。
2. 画出主要的功能结构图和主要模块的流程图。
3. 使用迪杰斯特拉算法：求一个城市到其它所有城市最短路径。
4. 使用弗洛伊德算法：求任意两个城市间最短路径。
三、对课程设计说明书撰写内容、格式、字数的要求1．课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。
一般不应少于3000字。
2．在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。
应做到文理通顺，内容正确完整，书写工整，装订整齐。
3．设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。
设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组组长给出评语。
4．课程设计说明书手写或打印均可。
手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用A4纸，页边距均为20mm，正文采用宋体小四号字，行间距18磅。
文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。
5．课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。
四、设计完成后应提交成果的种类、数量、质量等方面的要求1．完成“任务书”中指定的操作功能，运行稳定。
欢迎阅读榆林学院数据结构课程设计报告题目城市交通咨询系统1 .1.11.21.31.4 小结2.2.12.22.2.12.2.22.2.32.2.42.33.系统测试 (9)3.1操作说明 (9)3.2测试数据 (10)3.2.1用户进入界面： (10)3.2.2、具体功能的实现 (11)3.2.3、结束程序 (12)4.总结 (13)5.致谢 (13)6.附录 (14)1.系统需求分析现如今网络非常发达，无论人们出差，旅游或者做其他的出行之时，都会想到道路问题，切不仅仅关心的是交通费用，而且对于里程和所需要的时间等的问题也是同样的关心，在此系统中，完全面向用户，可以用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。
且在图中，顶点表示城市，边表示城市之间的交通关系。
设计一个交通咨询系统，能够让旅客咨询从任一城市顶点到达另外一个城市之间顶点的最短路径问题（最短里程问题）。
（2）用户根据自己设置的城市个数和路径数，具体输入每个路径的起始点以及每条路径的长度。
（3）进入菜单选择界面（4）选择2，系统为用户进行提供任意城市的交通查询,即查询任意两个城市之间的一条最短路径。
（5）选择1，系统为用户提供指定城市的交通查询，即查询指定城市到其他城市之间的最短路径。
如若输入顶点超出范围显示错误，系统回到菜单重新选择（6）选择0，系统推出程序。
1.2功能需求分析城市交通咨询系统总体的设计目标：用《数据结构》中的邻接矩阵作数据结构，并结合数据结构有向图的最短路径计算方法，结合相应的数据算法以及c采用邻接矩阵表示法构造有向图G，n、e表示图的当前顶点数和边数∙用弗洛伊德算法求任意一对顶点的最短路径用函数 void Floyd(MGraph *G,int n) 来定义。
利用费洛伊德算法，求出最短路径。
1.4 小结从各种需求方面下手改编代码，并不断调试，让界面更加友好。
不断地尝试上，在各种问题上不断突破，慢慢的完善代码，等最大限度的满足用户需求。
目录1 概述 (2)1.1 问题描述 (2)1.2 实现意义 (2)2 系统分析 (2)2.1 需求分析 (2)2.1.1程序的功能 (2)2.1.2输入输出的要求 (2)2.2 设计思想 (2)2.3 设计要求 (3)3 概要设计 (3)3.1用邻接矩阵建立交通网络模块 (3)3.2 查询任意两个顶点之间的最短路径 (4)3.3 查询一个城市到其他所有城市的最短路径 (5)4 详细设计 (5)4.1 用邻接矩阵构造图结构函数CreateMGraph() (5)4.2 费洛伊德Floyd() (6)4.3 迪杰斯特拉Dijkstra() (6)4.4 主要函数流程图及其函数调用 (7)4.4.1 主要函数流程图 (7)4.4.2 一个城市到其他城市的路径调用 (8)4.4.3 任意两个城市之间路径调用 (8)5 运行与测试 (8)5.1 有向图存储结构的建立模块的输出 (9)5.2 单源路径迪杰斯特拉算法模块的输出 (10)5.3 费洛伊德算法模块的输出 (10)6 总结与心得 (10)参考文献 (11)附录 (11)1 概述1.1 问题描述在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差、旅游或做其它出行时，不仅关心节省费用，而且对里程和所需时间等问题也感兴趣。
对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。
图中顶点表示城市之间的交通关系。
这个交通系统可以回答旅客提出的各种问题。
比如任意一个城市到其他城市的最短路径，任意两个城市之间的最短路径问题。
1.2 实现意义便于人们的日常出行，且更好地满足了用户的出行需求。
这种最短路径问题的计算方法既简单又便于实现，同时大大提高了计算机的运行速率。
2 系统分析2.1 需求分析2.1.1程序的功能（1）用户自己可以建立不同的路径之间的关系网（2）可以查询某个城市到达其余各城市的最短路径。
（3）可以任一查询两个城市之间的最短路径。
2.1.2输入输出的要求在刚进入主界面后系统提示输入建立交通网络储存结构，输入顶点个数和和边数为整数不能输入其他字符，随后系统提示输入边与边之间的关系分别为i，j，w表示边之间的距离。
然后进入查询页面，输入整数1，2，0分别表示你所要查询的功能：一个城市至其他所有城市的最短路径查询、任意两个城市之间的最短路径查询、退出程序。
不能输入其他字符否则不能执行操作。
在整个操作都是用整数表示城市。
2.2 设计思想用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最短路径问题，然后运用费洛伊德算法实现图中任意一对顶点间最短路径问题，这样就会实现交通咨询系统设计的问题。
2.3 设计要求该交通咨询系统要完成城市网络图的存储，并要实现求任意一个城市顶点到其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的最短路径问题。
故设计要分成三部分，一是建立交通网络图的存储结构；二是解决单源路径问题；最后再实现两个城市之间的最短路径问题。
3 概要设计3.1用邻接矩阵建立交通网络模块\3-2-1 建立邻接矩阵注：用户构建交通网络时，输入顶点个数n，边数e。
然后在分别输入每个顶点i和j之间的距离w。
程序将自动根本用户所输入的构建邻接矩阵。
3.2 查询任意两个顶点之间的最短路径3-2-2 费洛伊德算法注：用户输入他所需要查询的城市的起点v和终点w，程序利用费洛伊德算法依次输出起点v到终点w所经过的顶点。
3.3 查询一个城市到其他所有城市的最短路径3-2-3 迪杰斯特拉算法注：用户输入他所需要查询的城市的起点v，程序将会调用迪杰斯特拉算法，用S保存经过的顶点，最终会输出用户所需要查询的顶点v到其他所有顶点的最短路径。
4 详细设计4.1 用邻接矩阵构造图结构函数CreateMGraph()其中vexs[MVNum]保存顶点信息，arcs[MVNum][MVNum]用于保存边与边之间的信息。
在构建时通过输入的边数i，j作为矩阵的行、列确定顶点的出度和入度。
用邻接矩阵方法存储图，很容易确定图的任意两个顶点是否是有边相连，因此用邻接矩阵对有利于后面费洛伊德算法和迪杰斯特拉算法。
数据类型定义：typedef struct{VertexType vexs[MVNum];Adjmatrix arcs[MVNum][MVNum];}MGraph;邻接矩阵的程序代码：for(k=1;k<=e;k++) //读入e条边建立邻接矩阵{ printf(" 第%d条边的信息:",k);scanf("%d,%d,%d",&i,&j,&w);G->arcs[i][j]=w;G->arcs[j][i]=w;}4.2 费洛伊德Floyd()费洛伊德算法对求任意两个顶点之间的路径较优。
用邻接矩阵保存图存储后，另外需要存一个二维数组A存放当前顶点之间的最短路径长度。
分量A[i][j]表示当前顶点i到j的最短路径长度。
费洛伊德算法的基本思维是递推产生一个矩阵序列A0，A1，A2，….Ak，…An，其中Ak[i][j]表示从顶点到vi到顶点vj 的路径上所经过的顶点编号不大于k的最短路径长度。
A[i][j]=cost[i][j]A(k+1)[i][j]=min{Ak[i][j],Ak[i+1][k+1]+Ak[k+1][j]}费洛伊德主要算法，若Ak[i][j]已求出，顶点i到顶点k+1的路径长度为Ak[i][k+1]，顶点路径长度为Ak[i][j]，顶点k+1到顶点j的路径长度为Ak[k+1][j]，如果此时Ak[i][k+1]+Ak[k+1][j]< Ak[i][j],则将原来的顶点i到顶点j的路径改为顶点，否则不需要修改顶点i到j的路径。
for(k=1;k<=n;k++){for(i=1;i<=n;i++)for(j=1;j<=n;j++){ if(D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j]; //修改长度P[i][j]=P[i][k];}}}4.3 迪杰斯特拉Dijkstra()迪杰斯特拉算法对求一个顶到到其他所有顶点的路径较优。
初始时，S中只包含原点，顶点v到自己的距离为0，D中包含出v外的其他顶点，v到D中顶点u的距离为边上的权值。
从D中选取一个顶点k，顶点v到顶点k的距离最小，然后把顶点k加入到S中，该选定的距离就是v到k的最短路径长度。
以顶点k为新考虑的中间点，修改顶点v到U中各顶点的距离，若从原点v到顶点u的距离比原来的距离（不经过k）的距离看，短，则修改顶点u的距离值，修改后的距离值为顶点v到顶点k的距离加上边<k,u>上的权。
迪杰斯特拉的算法：D2[v1]=0;S[v1]=1; //原点编号放入s中for(i=2;i<n;i++){ min=IDF;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){v=w;min=D2[w];}S[v]=1; //修改顶点u放入s中for(w=1;w<=n;w++)if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){D2[w]=D2[v]+G->arcs[v][w];P2[w]=v;}}4.4 主要函数流程图及其函数调用4.4.1 主要函数流程图4.4.2 一个城市到其他城市的路径调用4-5-2 调用dijkstra()4.4.3 任意两个城市之间路径调用4-5-3 调用floyd()5 运行与测试求有向图的最短路径：如图5 所示的有向图，求顶点a到其余顶点的最短路径；分别求顶点b到顶点d之间以及顶点a到顶点d的最短路径。
图5 一个有向图因为在算法中，为了操作简便，对于图的顶点都是用序号来表示的，所以顶点的字母就用其对应的序号来操作：a(1)、b(2)、c(3)、d(4)、e(5)、f(6)、g(7)。
5.1 有向图存储结构的建立模块的输出a db cegf5.2 单源路径迪杰斯特拉算法模块的输出5.3 费洛伊德算法模块的输出6 总结与心得在这次课设中，我学到很多。
通过这次课设不仅知道了如何用狄克斯特拉和费洛伊德这两种算法求最短路径，最重要的是通过这次课设我知道自己在c语言、数据结构上存在的不足之处，引起了我的重视。
以前总是依赖于书，在学算法时总，觉得了解了这个算法的基本功能就可以了，其实没有掌握类似于费洛伊德这些算法的运用，如何建立数组保存，如何输出等。
在写程序中我也遇到了许多错误，开始思维一直局限在该如何保存输入的信息以便于在费洛伊德算法中运用。
后来通过不断的修改程序定义数组保存顶点的点数和边数，建立邻接矩阵构成无向图。
在考虑求最短路径算法时，发现迪杰斯特拉和弗洛伊德各有各的优点，最后决定用迪杰斯特拉算法求一个城市到其他城市的最短路径算法，费洛伊德算任意两点之间的最短路径。
当然如果完全按照书上的程序去写的话仍然会很多的不足，所以在程序稍稍修改过后就可以正确运行了。
深知我们现在书上学的都只是皮毛，对以后真正从事开发研究的工作而言我们懂的实在是太少了，在以后的日子里我会好好学习C语言和数据结构。
程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。
在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到C语言，C++具有的语句简洁，使用灵活，执行效率高等特点。
参考文献[1] 数据结构课程设计苏仕华等编著机械工业出版社[2] 数据结构（C语言版）严蔚敏吴伟民编著清华大学出版社[3] C程序设计（第三版）谭浩强著清华大学出版社附录#include<stdio.h>#include<stdlib.h>#define MVNum 100 //最大顶点数#define Maxint 32767enum boolean{FALSE,TRUE};typedef char Vertextype;typedef int Adjmatrix;typedef struct{Vertextype vexs[MVNum]; //顶点数组类型假定为char型Adjmatrix arcs[MVNum] [MVNum]; // 邻接矩阵假定为int型}MGraph;int D1[MVNum], p1[MVNum];int D[MVNum][MVNum],p[MVNum][MVNum];//文件名save.cvoid CreateMGraph(MGraph *G,int n,int e){ //采用邻接矩阵表示法构造有向图G,n,e表示图的当前顶点数和边数int i,j,k,w;for(i=1;i<=n;i++) //输入顶点信息G->vexs[i]=(char)i;for(i=1;i<=n;i++)for(j=1;j<=n;j++)G->arcs[i][j]=Maxint; // 初始化邻接矩阵printf ("输入%d条边的i,j及w: \n",e);for(k=1;k<=e;k++){ //读入e条边,建立邻接矩阵scanf("%d,%d,%d",&i,&j,&w);G->arcs[i][j]=w;}printf ("有向图的存储结构建立完毕\n");}//文件名:dijkstra.c(迪杰斯特拉算法void Dijkstra(MGraph *G, int v1,int n){ //用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径p[v]及其权D[v] //设G是有向图的邻接矩阵若边<i,j>不存在则G[i][j]=Maxint//S[v]为真当且仅当v属于S及以求的从v1到v的最短路径int D2[MVNum], p2[MVNum];int v,i,w,min;enum boolean S[MVNum];for(v=1;v<=n;v++){ // 初始化S和DS[v]=FALSE; //置空最短路径终点集D2[v]=G->arcs[v1][v]; //置初始的最短路径值if(D2[v]< Maxint)p2[v]=v1; //v1是的前趋双亲elsep2[v]=0; //v 无前趋} // End_forD2[v1]=0;S[v1]=TRUE; //S集初始时只有源点源点到源点的距离为0//开始循环每次求的V1到某个V顶点的最短路径并加V到S集中 for(i=2;i<n;i++){ //其余n-1个顶点for(i=2;i<n;i++)min=Maxint; // 当前所知离v1顶点的最近距离设初值为∞for(w=1;w<=n;w++) //对所有顶点检查if(!S[w] && D2[w]<min){ //找离v1最近的顶点w并将其赋给v距离赋给minv=w; //在S集之外的离v1最近的顶点序号min=D2[w]; //最近的距离} //W顶点距离V1顶点更近S[v]=TRUE; //将v并入S集for(w=1;w<=n;w++) //更新当前最短路径及距离if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){ //修改D2[w]和p2[w]w 属于V-SD2[w]=D2[v]+G->arcs[v][w]; //更新D2[w]p2[w]=v;} //End_if} //End_forprintf ("路径长度路径\n");for(i=1;i<=n;i++){printf ("%5d", D2[i]);printf ("%5d", i);v=p2[i];while(v!=0) {printf ("<-%d", v);v=p2[v];}printf("\n");}}//文件名floyd.c(费洛伊德算法void Floyd(MGraph *G, int n){int i, j, k;for(i=1;i<=n;i++) //设置路径长度D和路径path初值for(j=1;j<=n;j++){if(G->arcs[i][j]!=Maxint)p[i][j]=j; //j是i的后继elsep[i][j]=0;D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++) {{ //做K次迭代每次均试图将顶点K扩充到当前求得的从i到j的最短路径pij for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j]; //修改长度p[i][j]=p[i][k];}}}}}void main(){MGraph * G;int n, e, v, w, k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph));printf("输入图中顶点个数和边数n,e: ");scanf("%d,%d", &n, &e);CreateMGraph(G, n, e); //建立图的存储结构while(xz!=0){printf("******求城市之间的最断路径******\n");printf("================================\n");printf("1.求一个城市到所有城市的最短路径\n");printf("2.求任意的两个城市之间的最短路径\n");printf("================================\n");printf(" 请选择 1 或2, 选择0 退出:");scanf("%d",&xz);if(xz==2){Floyd(G,n); //调用费洛伊德算法printf("输入起点和终点: v,w:");scanf("%d,%d",&v,&w );k=p[v][w]; //k为起点v的后继顶点if(k==0)printf("顶点%d 到%d 无路径! \n",v,w);else{printf("从顶点%d到%d的最短路径是: %d",v,w,v);}while(k!=w){printf("->%d",k); //输出后继顶点k=p[k][w]; //继续找下一个后继顶点 } }printf("->%d",w); // 输出终点wprintf(" 路径长度:%d\n",D[v][w]);}if(xz==1){printf("求单源路径输入起点v :");scanf("%d", &v);Dijkstra(G,v,n); //调用迪杰斯特拉算法}}printf("结束求最短路径再见\n");}。
