数据结构报告 校园导航问题

数据结构试验报告校园导游《数据结构》课程设计报告课程名称：《数据结构课程设计》；课程设计题⽬：校园导游查询；姓名：张晓艺；院系：计算机学院；专业：数字媒体技术；年级：⼤⼆；学号：10054220；指导教师：王⽴波；2011年12⽉17⽇1 课程设计的⽬的 (x)2 需求分析 (x)3 课程设计报告内容 (x)1、概要设计 (x)2、详细设计 (x)3、调试分析 (x)4、⽤户⼿册 (x)5、测试结果 (x)6、程序清单 (x)4 ⼩结 (x)5 参考⽂献 (x)1.课程设计的⽬的：（1）熟练运⽤C++编写程序；（2）会⽤Floyd算法查找最短路径；2.需求分析：1.题⽬：【校园导游咨询】[问题描述]（1）设计你的学校的校园平⾯图，所含景点不少于10个。

以图中顶点表⽰学校各景点，存放景点名称、代号、简介等信息；以边表⽰路径，存放路径长度等相关信息。

（2）为来访客⼈提供图中任意景点的问路查询，即查询任意两个景点之间的⼀条最短的简单路径。

（3）为来访客⼈提供图中任意景点相关信息的查询。

[测试数据]由读者根据实际情况指定。

2.任务：通过此程序可实现以下功能：（1）⽤⼀维数组存放景点信息，⼆维数组存放景点间的距离，最短距离，最短路径；（2）Floyd算法计算最短距离和路径；（3）根据景点序号查询景点的⼀系列信息，及两景点间的最短路径和最短距离。

