数据结构课程设计 海南大学09通信 辛

《数据结构课程设计 海南大学09通信 辛》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录一、设计目的1二、设计任务1三、总体设计1四、详细设计34.1抽象数据类型34.2存储结构34.3主模块4五、Floyd算法55.1Floyd算法基本思想55.2Floyd算法的基本步骤6六、程序代码9七、程序测试与结果9八、心得体会16参考文献18附录1822一、设计目的（1）巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。（2）了解程序模块化的过程。（3）根据有向图的存储结构解决实际问题。（4）充分了解并掌握最短路径问题及其应用。学习迪杰斯特拉算法和弗洛伊德算法。（5）给用户提供路径咨询。实现了帮助用户了解全国各大城市间往来的最短路径费用问题。（6）可

2、以提供用户查询各大城市的相关信息。二、设计任务设计一个火车费用咨询系统，能让旅客在任一个城市顶点到另一个城市顶点之间的最短路径（里程）或最低花费等问题。（城市名称用数字代替）。同时要方便管理人员进行操作。本程序可以在TC2.0和VC6.0中运行。三、总体设计本程序页面清晰，功能明确，主要分为两个部分，即交通查询部分和管理员管理部分。交通查询部分又分为城市信息、城市路径、最短路径查询3个模块，而其中最短路径查询系统即为2个城市之间的最短路径。而管理员管理的部分则包括交通查询里面的功能以及添加城市、添加城市间的路径、删除城市以及删除两个城市之间的路径等部分。22总体设计框图如下图

3、（1）所示：火车费用资讯系统用户资讯平台显示相关城市信息显示路径和火车费用寻找最省钱路径狄克斯特拉算法（待解决）弗洛伊德算法弗洛伊德表格两个城市间的最短路径费用指定城市到其他所有城市的最短路径费用管理操作平台显示城市相关信息显示城市间路径和火车费用添加城市信息添加城市路径删除城市路径删除城市信息寻找最省钱路径自动保存图（1）车费资讯系统总体设计图22四、详细设计4.1抽象数据类型本程序运用了关于数组和图这种数据结构。4.2存储结构structcity_info/*城市信息结构*/{charname[20]；charinfo[100]；}cities[SIZE_city]；st

4、ructway_info/*路径信息结构*/{intstart_id；intend_id；intdist；}ways[SIZE_way]；structpath_info/*路径查询结构*/{intcount；intpath[SIZE_city]；}；22typedefstructGraph{charvexs[SIZE_city]；/*顶点*/intarcs[SIZE_city][SIZE_city]；/*邻接矩阵*/intvexnum；/*顶点数*/intarcnum；/*弧数*/}Graph；4.3主模块划分本程序采用自顶向下的编程模式，分为7个主模块，即考虑到7种算法的实

5、现：1、显示全国各地城市相关信息的算法：voidShowCity()的初始条件：voidReadCitiesFile()；voidReadWaysFile()；读取数据成功，操作结果：根据用户查询城市的名字，输出城市的特色；2、添加城市及城市相关信息的算法； voidAddCity()的初始条件：构造了结构体数组views[VIEW_SIZE]；操作结果：添加一个城市顶点到views数组中，并将数据输出到VIEWS文件中保存。3、删除一个城市的算法： voidDelCity();  初始条件：存在views[VIEW_SIZE]；操作结果：从views数组中删除一个城市顶点，

6、并重新将数组中数据输出到CITYS文件中保存。 4、是查询城市之间的路径的算法；22voidShowWay();初始条件：构造了结构体数组ways[WAY_SIZE];操作结果：添加一个城市顶点到ways数组中，并将数据输出到WAYS文件中保存。                               5、添加城市之间的路径的算法：voidAddWay（）的初始条件：构造了结构体数组ways[VIEW_SIZE]；操作结果：添加一条城市间的路径到ways数组中，并将数据输出到WAYS文件中保存。6、删除城市间的路径的算法； voidDelWay();初始条件：存在ways

7、[VIEW_SIZE]；操作结果：从ways数组中删除一个城市顶点，并重新将数组中数据输出到WAYS文件中保存。7、查询两个城市间最省路径的算法voidSearchWay()；初始条件：存在城市信息及路径的存储结构操作结果：根据用户输入，输出两个城市间的最短路径五、Floyd算法5.1Floyd算法基本思想Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。从邻接矩阵a开始进行n次迭代，第一次迭代后a[i,j]的值是从vi到vj且中间不经过变化大于1的顶点的最短路