数据结构课程设计 答辩

数据结构课程设计之校园导航问题校园导航问题设计要求及问题描述设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。本课题实现校园多个场所（至少10个）的最短路径求解。设计内容概述（1）输入的形式和输入值的范围：本系统主要数据类型为字符型char及整形int,char型主要包括单位编号，单位名称，单位简介，功能编号；输入功能编号与单位编号进行操作。(2)输出的形式：输出则通过已有的信息数据，通过相关的操作输出相应信息。(3)程序所能达到的功能：本程序可供任何人使用，主要功能1.浏览各单位及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看某一单位信息。（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。内容涉及范围该数据结构课程设计为校园导航问题，那么就一定会涉及到路径问题，那么迪杰斯特拉算法和弗洛伊德算法是我们所必须会掌握的。同样，涉及到这两个算法，那么，设计图必然也是必不可少的.以下是我设计的我们学校的简略图：算法的思想迪杰斯特拉算法：　　按路径长度递增次序产生最短路径算法：　把V分成两组：　（1）S：已求出最短路径的顶点的集合　　（2）V-S=T：尚未确定最短路径的顶点集合　　将T中顶点按最短路径递增的次序加入到S中，　（1）从源点V0到S中各顶点的最短路径长度都不大于　　从V0到T中任何顶点的最短路径长度　　（2）每个顶点对应一个距离值　　S中顶点：从V0到此顶点的最短路径长度　　T中顶点：从V0到此顶点的只包括S中顶点作中间　　顶点的最短路径长度弗洛伊德算法：（1）利用二维数组A[1..n-1][1..n-1],A[i][j]记录当前vi到vj的最短路径长度，数组A的初值等于图的代权邻接矩阵;   （2）集合S记录当前允许的中间顶点，初值S=Φ;   （3）依次向S中加入v0,v1…vn-1，每加入一个顶点，对A[i][j]进行一次修正：设S={v0,v1…vk-1}，加入vk，则A(k)[i][j]=min{A(k-1)[i][j]，A(k-1)[i][k]+A(k-1)[k][j]}。A(k)[i][j]的含义：允许中间顶点的序号最大为k时从vi到vj的最短路径长度。   A(n-1)[i][j]就是vi到vj的最短路径长度。程序开始12345结束浏览景点及简介查看所有浏览路线有选择的查看路径有选择的查看景点