数据结构课程设计-校园导航

分类号编号华北***大学North China Institute of Water Conservancy andHydroelectric Power课程设计题目校园导航院系信息工程学院专业计算机科学与技术姓名******学号201117000指导教师*****2012年7月6 日目录1.需求分析 (1)1.1问题描述 (1)1.2课程设计目的 (1)1.3设计要求 (1)2.概要设计 (2)2.1任务定义 (2)2.2数据结构 (2)2.3 校园平面图展示 (2)2.4系统功能图 (4)3.详细设计 (4)3.1各个模块名称和功能 (4)3.2具体函数模块详解 (5)3.2.1校园平面图展示 (5)3.2.2任意两点的所有路径 (5)3.2.3校园基础设施介绍 (6)3.2.4指定两点间最短路径 (6)3.2.5单点到其他左右顶点间最短路径 (6)3.2.6华北水利水电学院简介 (7)3.2.7访客留言 (7)3.2.8浏览访客留言 (7)3.3 主要算法思想描述 (7)3.4各函数之间的调用关系示意图 (7)4.测试与分析 (8)4.1测试显示 (8)4.2调试分析 (12)4.2．1调试过程中遇到的问题与解决方案 (12)4.2.2算法的时空复杂度分析 (12)5.用户使用说明 (12)6.实验总结 (14)7.参考文献 (14)8.附件 (15)校园导航系统1.需求分析1.1问题描述我们熟悉一个地方的地形情况通常是借助于一张地图，通常的地图包含的信息十分的有限，而且具体到某一个建筑物，你不能了解到它的进一步的详细的情况。

因此，导航系统就应运而生了。

具体到本系统，作为用户浏览校园时，只拿着学校的地图是能够游遍全校，但是各建筑内部的情况就必须实地考察才能了解，既费时又费力。

有了我们的校园的导航系统，用户可以根据自己的需要，迅速找到所关心的地点，并且可以看到它的详细的信息。

1.2课程设计目的本课程设计的目的就是要达到理论与实际应用相结合，使我们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，培养程序设计技能如下：(1)了解并掌握数据结构算法的设计方法，具备初步的独立分析和设计能力；(2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；(3) 独立完成，提高运用所学的理论知识和方法独立分析和解决问题的能力；1.3设计要求设计一个校园导航系统，为来访的客人提供导航服务，具体要求：(1) 设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

Microsoft Visual C++ 6.0设计一个校园导游程序，为来访的客人提供各种信息查询服务。

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

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

用户只需要按照页面的提示输入需要操作的序号，然后按回车确认即可。

当用户输入所要查询的地点序号，并且回车后，屏幕自动生成所查询路径的最短路线和距离。

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

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

结构体的定义：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() //主函数的定义求最短路径算法流程图：#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) //更新最短路径//修改 D[w]和if(!final[w]&&((min+G.arcs[v][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]); 到 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); 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; //从 D[NUM]中提取出 sight1 //通过 P[NUM][NUM]确定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 时继续循环}打开程序所显示的界面。

《校园导航系统》课程设计报告姓名：蒋小文学号：110236100123 班级：1班专业：网络工程指导教师：唐轶媛蒋荣萍时间：2012年7月5日信息科学与工程学院目录摘要 (1)1.目的 (2)2.要求 (2)3.题目 (2)4.任务 (2)1).需求分析 (3)2).概要设计 (4)3).详细设计 (5)4).调试分析 (8)5.课设总结 (18)6.附录源代码 (19)1.目的数据结构是计算机专业的核心课程，是一门实践性很强的课程。

课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C （C++）程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。

2.要求2.1 课程设计时间为2周；2.2 设计语言C（C++）不限；2.3 课余时间完成源程序和课程设计报告等文档书写工作，上机时间只能做调试工作。

上机时带上源程序、数据结构教材、C语言教材。

2.4 上机任务（1）选择并定义合适的数据结构；（2）根据程序所要完成的基本要求，设计出完整的算法；（3）设计出主程序（main函数），使其成为完整的程序。

