校园导航系统---算法及分析课程设计报告

-算法设计与分析课程设计题目： 校园导航问题 文档：物联网工程 学院物联网工程 专业学 号 学生 班 级 物联网1101 二一三年十二月设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最正确路最短路径。本系统为用户提供以下功能: (一)、查询了解学校概况，为导游参观者提供关于学校的相关信息。(二)、查询校园各个场所和景点信息; (三)、为导游者或外来人员参观人员提供校园交通信息，方便用户走访学校。完成需要操作时，退出系统校园导航查询系统的开发方法总结如下： (1) 需求分析，了解学校各个场所与场所或者是各个景点与景点之间的信息，路径和距离，考虑该如何设计才能满足用户需求。(2) 概要设计，对调查得到的数据进展分析，根据其要现的功能分析系统构造和界面将实现的根本功能。(3) 详细设计，设计系统界面并编辑实现其各个功能的代码。(4) 调试分析，在设计完成后，调试系统运行的状况，修改完善系统,然后进展测试。一、需求分析1学校以及各景点介绍模块采用一维数组将学校景点依次排放好编号G.ve*i.number=i 在选择校园介绍的时候，弹出G.ve*0校园简介。在选择各景点信息的时候，可按编号查询2查询最短路径主要查出出发地到想要到达的景点的最短路径，初步设想采用最经典的迪杰斯特拉算法最短路径函数3查询各点距离将所有景点的距离显示出来。4主菜单页面显示提供使用者选择功能界面，按照提示进展操作。5退出完成需要操作时，退出系统校园导航系统最短路径查询查询各景点距离查询校园所有景点路径校园介绍，各景点介绍输入起点与终点输出最短路径校园导航系统模式图2、 概要设计2.1算法设计说明 校园导航模型是由各个景点和景点以及场所和场所之间的路径组成的，所以这完全可以用数据构造中的图来模拟。用图的结点代表景点或场所，用图的边代表景点或场所之间的路径。所以首先应创立图的存储构造。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用构造体类型实现。计算路径长度，最短路线和最正确路径时可分别用迪杰斯特拉Dijkastra算法和哈密而顿回路算法实现。最后switch选择语句选择执行浏览景点信息或查询最短路径和距离。2.1.1学校以及各景点介绍模块 采用了图的邻接矩阵存储构造，首先初始化每一个景点名称一维数组for(i=1;iG.ve*num;+i) G.ve*i.number=i SearchMenu子菜单输入景点编号编号值=iInum输出景点介绍输出“错误完毕景点介绍功能流程图2.1.2查询最短路径主要 算法的主要思想是按路径长度递增的次序产生最短路径的算法。中心思想是假设s为已求得最短路径的终点的集合，则下一条最短路径或者是弧v,*或者是中间经过s中是顶点而最后到达顶点*的路径。（1） arcs表示弧上的权值。假设不存在，则置arcs为。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。则，从v出发到图上其余各顶点vi可能到达的最短路径长度的初值为D=arcsLocate Ve*(G,v),i viV（2） 选择vj，使得Dj=MinD | viV-S (3修改从v出发到集合V-S上任一顶点vk可达的最短路径长度路径查询流程图2.1.3查询各点距离由于图的构造比拟复杂，任意两个点之间都可能存在联系。因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，但是却可以借助数组的数据类型表示元素之间的关系。2.1.4主函数循环体用开关语句，该语句的条件值ck是当用户选择菜单通过调用主菜单函数得到，返回值整数作开关语句的条件。根据该值调用相应的各功能函数，同时设置一个退出程序点，执行完用户的*项功能后继续显示菜单，当返回值为e时函数完毕程序，以免造成死循环。2.2数据构造与函数考虑2.2.1数据构造定义构造体类型，将多个相关的变量包装成为一个整体使用。*define Ma* 32767 *define NUM 20自定义顶点的类型typedef struct Verte*Type int number; / 景点编号char *sight;/ 景点名称Verte*Type;自定义图的类型typedef structVerte*Type ve*NUM; / 图中的顶点，即为景点int arcsNUMNUM; / 图中的边，即为景点间的距离int ve*num; / 顶点数MGraph;把图定义为全局变量MGraph G;int PNUMNUM; 辅助变量存储最短路径长度long int DNUM;2.2.2使用的系统头文件*include stdio.h /*I/O 函数*/ *include stdlib.h /*使用systeme*itatoimallocfree函*/ *include string.h /*字符串函数，strcpystrlenstrcmp*/ 三、主程序*include *include *include *define Ma* 32767 *define NUM 20 typedef struct Verte*Type int number; char *sight; Verte*Type; typedef struct Verte*Type ve*NUM; int arcsNUMNUM; int ve*num; MGraph; MGraph G; int PNUMNUM; long int DNUM; void CreateMGraph(int v)/创立图的函数,v是函数入口 int i,j; G.ve*num=v; for(i=1;iG.ve*num;+i) G.ve*i.number=i; G.ve*0.sight=各个地点名字; G.ve*1.sight=江南大学校北门; G.ve*2.sight=第一食堂; G.ve*3.sight=江南大学东偏门; G.ve*4.sight=设计学院; G.ve*5.sight=体育中心; G.ve*6.sight=物联网工程学院; G.ve*7.sight=图书馆; G.ve*8.sight=江南大学东门; G.ve*9.sight=国家重点实验室; G.ve*10.sight=第二教学楼; G.ve*11.sight=第四食堂; G.ve*13.sight=臻善楼; G.ve*12.sight=江南大学南门; for(i=1;iG.ve*num;+i) for(j=1;jG.ve*num;+j) G.arcsij=Ma*; G.arcs12=G.arcs21=200; G.arcs13=G.arcs31=210; G.arcs15=G.arcs51=521; G.arcs24=G.arcs42=299; G.arcs25=G.arcs52=450; G.arcs23=G.arcs32=869; G.arcs35=G.arcs53=620; G.arcs38=G.arcs83=756; G.arcs45=G.arcs54=355; G.arcs46=G.arcs64=221; G.arcs57=G.arcs75=225; G.arcs58=G.arcs85=900; G.arcs67=G.arcs76=280; G.arcs69=G.arcs96=241; G.arcs78=G.arcs87=440; G.arcs710=G.arcs107=350; G.arcs810=G.arcs108=570; G.arcs910=G.arcs109=1300; G.arcs911=G.arcs119=998; G.arcs912=G.arcs129=1200; G.arcs1011=G.arcs1110=639; G.arcs1012=G.arcs1210=805; G.arcs1112=G.arcs1211=283; G.arcs1213=G.arcs1312=296; void Map()/地图展示函数 printf(t *江南大学大学地图导航系统* n); printf( 1 江南大学北大门 n); printf( n); printf( n); printf( 2第一食堂 3江南大学东偏门 n); printf( n); printf( n); printf( 4设计学院5体育中心 n); printf( n); printf( n); printf( n); printf( 6物联网工程学院7图书馆 8江南大学东门 n); printf( n); printf( n); printf( n); printf( 9国家重点实验室 10第二教学楼 n); printf( n); printf( n); printf( n); printf( n); printf( 11第四食堂 n); printf( n); printf( 13臻善楼12江南大学南门 n); void Info()/资料介绍函数 printf(1 江南大学校北大门 ：这是江南大学最有名的大门，是一座充满历史感的高大的牌坊，正上面写着“江南大学四个大字，反面写着“江南第一学府六个字n); printf(2 江南大学第一食堂n); printf(3 江南大学东偏门： n); printf(4 设计学院：n); printf(5 体育中心：n); printf(6 物联网工程学院：n); printf(7 图书馆：高达15层的雄伟的图书馆 n); printf(8 江南大学东门： n); printf(9 国家重点实验室： n); printf(10 第二教学楼： n); printf(11 第四食堂: n); printf(13 臻善楼: n); printf(12 江南大学南门: n);void ShortestPath(int num) / 迪杰斯特拉算法最短路径函数num为入口点的编号 int v,w,i,t; / i、w和v为计数变量int finalNUM; int min; for(v=1;vNUM;v+)finalv=0; / 假设从顶点num到顶点v没有最短路径Dv=G.arcsnumv;/ 将与之相关的权值放入D中存放for(w=1;wNUM;w+) / 设置为空路径Pvw=0;if(Dv32767) /存在路径Pvnum=1; /存在标志置为一 Pvv=1; /自身到自身Dnum=0; finalnum=1; /初始化num顶点属于S集合/ 开场主循环，每一次求得num到*个顶点的最短路径，并将其参加到S集合for(i=1;iNUM;+i) /其余G.ve*num-1个顶点min=Ma*; / 当前所知离顶点num的最近距离for(w=1;wNUM;+w) if(!finalw) / w顶点在v-s中if(Dwmin) / w顶点离num顶点更近v=w;min=Dw; / 更新当前最短路径极其距离finalv=1; / 离num顶点更近的v参加到s集合for(w=1;wNUM;+w) if(!finalw&(min+G.arcsvw)Dw) / 不在s集合，并且比以前所找到的路径都短就更新当前路径Dw=min+G.arcsvw; for(t=0;tNUM;t+)Pwt=Pvt;Pww=1; char Menu()/应用主界面显示函数char c;int flag;dosystem(cls);flag=1;Map();printf(tt欢送使用江南大学导航图系统n);printf(tt 1.查询地点之间最短路径 n);printf(tt 2.江南大学景点介绍n);printf(tt e.退出 n);printf(ttt请输入您的选择：);scanf(%c,&c);if(c=1|c=2|c=e)/如果输入为1,2,E中的一个，则返回Cflag=0;while(flag);return c;void Display(int sight1,int sight2)/最短距离显示函数 int a,b,c,d,q=0; a=sight2;if(a!=sight1)printf(nt从%s到%s的最短路径是,G.ve*sight1.sight,G.ve*sight2.sight);printf(t(最短距离为 %d.m)nnt,Da);printf(t%s,G.ve*sight1.sight);d=sight1;for(c=0;cNUM;+c)Pasight1=0;for(b=0;bNUM;b+)if(G.arcsdb%s,G.ve*b.sight);q=q+1;Pab=0;d=b;if(q%8=0) printf(n);void main()/主界面最短路线查询显示函数int v0,v1;char e;char ck;CreateMGraph(NUM);dosystem(cls);ck=Menu();switch(ck)case 1: gate:system(cls);Map();doprintf(nnttt请选择出发地序号113：);scanf(%d,&v0);if(v013)printf(nntttt输入错误!n);while(v013);doprintf(ttt请选择目的地序号113：);scanf(%d,&v1);if(v113|v1=v0)printf(nntttt输入错误!n);while(v113|v1=v0);ShortestPath(v0);Display(v0,v1);printf(nntttt按回车键继续,按e退回首页n);getchar();scanf(%c,&e);if(e=e)break;goto gate;case2:system(cls);Info();printf(nntttt按回车键返回首页.n);getchar();getchar();break;while(ck!=e);四、程序调试及运行结果贴图5、 总结通过这次设计，是我得以更好的掌握C语言的编程，对一些算法思想和实现方法有了更深的了解。在设计中，出现了一系列的问题，好屡次都差点坚持不下去，但最终还是完成了！当程序编译并且运行成功的那一刻，真的是非常的冲动。感教师平时上课时的教诲，可以使我更好的完成这次作业. z