校园导游程序报告

《校园导游程序报告》由会员分享，可在线阅读，更多相关《校园导游程序报告（16页珍藏版）》请在金锄头文库上搜索。

1、校园导游程序报告 一、 问题分析和任务定义 1、题目与要求校园导游程序题目：用无向网表示你所在学校的校园景点平面图，图中定点表示主要 景点，存放 景点的编号、名称、简介等信息。要求能够回答有关景点介绍、游览路经等问题。 要求：(1)查询各景点相关信息；(2)查询图中任意两个景点的最短路径。(3)查询图中任意两个景点的所有路径。. 选作内容：求多个景点的最佳游览路经。 根据设计的基本要求，可知本系统应实现以下几个功能：(1)景点查询：景点查询，输出所查询景点的相关信息(2)景点之间最佳路径查询功能：输出所选择的两点之间的最短路径及路径长度。 (3)两景点间所有路径：输出两点间存在的所有路径。 2

2、、问题分析 确定以无向图为数据结构的校园地图如图1： 南校门 1 行政楼 2 礼 堂 6 东 校 门 3 主教学区 4 图书馆 5 食 堂 8 宿 舍 区 9 荷 塘 10 图1校园地图 图的信息以邻接矩阵形式存储，邻接矩阵以二维数组的数据结构存储。costij；当i=j时及i点与j点无直接连通时，其值为无穷大，定义一个很大的整数Maxint代替 无穷大。当i与j点邻接时，其值为两点间的权值即两景点距离。 体 育 场 7（1） 、查询景点信息将相应景点信息存入文本文档中，依据需要调用读取文件，并显示在屏幕上。 （2） 、两点间最短路径利用迪杰斯特拉（Dirjstra）算法求两点之间最短路径。

3、（3） 、两点间所有路径利用邻接矩阵转换为邻接表，以邻接表的遍历查找路径，并将路径暂时存储，最后一 次将各路径输出。 3、任务定义 设计creat （） ；函数存入图的矩阵信息。 设计infor （） ；函数查询景点信息。 设计DJ_shortestpath （） ；函数利用迪杰斯特拉算法求最短路径。 设计Allpath （） ；函数求两点间所有路径。 4、程序实现功能 查询某景点信息。 查找两景点间最短路径。 查找两景点间所有路径。 二、 数据结构的选择和概要设计 1、数据结构的定义 图的定义： 图的信息以邻接矩阵存储，利用二维数组作为矩阵坐标，二维数组的值表示图的 两点间的距离，即无向图的

4、权值，若两点间无直接路径，则以无穷大为权值。景点相关信息：景点相关信息以文本文档存储，利用函数直接读取文本输出。景点名称输出以结构体存储各个景点编号及相对的名称，以便于输出显示。struct PlaceName char name10;Place11; 2、概要设计 主函数：调用各子函数完成选择功能。主函数中以switch语句选择操作。 查询景点信息1 查找路径2 查找所有路径3 退出程序4程序框架图如图2主函数 Dirjstra 算法最 短路径 邻接矩 阵转换 邻接表 创建图 输入临 接矩阵 遍历输 出所有 路径 查询景 点相关 信息 图2程序框架图 三、 详细设计和编码 迪杰斯特拉算法核心

5、思想： 把图的顶点集合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中剩余的顶点的距离值进 行调整。 算法步骤如下

6、： 初始时，S只包括顶点v，即S= v ，V-S包括其他所有顶点，v的距离值为 0，V-S中的顶点的距离值是这样确定的：对V-S中的任意顶点w，若图中有边 ，则w的距离为此边上的权值，否则w的距离值为（或用一个很大的 数表示，程序中用Maxint=9999表示） 。 然后从V-S中选择一个距离值最小的顶点k加入到S中去，此时k的距离值恰 好就是从v到它的最短路径的长度。 S中加入一个顶点k后，对V-S中的各个顶点的距离值进行一次修正。对V-S 中的任意顶点w，若k的距离值加上边上的权值小于w的原距离值，则 将w的距离值调整为k的距离值与边上的权值之和，否则w的距离值保 持不变。 重复步骤和，知

7、道所有顶点都已包括在S中为止，即知道S=V为止。 在函数 DJ_shortestpath （） ；中实现了迪杰斯特拉算法。图的大家邻接矩阵存储在二维数组cost中，数组dist存放各顶点的当前距离值。 程序中用Maxint=9999表示。数组path存放各定点在最短路径中的直接前驱。算 法执行完毕后，dist中的值即为最短路径的长度，最短路径可以从path求得。数 组dianji记录了顶点是否在S中，dianjii=1表示顶点i在S中，dianjii=0表 示顶点i不在S中。输出最短路径：由path中的各定点的直接前驱倒序遍历最短路径并存入临时数组 temp中，然后倒序输出temp并以temp

8、的值为下标调用景点名称数组Place以 直接显示景点名称（将景点编号转换为字符名称输出） 。dist中的值为两景点最短路 径的路径长度。景点信息查询：将景点信息预先写入文本文档A1.txt A10.txt中，输入要查询的景点标号x。switch （x）case 1： 读取A1.txt中信息； case 2： 读取A2.txt中信息； case 3： 读取A3.txt中信息； case 4： 读取A4.txt中信息； case 5： 读取A5.txt中信息； case 6： 读取A6.txt中信息； case 7： 读取A7.txt中信息； case 8： 读取A8.txt中信息； case 9