2.5 上机时间：上午8:30--11:30，下午3:00--5:303.题目题目：校园导航系统设计一个校园导游程序，后台操作：3.1、操作员信息管理如修改密码等3.2、能根据学校的规模进行添加景点信息、修改景点信息等功能，3.3、若临时有交通管制，能进行交通管制的设置和撤销（如某某时间段那条路进行那个方向的交通管制等）3.4、前台为来访的客人提供各种信息查询服务：3.4.1、设计学校的校园平面图，所含景点不少于10个。

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

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

3.4.3、提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径。

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

要用“邻接矩阵”来存储各点间的距离，然后用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++是一种静态数据类型检查的、支持多重编程范式的通用程序设计语言。

课程设计报告课程名称数据结构课程设计题目校园导航指导教师设计起始日期学院计算机学院系别计算机科学与工程学生姓名班级/学号成绩一、需求分析本次实验设计的任务是实现一个简易的北京信息科技大学的校园导航平面图。

设计要包括下列要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

本课题实现校园多个场所（至少10个）的最短路径求解。

（1）输入的形式和输入值的范围：本系统主要数据类型为字符型char及整形int,char型主要包括单位编号，单位名称，单位简介，功能编号；输入功能编号与单位编号进行操作。

(2 ) 输出的形式：输出则通过已有的信息数据，通过相关的操作输出相应信息。

(3) 程序所能达到的功能：本程序可供任何人使用，主要功能 1.浏览各单位及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看某一单位信息。

（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

a.首先看到的是校园导航系统的菜单：b．查看浏览路线等待输入起始景点：C．选择出发点与目的地等待输入起始景点与目的地编号：d．参看景点信息等待输入景点编号：二、概要设计本系统包含一个文件。

设计分有菜单，显示信息，弗洛伊德算法，迪杰斯特拉算法，查找景点信息等程序段。

主程序为整系统的入口处，菜单主要实现显示系统功能，显示信息主要实现显示景点信息，弗洛伊德算法主要实现求两景点之间最短路径，迪杰斯特拉算法实现求两景点之间最短路径，查找景点信息主要实现显示某一景点信息。

系统首先通过主程序调用void main( );进入系统主菜单函数，根据用户的选择可分别进入：1.浏览各景点及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看景点信息；5.退出系统。

选择“浏览各景点及简介”项，显示十个景点的有关信息，包括景点编号，景点名称，景点简介。

课程设计报告课程名称：数据结构设计题目：校园导航问题院系：信息技术学院班级：设计者：学号：指导教师：设计时间：目录一、设计目的 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）查找任一两个景点之间的最短路径。

校园导航课程设计报告书专业：计算机科学与技术课程设计名称：《数据结构课程设计》题目：校园导航问题班级：学号：姓名：同组人员:指导老师：完成时间：2012年2月17日摘要校园导航问题是基于校园中的不同的景点，从陌生人的角度，为来往的客人提供校园景点相关信息的查询以及为来往的客人提供校园中任意景点的问路查询，以便客人能用最短的时间从某一地点到达想要去的地方。

大大节约了旅客参观校园的时间。

本文是采用C++作为开发语言，又最大程度上用了C语言的有关的语法。

以visual c++为开发工具。

旨在实现校园导航系统中，学校的简介，景点的介绍，路线查询等基本的问题。

为来往客人参观校园提供方便。

关键词：C++；C；visual c++；校园导航目录第一章开发环境和开发工具1.1C/ C ++语言简介C语言是一种计算机程序设计语言。

它既具有高级语言的特点，又具有汇编语言应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。

它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画。

具体应用比如单片机以及嵌入式系统开发。

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

它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。

开发背景随着科学技术的不断发展，计算机科学日渐成熟，其强大的功能已为人们所深刻认识，它己进入人类社会的各个领域并发挥着越来越重要的作用。

