实验七校园导航问题
一．需求分析
设计你的学校的平面图，至少包括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
#include
#include
调用自定义函数为
#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。如果图中已经有顶点vertex,则图不变
void InsertVertex(AdjMGraph *G,DataType vertex)
/* 在带权有向图G中插入一条第v1个顶点指向第v2个顶点，权值为weight的有向边。
* 如果v1和v2有一个不是图中的顶点，则图不变；如果v1和v2相等，则图不变。
* 如果图已经包含该边，则边的权值更改为新的权值，时间复杂度:O(1)。
*/
void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)
//判断第v1个顶点到第v2个顶点的边是否是有向图G的边，是则返回1，否则返回0.时间复杂度O(1)。
int IsEdge(AdjMGraph *G,int v1,int v2)
/* 在带权有向图G中删除一条第v1个顶点指向第v2个顶点的有向边。
* 如果v1和v2有一个不是图中的顶点，则图不变；如果v1和v2相等，则图不变。
* 如果
*/
void DeleteEdge(AdjMGraph *G,int v1,int v2)
//在带权有向图G中取第v个顶点的第一个邻接顶点，如果这样的邻接顶点存在，则返回该顶点在顶点顺序表的序号，否则返回-1.时间复杂度:O(n)。
int GetFirstVex(AdjMGraph G,int v)
//创建有向图G，通过在空图G中插入n个顶点和e条边实现。时间复杂度:O(n^2+e)。
void GraphCreat(AdjMGraph *G,DataType v[],int n,RowColWeight W[],int e)
2.3 详细设计
（1）数据结构设计(包括逻辑结构设计和存储结构设计)
（2）算法设计
基本数据结构为：
typedef struct
{
DataType list[MaxSize] ;
int size ;
}SeqList;
/////初始化顺序表
void ListInitiate(SeqList *L) /* 初始化顺序表L*/
{
L->size = 0;
}
int ListLength(SeqList L) /* 返回顺序表L的当前数据元素个数*/ {
return L.size;
}
int ListInsert(SeqList *L, int i, DataType x)
/* 在顺序表L的第i(0 <= i = size)个位置前插入数据元素值x*/
/* 插入成功返回1，插入失败返回0*/
{
int j;
if(L->size >= MaxSize)
{
printf("顺序表已满无法插入!\n");
return 0;
}
else if(i < 0 || i > L->size)
{
printf("参数i不合法!\n");
return 0;
}
else
{
/*为插入做准备*/
for(j = L->size; j > i; j--)
L->list[j] = L->list[j-1];
L->list[i] = x;
L->size++; //元素个数加1
return 1;
}
}
int ListDelete(SeqList *L, int i, DataType *x)
/*删除顺序表L中位置为i(0 <= i = size-1)的数据元素并存放到x中*/ /*删除成功返回1，删除失败返回0*/
{
int j;
if(L->size <= 0)
{
printf("顺序表已空无数据元素可删!\n");
return 0;
}
else if(i < 0 || i > L->size-1 )
{
printf("参数i不合法!\n");
return 0 ;
}
else
{
*x = L->list[i]; /*保存删除的元素到x中*/
/*依次前移*/
for(j = i+1; j <= L->size-1; j++)
L->list[j-1] = L->list[j];
L->size--; //元素个数减1
return 1;
}
}
int ListGet(SeqList L, int i, DataType *x)
/*取顺序表L中第i个数据元素存于x中，成功返回1，失败返回0*/
{
if(i < 0 || i > L.size-1)
{
printf("参数i不合法!\n");
return 0;
}
else
{
*x = L.list[i];
return 1;
}
}
基本函数为
Dijkstra算法
算法具体步骤
（1）初始时，S只包含源点，即S=，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。
（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k 的最短路径长度）。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中
三．调试分析
Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
空间复杂度度
Dijkstra 算法的时间复杂度为O(n^2)
空间复杂度取决于存储方式，邻接矩阵为O(n^2)
四．用户手册
1.首先选择要进行的操作
2选1、2、3、4分别为查询景点信息、问路查询、修改景点信息、退出。
3.选1 输入景点代号即可进行信息查询。
4.选2 输入两景点代号即可进行问路查询。并输出最短路径长度以及两路径的景点。
4.选3 输入景点代号即可进行修改。
5选4退出
五．测试数据及测试结果
数据结构课程设计-校 园导航 -CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN
课程设计报告 课程名称数据结构课程设计题目校园导航 指导教师 设计起始日期 5.9~5.16 学院计算机学院 系别计算机科学与工程 学生姓名 班级/学号 成绩
一、需求分析 本次实验设计的任务是实现一个简易的北京信息科技大学的校园导航平面图。设计要包括下列要求： 设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 本课题实现校园多个场所（至少10个）的最短路径求解。 （1）输入的形式和输入值的范围：本系统主要数据类型为字符型char及整形int,char型主要包括单位编号，单位名称，单位简介，功能编号；输入功能编号与单位编号进行操作。 (2 ) 输出的形式：输出则通过已有的信息数据，通过相关的操作输出相应信息。 (3) 程序所能达到的功能：本程序可供任何人使用，主要功能1.浏览各单位及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看某一单位信息。 （4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 a.首先看到的是校园导航系统的菜单： b．查看浏览路线等待输入起始景点： C．选择出发点与目的地等待输入起始景点与目的地编号： d．参看景点信息等待输入景点编号：
二、概要设计 本系统包含一个文件。设计分有菜单，显示信息，弗洛伊德算法，迪杰斯特拉算法，查找景点信息等程序段。主程序为整系统的入口处，菜单主要实现显示系统功能，显示信息主要实现显示景点信息，弗洛伊德算法主要实现求两景点之间最短路径，迪杰斯特拉算法实现求两景点之间最短路径，查找景点信息主要实现显示某一景点信息。 系统首先通过主程序调用void main( );进入系统主菜单函数，根据用户的选择可分别进入：1.浏览各景点及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看景点信息；5.退出系统。 选择“浏览各景点及简介”项，显示十个景点的有关信息，包括景点编号，景点名称，景点简介。 选择“查看所有游览路线”项，会进入输入起始景点编号的界面，输入正确编号后会显示起始景点到其余九个景点的最短路线的方案。 选择“选择出发点和目的地”项，会进入输入起始景点与目的景点的界面，输入起始景 点与目的景点，并有空格隔开就得到两景点之间的最佳路径。 选择“查看景点信息”项，会进入输入要查看的景点的界面，如入后会显示该景点的有关信息。 选择“退出系统”项，就会退出程序。 三、详细设计 （1）十三个单位的图
算法设计与分析课程设计 题目：校园导航问题 文档： 物联网工程学院物联网工程专业 学号 学生姓名 班级物联网1101 二〇一三年十二月
设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路（最短路径）。 本系统为用户提供以下功能: (一)、查询了解学校概况，为导游参观者提供关于学校的相关信息。 (二)、查询校园各个场所和景点信息; (三)、为导游者或外来人员参观人员提供校园交通信息，方便用户走访学校。完成需要操作时，退出系统 校园导航查询系统的开发方法总结如下： (1) 需求分析，了解学校各个场所与场所或者是各个景点与景点之间的信息，路径和距离，考虑该如何设计才能满足用户需求。 (2) 概要设计，对调查得到的数据进行分析，根据其要求实现的功能分析系统结构和界面将实现的基本功能。 (3) 详细设计，设计系统界面并编辑实现其各个功能的代码。 (4) 调试分析，在设计完成后，调试系统运行的状况，修改完善系统,然后进行测试。 一、需求分析 1学校以及各景点介绍模块 采用一维数组将学校景点依次排放好编号G.vex[i].number=i 在选择校园介绍的时候，弹出G.vex[0]校园简介。在选择各景点信息的时候，可按编号查询2查询最短路径（主要） 查出出发地到想要到达的景点的最短路径，初步构想采用最经典的迪杰斯特拉算法最短路径函数 3查询各点距离 将所有景点的距离显示出来。 4主菜单页面显示 提供使用者选择功能界面，按照提示进行操作。 5退出 完成需要操作时，退出系统
校园导航系统模式图 二、概要设计 2.1算法设计说明 校园导航模型是由各个景点和景点以及场所和场所之间的路径组成的，所 以这完全可以用数据结构中的图来模拟。用图的结点代表景点或场所，用图的边 代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信 息，边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查 询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所 以给每个景点一个代码，用结构体类型实现。计算路径长度，最短路线和最佳路 径时可分别用迪杰斯特拉（Dijkastra ）算法和哈密而顿回路算法实现。最后switch 选择语句选择执行浏览景点信息或查询最短路径和距离。 2.1.1学校以及各景点介绍模块 采用了图的邻接矩阵存储结构，首先初始化每一个景点名称（一维数组） fo r(i=1;i 课程设计 课程名称软件工程 题目名称校园导航系统专业班级2012级网络工程应用学生姓名柴安康 学号 51202031022 指导教师储德锋 二○一五年六月一日 任务书 上机时间安排星期 周次 一二三四五 第14 周-第 17周 12网络工程 应用，1-2节 12网络工程应 用，3-4节 指导时间地点上机时间，计算机基础实验室（B521） 课程软件工程班级2012网络工程 应用 指导教师储德锋 题目校园导航系统完成时间2015年5月20日至2015年6月11日 主要内容要求完成以下功能： 1. 了解模型机的指令系统。 2. 设计模型机指令，掌握指令的执行过程。 3. 了解简单计算机内部各部件的连接，微程序控制器的设计。 4. 熟练掌握程序汇编机器码指令的含义及编写。 5. 能熟练区分直接寻址、间接寻址、寄存器寻址等各种寻址方式的不同。 设计报告要求1．封面：（格式附后） 2．课程设计任务书 3．课程设计报告： （1）需求分析 （2）功能设计 （3）程序代码设计 （4）程序设计总结 （5）心得体会和参考文献 说明：学生完成课程设计后，提交课程设计报告及软件，要求文字通畅、字迹工整（也可用以打印），文字不少于5000 字，并装订成册。 版面要求1．题目用黑体三号，段后距18磅（或1行），居中对齐；2．标题用黑体四号，段前、段后距6磅（或0.3行）；3．正文用小四号宋体，行距为1.25倍行距； 4．标题按“一”、“㈠”、“1”、“⑴”顺序编号。 分工协作说明 课题名称学生姓名学号所做的工作 校园导航系统金海侠51202032014 总体分工 指令结构总体设计夏昭明51202031005 需求分析 实地考察 陈金锁51202031010 指令具体实现夏宇峰51202031015 部分程序代码设计柴安康51202031018 调试运行 杨辉51202031022 心得体会 格式调整 代码指令的共同调试 课程设计报告 课程名称数据结构课程设计题目校园导航 指导教师 设计起始日期 5.9~5.16 学院计算机学院 系别计算机科学与工程 学生姓名 班级/学号 成绩 一、需求分析 本次实验设计的任务是实现一个简易的北京信息科技大学的校园导航平面图。设计要包括下列要求： 设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路， 且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 本课题实现校园多个场所（至少10个）的最短路径求解。 （1）输入的形式和输入值的范围：本系统主要数据类型为字符型char及整形int,char 型主要包括单位编号，单位名称，单位简介，功能编号；输入功能编号与单位编号进行操作。 (2 ) 输出的形式：输出则通过已有的信息数据，通过相关的操作输出相应信息。 (3) 程序所能达到的功能：本程序可供任何人使用，主要功能1.浏览各单位及简介； 2.查看所有游览路线； 3.选择出发点和目的地求出最佳路径； 4.查看某一单位信息。 （4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 a.首先看到的是校园导航系统的菜单： b．查看浏览路线等待输入起始景点： C．选择出发点与目的地等待输入起始景点与目的地编号： d．参看景点信息等待输入景点编号： 二、概要设计 本系统包含一个文件。设计分有菜单，显示信息，弗洛伊德算法，迪杰斯特拉算法，查找景点信息等程序段。主程序为整系统的入口处，菜单主要实现显示系统功能，显示信息主要实现显示景点信息，弗洛伊德算法主要实现求两景点之间最短路径，迪杰斯特拉算法实现求两景点之间最短路径，查找景点信息主要实现显示某一景点信息。 数据结构-校园导航系统 简介:本系统采用C语言编写,运行环境为Dev-C++; 容以电子科技大学南校区为例; 主要功能有:1.查询景点信息;2.查询两景点间最短距离;3.查询两景点间所有路线;4.查询西电校园地图;5.修改景点和路径信息. 注意事项:在进行修改景点和路径信息操作前,请在可执行文件目录下用记事本创建”superUser.CODE”文件来存放用户名与密码(中间以空格隔开),否则无法进入. 源代码: #include char particular1[1000]; char particular2[1000]; char particular3[1000]; //景点详情 }VertexType; typedef struct { VertexType vex[20]; //最多存放20个景点信息ArcCell arcs[20][20]; //两个景点间的距离 int vexnum,arcnum; }MGraph; MGraph G; char nameofschool[100]; //学校名称 int NUM=9; int P[20][20]; int p[20]; int visited[20]; int a=0; long int D[20]; int x[20]={0}; //函数声明 void CreateUDN(int v,int a); void narrate(); void ShortestPath(int num); void output(int sight1,int sight2); char Menu(); void search(); char SearchMenu(); void HaMiTonian(int); void Searchpath1(MGraph g); void disppath(MGraph g,int i,int j); void path(MGraph g,int i,int j,int k); void NextValue(int); void display(); int Addnewsight(int n); int Deletesight(int n); void Changesight(); char Changemenu(); char Sightmenu(); int Maintain(void); int VerificatianIdentity(void); void map(); 课程设计报告 院、系： 专业：软件工程 班级： 课程设计科目数据结构 学生姓名： 指导教师： 完成时间： 校园导航系统设计报告 一、设计任务与目标 设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 本系统是一个涉及吉林大学珠海学院相关景点和场所查询系统,是为了方便人们能够更快更准地获得学校各个景点和场所的详细信息。 本系统为用户提供以下功能: (一)、查询了解学校概况，为导游参观者提供关于学校的相关信息。 (二)、查询校园各个场所和景点信息; (三)、为导游者或外来人员参观人员提供校园交通信息，方便用户走访学 校。 校园导航查询系统的开发方法总结如下： (1) 调查，了解学校各个场所与场所或者是各个景点与景点之间的信息， 路径和距离，从外来人员或者参观者和走访者的角度出发，该如何设 计才能满足用户需求。 (2) 分析，对调查得到的数据进行分析，根据其要求实现的功能分析系统 结构和界面将实现的基本功能。 (3) 设计与开发，设计系统界面并编辑实现其各个功能的代码。 (4) 调试，在设计完成后，调试系统运行的状况，修改完善系统,然后进行 测试。 二、方案设计与论证 校园旅游模型是由各个景点和景点以及场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点或场所，用图的 边代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度，最短路线和最佳路径时可分别用迪杰斯特拉（Dijkastra）算法和哈密而顿回路算法实现。最后用switch选择语句选择执行浏览景点信息或查询最短路径和距离。 搭建程序框架图，其图如下所示： 三、算法说明 （一）设计功能的实现 接下来根据以上搭建的程序框架完成各个模块的算法 1、首先是抽象数据类型的定义： *作者：座殿角* 作品编号48877446331144215458 创作日期：2020年12月20日 实用文库汇编之一、课程设计目的 本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。 设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。 通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 二、课程设计内容 1)问题描述 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 2)基本要求 （1）查询各景点的相关信息； （2）查询图中任意两个景点间的最短路径。 （3）查询图中任意两个景点间的所有路径。 （4）增加、删除、更新有关景点和道路的信息 三、课程设计过程 1．需求分析 （1）设计学校的校园平面图，选取出若干的具有代表性的景点构成一个抽象的无向带权图，顶点为景点，边的权值代表了景点间路径的长度。 （2）将景点的序号，名称，介绍存放起来准备查询。 （3）提供任意景点的信息； （4）提供任意经典的路径查询及其最优路线的查询 （5）平面图景点的增加及删除，以及边和权值（长度）的改变 2．概要设计 1：第一点是主界面的设计，首先，为了该系统各个功能的管理，设计出含有多个菜单项的主菜单界面，可以更方便的使用该系统。 2：第二点是存储结构的设计，采取了图结构类型（mgraph）存储校 园图的信息，景点信息用结构数组vexs存储，而且利用全局变量：visited[]数组用于存储顶点是否被访问标志；d[]数组用于存放权值和查找路径顶点的编号；campus是一个图结构的全局变量。 3：第三点是设计各个功能的实现，学校景点的介绍通过函数 browsecompus()来实现；查询景点间的最段路径通过Floyd(弗洛伊德)算法实现；查询景点间的所有路径通过allpath函数和path函数来实现；更改图的信息可以由主函数changegraph以及其他函数可以实现。 3．详细设计 （1）主要的操作界面的显示以及无向网操作 void initgraph(graph *ga) 题号：第七题 题目：校园导航问题 1，需求分析： 设计你的学校的平面图，至少包括10个以上的景点（场所），每两个景点间可以有不同的路，且路长也可能不同，找出从任意景点到达另一景点的最佳路径（最短路径）。 要求： （1）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。 （2）为来访客人提供图中任意景点相关信息的查询。 （3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。 （4）修改景点信息。 实现提示： 一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。 选做内容： （1）提供图的编辑功能：增、删景点；增、删道路；修改已有信息等。 （2）校园导游图的仿真界面。 2，设计： 2.1 设计思想： <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; 用图来存放所提供的所有景点，然后用线性表来存放每一个景点的信息，其中包括景点的名称，代号，信息简介，以及其它的一些信息。这样就将对景点的操作，变成对图中各顶点的操作。 <2>，算法设计： 关于本课题的算法，很大部分来源于这学期数据结构课程的学习，其中包括： 第17卷第6期中国水运Vol.17No.62017年6月China Water Transport June 2017 收稿日期：2017-05-07 作者简介：李能斌，上海中船航运有限公司船长，总经理。 智能导航系统的发展与应用 李能斌 （上海中船航运有限公司，上海200000） 摘 要：本文首先然后分析了智能导航系统和运行原理，并针对其适用范围，指出在应用方面的局限性，以期对智 能导航系统的开发研究有所帮助。 关键词：智能导航；系统；智能决策；船舶避碰中图分类号：TP301文献标识码：A 文章编号：1006-7973（2017）06-0044-03 一、引言 随着信息科学、计算机技术、人工智能及其现代控制等技术的飞速发展，人们尝试用它们来解决船舶航行的安全问题。航行安全问题一直是航海界面临的急需解决的重大课题，据海外资料统计，每年头事船舶约为200艘，总吨数为120万t，占世界船队的0.4%左右，这相当于每15d 损失一艘5万t 级的船舶。然而，在碰撞船舶的原因调查中，有80%以上是由于人为因素造成的。解决人为因素问题可以通过二个途径：一是加强船员技术培训和管理，提高船员素质和责任感；二是提高船舶自动化程度，逐步实现航海自动化，随着经济的发展，船员不长期从事这个职业已成事实。因此从技术上提高自动化程度，在决策和操作上减少人的参与，逐步实现船舶避碰自动化，这才是解决人为因素的根本方法。自80年代以来，国内外航海界在智能导航技术方面取得了重大发展，而实现智能导航的核心就是实现自动避碰，为此，许多专家、学者从各个领域，不同角度致力于解决船舶的智能避碰问题。 二、智能导航系统结构框图及各部分的作用 船舶自动避碰系统结构如图1所示。本系统由数据库、 图1船舶自动避碰系统结构图 带有虚线部分为本船的传感器，其功能是收集本船及他船的运动信息，并将所收集的信息输入数据库。根据GPS 找出我船的船位，从计程仪和罗径上知道，我船船速和航向，从雷达上可获知周围船舶动态和环境情况，通过ARPA 可知他船和我船的DCPA 和TCPA。 电子海图提供了当地水深和地质数据，航海危险物数据，助航标志数据等海图信息。 数据库主要存放来自传感器和电子海图的信息以及推理过程中的中间结果等数据，供机器学习及进行深入推理时随时调用。 知识库主要包括了根据国际海上避碰规则、船员经验和专家对国际海上避碰规则的理解和认识的模块及根据船员避碰行为和专家经验所推导的研究成果，包括了良好船艺的基础知识和规则；包括了实现避碰了推理所需的算法及其结果和由各种产生式规则形成的若干个基本避碰知识模块等构成。避碰知识库是船舶自动避碰块决策的核心部分。根据船员避碰实践、国际海上避碰规则、航海专家和专业人员对规则的解释及良好船艺的实地应用，通过知识工程的处理将其转化成可用的形式。所谓知识工程是这样的技术：它从专家和文献中选取有关特定领域的信息，并将其模型制成所选定的知识形式。描述知识可以有很多种不同形式，在本系统中所采用的专家系统中通常所采取的形式，即为“如果……那么……”产生规则。其主要优点在于它的积木性。对于避碰局面的划分，根据能见度好坏分为能见度好时两船会遇、能见度不好时两船会遇、能见度良好时多船会遇和能见度不良时多船会遇基本形式。在每一种划分中，根据不同的会遇情 况又有不同的避碰操纵划分。对每一划分的每一避碰操纵划分，根据专家意见及船员实际避碰操纵，规定了具体的操纵避碰方式。其根本目的是为推理机的推理提供充分的和必需的知识。 机器学习就是计算机自动获取知识。对于避碰这样一个动态、时变的过程，就要求系统具有实时掌握目标动态的能力，这样依据知识而编制的避碰方案才会具有人的应变能力。所建造的专家系统性能的好坏，关键取决于机器学习的质量，学习质量是通过学习的佥性（真实性）、有效性和抽象层次这三个标准来衡量的。本系统采取以下方式，提高专家系统的性能。系统设计中采用算法作为学习的表示形式，采用归纳学习作为学习策略，即学习中采用推理的方法。机器学习就是在推理机推理决定应选取哪个模块来确定避碰方法。方法 《校园导航系统》课程设计报告 姓名： 学号： 班级：网络 专业：网络工程 指导教师： 时间：2 目录 摘要 (1) 1.题目 (1) 2.概要设计 (1) 3.调试分析 (15) 4.参考文献 (15) 1.题目 校园导航系统 设计一个校园导游程序，后台操作： 1、操作员信息管理如修改密码等 2、能根据学校的规模进行添加景点信息、修改景点信息等功能， 3、若临时有交通管制，能进行交通管制的设置和撤销（如某某时间段那条路进行那个方向的交通管制等） 前台为来访的客人提供各种信息查询服务： 1、设计学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名 称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 2、为来访客人提供图中任意景点相关信息的查询。 3、提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径。 1.1 需求分析 设计一个校园导航系统，导航系统又分为游客和管理员。要进行管理操作还是游客操作由用户自己选择 管理员的操作：修改景点信息、增加景点信息、交通管制等。 游客的操作：查看景点信息和查最短路径。 2.概要设计 景点的信息由一维数组存放，景点关系由二维数据来存放 景点的信息和关系从文件读取，进而初始化 typedef struct //保存单个景点信息的结构体 { char code[10]; //存放景点代码 char name[20]; //存放景点名称 char instruction[100]; //存放景点简介 }ViewPoint; typedef struct //存放景点关系的二维数组 { int edges[MAXV][MAXV]; //两景点间的距离 int number; //景点的数量 ViewPoint V[MAXV]; //保存景点信息的结构体数组 }MGraph; 数学与计算机学院 课程设计说明书 课程名称: 数据结构-课程设计 课程代码: 8404181 题目: 校园导航问题 年级/专业/班: 学生姓名: 学号: 开始时间:年月日 完成时间:年月日 课程设计成绩： 指导教师签名：年月日 数据结构课程设计任务书 学院名称：数学与计算机学院课程代码：8404181 专业：年级： 一、设计题目 校园导航问题 二、主要内容 设计西华大学的平面图，至少包括10个以上的场所，找出从任意场所到达另一场所的最短路径。 三、具体要求及应提交的材料 1．每个同学以自己的学号和姓名建一个文件夹，如：“312009*********张三”。里面应包括：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）、任务书和课程设计说明书的电子文档。 2．打印的课程设计说明书（注意：在封面后夹入打印的“任务书”以后再装订）。 四、主要技术路线提示 涉及无向图的操作。该设计共分三部分，一是建立西华大学平面图的存储结构，二是解决单源点最短路径问题，最后再实现任意一对场所之间的最短路径问题。 五、进度安排 共计两周时间，建议进度安排如下： 选题，应该在上机实验之前完成 需求分析、概要设计可分配4学时完成 详细设计可分配4学时 调试和分析可分配10学时。 2学时的机动，可用于答辩及按教师要求修改课程设计说明书。 注：只用课内上机时间一般不能完成设计任务，所以需要学生自行安排时间做补充。 六、推荐参考资料(不少于3篇) ［1］苏仕华等编著，数据结构课程设计，机械工业出版社，2007 ［2］严蔚敏等编著，数据结构（C语言版），清华大学出版社，2003 ［3］严蔚敏等编著，数据结构题集（C语言版），清华大学出版社，2003 指导教师签名日期年月日 系主任审核日期年月日 一、课程设计目的 令狐采学 本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。 设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。 通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 二、课程设计内容 1)问题描述 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 2)基本要求 （1）查询各景点的相关信息； （2）查询图中任意两个景点间的最短路径。 （3）查询图中任意两个景点间的所有路径。 （4）增加、删除、更新有关景点和道路的信息 三、课程设计过程 1．需求分析 （1）设计学校的校园平面图，选取出若干的具有代表性的景点构成一个抽象的无向带权图，顶点为景点，边的权值代表了景点间路径的长度。 （2）将景点的序号，名称，介绍存放起来准备查询。 （3）提供任意景点的信息； （4）提供任意经典的路径查询及其最优路线的查询 （5）平面图景点的增加及删除，以及边和权值（长度）的改变 2．概要设计 1：第一点是主界面的设计，首先，为了该系统各个功能的管理，设计出含有多个菜单项的主菜单界面，可以更方便的使用该系统。 2：第二点是存储结构的设计，采取了图结构类型（mgraph）存储校园图的信息，景点信息用结构数组vexs存储，而且利用 #define INFINITY 10000 #define MAX_VERTEX_NUM 40 #define MAX 40 #include }MGraph; MGraph b; void cmd(void); MGraph InitGraph(void); void show1(); void list(); void Menu(void); void ShortestPath_DIJ(MGraph * G); void Search(MGraph *G); int LocateVex(MGraph *G,char* v); /**********主函数************************/ void main(void) { system("color 5f"); /*修改控制台的颜色信息,改为白字蓝底的模式*/ system("mode con: cols=140 lines=130"); /*设置批处理运行时窗口大小的*/ cmd(); } /********自定义函数***************/ /* cmd函数(根据目录选择要进行的项目)*/ void cmd(void) { char k; b=InitGraph(); show1(); 目录 摘要 (2) 正文 (3) 1设计目的及要求 (3) 2 设计原理 (3) 2.1 C/C++语言简介 (3) 2.2 开发环境 (3) 2.3系统模块分析 (4) 3设计内容 (4) 3.1方案设计与论证 (4) 3.2数据结构描述与定义 (5) 3.3主要函数的说明 (6) 3.4设计结果验证 (11) 总结与致谢 (14) 参考文献 (15) 附录 (16) 摘要 与传统的地图相比较，地理信息系统有着不可比拟的优势，信息量大，切换方便，可扩展性强。校园导航问题是基于校园中的不同的景点，从陌生人的角度，为来往的客人提供校园景点相关信息的查询以及为来往的客人提供校园中任意景点的问路查询，以便客人能用最短的时间从某一地点到达想要去的地方。大大节约了旅客参观校园的时间。 本文是采用C++作为开发语言，又最大程度上用了C语言的有关的语法。以visual c++6.0为开发工具。旨在实现校园导航系统中，学校的简介，景点的介绍，路线查询等基本的问题。为来往客人参观校园提供方便。 关键字：visual c++6.0 ；校园导航系统； 正文 1设计目的及要求 1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3. 独立完成，提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 5. 设计学校平面图，至少包括10个以上场所，校园导航系统能自动找出校园平面图中任意起始点与终点的最佳路径（最短路径）。求并输出路径及路径长度。 2 设计原理 2.1 C/C++语言简介 C语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出。1978后，C语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画。具体应用比如单片机以及嵌入式系统开发。 C++是一种静态数据类型检查的、支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。 2.2 开发环境 随着科学技术的不断发展，计算机科学日渐成熟，其强大的功能已为人们所深刻认识，它己进入人类社会的各个领域并发挥着越来越重要的作用。采用计算机进行校园导航已成为衡量校园数字化的重要标志。校园导航效率的好坏对于来校参观的客人和学校管理者来说都至关重要，在很大程度上影响着校园的数字化建设和学校的影响力。因此，本文所研究的校园导航系统具有一定的使用价值和现实意义。 校园导航 课程设计报告书专业：计算机科学与技术 课程设计名称：《数据结构课程设计》 题目：校园导航问题 班级： 学号： 姓名： 同组人员: 指导老师： 完成时间：2012年2月17日 摘要 校园导航问题是基于校园中的不同的景点，从陌生人的角度，为来往的客人提供校园景点相关信息的查询以及为来往的客人提供校园中任意景点的问路查询，以便客人能用最短的时间从某一地点到达想要去的地方。大大节约了旅客参观校园的时间。 本文是采用C++作为开发语言，又最大程度上用了C语言的有关的语法。以visual c++为开发工具。旨在实现校园导航系统中，学校的简介，景点的介绍，路线查询等基本的问题。为来往客人参观校园提供方便。 关键词：C++；C；visual c++；校园导航 目录 第一章开发环境和开发工具 1.1C/ C ++语言简介 C语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画。具体应用比如单片机以及嵌入式系统开发。 C++是一种静态数据类型检查的、支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。 开发背景 随着科学技术的不断发展，计算机科学日渐成熟，其强大的功能已为人们所深刻认识，它己进入人类社会的各个领域并发挥着越来越重要的作用。采用计算机进行校园导航已成为衡量校园数字化的重要标志。校园导航效率的好坏对于来校参观的客人和学校管理者来说都至关重要，在很大程度上影响着校园的数字化建设和学校的影响力。因此，本文所研究的校园导航系统具有一定的使用价值和现实意义。 开发环境 本文所采用的开发环境主要是基于c++的visual stadio c++。它是一个系统的集成开发环境。很适合C\C++程序的开发。我们日常的学习和生活中大多就用这个开发环境进行学习和编程。 计算机学院 单片机设计与开发技术报告 题目：盲人智能导航路面系统设计与开发姓名：学号 姓名：学号 姓名：学号 指导老师： 起止时间：2016 年9 月至2016 年12月 西安电子科技大学计算机工程系 2012年5月制 摘要 此系统目的在于提供一种方便盲人独自安全出行的导航系统，旨在解决现有的盲人导航系统不能够准确、安全的为盲人导航的问题。系统采用RFID射频识别技术进行导航，将道路存储在电子标签，再转换成相应的语音提示信息，从而实现为盲人提供精确、安全的导航，解决盲人的出行问题。现阶段已完成预定功能，实现RFID盲人导航、语音提示、盲人输入法、GPS导航、语音读取短信、GSM相关功能等。系统能准确的帮助盲人到达目的地，让盲人实现自由地出行。 关键词：盲人出行；盲人导航；RFID 第一章绪论 当今社会科技发展迅速，带给人们生活的便利也越来越多，从物联网到大数据，从互联网到人工智能，所有的一切都是为了让人们体会到更加便捷。然而这些技术中却很少有为盲人服务的。中国是世界盲人最多的国家之一，目前约有500万盲人占世界盲人总数的10%以上，低视力者600多万，盲人的出行成了一个不可忽视的社会问题。 目前盲人出行主要依靠盲道、手杖。已经面世的盲人导航系统大多基于超声波识别系统，现有的超声波盲产品往往只能够辨别出前方是否有障碍物以及障碍物的距离，无法知道障碍物到底是什么。而这些在实际使用过程中，都存在一些不足之处，存在安全隐患和导盲的精确性问题。利用RFID新兴技术进行盲人导航有着可靠性高、定位精确的特点，通过语音的方式对盲人出行进行引导，为成千上万的盲人出行带来方便。 课程设计报告 课程设计题目：校园导航 专业：计算机科学与技术 班级：1230701 学号：2 学生姓名：胡玖龙 指导教师：刘志锋 2014年6月19日 1 / 17 实验题目: 校园导航系统 实验时间： 2014/6/16-2014/6/19 实验地点： 软件楼402 实验目的： 综合运用所学的数据结构知识解决一个关于学校导航系统的问题，侧重对图的相关内容特别是求最短路径的应用，使得能进一步熟悉掌握数据结构的基础知识，进一步提升自己的解决问题和编程调试能力，为后续专业课程的学习打下基础。 实验要求： 设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从某个场所到达另一场所的最佳路径。 求最短路径用Dijkstra或Floryd算法实现。 2 / 17 实现思路： 先分析需求，本程序的主要目的是提供本学校地点的路径查询,并提供其他各种信息查询服务。 需求： 1、提供校园平面图，使得能直观的了解学校。 2、提供地点信息查询，为各地点提供简短的介绍。 3、提供任意两地点间最短路径查询，并计算总路程。 根据要求，先将校园平面图信息抽象为无向网，用邻接矩阵存储。 需求1： 定义map()函数，功能是输出校园的平面图。可简单的通过printf()函数实现。 需求2： 定义Query()函数，功能是查询输出地点信息。可直接输出无向网中的顶点信息。 需求3： 根据输入的起点和终点，运用Floryd算法，求出最短路径，计算路径长度并输出。 考虑到使用者并不一定需要使用所有的功能，所以开始时需要一个选择菜单。定义Menu()函数，功能是提供功能选择。 输入1，选择查看学校平面图 输入2，选择查看各地点信息 输入3，选择查找两地点间最短路径 输入4，退出程序 3 / 17 题目：校园导航问题 班级：信计0901 姓名：刘佺学号：3090104020 完成日期：2011.6 一：需求分析 1.运行环境： Microsoft Visual C++ 6.0 2.程序所实现的功能： 设计一个校园导游程序，为来访的客人提供各种信息查询服务。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点相关信息的查询。 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).程序的主要流程图 求最短路径算法流程图： 智能车自主导航系统设计 本设计是一种基于摄像头的智能车自主导航系统，采用飞思卡尔公司的S12XS128单片机为控制核心，主要由电源模块，电机驱動模块，摄像头，舵机，以及反馈控制模块构成，实验表明，智能小车能很好地识别赛道信息，并作出判断，实现了自主转弯，过障碍等功能。 标签：智能汽车；自主导航；单片机；自主转弯；过障碍 智能小车是一结合了很多学科的综合的制作，它包括了虚拟智能、机械设计、高等数学、信号处理、传感器技术、电路设计、C语言、单片机、自动控制原理等学科。本设计采用摄像头作为采集信号的模块，微处理器接收处理信号，并把这个处理过的信号作为小车导航的依据，来控制小车转弯、前进、停止、加速等，从而实现小车在环境较简单的情况下的自主导航。 1 方案论证 1.1 加固车模底盘，使之成为刚体，可以有效减少小车在行驶时产生的震动以及震动对摄像头的影响。 1.2 小车在转弯，过障碍时容易发生侧翻，可以适当降低小车底盘，增加其可控性，防止侧翻发生。 1.3 测试赛道比较平坦，光滑，小车在直的长赛道上行驶时，易冲出赛道，可以在车轮上套上防滑套，来减少因速度快造成的轮胎磨损，增加轮胎的抓地性能，从而提高小车的操控性，同时使马力能更好的传到地面驱动小车加速。 1.4 电机驱动模块是智能小车重要的模块之一，需要性能稳定、可靠性高、散热性好等特点，所以采用BTN7971芯片作为电机驱动芯片。并且该芯片具有自我保护能力，抗电子干扰能力强，且对环境的适应能力较强，加速过程快等优点[1]。 1.5 智能车系统采用7.2V2000mAhNi-cd蓄电池进行供电，但各个模块所需要的电压不同，因此需要进行电压调节。7.2V直接为BTN7971供电，使用LM7806（6V）将7.2V稳压成6V后给舵机供电，用LM2940（5V）分别为单片机、摄像头编码器供电。 1.6 智能车的转向控制是关键的技术之一，转向性能的好坏和转向控制的适当与否对智能小车的速度及稳定性有很大的影响。舵机本身是一个随动系统，影响舵机控制性能的一个重要参数是舵机的响应速度，而舵机的响应速度直接影响智能车通过弯道的最高速度，适当地提高舵机的工作电压可以提高舵机的响应速度，把舵机改装在两个转向轮中间，以此来减小响应时间，根据杠杆原理加长力臂，来增加舵机的扭转能力，提高了小车的转向控制速度[2]。校园导航系统
数据结构课程设计-校园导航
校园导航系统源代码
数据结构课程设计—校园导航报告
实用文库汇编之数据结构课程设计校园导航
校园导航系统
智能导航系统的发展与应用
《校园导航系统》课程设计报告
数据结构—课程设计—校园导航问题报告
数据结构课程设计校园导航
校园导航系统源代码
校园导航系统
校园导航系统课程设计
智能盲人路面导航系统报告
C语言校园导航系统
数据结构报告_校园导航问题
智能车自主导航系统设计
相关主题
文本预览