校园导航问题课程设计论文.doc

摘 要校园导航要求每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径(最短路径)。要用“邻接矩阵”来存储各点间的距离，然后用Dijkstra算法求出最短路径。所以采用工程思想，将系统共分以下五个模块：节点数据结构类型、创建导航图函数、最短路径导航函数、查询函数声明、主菜单。关键字 校园导航 查询 Dijkstra算法目 录摘 要1校园导航问题61 问题分析与任务定义：62 数据结构描述与定义73 Dijkstra算法流程图84 程序运行调试95 结论11参考文献12附录：12校园导航问题1 问题分析与任务定义：本课程设计的内容为设计学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。如图1,图中已标出主要路线，各路线的长度如表1中所示。显然要解决这一问题要用“邻接矩阵”来存储各点间的距离，然后用Dijkstra求出最短路径。 7 图书馆1 会堂8 主楼0 分析测试中心 3 二教学楼6 足球场410号 楼2一教学楼9 学生食堂 5 篮球场图1：校园平面图01:200 03:20 07:100 08:10017:50 18:50 24:350 25:20026:100 29:150 34:290 36:20039:300 45:200 49:50 59:10067:200 78:100 表1：各景点距离单位：米（m）2 数据结构描述与定义1.节点数据结构类型#define Max 20000#define NUM 10typedef struct ArcCellint adj; /* 相邻接的景点之间的路程 */ArcCell; /* 定义边的类型 */typedef struct VertexTypeint number; /* 景点编号 */char* sight; /* 景点名称 */char* info; /* 景点描述 */VertexType; /* 定义顶点的类型 */typedef structVertexType vexNUM; /* 图中的顶点，即为景点 */ArcCell arcsNUMNUM; /* 图中的边，即为景点间的距离 */int vexnum,arcnum; /* 顶点数，边数 */MGraph; /* 定义图的类型 */2.创建导航图函数void CreateUDN(int v,int a)函数描述：主要将每个节点进行命名、每个顶点到其他所有定点的路径值用邻接矩阵进行存储。例：G.vex0.sight=“分析测试中心”； 作用：使0号定点命名为“分析测试中心”；G.=“老师办公和学生做实验”；作用：0号描述为“老师办公和学生做实验”；G.arcs01.adj=G.arcs10.adj=200；作用：使0号节点到1号节点的路径赋值为200，应为是无向图，所以1号节点到0号节点的路径长度也应赋值为200。3.最短路径导航函数void ShortestPath(int num)函数描述：用Dijkstra算法求无向网G的V0定点到其余定点V的最短路径Pv及其带权长度Dv。若Pvw为True，则w是从V0到V当前求得最短路径上的顶点。Finalv为True当且仅当VS，即已经求得从V0到V的最短路径。4.查询函数声明char SearchMenu()void HaMiTonian(int)函数描述：哈密尔顿图的遍历。5.主菜单char Menu()描述;显示导航图中的所有导航节点，能够快速方便的对各个地点进行导航。3 Dijkstra算法流程图4 程序运行调试 本程序用microsoft visual c+ 6.0运行结果如下：主界面：景点路径查询景点信息查询推荐参观路线6 结论 本系统实现了在大量的校园景点中任意指定两个景点就能给出最短路径。并且设计save()保存函数，和load()下载函数，分别用来保存创建的导航数据，和下载其它导航数据，这样这个系统才能更加实用，void createadj()原来的函数原型为arcnode *createdj()函数中用链表结构把adjmatrix的数据都保存其中，这样就能实现数据的保存，但随之要把ijkstra中的adjmatrix转换成用arcnode 指针的形式进行表示，因为只有这样，下载后的数据才能使用。参考文献1数据结构（C语言版），严蔚敏，清华大学出版社，20052算法设计与分析，王晓东主编，清华大学出版社，20053汪诗林等译，数据结构、算法与应用，（美）Sartaj Sahni著，机械工业出版社， 19994数据结构与算法分析，CLIFFORD A. SHAFFER著，张铭、刘晓丹译，电子工业出版社，19985 谭浩强 .C程序设计Z.北京：清华大学出版社，2001. 6 薛万鹏.C语言程序设计教程Z.北京：机械工业出版社，2000.7 鲁岩.实用C语言及其程序设计Z.大连：大连理工大学出版社，1993.8 袁征.C语言编程序技巧程序集Z.北京：电子工业出版社，1993.附 录源程序：#include string.h #include stdio.h #include stdio.h#include malloc.h#include stdlib.h#define Max 20000#define NUM 10typedef struct ArcCellint adj; /* 相邻接的景点之间的路程 */ArcCell; /* 定义边的类型 */typedef struct VertexTypeint number; /* 景点编号 */char* sight; /* 景点名称 */char* info; /* 景点描述 */VertexType; /* 定义顶点的类型 */typedef structVertexType vexNUM; /* 图中的顶点，即为景点 */ArcCell arcsNUMNUM; /* 图中的边，即为景点间的距离 */int vexnum,arcnum; /* 顶点数，边数 */MGraph; /* 定义图的类型 */MGraph G; /* 把图定义为全局变量 */int PNUMNUM; /* */long int DNUM; /* 辅助变量存储最短路径长度 */int x9=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 NextValue(int); void display(); /* 显示遍历结果 */void main() /* 主函数 */ int v0,v1; char ck;CreateUDN(NUM,11);do ck=Menu(); switch(ck) case 1: system(cls); narrate(); /* 输出景点列表 */ printf(nnttt请选择起点景点（09）：); scanf(%d,&v0); printf(ttt请选择终点景点（09）：); scanf(%d,&v1); ShortestPath(v0); /* 计算两个景点之间的最短路径 */ output(v0,v1); /* 输出结果 */ printf(nntttt请按任意键继续.n); getchar(); getchar(); break; case 2:search(); break; case 3: system(cls); narrate(); x0=1; HaMiTonian(1); printf(nntttt请按任意键继续.n); getchar(); getchar(); break; ;while(ck!=e);char Menu() /* 主菜单 */char c;int flag;do flag=1; system(cls); narrate(); /* 输出景点列表 */ printf(ntttn); printf(ttt n); printf(ttt 1、查询景点路径 n); printf(ttt 2、查询景点信息 n); printf(ttt 3、推荐参观路线 n); printf(ttt e、退出 n); printf(ttt n); printf(tttn); printf(tttt请输入您的选择：); scanf(%c,&c); if(c=1|c=2|c=3|c=e) flag=0;while(flag);return c; char SearchMenu() /* 查询子菜单 */char c;int flag;do flag=1; system(cls); narrate(); printf(ntttn); printf(ttt n); printf(ttt 1、按照景点编号查询 n); printf(ttt 2、按照景点名称查询 n); printf(ttt e、返回 n); printf(ttt n); printf(tttn); printf(tttt请输入您的选择：); 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 name20;do system(cls); c=SearchMenu(); switch (c) case 1: system(cls); narrate(); printf(nntt请输入您要查找的景点编号：); scanf(%d,&num); for(i=0;iNUM;i+) if(num=G.vexi.number) printf(nnttt您要查找景点信息如下:); printf(nnttt%-25snn,G.); printf(nttt按任意键返回.); getchar(); getchar(); break; if(i=NUM) printf(nnttt没有找到！); printf(nnttt按任意键返回.); getchar(); getchar(); break; case 2: system(cls); narrate(); printf(nntt请输入您要查找的景点名称：); scanf(%s,name); for(i=0;iNUM;i+) if(!strcmp(name,G.vexi.sight) printf(nnttt您要查找景点信息如下:); printf(nnttt%-25snn,G.); printf(nttt按任意键返回.); getchar(); getchar(); break; if(i=NUM) printf(nnttt没有找到！); printf(nnttt按任意键返回.); getchar(); getchar(); break; while(c!=e);void CreateUDN(int v,int a) /* 造图函数 */ int i,j;G.vexnum=v; /* 初始化结构中的景点数和边数 */G.arcnum=a;for(i=0;iG.vexnum;+i) G.vexi.number=i; /* 初始化每一个景点的编号 */* 初始化没一个景点名及其景点描述 */G.vex0.sight=分析测试中心; G.=老师办公和学生做实验;G.vex1.sight=会堂; G.=业余活动，举办各种晚会。;G.vex2.sight=一教学楼; G.=老教学楼;G.vex3.sight=二教学楼; G.=新教学楼;G.vex4.sight=10号楼; G.=学生宿舍;G.vex5.sight=篮球场; G.=打篮球及比赛;G.vex6.sight=足球场; G.=踢足球及举办典礼;G.vex7.sight=图书馆; G.=借还书;G.vex8.sight=主楼; G.=行政楼;G.vex9.sight=学生食堂; G.=学生吃饭的地方;/* 这里把所有的边假定为20000，含义是这两个景点之间是不可到达 */for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum;+j) G.arcsij.adj=Max; /*下边是可直接到达的景点间的距离，由于两个景点间距离是互相的， 所以要对图中对称的边同时赋值。 */ G.arcs01.adj=G.arcs10.adj=200; G.arcs03.adj=G.arcs30.adj=20; G.arcs07.adj=G.arcs70.adj=100; G.arcs08.adj=G.arcs80.adj=100; G.arcs17.adj=G.arcs71.adj=50; G.arcs18.adj=G.arcs81.adj=50; G.arcs24.adj=G.arcs42.adj=350; G.arcs25.adj=G.arcs52.adj=200; G.arcs26.adj=G.arcs62.adj=100; G.arcs29.adj=G.arcs92.adj=150; G.arcs34.adj=G.arcs43.adj=290; G.arcs36.adj=G.arcs63.adj=200; G.arcs39.adj=G.arcs93.adj=300; G.arcs45.adj=G.arcs54.adj=200; G.arcs49.adj=G.arcs94.adj=50; G.arcs59.adj=G.arcs95.adj=100; G.arcs67.adj=G.arcs76.adj=200; G.arcs78.adj=G.arcs87.adj=100;void narrate() /* 说明函数 */int i,k=0;printf(ntt*欢迎使用校园导航程序*n);printf(t_n);printf(tt景点名称tt|t景点描述n);printf(t_|_n);for(i=0;iNUM;i+) printf(t%c (%2d)%-10stt|t%-25s%cn,3,i,G.vexi.sight,G.,3); /* 输出景点列表 */ k=k+1;printf(t_|_n);void ShortestPath(int num) /* 迪杰斯特拉算法最短路径函数 num为入口点的编号 */ int v,w,i,t; /* i、w和v为计数变量 */int finalNUM; /* */int min;for(v=0;vNUM;v+) finalv=0; /* 假设从顶点num到顶点v没有最短路径 */ Dv=G.arcsnumv.adj;/* 将与之相关的权值放入D中存放 */ for(w=0;wNUM;w+) /* 设置为空路径 */ Pvw=0; if(Dv20000) /* 存在路径 */ Pvnum=1; /* 存在标志置为一 */ Pvv=1; /* 自身到自身 */ Dnum=0;finalnum=1; /* 初始化num顶点属于S集合 */ /* 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合 */for(i=0;iNUM;+i) /* 其余G.vexnum-1个顶点 */ min=Max; /* 当前所知离顶点num的最近距离 */ for(w=0;wNUM;+w) if(!finalw) /* w顶点在v-s中 */ if(Dwmin) /* w顶点离num顶点更近 */ v=w; min=Dw; finalv=1; /* 离num顶点更近的v加入到s集合 */ for(w=0;wNUM;+w) /* 更新当前最短路径极其距离 */ if(!finalw&(min+G.arcsvw.adj)Dw)/* 不在s集合，并且比以前所找到的路径都短就更新当前路径 */ Dw=min+G.arcsvw.adj; for(t=0;tNUM;t+) Pwt=Pvt; Pww=1; void output(int sight1,int sight2) /* 输出函数 */int a,b,c,d,q=0;a=sight2; /* 将景点二赋值给a */if(a!=sight1) /* 如果景点二不和景点一输入重合，则进行. */ printf(nt从%s到%s的最短路径是,G.vexsight1.sight,