采用计算机进行校园导航已成为衡量校园数字化的重要标志。

校园导航效率的好坏对于来校参观的客人和学校管理者来说都至关重要，在很大程度上影响着校园的数字化建设和学校的影响力。

因此，本文所研究的校园导航系统具有一定的使用价值和现实意义。

开发环境本文所采用的开发环境主要是基于c++的visual stadio c++。

它是一个系统的集成开发环境。

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称《数据结构》课题名称校园导航系统专业计算机科学与技术班级10计本2班学号********姓名吴宗林联系方式152****6478指导教师江家宝20 11 年12 月29 日目录1、数据结构课程设计任务书 (1)1.1、题目 (1)1.2、要求 (1)2、详细设计 (1)2.1、程序中所采用的数据结构及存储结构的说明 (1)2.2、算法的设计思想 (2)3、调试与测试： (2)3.1、调试方法与步骤： (2)3.2、测试结果的分析与讨论： (2)4、时间复杂度的分析： (4)5、源程序清单和执行结果 (5)6、C程序设计总结 (9)7、致谢 (10)8、参考文献 (10)1、数据结构课程设计任务书1.1、题目校园导航问题1.2、要求设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

1）设计校园平面图，在校园景点选10个左右景点。

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

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

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

2、详细设计模块功能说明：如函数功能、入口及出口参数说明，函数调用关系描述等；2.1、程序中所采用的数据结构及存储结构的说明（1）图。

采用邻接矩阵存储，其中图所用到的结构体为：typedef struct{SeqList vertices; //表示图中的顶点int Edge[MaxVertices][MaxVertices]; //表示图中的边int numOfEdge; //表示图中边的数目}AdjMGraph;（2）景点。

用顺序表存储。

所用到的结构体为：typedef struct{char name[20]; //顶点名称int code; //顶点代号char introduction[50]; //顶点信息简介}DataType;（3）景点之间的连接描述，所用到的结构体为：typedef struct{int row;int col;int weight;}RowColWeight;用图来存放所提供的所有景点，然后用线性表来存放每一个景点的信息，其中包括景点的名称，代号，信息简介，以及其它的一些信息。

一、课程设计目的本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。

设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。

通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。

同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

二、课程设计内容1)问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。

要求能够回答有关景点介绍、游览路径等问题。

2)基本要求（1）查询各景点的相关信息；（2）查询图中任意两个景点间的最短路径。

（3）查询图中任意两个景点间的所有路径。

（4）增加、删除、更新有关景点和道路的信息三、课程设计过程1．需求分析（1）设计学校的校园平面图，选取出若干的具有代表性的景点构成一个抽象的无向带权图，顶点为景点，边的权值代表了景点间路径的长度。

（2）将景点的序号，名称，介绍存放起来准备查询。

（3）提供任意景点的信息；（4）提供任意经典的路径查询及其最优路线的查询（5）平面图景点的增加及删除，以及边和权值（长度）的改变2．概要设计1：第一点是主界面的设计，首先，为了该系统各个功能的管理，设计出含有多个菜单项的主菜单界面，可以更方便的使用该系统。

2：第二点是存储结构的设计，采取了图结构类型（mgraph）存储校园图的信息，景点信息用结构数组vexs存储，而且利用全局变量：visited[]数组用于存储顶点是否被访问标志；d[]数组用于存放权值和查找路径顶点的编号；campus是一个图结构的全局变量。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

校园导航系统的课程设计一、课程目标知识目标：1. 学生能理解并掌握校园导航系统的基本概念和原理；2. 学生能掌握使用校园导航系统所需的相关地图知识，如地图阅读、方向识别等；3. 学生能了解并描述校园导航系统中的定位技术、路径规划算法等关键技术。

技能目标：1. 学生能够运用所学知识，独立操作校园导航系统，完成校园内的定位和路径规划；2. 学生能够分析并解决在使用校园导航系统过程中遇到的问题，提高问题解决能力；3. 学生能够通过小组合作，共同设计与完善校园导航系统，提高团队协作能力。