9、： 读取A9.txt中信息； case 10： 读取A10.txt中信息； 各文件内容如下图图3各文件内容 两点间所有路径：定义临时存储用栈。 邻接矩阵转换为邻接表。对邻接矩阵进行遍历，将遍历路径存入栈中。输出栈中元素。回溯再遍历。直到完全遍历整个邻接表。 四、 上机调试 首先遇到的难题是图的定义，对于本程序，常规的图的创建已经不利于算法的优化，经过 考虑，最后决定定义全局变量二维数组，直接存储图的邻接矩阵。 其次，从未接触过的迪杰斯特拉算法让我开始时手足无措，去图书馆借了资料从头学习了 迪杰斯特拉算法的核心思想，并对书本的案例程序进行了分块结构化，最后确定的迪杰斯 特拉算法的具体实现方法。

10、对于景点查询一块，本来想法是将景点相关信息存入图的顶点信息结构体中，后来发现这 样会将图信息的初始化复杂化，后来决定将相关信息写入文本文档，利用函数调用读取文 件信息完成景点查询。 最难的就是所有路径问题，在经过一本一本书的搜索淘汰，一个网页一个网页的搜索淘汰， 最后在同学的帮助下完成了算法，但是觉得这个算法太复杂，应该有更好的，却觉得已经 力不从心了。 经常出现的错误： 初始化函数creat （） ；未调用，使得邻接矩阵无数据，最后无运算结果输出。对文件的读取格式不规范，显示的只是文件的片段或乱码。输出路径的临时存储数组的输出接点起始错误，逆序的初始状态为非空结点的最大下标 开始至0结束，下

11、标变量i不能再次被赋值，否则会出错。 程序中存在的问题：程序部分算法扔有待改进优化。在路径的输出结果中会出现错误输出。若两点间有两条长度相同的路径，且为最短路径，程序只能输出其中之一。 经验体会相对于其他同学的课程设计题目，这个题目的难度高了很多，同样含金量也很高，思 索，写代码，画算法，改错，删除、删除、再删除，难题接踵而至，未遇到的算法，未曾 想过的问题都出现了。两个星期做一个程序还未能尽善尽美的完成它，让我深感对数据结 构一门课程学习的不足。也让我对课程设计这门课有了新的认识。 数据结构刚开始时老师说，我教给你们的不是编程。当初想，这整本书都是说编程的， 怎么会“不是编程”？现在明白了算

12、法一词的重要性，编程的核心是算法的掌握。以前的 程序语言的学习只是像学外语学了单词一样，会使用了编程的工具，认识了编程的单词， 真正的编程是算法的学习，就像是外语的语法的掌握一样重要。 这个程序所涉及的图的知识及迪杰斯特拉算法等知识均是离散数学和图论等数学课程 中的知识，对数学知识的学习不足，接触不深，部分数学知识未学习的我难度又加大了一 层，使得行动步步都捉襟见肘。 知识的学习和应用不是专业局限性的，知识之间是广泛联系的，数学与计算机专业知 识之间的联系异常紧密。 五、 测试结果及其分析 1、主函数及主菜单的输出 图4 2、查询景点信息 选择测试数据景点编号5。测试结果如下3、查找最短路径

13、测试数据 南校门至体育场路径 结果如下： 图5 4、查找所有路径 测试数据 行政楼至主教学区 结果如下 （为完全显示） 图6 5、结束程序 结果如下图7 六、 用户使用说明 1、主菜单界面 程序运行进入主菜单 可以看到选择操作菜单如下图 图8 2、由菜单显示信息选择相应操作 （1） 、选择1，查询景点信息输入景点编号。程序输出景点相关信息。 （2） 、选择2，查找两点间最短路径按提示依次输入起点景点编号及终点景点编号。程序输出建议路径即为两点间最短路径。 （3） 、选择3，查找所有路径按提示输入查找的两点。程序输出两点间所有路径。 （4） 、选择4，退出程序程序循环运行结束。若不选择4操作，程

14、序将继续等待操作选择不结束。 3、程序编译环境为Microsoft Visual C+ 6.0。 七、 参考文献：1、谭浩强.C 程序设计(第三版).北京：清华大学出版社，2005 年 7月 2、王昆仑。数据结构与算法。北京：中国铁道出版社，2007年6月第1版 3、章炯民，窦亮，黄国兴。数据结构与算法教程。上海：华东师范大学出版社， 2007年7月第1版 4、侯风巍。数据结构要点分析 C 语言版。北京：北京航空航天大学出版社，2007 年 3 月 第 1 版 八、 附录 源程序代码：/ *校园导游程序 #include #include #include #include #define M

15、axn 20 #define Maxint 999 int pathMaxnMaxn; int n=10; /顶点数 int e=13; /边数 int costMaxnMaxn; /邻接矩阵 struct PlaceName char name10;Place11; struct PlaceName Place11= “, “南校门“, “行政楼“, “东校门“, “主教学区“, “图书馆“, “礼堂“, “体育场“, “食堂“, “宿舍区“, “荷塘“, ; /景点名结构数组 void *creat() /输入邻接矩阵 int i,j;for (i=1;i=n;i+)for (j=1;j=n;j+) costij=Maxint; /置空邻接表 cost12=cost21=5; cost13=cost31=10; cost14=cost41=5; cost26=cost62=2; cost34=cost43=4; cost37=cost73=7; cost45=cost54=2; cost410=cost104=3; cost56=cost65=3; cost59=cost95=8; cost69=cost96=5; cost78=cost87=2; cost89