数据结构课程设计
实验报告
学
号：
姓
名：
提交日
期：
成
主界面：
1.浏览校园全景
2.查看各景点所有游览路线输入景点编号1：
输入顶点编号3：
3.选择出发点和目的地
输入出发点和目的地的编号分别是：2和8
输入出发点和目的地的编号分别是：1和9
4.查看景点信息
查看景点信息：1
查看景点信息4：
5.显示此图的邻接矩阵
6.退出系统
六、调试与分析
刚开始调试时出现很多错误，有些忘了写头文件，然后迅速从网上查到该词的头文件加在程序里。也有的函数忘记了提前声明导致了程序不能运行，以及其他各种问题。不过最后都能够通过各种途径调试出来，有查书的，也有向同学请教的。当程序能够正常运行出来时，界面显示也出现了很多问题。有的是因为少了换行符，导致界面排列不好。不过，最终都慢慢地改了过来。
七、心得与体会
经过两周的课程设计收获很多，在做课程设计之前，我觉得这是一项浩大的工程，总觉得自己会做不到。现在当我真的完成这个课程设计时，心里有一种成就感。这次课程设计，我学到了很多东西：学会了在编写几百行程序时如何查找错误，如何改错误；了解数据结构在编写比较复杂的程序的重要作用；对数据结构中定义无向图和创建无向图的理解更加深刻；最重要的是让我基本上明白了迪杰斯特拉算法和弗洛伊德算法。巩固和加深了对数据结构的理解，提高综合
重庆科技学院 课程设计报告 院（系）:_电气与信息工程学院专业班级:计科普0902 学生姓名:周杨学号: 2009441622 设计地点（单位）____计算机基础自主学习中心I306___ 设计题目:_________校园导游咨询____________________ 完成日期： 2011 年 1 月 14 日 指导教师评语: _______________________________________ ___________________________________________________________________________ ___________________________________________________________________________ ___________________________________________________ __________ _ 成绩（五级记分制）:______ __________ 指导教师（签字）:________ ________
重庆科技学院 课程设计任务书设计题目：校园导游咨询
教研室主任：指导教师：向毅、陈刘奎、熊茜 2010年 12 月 20日
摘要 现代快节奏的生活使得都市人越来越渴望亲近自然，因此外出旅游现在被越来越多的都市人所看中，所以如何快速方便的找到我们想要的旅游景点的信息和最短路径就成了一个很重要的问题。 本设计基于图的结构，创建一个无向图，针对游客的实际需求，将重庆科技学院的景点编号、名称、介绍等信息放入到图的顶点当中并保存在景点文本文件当中，将两个景点的编号和它们之间的距离当作权值也保存到权值文本文件当中，利用迪杰斯特拉算法来求从一个景点到另一个景点的最短距离，利用strcmp();函数来查找景点，并显示出它的信息，从而解决了要查找景点信息和景点之间的最短路径的问题，最后按照显示屏上的提示进行相关的操作。 关键词：无向图、查找信息、最短距离、校园导游咨询
校园导游系统设计与实现
目录 1.设计要求 2.1需求分析 2.2概要设计 2.3各个模块名称和功能 2.4 系统导游主界面 2.4.1前台系统 2.4.2后台系统 2.4.3退出系统 3实验总结 参考文献 附件
1.设计要求 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 2.1需求分析 ⑴设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图（无向网），所含景点不少于30 个。以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。 ⑵存放景点代号、名称、简介等信息供用户查询。 ⑶为来访客人提供图中任意景点相关信息的查询。 ⑷为来访客人提供图中任意景点之间的问路查询。 ⑸可以为校园平面图增加或删除景点或边，修改边上的权值等。 景点距离图 2.2概要设计
校园旅游模型是由景点和景点之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点，用图的边代表景点之间的路径。所以首先应设计一个图类。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度和最短路线时可用迪杰斯特拉（Dijkastra）算法实现。最后用switch 选择语句选择执行浏览景点信息或查询最短路径。 1、主界面设计 为了实现校园导游系统各功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本系统。 2、存储结构设计 本系统采用图结构类型（mgraph）存储抽象校园图的信息。其中，各景点间的邻接关系用图邻接矩阵类型（adjmatrix）存储；景点（顶点）信息用结构数组(vexs)存储，其中每个数组元素是一个结构变量，包含景点编号、景点名称及景点介绍三个分量；图的顶点个数及边的条数由分量vexnum、arcnum 表示，它们是整型数据。 3、系统功能设计 本系统除了要完成图的初始化功能外还设置了9个子功能。图的初始化由initgraph()函数实现。依据读入的图的顶点个数和边的条数，分别初始化图结构中图的顶点数组和图的邻接矩阵。9个子功能的设计描述如下。 ⑴景点信息查询 景点信息查询由函数seeabout()实现。该功能根据用户输入的景点编号输出该景点的相关信息。如景点编号、名称等。 ⑵学校景点介绍 学校景点介绍由函数browsecampus()实现。当用户选择该功能，系统即能输出学校全部景点的信息：包括景点编号、景点名称及景点介绍。 ⑶相邻的景点及其距离 为使游客能够知道其周围的景点和路径，方便他们迅速知道其所在位置和周围信息 ⑷查看浏览线路 查看浏览线路由函数shortestpath_dij()实现。该功能采用迪杰斯特拉(Dijkstra)算法实现。当用户选择该功能，系统能根据用户输入的起始景点编号，求出从该景点到其他景点的最短路径线路及距离。当用户选择该功能，系统能根据用户输入的起始景点及目的景点编号，查询任意两个景点之间的最短路径线路及距离。 ⑸更改图信息 修改一个已有景点的相关信息、删除一个景点及其相关信息、删除一条路径、加一条路径、修改路径长度、添加一个景点 ⑹数据安全防范 设置密码，能保证数据不会被随便更改，由pass()判定密码是否正确，可由changepw()函数修改密码，初始密码为gdufsx ⑺写入文件并保存修改 打开该软件，若没有graph.txt，则会由系统初始化生成一个graph.txt，若已存在该文档会由该文档中的内容初始化系统。 ⑻恢复初始状态 若数据已经显得很杂乱并很难修理，就可以启用这个功能
数据结构课程设计 设计题目：校园导游咨询 学院：信息学院 班级：计算机1008班 姓名： 学号： 20101221180 日期： 2012 年 3 月
校园导航问题 [问题描述] 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 [基本要求] （1）设计所在学校的校园平面图，所含景点不少于十个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。 （2）为来访客人提供图中任意景点相关信息的查询。 （3）为来访客人提供图中任意景点的问路查询，即查询任意两个顶点之间的一条最短的简单路径。 （4）校园导游图的景点和道路的修改扩充功能。 （5）扩充道路信息，如道路类别（车道、人行道），以致可按客人所需分别查询人行路径或车行路径。 （6）扩充每个景点的林洁景点的方向等信息，使得路径查询结果能提供详尽的导向信息。 （7）实现校园导游的仿真界面。
一、概要设计 (4) 二、详细设计 (6) 三、调试分析 (12) 四、调用关系 (12) 五、用户操作指南 (13)
[测试数据] 一、概要设计 1. 数据类型 #define V_MAX 20 #define E_MAX 200 typedef struct { char name[10];//名字 //char code[10];//代码 char info[20];//信息，简介 int x,y;//坐标 }VType;//顶点类型 typedef struct { int live;//标记是否存在，如果被删除则为0，存在为1 char name[10];// 路名 int length;//路的长度
一、课程设计题目：校园最短路径问题 二、课程设计目的： 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、问题描述 创建一个至少有15个点的无向网表示的某个旅游景点的导游图。顶点代表景点,类型为字符串（例如，泰山导游图：“天地广场门”，“十八盘”，“冯玉祥墓”，“桃花峪门”，“中天门”，“南天门”，“玉皇顶”等），弧表示两个景点之间可以直达，弧上的权值表示两个景点之间的路程（公里数），弧上还有到达方法的信息（有步行和索道两种）。建立一个游客咨询系统。 2、基本要求 a.创建图的存储结构。 b.输入两个景点名，就可以得到从一个景点到达另一个景点的所有简单路径、相应路径的路程公里数、行走的方法（每一段是步行，还是坐索道）。 c.输入两个景点名，就可以得到其最短路径，即：路程最短的行进方法；如果两者无路径可通，就得出“两景点不可达的信息”。 二、概要设计 1.数据结构 本程序需要用到两个结构体，分别为ArcCell和MGraph。 2.程序模块 本程序包含两个模块，一个是实现功能的函数的模块，另一个是主函数模块。
系统子程序及功能设计 本系统共有七个子程序，分别是： int LocateVex(MGraph G,VertexType u)//得到顶点u的序号 void CreateDN(MGraph *G)//建立景点间的无向网 VertexType* GetVex(MGraph G,int v)//根据顶点序号返回顶点值 int FirstAdjVex(MGraph G,VertexType v)//返回v的第一个邻接顶点的序号 int NextAdjVex(MGraph G,VertexType v,VertexType w)//返回v的(相对于w的)下一个邻接顶点的序号 void Simpleway(MGraph& m,char *str,char *buf)//求任意两个景点之间的所有简单路径 int Minway(MGraph& m,char *str,char *buf)//求两顶点间的最短路径 3.各模块之间的调用关系以及算法设计 函数CreateDN调用函数LocateVex 函数Simpleway调用函数LocateVex 函数Minway调用函数LocateVex，GetVex，FirstAdjVex，NextAdjVex 主函数调用函数CreateDN，Simpleway，Minway。 三、详细设计 1.数据类型定义 typedef struct { VRType adj; int info;
姓名： 班级： 学号： 指导教师： 2012年12月
目录 1、需求分析 (1) 1.1 系统简介 (1) 1.2 系统功能模块介绍 (1) 2、概要设计 (2) 2.1 系统功能结构图 (2) 2.2 系统流程图 (2) 2.3 主要函数概要设计 (3) 2.3.1 主函数概要设计 (3) 2.3.2 初始化图函数InitGraph() (4) 2.3.4 查询景点信息函数设计SearchGraph() (4) 2.3.5 显示图中信息函数设计ShowGraph() (4) 2.3.6 弗洛伊德算法函数设计Floyd() (5) 3、详细设计 (5) 3.1 主函数详细设计 (5) 3.2初始化图函数详细设计InitGraph() (6) 3.3查询景点信息函数详细设计SearchGraph() (7) 3.4 弗洛伊德算法函数详细设计Floyd() (8) 4、调试分析 (9) 4.1 显示主界面函数测试 (9) 4.2 查找两景点间最短路径测试 (10) 4.3 查看景点信息测试 (11) 5.课程设计总结 (12) 6、附录 (13)
1、需求分析 1.1 系统简介 随着现代社会生活节奏的加快，人们外出旅行以寻求放松的时间越来越多。考虑到游客不可能对所有景点都有所了解，因此可能无法找到游玩景点最省时，最高效的路径，而人工导游成本又过高，故使用C语言，基于《数据结构》中图的相关算法开发了“江西农业大学校园咨询系统”。 开发本系统目的在于为来访我校的游客提供一条最短游览路径，本系统从实际出发，通过对校园平面图的分析，将其转化为数据并保存在系统中，因此系统提供的路径具有较大的可信性。 本系统界面友好，提示信息充分，在实际使用过程中运行良好。 1.2 系统功能模块介绍 本系统主要分为以下三大功能模块： 1、查询两景点最短路径：用户在选择此功能模块后，按照屏幕上方提示的景点名称及其对应的编号，要求用户输入起点和终点的编号,系统将在已存储的景点中进行匹配，若未找到所需查询的景点编号，系统将提示错误并要求用户再次输入。若输入信息合法，则回车后系统将给出最短路径，显示于屏幕上方； 2、查询景点信息：用户在选择此功能模块后，按照屏幕上方提示的景点名称及其对应的编号，要求用户输入想要查询的景点的编
八年级数学最短路径问题 【问题概述】最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．算法具体的形式包括： ①确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题． ②确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题． ③确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径． ④全局最短路径问题 - 求图中所有的最短路径． 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查．
在直线l 上求一点P ，使PB PA -的值最大． 作直线AB ，与直线l 的交 点即为P ． 三角形任意两边之差小于 第三边．PB PA -≤AB ． PB PA -的最大值＝AB ． 【问题11】 作法 图形 原理 在直线l 上求一点P ，使PB PA -的值最大． 作B 关于l 的对称点B ＇作直线A B ＇，与l 交点即 为P ． 三角形任意两边之差小于 第三边．PB PA -≤AB ＇． PB PA -最大值＝AB ＇． 【问题12】“费马点” 作法 图形 原理 △ABC 中每一内角都小于120°，在△ABC 内求一点P ，使P A +PB +PC 值最小． 所求点为“费马点”，即满足∠APB ＝∠BPC ＝∠ APC ＝120°．以AB 、AC 为边向外作等边△ABD 、△ACE ，连CD 、BE 相交于P ，点P 即为所求． 两点之间线段最短． P A +PB +PC 最小值＝CD ． 【精品练习】 1．如图所示，正方形ABCD 的面积为12，△ABE 是等边三角形，点E 在正方形ABCD 内，在对角线AC 上有 一点P ，使PD +PE 的和最小，则这个最小值为（ ） A ．3 B ．26 C ．3 D 6 2．如图，在边长为2的菱形ABCD 中，∠ABC ＝60°，若将△ACD 绕点A 旋转，当AC ′、AD ′分别与BC 、CD 交于点E 、F ，则△CEF 的周长的最小值为（ ） A ．2 B ．32 C ．32+ D ．4 l B A l P A B l A B l B P A B' A B C P E D C B A A D E P B C
1.需求分析 1.1创建结点（旅游景点） 创建该旅游景点是在顺序表中完成的，在顺序表中，首先要创建结点结构体，将该结构体命名为SeqList，成员变量有数组list和size，分别用来表示最大元素个数（即旅游景点的最大个数）和顺序表中当前存储的数据元素个数，顺序表可以完成的功能有求当前数据元素个数，插入数据元素，删除数据元素，取数据元素。 1.2创建图 在构造图的操作中包括结点的插入（实参包括AdjMGraph *G，DataTyp v[],n,RowColWeight E[],e）分别表示在该*G的结构体中的SeqlistV ertices[]中插入结点，在*G的结构体中的edge[MaxV ertices][MaxV ertices]的边数组中插入边信息结点分别为行下标、列下标、权值，该*G的结构体中numOfEdges，e表示边的条数，即将e的值给它。结点的顺序表初始化，在该函数中也应包括一个结构体边信息结构体：成员包括行下标、列下标、权值。并将该结构体命名为RowColWeight。 1.3图的实现 在该函数中要使用SeqList头文件，在该文件中要真正进行插入边和结点。首先在该函数中应该定义一个结构体AdjMGraph，在该结构体的成员变量包括存放结点的顺序表定义为SeqlistV ertices[]、存放边的邻接矩阵用edge[MaxV ertices][MaxV ertices]表示，边的条数numOfEdges。初始化AdjMGraph 中的成员变量线性表和边数及存放边的邻接矩阵。然后在顺序表中插入结点，在邻接矩阵中插入边，删除边，删除结点。取序号为V的结点的第一个邻接结点，取序号为V1的邻接结点V2结点的下一个邻接结点 1.4求最短路径 在该函数中，应该有四个参数，两个位输入参数，分别为带权图G和源点（景点起点）序号v0，两个为输出参数，分别为distance[]和path[],distance[]用来存放达到的从源点v0到其余各结点的最短距离，path[]用来存放最短路径的下标。 1、从江西农业大学的平面地图中选取出6个有代表性的景点。 2、为来访的客人提供图中任意景点的路径查询，即查询任意两个景点之间的最短简单路径。当用户输入正确时，为用户输出任意两景点的最短路径；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。 3、为来访客人推荐参观最短路线。 2.概要设计 1．首先用邻接矩阵存储校园图。 2．用数据结构知识创建校园图。 3．手动给校园图赋上相关信息（景点名称、代号、简介），路径及路径长度。4．利用C语言知识编写查找景点相关信息的程序。 5．利用迪杰斯特拉算法计算任意两点之间的最短路径。 6．最后用一个主函数main输出各项结果。
石家庄经济学院 本科生课程设计报告书 题目校园导游咨询系统 姓名 学号 学院信息工程学院 专业计算机 指导教师 完成日期：2012年7 月5 日
校园导游咨询系统 1 需求分析 需要设计一个校园导游咨询系统，为来访的客人提供各种信息查询服务。 a)基本要求： 设计你所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放有景点名称、代号、简介等信息；以边表示路径， 存放路径长度等相关信息。 为来访客人提供图中任意景点相关信息的查询。 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 b)问题分析： 系统要处理的数据有字符型、字符串型、浮点型，如景点的代号使用字符类型、景点名称及简介等信息用字符串型、路径的长度用浮点型 等。它们之间存在并列、包含等关系，采用线性单链表、图的邻接矩阵 等数据结构来存储数据。 c)系统完成的功能： 来访客人浏览校园全景 查询相关景点的信息 可查询所有浏览路线 来访客人可以查询从某一景点到另一景点的最短路径； d)程序设计分析： 构造一个无向带权网G并用邻接矩阵来存储； 利用弗洛伊德算法来计算出起点到各个顶点之间的最短路径并进行存储，弗洛伊德算法将找出每一对顶点之间的最短路径； e)系统的输入与输出： 键盘输入，磁盘输入、输出等。 f)系统的操作用例： 学校北门（0）学生公寓（1）博物馆（2）惠馨园（3）操场（4）图书馆（5）校医院（6）主楼（7）教学楼（8）实验 楼（9） 校园平面图顶点代码以及各顶点之间的权值所构成的邻接矩阵：
校园北门 学生公寓 校医院博物馆 惠馨园操场 图书馆 教学楼 实验楼 主楼 树 校园平面图 0 1 2 3 4 5 6 7 8 9 0 0 100 200 400 1 0 300 2 0 100 3 0 100 200 4 0 300 250 5 0 350 6 0 50 200 7 0 50 8 0 20 9
9、校园导游咨询 问题描述： 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 基本要求： ⑴设计华东交通大学的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点， ⑵存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 ⑶为来访客人提供图中任意景点相关信息的查询。 ⑷为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 #include
1、需求分析 设计一个校园导游系统程序，为来访的客人提供各种服务的信息查询。 (1).设计工商学院校园无向图，所含的景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 (2).为来访客人提供图中任意景点相关信息的查询。 (3).为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 2、设计思路 校园旅游模型是由景点和景点之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点，用图的边代表景点之间的路径。所以首先应设计一个图类。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度和最短路线时可用弗洛伊德（Floyd）算法实现。最后用switch选择语句选择执行浏览景点信息或查询最短路径。 3 算法设计 3.1 概要设计 3.1.1 程序中包含的模块 （1）主程序模块 主函数：void main(void) void cmd(void) cmd修改显示框大小,字体背景颜色,初始化景点，景点信息 打印菜单， MGraph InitGraph(void); //初始化图。 MGraph * CreatUDN(MGraph *G);//初始化图形接受用户输入 void Menu(void);//菜单函数 void Browser(MGraph *G);//浏览函数 void ShortestPath_DIJ(MGraph *G); void Floyd(MGraph *G);//查询图中任意两个景点间的所有路径 void Search(MGraph *G);//查找函数 int LocateVex(MGraph *G,char*v); // 迪杰斯特拉算法计算起点各顶点间短
2009年西北民族大学本科生数学建模竞赛承诺书 我们仔细阅读了西北民族大学本科生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛的论文题目是：校园最短路径问题研究 校园最短路径问题研究 ——以西北民族大学榆中校区为例 摘要:本文以西北民族大学榆中校区为例，分析了其道路分布的特点，提出了如何选择最短路径的问题，并应用图与网络分析中的Dijskra算法和动态规划中的解决旅行售货员问题的方法，通过建立
合适的数学模型，并适当的应用matlab软件，给出了实际问题中的最短路径和最佳路线，为大家提供参考。建议在学习生活中选择合适的路线。 关键词：Dijskra算法最短路径旅行售货员 Abstract In this paper we use Northwest University for Nationalities YuZhong campus as an example, it analyzes the characteristics of the distribution of the road, and raise a question about how to choose the shortest path, and apply to Graph Theory and Network Analysis with Dijskra algorithm and Dynamic Programming in the Traveling Salesman Problem solving methods, through establish proper mathematical model, and appropriate application of matlab software, present a practical problem the shortest path and the best route, provide the reference for everyone. The suggestion is that we should choose the appropriate route in the study life . Key words: Dijskra algorithm the shortest path Traveling Salesman Problem 1、问题的提出 西北民族大学榆中校区是一个占地面积十分庞大的大学校园，由于其中仍有一些主体建筑正在建设过程中，导致校园内道路星罗棋布，错综复杂。而且，交通问题关乎到每一个民大人的出行等日常生活，因此，校园路径问题成为了一个很有必要进行研究的方向。
实验三：校园导游咨询 一、设计方案简介 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 1）设计你所在学校的校园平面图， 2）为来访客人提供图中任意景点相关信息的查询。 3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 二、设计题目实现: 实际需求 1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等相关信息。 2）为来访客人提供图中任意景点相关信息的查询。 3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 2）概要设计 1、校园全景一览图、显示出校园的平面图。 2、提供校园中任意景点问路查询，即求任意两个景点之间的所有路径。 3、提供校园图中多个景点的最佳访问路线查询，即求途径这过个景点的最佳（短）路径。 1．功能模块图； void Map();//校园地图 void CreateGraph();//创建图 void OutputPlace();//输出景点列表
void SearchPlace();//查询景点信息 void SearchPath();//查询最短路径 void Shortpath(int i);//计算最短路径 void Output(int sight1,int sight2);//输出函数 2．各个模块详细的功能描述。 Map();//显示校园整体的地图、包含学校各景点的详细位置 CreateGraph();//创建图、主要用来保存各景点信息 OutputPlace();//输出景点列表、供选择景点信息查询时使用 SearchPlace();//查询景点信息、景点的名称及介绍 SearchPath();//查询最短路径、两景点间最短距离 Shortpath(int i);//计算两景点间最短路径 Output(int sight1,int sight2);//输出两景点最短路径及信息 四．详细设计 1．功能函数的调用关系图 2．各功能函数的数据流程图 全局变量 Graph G; int path[NUM][NUM]; int D[NUM]; Main() CreateGraph() Map() SearchPlace() SearchPath() Outputplace() Shortpath(i); Output(i,j);
最短路径问题探究 一、教材分析与学情分析 1．教材分析 （1）教学内容 《最短路径问题探究》是九年级下为让学生能灵活的运用对称、平移解决近几年中考中常见的最短路径问题而设置的一节专题课． 初中三年，孩子们也具备了一定的学习能力，在老师的指导下，能针对某一问题展开讨论并归纳总结．但受年龄特征的影响，他们知识迁移能力不强，自主探究能力较差，不善于思考。所以本节课设计为通过对最短路径问题探究，在于引导学生学会思考，帮助学生掌握良好的学习方法为一节学法指导课 （2）地位和作用 近几年各地中考均有最短路径问题的考试，为让学生能熟练解决该类问题，本节课在已有平移、对称知识的基础上，引导学生探究如何运用平移、对称解决最短路径问题。它既是平移、对称知识运用的延续，又能培养学生自主探究，学会思考，在知识与能力转化上起到桥梁作用. 2．学情分析 （1）已有基础知识与生活经验分析 学生已掌握对称、平移、勾股定理等知识，但综合运用能力还较差。加之来自社会、家长和老师的压力较大，学生学的辛苦．对于学习方法不好的同学来说，感觉疲惫，无法体验学习的乐趣；从平时教学反映出学生不重视学习方法，不注意归纳总结，不会思考，更不善于思考，学生学得累。所以想通过本节课引导学生学会学习，学会思考，从而使其感受到学习的快乐，提高学习的兴趣，避免死做题，读死书，以达到提高学习能力的目的. （2）学生起点能力分析 学生已学过一些关于空间与图形的简单推理知识，具备了一定的合情推理能力，能应用勾股定理、线段公理等知识解决简单的问题，但演绎推理的意识和能力还有待加强，思维缺乏灵活性．综合运用能力较差，学习死，不能做到学习与研究相结合. 二、教学目标： 依据新课程标准的理念和学生实际情况，制定如下教学目标： ●知识与技能目标 1、结合具体实例，能灵活的运用勾股定理、线段公理解决实际问题 2、学会思考，逐步提高思维技能和思维的有效性，初步学会探究问题 ●方法与过程目标 1、经历问题的探究，学会从中提取有用信息，善于思考，善于提问，善于归纳总结，培养良好思维习惯． 2、经历运用已有的生活经验，已有的数学知识，培养思维能力、推理能力和有条理的表达能力 ●情感与态度目标
计算机科学与技术教研室 课程设计说明书（2014-2015学年第1学期） 注：成绩均用百分制。总成绩=平时成绩*20%+报告成绩*40%+演示与答辩成绩*40%
设计题目：校园附近门店服务查询系统 1、课程设计目的 （1）数据结构课程设计是综合运用数据结构课程中学到的几种典型数据结构，以及程序设计语言（C++语言），自行实现一个较为完整的应用系统。 （2）通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。 （3）学会将知识应用于实际的方法，提高分析和解决问题的能力，增加综合能力。 1）熟练掌握链表存储结构及其建立过程和常用操作； 2）学会自己调试程序的方法并掌握一定的技巧； 3）通过温习旧的知识，学习新知识，并提高分析和解决问题的能力。 2、课程设计正文 2.1概要设计 2.1.1 系统分析 该系统主要功能包括：增添服务信息、查询服务信息、修改服务信息、删除服务信息以及推荐路径等。 1.主程序模块：连接各种功能子模块，使用循环等待用户操作，完成程序的基本操作实现功能。 2.菜单显示模块：生成每个菜单的显示界面，使程序更简单清晰。 3.查询服务信息：用户在选择此功能模块后，按照屏幕上方提示的服务信息名称及其对应的编号，要求用户输入想要查询的服务信息的编号，回车后系统将在已存储的服务信息中进行匹配，若该景点信息尚未存储则将提示错误；若找到对应信息则系统将输出服务信息，显示于幕上方。 4.查询两服务信息最短路径：运用弗洛伊德算法，用户在选择此功能模块后，按照屏幕上方提示的服务信息名称及其对应的编号，要求用户输入起点和终点的编号,系统将在已存储的景点中进行匹配，若未找到所需查询的服务信息编号，系统将提示错误并要求用户再次输入。若输入信息合法，则回车后系统将给出最短路径，显示于屏幕上方。 5.删除服务信息：用户操作功能模块，由主程序直接调用的函数模块，将功能具象化，系统工具函数模块，先查找到所存在的服务信息，然后对用户希望删除的服务信息进行删除操作，若所要删除的服务信息不存在，则输出不存在此服务信息。
创作编号： GB8878185555334563BT9125XW 创作者：凤呜大王* 实验三：校园导游咨询 一、设计方案简介 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 1）设计你所在学校的校园平面图， 2）为来访客人提供图中任意景点相关信息的查询。 3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 二、设计题目实现: 实际需求 1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等相关信息。 2）为来访客人提供图中任意景点相关信息的查询。 3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 2）概要设计
1、校园全景一览图、显示出校园的平面图。 2、提供校园中任意景点问路查询，即求任意两个景点之间的所有路径。 3、提供校园图中多个景点的最佳访问路线查询，即求途径这过个景点的最佳（短）路径。 1．功能模块图； void Map();//校园地图 void CreateGraph();//创建图 void OutputPlace();//输出景点列表 void SearchPlace();//查询景点信息 void SearchPath();//查询最短路径 void Shortpath(int i);//计算最短路径 void Output(int sight1,int sight2);//输出函数 2．各个模块详细的功能描述。 Map();//显示校园整体的地图、包含学校各景点的详细位置CreateGraph();//创建图、主要用来保存各景点信息 OutputPlace();//输出景点列表、供选择景点信息查询时使用SearchPlace();//查询景点信息、景点的名称及介绍 SearchPath();//查询最短路径、两景点间最短距离 Shortpath(int i);//计算两景点间最短路径 Output(int sight1,int sight2);//输出两景点最短路径及信息 四．详细设计 1．功能函数的调用关系图 2012年01 月
13.4 课题学习最短路径问题 一、教学设计理念 最短路径问题在现实生活中经常遇到，初中阶段主要以“两点之间线段最短”、“连接直线外一点与直线上各点的所有线段中，垂线段最短”为知识基础，有时还要借助轴对称、平移、旋转等变化进行研究。 本节课以数学史中的两个经典问题——“将军饮马”“造桥选址”为载体展开对“最短路径问题”的课题研究，让学生经历将实际问题转化为数学问题，利用轴对称、平移等变化再把数学问题转化为线段和最小问题，并运用“两点之间线段最短”（或“三角形两边之和大于第三边”）解决问题，体现了数学化的过程和转化思想。 最短路径问题从本质上说是最值问题，作为初中生，此前很少在几何中接触最值问题，解决此类问题的数学经验尚显不足，特别是面对具有实际背景的最值问题，更会感到陌生，无从下手．解答“当点A、B在直线l的同侧时，如何在直线l上找到点C，使AC与CB 的和最小”，需要将其转化为“在直线l异侧两点的线段和最小值问题”，为什么需要这样转化、怎样通过轴对称、平移变化实现转化，一些学生在理解和操作上存在困难．在证明作法的合理性时，需要在直线上任取点(与所求作的点不重合)，证明所连线段和大于所求作的线段和，这种思路、方法，一些学生想不到．所以在课堂上特别对这几个问题进行了针对性的设计。 二、教学对象分析 八年级的学生已经学习研究过一些“两点之间，线段最短”、“垂线段最短”等问题。一直以来，学生对多媒体环境下的几何探究都十分感兴趣，有较强的好奇心，在学习上有较强的求知欲望，学习投入程度大。他们观察、操作、猜想能力较强，但演绎推理、归纳、运用数学意识的思想比较薄弱，思维的广阔性、敏捷性、灵活性比较欠缺，自主探究和合作学习能力也需要在课堂教学中进一步加强和引导。学生在数学问题的提出和解决上有一定的方法，但不够深入和全面，需要教师的引导和帮助，学生本身具有一定的探究精神和合作意识，能在亲身的经历体验中获取一定的数学新知识，但在数学的说理上还不规范，几何演绎推理能力有待加强。(1)最短路径问题从本质上说是最值问题，作为初中生，此前很少在几何中接触最值问题，解决此类问题的数学经验尚显不足，特别是面对具有实际背景的最值问题，更会感到陌生，无从下手。(2)解答“当点A、B在直线l的同侧时，如何在直线l上找到点C，使AC与CB的和最小”，需要将其转化为“在直线l异侧两点的线段和最小值问题”，为什么需要这样转化、怎样通过轴对称、平移变化实现转化，一些学生在理解和操作上存在困难。(3)在证明作法的合理性时，需要在直线上任取点(与所求作的点不重合)。证明所连线段和大于所求作的线段和，这种思路、方法，一些学生会想不到。 三、教学目标 1、了解解决最短路径问题的基本策略和基本原理。 2、能将实际问题中的“地点”“河”“桥”等抽象为数学中的“点”“线”，使实际问题数学化。 3、能运用轴对称、平移变化解决简单的最短路径问题，体会几何变化在解决最值问题中的重要作用。 4、在探索最短路径的过程中，感悟、运用转化思想。进一步培养好奇心和探究心理，更进一步体会到数学知识在生活中的应用。 四，教学重点
#include
G.vexnum=10; G.arcnum=10; for(i=0;i
相关主题
文本预览