情感态度价值观目标：1. 学生通过学习校园导航系统，培养对地理信息科学和现代信息技术的兴趣和热情；2. 学生在学习过程中，增强对团队合作、互助互爱的认识，培养良好的团队精神和沟通能力；3. 学生能够认识到科技在现实生活中的应用，提高社会责任感和创新意识。

本课程针对初中年级学生设计，结合学生年龄特点，注重培养学生的学习兴趣和实际操作能力。

课程性质以实践性、综合性为主，通过讲授、实践、小组合作等多种教学方式，使学生掌握校园导航系统的相关知识，提高学生的实际问题解决能力和团队协作能力。

在教学过程中，注重分层教学，关注学生的个体差异，确保课程目标的实现。

课程目标的具体分解，便于教师在教学设计和评估中，有针对性地提高教学质量，实现学生的全面发展。

二、教学内容本章节教学内容主要包括以下几部分：1. 校园导航系统基础知识：- 地图的基本概念与类型；- 方向识别与地图阅读技巧；- 常见导航系统的功能与原理。

2. 定位技术与路径规划算法：- GPS定位原理及其在校园导航中的应用；- 路径规划算法的基本原理与分类；- 校园路径规划的实际应用案例分析。

3. 校园导航系统的操作与应用：- 系统注册、登录及基本设置；- 校园地图浏览与搜索功能；- 实地操作：使用校园导航系统完成指定路线的导航。

4. 小组合作设计与完善校园导航系统：- 分析现有校园导航系统的优缺点；- 小组讨论、设计并完善校园导航系统功能；- 展示与评价：展示各组设计成果，进行评价与交流。

##大学数据结构课程设计报告题目：校园导航系统院（系）：计算机工程学院学生姓名:班级：学号:起迄日期: 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的邻接顶点。

校园导航课程设计报告书专业：计算机科学与技术课程设计名称：《数据结构课程设计》题目：校园导航问题班级：学号：姓名：同组人员:指导老师：完成时间：2012年2月17日摘要校园导航问题是基于校园中的不同的景点，从陌生人的角度，为来往的客人提供校园景点相关信息的查询以及为来往的客人提供校园中任意景点的问路查询，以便客人能用最短的时间从某一地点到达想要去的地方。

大大节约了旅客参观校园的时间。

本文是采用C++作为开发语言，又最大程度上用了C语言的有关的语法。

以visual c++6.0为开发工具。

旨在实现校园导航系统中，学校的简介，景点的介绍，路线查询等基本的问题。

为来往客人参观校园提供方便。

关键词：C++；C；visual c++6.0；校园导航目录目录 ................................................. 错误!未指定书签。

第一章开发环境和开发工具............................. 错误!未指定书签。

1.1C/ C ++语言简介................................ 错误!未指定书签。

1.2 开发背景........................................ 错误!未指定书签。

1.3 开发环境........................................ 错误!未指定书签。

第二章算法思想 ....................................... 错误!未指定书签。

2.1 系统需求分析.................................... 错误!未指定书签。

2.2 系统总体设计.................................... 错误!未指定书签。

2.2.1 系统设计目标 .............................. 错误!未指定书签。

毕业论⽂校园导航系统数据结构课程设计报告书课程设计报告书课程名称数据结构设计题⽬校园导航系统专业班级计算机11-4 班⽬录1.设计时间 (2)2.设计⽬的 (2)3.设计任务 (2)4.设计内容 (2)4.1需求分析 (2)4.2总体设计 (3)4.3详细设计 (4)4.4测试与分析 (12)4.4.1测试 (12)4.4.2分析 (13)4.5 附录 (14)5 总结与展望 (20)6.参考⽂献 (21)7.成绩评定 (21)1 设计时间2013年12⽉3⽇2 设计⽬的1．加深对《数据结构》这⼀课程所学内容的进⼀步理解与巩固2．通过完成课程设计，逐渐培养⾃⼰的编程能⼒；3．培养给出题⽬后，构建框架，⽤计算机解决的能⼒；4．通过调试程序积累调试C程序设计的经验；3设计任务给出校园各主要建筑的名称信息及有线路联通的建筑之间的距离，利⽤校园导航系统计算出给定的起点到终点之间的最近距离及线路。