3.测试数据:查询类型：I（表⽰查询景点信息）；景点编号：3；查询类型：D（表⽰查询景点间的最短路径和最短距离）；景点编号：1 9；3. 课程设计报告内容：1. 概要设计：（1）⾸先我画了学校主要⼏个景点的分布图以及⾃⼰定的⼀些距离，图如下：（2）接着我定义了⼀个顶点结构体，定义如下：struct Date{int num; //景点编号char name[50]; //景点名称char introduce[100]; //景点介绍};（3）然后我定义了⼀个类，定义如下：class Travel{private:Date date[15];int distance[15][15];int Path[15][15];int ShortestDistance[15][15];void Floyd();public:Travel();~Travel(){}void Introduce(int);void Scanf();void ShortDistance(int,int);};（4）基本操作：void Floyd(); //Floyd算法，计算最短路径和最短距离Travel(); //构造函数~Travel(){} //析构函数void Introduce(int); //介绍景点函数void Scanf(); //外部输⼊函数void ShortDistance(int,int); //最短距离计算函数本程序分为2个模块：Int main(){初始化；Void Scanf();}函数调⽤关系基本结构图如下所⽰：2. 详细设计：（1）主函数初始化变量；（2）调⽤外部接⼝函数Scanf()；（3）输⼊查询类型，如果为“I”，调⽤景点介绍函数，如果为“D”，调⽤最短距离和路径函数。

数据结构与算法分析课程设计报告设计题目：校园导航咨询系统专业学号姓名2013 年3 月3 日一、问题描述设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）（参考课本P186-P192）。

二、需求分析本程序分为五个模块，分别是显示校园全景、查询景点信息、问路查询系统、查看游览路线和退出系统。

（1）显示校园全景展示校园概貌图和各景点编号、名称。

（2）查询景点信息输入要查询的景点编号，显示景点的编号、名称和景点的简单介绍。

（3）问路查询系统输入要参观的两个景点的编号（按从大到小输入），显示两个景点间的最短路径游览方式和最短路径长。

（4）查看游览路线查询某个景点到其他景点的所有路径，并显示其长度。

（5）退出系统查询完毕关闭窗口，显示退出系统的界面三、概要设计1、主要函数：void main() 主函数，程序入口csinfo() 初始化景点信息csroad() 初始化道路信息showpath() 显示校园全景search() 查询景点信息floyd() 弗洛伊德函数，查询两个景点之间的最短路径所要经过的中间节点print(int i,int j) 打印两个景点的路径及最短距离shortpath() 问路查询，求最短路径ShortestPath_DIJ(Maph * M) 利用Dijkstra算法来计算出起点到各个顶点之间的最短路径,以v0为起点menu() 显示菜单选项2、主要变量：ps[MaxPointNum] 定义主要景点信息，存放景点的编号、名称、简要介绍等信息char name[20] 景点名称char number[15] 景点编号char info[100] 景点简介信息MaxPointNum 最大景点个数INFINITY 近似无穷大，表示两景点不可达Maph M 全局变量,定义M为Maph类型int shortest[MaxPointNum][MaxPointNum] 定义全局变量存贮最短路径int path[MaxPointNum][MaxPointNum] 定义存贮路径3、存储结构：3.1 图的类型定义typedef struct{char name[20]; //景点名称char number[15]; //景点代号char info[100]; //景点信息}Elemtype; //景点类型3.2 定义景点typedef struct{int num; //顶点编号Elemtype data; //顶点信息}Point; //定义顶点3.3定义全局变量typedef struct{Point ps[MaxPointNum]; //存放顶点的一维数组int road[MaxPointNum][MaxPointNum];//存放路径的长度(邻接矩阵)int poinum,arcnum; //顶点数，边数}Maph;4、求解算法：迪杰斯特拉算法求解无向图的最短路径四、详细设计详细参见C语言源程序1.调试分析运行程序进行调试：1.进入主界面，出现校园导航咨询系统主菜单。

数据结构课程设计报告题目：校园导航系统学生姓名：谌幼华学号： 09110806班级：091108指导教师：邹国华2011 年6 月3 日目录一、需求分析说明 (3)二、总体设计 (3)三、详细设计 (5)四、实现部分 (8)五、程序测试 (13)六、总结 (15)七、参考文献 (15)校园导航系统一、需求分析说明：（一）课程设计目的：本课程设计的目的就是要达到理论与实际应用相结合，使我们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

（二）设计要求：设计一个校园导航系统，为来访的客人提供导航服务，具体要求：1. 设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

2. 为来访客人提供图中任意景点相关信息的查询。

3. 提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径以及任意景点到其他所有景点的最短路径查询。

4.列出所有校内无重复排列的景点，将所有景点的距离以邻接矩阵的方式呈现给使用者，提供使用者选择功能界面，按照提示进行操作。

5.在邻接矩阵中MAX表示最大距离即两个景点之间是不可到达的。

用实际权值来表示两个景点之间的距离，并且是可达的。

二、总体设计：1.数据结构：用图（无向网）来描述学校n个景点之间的关系，顶点为单位代号，权值为两景点的距离。

本系统基于东华理工大学校园平面图为基准而设计，先将校园内15个具有代表性的顶点列出，然后绘制出其平面图，标出任意两顶点间是否有直达的边，同时在图上有直达边的两顶点边的权值，本系统中设计的东华理工大学校园平面图如下（景点前面所对应的代号为系统中无向网的顶点号）：东华理工大学学校平面图2.系统功能图：三、详细设计：一、按所设想的功能，把程序化分为7个模块，各模块的名称和其数据类型如下表所示：各模块的说明如下：1.类模块：本系统中只涉及了一个Graph（无向网类）类，其数据成员为无向网的相关信息，例如图的邻接矩阵(程序中用数组arcs[n+1][n+1]存放有关邻接矩阵的相关信息)、原点到各定点的相关信息（存放在dist[n+1数组中]）、最短路径上该顶点的前一顶点相关信息（存放在path[n+1]数组中）、以求得到的最短路径上的顶点的顶点号（存放在s[n+1]数组中），同时将求最小路径的实现函shortest_path（）定义为其成员函数。

课程设计报告学院、系：大学学院计算机科学与技术系专业：软件工程班级：2008级9班课程设计科目数据结构学生：04080904 喆指导教师：娄雅芳完成时间：2010年10月-12月校园导航系统设计报告一、设计任务与目标设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

本系统是一个涉及大学学院相关景点和场所查询系统,是为了方便人们能够更快更准地获得学校各个景点和场所的详细信息。

本系统为用户提供以下功能:(一)、查询了解学校概况，为导游参观者提供关于学校的相关信息。

(二)、查询校园各个场所和景点信息;(三)、为导游者或外来人员参观人员提供校园交通信息，方便用户走访学校。

校园导航查询系统的开发方法总结如下：(1) 调查，了解学校各个场所与场所或者是各个景点与景点之间的信息，路径和距离，从外来人员或者参观者和走访者的角度出发，该如何设计才能满足用户需求。

(2) 分析，对调查得到的数据进行分析，根据其要求实现的功能分析系统结构和界面将实现的基本功能。

(3) 设计与开发，设计系统界面并编辑实现其各个功能的代码。

(4) 调试，在设计完成后，调试系统运行的状况，修改完善系统,然后进行测试。

二、方案设计与论证校园旅游模型是由各个景点和景点以及场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。

用图的结点代表景点或场所，用图的边代表景点或场所之间的路径。

所以首先应创建图的存储结构。

结点值代表景点信息，边的权值代表景点间的距离。

结点值及边的权值采用图存储。

本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。

计算路径长度，最短路线和最佳路径时可分别用迪杰斯特拉（Dijkastra）算法和哈密而顿回路算法实现。

最后用switch选择语句选择执行浏览景点信息或查询最短路径和距离。

课程设计报告书专业：计算机科学与技术课程设计名称：《数据结构课程设计》题目：校园导航问题班级：学号：姓名：同组人员：指导老师：完成时间：摘要校园导航要求每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径(最短路径)。

要用“邻接矩阵”来存储各点间的距离，然后用floyd算法求出最短路径。

所以采用工程思想，将系统共分以下五个模块：节点数据结构类型、创建导航图函数、最短路径导航函数、查询函数声明、主菜单。

关键词：数据结构；算法设计目录目录第一章开发环境和开发工具 (1)1.1 C语言简介 .......................................................................................................... . (1)1.2 开发背景 (2)1.3 开发环境 (2)第二章算法思想 (3)2.1 系统需求分析 (3)2.2 系统总体设计 (4)2.2.1 系统设计目标 (4)2.2.2 开发设计思想 (4)2.2.3 系统功能模块设计 (4)2.3 算法思想描述 (4)第三章算法实现 (6)3.1 数据结构 (6)3.2 程序模块 (8)3.3 各模块之间的调用关系 (9)3.4 源程序代码 (10)第四章测试与分析 (16)4.1 测试数据选择 (16)4.2 测试结果分析 (20)总结 (21)心得体会 (21)参考文献 (22)第一章开发环境和开发工具1.1 C/C++简介计算机诞生初期,人们要使用计算机必须用机器语言或汇编语言编写程序｡世界上第一种计算机高级语言诞生于1954年,它是FORTRAN语言｡先后出现了多种计算机高级语言｡其中使用最广泛､影响最大的当推BASIC语言和C语言｡它是一种使用非常广泛的计算机编程语言。

C++是一种静态数据类型检查的、支持多重编程范式的通用程序设计语言。

课程设计（数据结构）院、系计算机与软件学院专业网络工程姓名顾容宇徐鹏学号20091346087、20091346088 指导教师郑玉二Ｏ一Ｏ年十二月二十五日校园导航问题王耀南京信息工程大学计算机与软件学院，南京 210044摘要：程序设计目的是用哈斯图方式计算两个旅游点的最短距离以及路线。

编程所实现的功能除了可以查询两个旅游点的最短距离以及最短的路线，还可以看到旅游点的介绍，以及逛遍所有旅游点所能组成的所有路线可能，实现全面查询。

关键字：景点；路线；距离；校园导航1．课程设计题目设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

2．分析2．1设计基础：要掌握最短路径的实现方式。

2．2分析设计课题的要求，要求编程实现以下功能：（1）查询景点路径（2）查询景点信息（3）查看参观路线（4）查询各景点之间的距离2．3主控菜单设计为实现通信录管理的操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。

程序运行后，给出菜单项的内容和输入提示，如下：1．学校简介2．查询景点路径3. 查询景点信息4. 查看参观路线5. 查询各景点之间的距离6. 退出2．4设计课题已明确要求，有关的定义如下：typedefstructArcCell{intadj; // 相邻接的景点之间的路程char *info;}ArcCell; // 定义边的类型typedefstructVertexType{int number; // 景点编号char *sight; // 景点名称char *description; // 景点描述}VertexType; // 定义顶点的类型typedefstruct{VertexType vex[NUM]; // 图中的顶点，即为景点ArcCell arcs[NUM][NUM]; // 图中的边，即为景点间的距离intvexnum,arcnum; // 顶点数，边数}MGraph; // 定义图的类型3．步骤3.1函数调用图函数调用关系3.2主代码#include<iostream >#include <string.h>#include <stdio.h>#include <stdlib.h>#define Max 32767#define NUM 11typedef struct ArcCell{int adj; // 相邻接的景点之间的路程char *info;}ArcCell; // 定义边的类型typedef struct VertexType{int number; // 景点编号char *sight; // 景点名称char *description; // 景点描述}VertexType; // 定义顶点的类型typedef struct{VertexType vex[NUM]; // 图中的顶点，即为景点ArcCell arcs[NUM][NUM]; // 图中的边，即为景点间的距离int vexnum,arcnum; // 顶点数，边数}MGraph; // 定义图的类型MGraph G; // 把图定义为全局变量int P[NUM][NUM]; // //long int D[NUM]; // 辅助变量存储最短路径长度int x[13]={0};void CreateUDN(int v,int a); // 创建图的函数void pingmu(); //屏幕输出函数void introduce();void ShortestPath(int num); //最短路径函数void output(int sight1,int sight2); //输出函数void PrintMGraph();char Menu(); // 主菜单void search();;// 查询景点信息char SearchMenu(); // 查询子菜单void HaMiTonian(int); // 哈密尔顿图的遍历void NextValue(int);void display(); // 显示遍历结果void main() // 主函数{ int v0,v1;char ck;system("color 0");CreateUDN(NUM,11);do{ck=Menu();switch(ck){case'1':introduce();printf("\n\n\t\t\t%-25s\n\n",G.vex[0].description); getchar();getchar();break;case '2':system("cls");pingmu();printf("\n\n\t\t\t请选择起点景点（1～10）："); scanf("%d",&v0);printf("\t\t\t请选择终点景点（1～10）：");scanf("%d",&v1);ShortestPath(v0); // 计算两个景点之间的最短路径output(v0,v1); // 输出结果printf("\n\n\t\t\t\t请按回车键继续...\n");getchar();getchar();break;case '3':search();break;case '4':system("cls");pingmu();x[0]=1;HaMiTonian(1);printf("\n\n\t\t\t\t请按回车键继续...\n");getchar();getchar();break;case'5':PrintMGraph();printf("\n\n\t\t\t\t请按回车键继续...\n");getchar();getchar();break;};}while(ck!='e');}char Menu() // 主菜单 //{char c;int flag;do{flag=1;system("cls");pingmu();introduce();printf("\n\t\t\n");printf("\t\t \n");printf("\t\t 1.学校简介 \n");printf("\t\t 2.查询景点路径 \n");printf("\t\t 3.查询景点信息 \n");printf("\t\t 4.查看参观路线 \n");printf("\t\t 5.查询各景点之间的距离 \n");printf("\t\t e.退出 \n");printf("\t\t \n");printf("\t\t\n");printf("\t\t\t\t请输入您的选择：");scanf("%c",&c);if(c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='e') flag=0;}while(flag);return c;}char SearchMenu() // 查询子菜单{char c;int flag;do{flag=1;system("cls");pingmu();introduce();printf("\n\t\t\n");printf("\t\t \n");printf("\t\t 1、按照景点编号查询 \n");printf("\t\t 2、按照景点名称查询 \n");printf("\t\t e、返回 \n");printf("\t\t \n");printf("\t\t \n");printf("\t\t\t请输入您的选择：");scanf("%c",&c);if(c=='1'||c=='2'||c=='e')flag=0;}while(flag);return c;}void search() // 查询景点信息{int num;int i;char c;char name[20];do{system("cls");c=SearchMenu();switch (c){case '1':system("cls");introduce();pingmu();printf("\n\n\t\t请输入您要查找的景点编号："); scanf("%d",&num);for(i=0;i<NUM;i++){if(num==G.vex[i].number){printf("\n\n\t\t\t您要查找景点信息如下:");printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description); printf("\n\t\t\t按任回车返回...");getchar();break;}}if(i==NUM){printf("\n\n\t\t\t没有找到！");printf("\n\n\t\t\t按回车键返回...");getchar();getchar();}break;case '2':system("cls");pingmu();introduce();printf("\n\n\t\t请输入您要查找的景点名称："); scanf("%s",name);for(i=1;i<NUM;i++){if(!strcmp(name,G.vex[i].sight)){printf("\n\n\t\t\t您要查找景点信息如下:");printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description); printf("\n\t\t\t按回车键返回...");getchar();getchar();break;}}if(i==NUM){printf("\n\n\t\t\t没有找到！");printf("\n\n\t\t\t按回车键返回...");getchar();}break;}}while(c!='e');}void CreateUDN(int v,int a) // 创建图的函数{int i,j;G.vexnum=v; // 初始化结构中的景点数和边数G.arcnum=a;for(i=1;i<G.vexnum;++i) G.vex[i].number=i; // 初始化每一个景点的编号// 初始化没一个景点名及其景点描述G.vex[0].sight="学校简介";G.vex[1].sight="东大门";G.vex[2].sight="培训楼";G.vex[3].sight="气象楼";G.vex[4].sight="文德楼";G.vex[5].sight="明德楼";G.vex[6].sight="尚贤楼";G.vex[7].sight="电影院";G.vex[8].sight="北辰楼";G.vex[9].sight="图书馆";G.vex[10].sight="实验楼";// 这里把所有的边假定为32767，含义是这两个景点之间是不可到达for(i=1;i<G.vexnum;++i){for(j=1;j<G.vexnum;++j){G.arcs[i][j].adj=Max;G.arcs[i][j].info=NULL;}}//下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，// 所以要对图中对称的边同时赋值。

课程设计报告课程名称：数据结构设计题目：校园导航问题院系：信息技术学院班级：设计者：学号：指导教师：设计时间：目录一、设计目的 0二、设计要求和设计指标 0三、设计内容 03.1需求分析 03.1.1程序所能达到的功能 03.1.2输入的形式和输入值的范围 03.1.3输出的形式 (1)3.1.4测试数据和输出结果 (1)3.2总体设计 (1)3.2.1抽象数据类型定义 (1)3.2.2主程序模块的整体流程 (2)3.2.3各模块调用关系如下 (2)3.3详细设计 (2)3.3.1有向网节点结构体类型定义 (2)3.3.2 主程序和其它主要函数伪码算法 (3)3.3.3 函数的调用关系 (10)3.4测试与分析 (10)3.4.1测试 (10)3.4.2分析 (12)四、总结 (13)五、参考文献 (13)六、附录 (13)课程设计（大作业）报告一、设计目的1．加深对《数据结构》这一课程所学内容的进一步理解与巩固2．通过完成课程设计，逐渐培养自己的编程能力；3．培养给出题目后，构建框架，用计算机解决的能力；4．通过调试程序积累调试C程序设计的经验；二、设计要求和设计指标设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）三、设计内容3.1需求分析3.1.1程序所能达到的功能(1) map——输出辽宁工程技术大学平面图。

(2) init()——按相应编号输入各个节点内容，对相应路径赋值的函数。

(3) menu()——菜单函数(4) information()——输出简介的函数(5) way()——最短路径的输出函数(6) shortestpath()——调用弗洛伊德和最短路径输出的函数(7) main()——主函数3.1.2输入的形式和输入值的范围输入数字和字母：字母：以s查询最短路径；以i查询信息；以e退出程序。

校园导航问题【问题描述】以我校为例，设计一个校园导航系统，主要为来访的客人提供信息查询。

系统有两类登陆账号，一类是游客，使用该系统方便校内路线查询；一类是管理员，可以使用该系统查询校内路线，可对校园景点路线可编辑。

【需求分析】设计学校的平面图，至少包括10个以上景点（场所），每两个景点间可以有不同道路，且路长也可能不同，找出在游人所在景点到其他景点的最短路径，或游人输入的任意两个景点的最短路径。

要求：（1）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，路径权重为路径长度。

（2）为游人提供任意景点相关信息查询。

（3）为游人提供任意景点的问路查询，即任意两个景点之间的最短路径。

实现提示：一般情况下，校园道路是双向通行的，可设计校园平面图是一个无向图。

顶点和边均含有相关信息。

选做内容：（1）提供图的编辑功能：增删景点；增删道路；修改已有信息等。

（2）校园导游图的仿真界面。

【概要设计】1. 抽象数据类型定义：（1）景点顶点名称代号顶点信息简介Typedef struct{Int num;Char name[100];Char features[200];} VertexType;（2）图的存储结构：Typedef int EdgeType;Typedef struct{VertexType vexs[MaxVertexNum];EdgeType edges[MaxVertexNum][MaxVertexNum];Int n, e;} MGraph;2 主要功能模块（1）创建图的邻接矩阵存储结构void create( Graph *G );（2）浏览图中任一景点介绍VertexType GetVex(Graph *G, int v);（3）修改景点信息void PutVertex(Grahp *G, int v);（4）增加景点信息void InsertVertex(Graph*G, VertexType v);（5）删除景点信息void DeleteVertex(Graph *G, VertexType v);（6）增加道路void InsertArc(Graph *G,int v, int w);（7）删除道路void DeleteArc(Graph*G ,int v,int w);（8）查找某一景点到其他景点的最短路径void ShortestPath(Graph *G, int P[ ], int D[ ]); （9）查找任一两个景点之间的最短路径。

题目：校园导航问题班级：信计0901 姓名：刘佺学号：3090104020 完成日期：2011.6一：需求分析1.运行环境：Microsoft Visual C++ 6.02.程序所实现的功能：设计一个校园导游程序，为来访的客人提供各种信息查询服务。

为来访客人提供图中任意景点相关信息的查询。

为来访客人提供图中任意景点相关信息的查询。

3.程序的输入和包含输入的数据格式和说明：用户只需要按照页面的提示输入需要操作的序号，然后按回车确认即可。

4.程序的输出格式和说明：当用户输入所要查询的地点序号，并且回车后，屏幕自动生成所查询路径的最短路线和距离。

5.测试数据：当用户进入最短距离查询界面后，输入起始地点序号1（江苏大学校大门）和终点序号后5（药学院），屏幕上自动生成这两条路径之间的最短距离519米，和最短路径江苏大学校大门→图书馆→药学院。

当用户输入起始地点序号7（三江楼）和终点序号后13（女生一区），屏幕上自动生成这两条路径之间的最短距离1305米，和最短路径为三江楼→三山楼→东山操场→女生一区。

二：设计说明(1).主要的数据结构设计说明：结构体的定义：typedef struct VertexType{int number;char *sight;}VertexType;typedef struct{VertexType vex[NUM];int arcs[NUM][NUM];int vexnum;}MGraph;常量的定义：#define Max 32767#define NUM 1各个函数的定义：void CreateMGraph(int v) //创建图的函数，其中v表示图中的顶点数void Map() //地图展示函数,用于输出西安科技大学的平面简略图char Menu() //主菜单显示于操作界面void Info() //资料介绍函数，用于当用户选择查询地点资料时输出地点的资料信息void Dijkstra(int num) //迪杰斯特拉函数void Display(int sight1,int sight2) //地图展示函数void main() //主函数的定义(2).程序的主要流程图求最短路径算法流程图：(3.)主函数对各个函数的调用工作(4).主要函数的说明：#define Max 32767 //用Max来表示权值为此时的两点间直接不可达#define NUM 15 //选取了学校的十七个地点用数组存储，其中数组第一个元素不存储地点以方便操作typedef struct VertexType{int number;char *sight;}VertexType; //定义顶点的结构体类型，number表示顶点编号，字符数组表示顶点的名称typedef struct{VertexType vex[NUM];int arcs[NUM][NUM];int vexnum;}MGraph; //定义图的结构体类型，vex[NUM]数组存储顶点，arcsp[NUM][NUM]矩阵存储边的权值，vexnum表示顶点的个数MGraph G;{生成G表示结构体变量MGraph}int P[NUM][NUM]; //定义全局变量P[NUM][NUM]存储点之间的最短路径long int D[NUM]; //定义全局变量D[NUM]存储点之间最短路径的权值void Dijkstra(int num) //通过迪杰斯特拉算法求num点到其余点的最短路径，并将最短路径保存在数组P[NUM][NUM]中，将最短路径的权值保存在数组D[NUM]中{int v,w,i,t;int final[NUM];int min;for(v=1;v<NUM;v++){final[v]=0; //置空最短路径终点集D[v]=G.arcs[num][v]; //置初始的最短路径长度for(w=1;w<NUM;w++)P[v][w]=0; //置空最短路径if(D[v]<32767){P[v][num]=1;P[v][v]=1;}}D[num]=0;final[num]=1; //初始化num顶点属于S集for(i=1;i<NUM;++i) //开始循环,每次求得num到某个顶点的最短路径,并添加到S 集{min=Max; //min为当前所知的num到顶点的最短距离for(w=1;w<NUM;++w)if(!final[w]) //w顶点在V-S集中if(D[w]<min){v=w;min=D[w];}final[v]=1; //与num相距最近的顶点并入S集for(w=1;w<NUM;++w) //更新最短路径if(!final[w]&&((min+G.arcs[v][w])<D[w])) //修改D[w]和P[w]，w在V-S集中{D[w]=min+G.arcs[v][w];for(t=0;t<NUM;t++)P[w][t]=P[v][t];P[w][w]=1;}}}char Menu() //主菜单显示于操作界面从而让用户选择查询路径功能或者查询地点信息功能char c;int flag; //定义标志flag确定循环条件do{flag=1;Map();printf("\t\t 1.查询地点路径 \n");printf("\t\t 2.地点信息简介\n");printf("\t\t e.退出 \n");printf("\t ***********************江苏大学*************************\n");printf("\t\t\t请输入您的选择：");scanf("%c",&c);if(c=='1'||c=='2'||c=='e')flag=0;}while(flag);return c;}void Display(int sight1,int sight2) //输出函数用于通过数组P[NUM][NUM]提取出从点sight1到点sight2的最短路径，从D[NUM]中输出点sight1到点sight2的最短路径的权值{int a,b,c,d,q=0;a=sight2;if(a!=sight1){printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight);printf("\t(最短距离为 %dm.)\n\n\t",D[a]); //从D[NUM]中提取出sight1到sight2的最短距离的权值输出printf("\t%s",G.vex[sight1].sight);d=sight1;for(c=0;c<NUM;++c){P[a][sight1]=0;for(b=0;b<NUM;b++){if(G.arcs[d][b]<32767&&P[a][b]){printf("-->%s",G.vex[b].sight); //通过P[NUM][NUM]确定sight1到sight2的最短路径q=q+1;P[a][b]=0;d=b;if(q%8==0) printf("\n");}}}}}void main() //主函数{int v0,v1;char e;char ck;CreateMGraph(NUM);Do //用do while循环确保循环至少进行一次{system("cls"); //用system("cls")清屏使屏幕简洁ck=Menu();switch(ck) //用switch语句确定用户选择功能{case '1':gate: //门函数使程序退回到gate位置system("cls");Map();do{printf("\n\n\t\t\t请选择出发地序号（1～14）：");scanf("%d",&v0);if(v0<1||v0>17)printf("\n\n\t\t\t\t输入错误!\n");}while(v0<1||v0>17);do{printf("\t\t\t请选择目的地序号（1～14）：");scanf("%d",&v1);if(v1<1||v1>14||v1==v0)printf("\n\n\t\t\t\t输入错误!\n");}while(v1<1||v1>14||v1==v0);Dijkstra(v0);Display(v0,v1);printf("\n\n\t\t\t\t请按任意键继续,按e退回首页\n");getchar();scanf("%c",&e);if(e=='e'){当标识符e等于e时跳出语句}break;goto gate;case'2':system("cls");Info();printf("\n\n\t\t\t\t请按回车键退回首页...\n");getchar();getchar();break;};}while(ck!='e'); //当标识符ck不等于e时继续循环}三．上机结果及体会1.测试结果：（如图所示）打开程序所显示的界面。

##大学数据结构课程设计报告题目：校园导航系统院（系）：计算机工程学院学生姓名:班级：学号:起迄日期: 2011.6.19--6.30指导教师:指导教师评语：成绩：签名：年月日20XX—20XX年度第 2 学期一、需求分析1.问题描述：从理工大学的平面图中选取10个有代表性的景点，抽象成一个无向带权图。

以图中顶点表示景点，边上的权值表示两地之间的距离，求取任意两点间最短路径。

2.基本功能本程序主要实现的功能是为用户提供路径咨询。

根据用户指定的始点和终点输出相应路径（用到output（）函数），或者根据用户指定的景点输出景点的信息（用到search（）函数）。

3.输入输出本程序主要输入输出信息是景点编号和景点名称，以字符串的形式输入输出。

二、概要设计1.设计思路：本程序是校园导航系统，即求两点间的最短路径。

其主要算法是迪杰斯特拉算法，在此基础上再加上菜单函数输出函数造图函数查找函数即可。

2.数据结构设计：抽象数据类型图的定义如下：ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={VR}VR={(v,w)|v,w V,(v,w）表示v和w之间存在路径}基本操作p：CreatGraph（&G，V，VR）初始条件：V是图的顶点集，VR是图中边的集合。

操作结构：按V和VR的定义构造图G。

DestroyGraph（&G）初始条件：图G存在。

操作结果:销毁图G。

LocateVex（G，u）初始条件：图G存在，u和G中顶点有相同特征。

操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。

GetVex（G，v）初始条件：图G存在，v是G中某个顶点。

操作结果：返回v的信息。

FirstEdge（G，v）初始条件：图G存在，v是G中某个顶点。

操作结果：返回依附于v的第一条边。

若该顶点在G中没有邻接点，则返回“空”。

NextEdge（G，v，w）初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。

校园导航问题【问题描述】以我校为例，设计一个校园导航系统，主要为来访的客人提供信息查询。

系统有两类登陆账号，一类是游客，使用该系统方便校内路线查询；一类是管理员，可以使用该系统查询校内路线，可对校园景点路线可编辑。

【需求分析】设计学校的平面图，至少包括10个以上景点（场所），每两个景点间可以有不同道路，且路长也可能不同，找出在游人所在景点到其他景点的最短路径，或游人输入的任意两个景点的最短路径。

要求：（1）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，路径权重为路径长度。

（2）为游人提供任意景点相关信息查询。

（3）为游人提供任意景点的问路查询，即任意两个景点之间的最短路径。

实现提示：一般情况下，校园道路是双向通行的，可设计校园平面图是一个无向图。

顶点和边均含有相关信息。

选做内容：（1）提供图的编辑功能：增删景点；增删道路；修改已有信息等。

（2）校园导游图的仿真界面。

【概要设计】1. 抽象数据类型定义：（1）景点顶点名称代号顶点信息简介Typedef struct{Int num;Char name[100];Char features[200];} VertexType;（2）图的存储结构：Typedef int EdgeType;Typedef struct{VertexType vexs[MaxVertexNum];EdgeType edges[MaxVertexNum][MaxVertexNum];Int n, e;} MGraph;2 主要功能模块（1）创建图的邻接矩阵存储结构void create( Graph *G );（2）浏览图中任一景点介绍VertexType GetVex(Graph *G, int v);（3）修改景点信息void PutVertex(Grahp *G, int v);（4）增加景点信息void InsertVertex(Graph*G, VertexType v);（5）删除景点信息void DeleteVertex(Graph *G, VertexType v);（6）增加道路void InsertArc(Graph *G,int v, int w);（7）删除道路void DeleteArc(Graph*G ,int v,int w);（8）查找某一景点到其他景点的最短路径void ShortestPath(Graph *G, int P[ ], int D[ ]); （9）查找任一两个景点之间的最短路径。

数据结构报告校园导航问题一、引言校园导航问题是在大型校园环境中，为了帮助学生、教职员工和访客快速准确地找到目的地而提出的。

校园导航系统需要提供用户友好的界面和高效的导航功能，以满足用户的需求。

本报告将介绍一个基于数据结构的校园导航系统的设计和实现。

二、问题描述在大型校园中，学生、教职员工和访客常常面临找不到目的地的问题。

校园导航系统的目标是提供一个方便、快捷且准确的导航服务。

该系统需要满足以下需求：1. 提供校园地图：系统需要包含校园的地图信息，包括建筑物、道路和其他地标的位置和连接关系。

2. 支持路径规划：用户可以输入起始点和目的地，系统能够计算出最短路径，并提供导航指引。

3. 支持多种交通方式：系统需要考虑不同交通方式，如步行、自行车和汽车，并根据用户选择提供相应的路径。

4. 提供实时信息：系统需要实时更新校园地图信息，包括建筑物的开放时间、道路的交通情况等。

三、设计思路为了实现校园导航系统，我们可以采用以下数据结构和算法：1. 图结构：校园地图可以表示为一个有向加权图，其中节点表示建筑物或地标，边表示道路或连接关系，边的权重表示距离或时间。

2. 最短路径算法：可以使用Dijkstra算法或A*算法计算起始点到目的地的最短路径。

3. 用户界面：可以设计一个用户友好的界面，包括输入起始点和目的地、选择交通方式等功能。

四、系统实现基于上述设计思路，我们可以实现一个校园导航系统。

系统的实现可以分为以下几个步骤：1. 数据采集：收集校园地图信息，包括建筑物和道路的位置和连接关系。

可以使用GPS定位和地图绘制工具进行数据采集。

2. 数据存储：将采集到的数据存储到数据库中，以便系统可以快速访问和处理。

3. 路径规划：根据用户输入的起始点和目的地，使用最短路径算法计算最短路径，并生成导航指引。

4. 用户界面：设计一个用户友好的界面，包括地图显示、输入框、按钮等元素，以便用户可以输入起始点和目的地，并选择交通方式。

校园导游实验报告——数据结构校园导游实验报告——数据结构⒈引言本实验旨在通过设计和实现一个校园导游系统，运用数据结构的相关知识，解决校园导游中的路径规划和信息查询等问题。

通过该实验，掌握数据结构在实际问题中的应用，并提高对数据结构的理解和运用能力。

⒉实验目的⑴理解和掌握树结构的概念和基本操作。

⑵掌握图的存储结构和常用算法。

⑶学习使用数据结构解决实际问题。

⑷提高编程能力和团队合作能力。

⒊实验任务⑴设计一个数据结构，用于表示校园地图的各个景点和路径关系。

⑵实现校园导游系统，包括路径规划和信息查询功能。

⑶对系统进行测试和性能优化。

⒋实验步骤⑴根据校园地图，设计合适的数据结构，包括景点、路径和导游系统等。

⒋⑴景点：定义景点的属性，包括名称、位置、介绍等。

⒋⑵路径：定义路径的属性，包括起始点、终点、距离等。

⒋⑶导游系统：定义导游系统的功能，包括路径规划和景点信息查询等。

⑵实现校园导游系统的核心功能。

⒋⑴路径规划：根据用户输入的起始点和终点，使用图的遍历算法，寻找最短路径。

⒋⑵景点信息查询：根据用户输入的景点名称，查询并展示景点的详细信息。

⑶对导游系统进行完整性测试和性能优化。

⒋⑴测试导游系统的各个功能模块，确保无误。

⒋⑵针对导游系统的性能瓶颈，进行分析和优化，提高系统响应速度和稳定性。

⒌实验结果与分析⑴校园导游系统实现了路径规划和景点信息查询的功能。

⑵经过完整性测试，系统的各个功能模块均正常运行，没有明显的错误。

⑶对导游系统的性能进行优化后，系统响应速度明显提升，用户体验更加良好。

⒍实验总结通过本次实验，我们深入理解了数据结构的应用，并成功设计和实现了一个校园导游系统。

在实验过程中，我们不仅提高了编程能力，还增强了团队合作意识。

通过测试和优化，我们不断完善系统，使其达到了预期目标。

附件：⒈校园地图⒉系统设计文档⒊测试报告法律名词及注释：⒈数据结构：指描述数据元素之间相关关系的一种方式，包括逻辑结构和物理结构。

计算机工程学院课程设计报告课程名称：数据结构课程设计设计题目：校园导航问题院系：计算机工程学院专业：计算机科学与技术组别：学生姓名: 学号:起止日期:2011 年12 月26 日~2012 年 1月3 日指导教师:目录1需求分析 02.1 课程设计（实践周）题目···························································错误！未定义书签。

2.2课程设计（实践周）任务及要求 ················································错误！未定义书签。

2.3课程设计（实践周）思想 (1)2.4 软硬件运行环境开发工具 (1)2概要设计 .................................................................................. 错误！未定义书签。

实验七校园导航问题一．需求分析设计你的学校的平面图，至少包括10个以上的景点（场所），每两个景点间可以有不同的路，且路长也可能不同，找出从任意景点到达另一景点的最佳路径（最短路径）。

要求：（1）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。

（2）为来访客人提供图中任意景点相关信息的查询。

（3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。

（4）修改景点信息。

实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。

顶点和边均含有相关信息。

二．设计2.1 设计思想（1）数据结构设计(包括逻辑结构设计和存储结构设计)1. 创建有向图G，在空图G中插入n个顶点和e条边。

并实现最短路径算法。

2. 定义邻接矩阵实现图的存储类型定义。

用来保存景点的数据信息，如景点间的距离。

3. 定义结构体数组实现景点信息的保存，如景点名称等（2）算法设计1.根据景点信息建立临接矩阵2.调用Dijkstra求出两景点的最短路径3.建立结构体数组存储数据4.将修改的信息直接写入数组中2.2 设计表示（1）函数调用关系图主函数main()依次调用以下个函数#include "AdjMGraph.h"#include "Dijkstra.h"（2）函数接口规格说明调用库函数为#include <stdio.h>#include <stdlib.h>#include <malloc.h>调用自定义函数为#include "AdjMGraph.h"#include "Dijkstra.h"各函数说明void ListInitiate(SeqList *L) /* 初始化顺序表L*/int ListLength(SeqList L) /* 返回顺序表L的当前数据元素个数*/ int ListInsert(SeqList *L, int i, DataType x)int ListDelete(SeqList *L, int i, DataType *x)/*删除顺序表L中位置为i(0 <= i = size-1)的数据元素并存放到x中*//*删除成功返回1，删除失败返回0*/int ListGet(SeqList L, int i, DataType *x)/*取顺序表L中第i个数据元素存于x中，成功返回1，失败返回0*/ void Dijkstra(AdjMGraph G,int v0,int distance[],int path[]) 最短路径算法//置带权有向图G为空图void GraphInitiate(AdjMGraph *G)//判断顶点vertex是否是有向图G的顶点，是则返回顶点在顶点顺序表中的序号，否则返回-1。

数据结构课程设计—校园导航报告
校园导航作为一种常用的地图应用，其设计并不复杂，但在功能实现中涉及到多种常
见数据结构，如图、树结构等。

本报告对校园导航的数据结构设计进行详细说明，主要可
以分为三个部分：
1、数据输入。

在实现校园导航功能之前，需要输入校园数据，各个元素需要形成节点并构建图，比
如楼宇、地点以及相连的路径等，用户可以输入各个节点的属性，然后形成节点、构建图、标记属性等。

2、数据结构设计
对于校园地图来说，一般采用有向图和无向图这两种图形结构。

有向图表示有方向性
的连接关系，一般用于实现单程导航；无向图表示无方向性的连接关系，一般用于实现多
程导航，比如从一个地点到达另一个地点的最短路径。

另外，在校园地图中也会遇到对节点进行索引的情况，一般采用哈希表来构造索引，
哈希表存储不同的数据结构的元素，以及这些元素的信息，从而实现快速查找功能。

3、搜索算法设计
如许多搜索应用，校园导航中也有搜索功能，搜索过程中，会在图和哈希表中寻找符
合条件的结果。

有关搜索算法，常用的有深度优先搜索算法和广度优先搜索算法。

深度优先搜索算法通过沿着关系网的深度来搜索，即每次搜索一条路径直至无路可走；而广度优先搜索算法通过沿着关系网的广度来搜索，即每次从多条路径中选择最佳路径进
行搜索，并将其标记，直到找到最终结果
总体来看，校园导航数据结构设计包含了输入、构建图、节点索引以及搜索等多种操作，可以利用图、树、哈希表等数据结构设计实现各项功能，以最优的性能完成地图搜索
工作。

数据结构课程设计校园导航一、课程目标知识目标：1. 学生能理解并掌握数据结构中图的基本概念，包括顶点、边、邻接矩阵和邻接表。

2. 学生能够运用图的表示方法，特别是适合校园导航的图结构。

3. 学生能够描述并实现至少两种图的遍历算法，如深度优先搜索（DFS）和广度优先搜索（BFS）。

技能目标：1. 学生能够运用所学知识，设计并实现一个简单的校园导航系统，能够规划出两点之间的最短路径。

2. 学生通过实践项目，培养解决实际问题的能力，掌握算法的应用和优化。

3. 学生能够通过编程实践，提高使用数据结构解决复杂问题的能力。

情感态度价值观目标：1. 学生能够认识到数据结构在解决实际问题中的重要性，增强学习数据结构的兴趣和积极性。

2. 学生通过小组合作完成项目，培养团队协作能力和交流沟通技巧。

3. 学生在探索过程中能够体验到算法解决问题的乐趣，培养科学探究精神和创新思维。

本课程设计针对高年级学生，结合数据结构学科特点，旨在通过校园导航项目，使学生将理论知识与实际应用紧密结合。

课程强调理解与操作并重，注重培养学生的实践能力和创新精神，同时引导学生形成积极的情感态度和正确的价值观。

通过具体学习成果的分解，课程为教学设计和评估提供了明确、可衡量的标准。

二、教学内容1. 图的基本概念：- 顶点与边- 有向图与无向图- 邻接矩阵与邻接表2. 图的遍历算法：- 深度优先搜索（DFS）- 广度优先搜索（BFS）- 应用实例分析3. 最短路径算法：- Dijkstra算法- Floyd-Warshall算法- 应用实例分析4. 校园导航系统设计：- 系统需求分析- 图的构建与表示- 导航算法实现与优化5. 项目实践：- 小组分工与合作- 编程实现与调试- 系统测试与评估本教学内容按照课程目标，以数据结构课本中图的相关章节为基础，结合校园导航项目进行系统组织。

教学大纲明确教学内容安排和进度，确保学生能够逐步掌握图的原理、算法和项目实践。

实验七校园导航问题一．需求分析设计你的学校的平面图,至少包括10个以上的景点（场所），每两个景点间可以有不同的路，且路长也可能不同，找出从任意景点到达另一景点的最佳路径(最短路径）。

要求：（1）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。

(2）为来访客人提供图中任意景点相关信息的查询。

（3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。

（4）修改景点信息。

实现提示：一般情况下，校园的道路是双向通行的,可设计校园平面图是一个无向网。

顶点和边均含有相关信息。

二．设计2.1 设计思想（1）数据结构设计(包括逻辑结构设计和存储结构设计)1. 创建有向图G,在空图G中插入n个顶点和e条边。

并实现最短路径算法。

2. 定义邻接矩阵实现图的存储类型定义。

用来保存景点的数据信息，如景点间的距离.3. 定义结构体数组实现景点信息的保存，如景点名称等（2）算法设计1。

根据景点信息建立临接矩阵2。

调用Dijkstra求出两景点的最短路径3。

建立结构体数组存储数据4。

将修改的信息直接写入数组中2。

2 设计表示（1）函数调用关系图主函数main（）依次调用以下个函数#include ”AdjMGraph.h"#include ”Dijkstra。

h"（2）函数接口规格说明调用库函数为#include 〈stdio.h>＃include 〈stdlib。

h〉#include 〈malloc。

h>调用自定义函数为＃include "AdjMGraph。

h”＃include ”Dijkstra。

h”各函数说明void ListInitiate(SeqList ＊L） /* 初始化顺序表L＊/int ListLength（SeqList L） /* 返回顺序表L的当前数据元素个数*/int ListInsert(SeqList ＊L, int i， DataType x)int ListDelete（SeqList *L， int i, DataType ＊x）/*删除顺序表L中位置为i(0 〈= i = size—1）的数据元素并存放到x中＊//＊删除成功返回1，删除失败返回0＊/int ListGet(SeqList L， int i， DataType ＊x）/＊取顺序表L中第i个数据元素存于x中，成功返回1，失败返回0*/void Dijkstra（AdjMGraph G,int v0,int distance［]，int path［]) 最短路径算法//置带权有向图G为空图void GraphInitiate(AdjMGraph *G）//判断顶点vertex是否是有向图G的顶点，是则返回顶点在顶点顺序表中的序号，否则返回-1.int IsVertex（AdjMGraph *G,DataType vertex）//在带权有向图G中插入顶点vertex。