校园导游程序报告.doc

校园导游程序报告 问题分析和任务定义 题目与要求 校园导游程序题目：用无向网表示你所在学校的校园景点平面图，图中定点表示主要景点，存放 景点的编号、名称、简介等信息。要求能够回答有关景点介绍、游览路经等问题。 要求：(1)查询各景点相关信息； (2)查询图中任意两个景点的最短路径。 (3)查询图中任意两个景点的所有路径。. 选作内容：求多个景点的最佳游览路经。 根据设计的基本要求，可知本系统应实现以下几个功能： (1)景点查询：景点查询，输出所查询景点的相关信息 (2)景点之间最佳路径查询功能：输出所选择的两点之间的最短路径及路径长度。 (3)两景点间所有路径：输出两点间存在的所有路径。 问题分析 确定以无向图为数据结构的校园地图如图1： 图1校园地图 图的信息以邻接矩阵形式存储，邻接矩阵以二维数组的数据结构存储。cost[i][j]； 当i=j时及i点与j点无直接连通时，其值为无穷大，定义一个很大的整数Maxint代替无穷大。当i与j点邻接时，其值为两点间的权值即两景点距离。 （1）、查询景点信息 将相应景点信息存入文本文档中，依据需要调用读取文件，并显示在屏幕上。 （2）、两点间最短路径 利用迪杰斯特拉（Dirjstra）算法求两点之间最短路径。 （3）、两点间所有路径 利用邻接矩阵转换为邻接表，以邻接表的遍历查找路径，并将路径暂时存储，最后一次将各路径输出。 任务定义 设计creat （）；函数存入图的矩阵信息。 设计infor （）；函数查询景点信息。 设计DJ_shortestpath （）；函数利用迪杰斯特拉算法求最短路径。 设计Allpath （）；函数求两点间所有路径。 程序实现功能 查询某景点信息。 查找两景点间最短路径。 查找两景点间所有路径。 数据结构的选择和概要设计 数据结构的定义 图的定义： 图的信息以邻接矩阵存储，利用二维数组作为矩阵坐标，二维数组的值表示图的两点间的距离，即无向图的权值，若两点间无直接路径，则以无穷大为权值。 景点相关信息： 景点相关信息以文本文档存储，利用函数直接读取文本输出。 景点名称输出 以结构体存储各个景点编号及相对的名称，以便于输出显示。 struct PlaceName { char name[10]; }Place[11]; 概要设计 主函数：调用各子函数完成选择功能。 主函数中以switch语句选择操作。 查询景点信息——1 查找路径——2 查找所有路径——3 退出程序——4 程序框架图如图2 图2程序框架图 详细设计和编码 迪杰斯特拉算法核心思想： 把图的顶点集合V分成两个子集，第一个子集包含已确定了最短路径的顶点，令其为S，第二个子集（V-S）包含尚未确定最短路径的顶点。按最短路径长度递增的顺序逐个把V-S中的顶点加到S中去，直至从v出发可以到达的所有顶点都包含在S中。在这个过程中，总保持从v到S中各顶点的最短路径的长度都不大于从v到V-S中的任何顶点的最短路径的长度。另外，每个顶点对应一个距离值，S中的定点的距离值就是从v到此顶点的最短路径的长度，V-S中的顶点的距离值是从v到此顶点的只包括S中的顶点的最短路径长度。当然，每当把一个顶点从V-S移到S中去后，必须对V-S中剩余的顶点的距离值进行调整。 算法步骤如下： 初始时，S只包括顶点v，即S={ v }，V-S包括其他所有顶点，v的距离值为0，V-S中的顶点的距离值是这样确定的：对V-S中的任意顶点w，若图中有边v，w，则w的距离为此边上的权值，否则w的距离值为∞（或用一个很大的数表示，程序中用Maxint=9999表示）。 然后从V-S中选择一个距离值最小的顶点k加入到S中去，此时k的距离值恰好就是从v到它的最短路径的长度。 S中加入一个顶点k后，对V-S中的各个顶点的距离值进行一次修正。对V-S中的任意顶点w，若k的距离值加上边k，w上的权值小于w的原距离值，则将w的距离值调整为k的距离值与边k，w上的权值之和，否则w的距离值保持不变。 重复步骤②和③，知道所有顶点都已包括在S中为止，即知道S=V为止。 在函数 DJ_shortestpath （）；中实现了迪杰斯特拉算法。 图的大家邻接矩阵存储在二维数组cost[][]中，数组dist[]存放各顶点的当前距离值。程序中用Maxint=9999表示∞。数组path[]存放各定点在最短路径中的直接前驱。算法执行完毕后，dist[]中的值即为最短路径的长度，最短路径可以从path[]求得。数组dianji[]记录了顶点是否在S中，dianji[i]=1表示顶点i在S中，dianji[i]=