4 设计内容4.1需求分析1．程序所能达到的功能：(1) map——输出⼭东科技⼤学平⾯图。

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

(3) floyd()-- --弗洛伊德求最短路径(4) information()——输出简介的函数(5) Path()——最短路径的输出函数(6) shortestpath()——调⽤弗洛伊德和最短路径输出的函数(7) main()——主函数2．输⼊的形式和输⼊值的范围：输⼊数字和字母：字母：以s查询最短路径；以i查询信息；以e退出程序。

数字：从1到9输⼊。

3．输出的形式：从A到B得最短路径为：A-到-C-到-D-到-B最短距离为：xxx⽶。

4．测试数据包括在正确的输⼊及输出结果及含有错误的输⼊及输出结果：Input：sOutput:Please enter the number two to query : 1 7Output：The shortest path from Area C dormitory building to library is: Area C dormitory building--Area C restaurant--library; The shortest distance is:150meters.Input：iOutput:Please enter the number of query site: 3Output:@name: Area B dormitory building@introduction:Area B student rest areainput：eoutput：Thank you for you use4.2总体设计1．抽象数据类型定义typedef struct{char name[100] ;int number;char introduce[100];}Vertex;2．主程序模块的整体流程1、进⼊主函数，调⽤init()，map()。

南京工程学院课程设计说明书(论文)题目校园导航系统课程名称数据结构院系通信工程学院专业信息工程班级学生姓名学号设计地点指导教师设计起止时间：2008 年12月29 日至年月日目录1．课程设计题目 (1)2．软件功能描述 (1)3．软件总体设计 (1)3．1数据结构描述与定义 (1)3．2模块设计 (3)4．测试结果与分析 (4)5．课程设计总结 (5)附录：源程序清单 (6)1．课程设计题目校园导航系统2．软件功能描述在近一个星期的努力下，我编写的校园导航系统软件终于能够成功完成。

采用工程思想，将系统共分一下几个模块:数据结构定义模块、导航图建立模块、求最短路径模块、主菜单；下面是具体各功能简单的实际应用：➢数据结构定义模块：模块定义了导航图中各个节点的基本结构类型，主要采用邻接矩阵的存储结构来真实反映各节点到其他所有节点的路径长度（权值大小）。

➢导航图建立模块：采用上述结构体类型对导航图中每个节点进行赋值。

包括：各定点的名称（地点名），各个节点到其他所有节点的真实路径长度（赋权值）。

➢求最短路径模块：本模块的基本思想是采用迪杰斯特拉算法求最短路径。

次模块是本校园导航系统的核心模块，求两点间的最短路径与求一点到其他所有点最短路径两个子功能均是在最短路径算法模块的基础上进行调用，进而实现导航功能。

➢主菜单：主菜单中主要是显示导航图中的所有导航节点，能够快速方便的对各个地点进行导航。

以上程序的几个模块，构成了校园导航系统的基本组成部分，程序运行良好，达到了课程设计的基本要求。

由于所学知识有限，功能各个方面还有欠妥之处，希望得到指出与改正。

3．软件总体设计3．1数据结构描述与定义1.节点数据结构类型：#define MAX_V 30 //最大顶点个数typedef struct{char* vexs[MAX_V]; //顶点向量int arcs[MAX_V][MAX_V];//邻接矩阵int vexnum,arcnum;//图的当前顶点数和弧数}MGraph;2.创建导航图函数：int CreateUDN(MGraph &G)函数描述：主要将每个节点进行命名、每个顶点到其他所有定点的路径值用邻接矩阵进行存储。