数据结构,课程设计,校园最短路径问题.docx
16页
一、课程设计题目： 校园最短路径问题二、课程设计目的：1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2,初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法 和技能；3 .提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4 .训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所具 备的科学工作方法和作风三、课程设计要求：1,设计的题目要求达到一定的工作量（300行以上代码），并具有一定的深度和 难度2,编写出课程设计报告书，内容不少于 10页（代码不算）四、需求分析1、问题描述图的最短路径问题是指从指定的某一点 v开始，求得从该地点到图中其它各 地点的最短路径，并且给出求得的最短路径的长度及途径的地点 除了完成最短 路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等校园最短路径问题中的数据元素有：a） 顶点数b） 边数c） 边的长度2、功能需求要求完成以下功能：a）输出顶点信息：将校园内各位置输出b）输出边的信息：将校园内每两个位置（若两个位置之间有直接路径）的 距离输出c）修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输 出每两个位置（若两个位置之间有直接路径）的距离。
d）求最短路径：输出给定两点之间的最短路径的长度及途径的地点或输出 任意一点与其它各点的最短路径e）删除：删除任意一条边f）插入：插入任意一条边3、实现要点a） 对图的创建采用邻接矩阵的存储结构，而且对图的操作设计成了模板类为了便于处理，对于图中的每一个顶点和每一条边都设置了初值b） 为了便于访问，用户可以先输出所有的地点和距离c） 用户可以随意修改两点之间好的距离d） 用户可以增加及删除边e） 当用户操作错误时，系统会出现出错提示五、概要设计:1 .抽象数据类型图的定义如下：ADT Graph{数据对象V: V是具有相同特性数据元素的集合，称为顶点集数据关系R：R={VR}VR={ (v, w) | v , w C V, (v , w) 表示v和w之间存在路径}基本操作P:CreatGraph(&G, V, VR)初始条件：V是图的顶点集，VR是图中边的集合操作结果：按定义(V, VR)构造图GDestroyGraph(&G)初始条件：图G已存在操作结果：销毁图LocateVex(G, u)初始条件：图G存在，u和G中顶点具有相同特征操作结果：若G中存在顶点u,则返回该顶点在图中“位置” ；否则返回其它信息。
GetVex(G, v)初始条件：图G存在，v是G中某个顶点操作结果：返回v的信息InsertVex(&G, v)初始条件：图G存在，v和G中顶点具有相同特征操作结果：在图G中增添新顶点vDeleteVex(&G, v)初始条件：图G存在，v和G中顶点具有相同特征操作结果：删除G中顶点v及其相关的边InsertArc(&G, v, w)初始条件：图G存在，v和w是G中两个顶点操作结果： 在G中增添弧＜v,w＞，若G是无向的，则还增添对称弧＜w,v＞ DeleteArc(&G, v, w)初始条件：图G存在，v和w是G中两个顶点操作结果： 在G中删除弧＜v,w＞，若G是无向的，则还删除对称弧＜w,v＞} ADT Graph2 .主程序void main(){初始化；while( “命令”！= “退出”){Switch语句接受命令(输入选择项序号)；处理命令；}}3,本程序运用函数的调用，只有两个模块，它们的调用关系为: 主程序模块带权无向图模块六、详细设计(详细见下面的源代码)typedef struct //void Menu() //void PutOutVex(MGraph *G) //void PutOutArc(MGraph *G) //void Dijkstra(MGraph * G) //void DeleteVex(MGraph *G) //void DeleteArc(MGraph *G) //void InsertArc(MGraph *G) //void main() //七、源程序代码 #include
