数据结构课程设计_校园导航系统 _课程设计报告.doc

成绩南京工程学院课程设计说明书(论文)题 目 校园导航系统 课 程 名 称 数 据 结 构 院 系 通信工程学院 专 业 信息工程 班 级 学 生 姓 名 学 号 设 计 地 点 指 导 教 师 设计起止时间：2008 年12月29 日至 年 月 日目 录1课程设计题目12软件功能描述13软件总体设计131数据结构描述与定义132模块设计34测试结果与分析45课程设计总结5附录：源程序清单6151课程设计题目校园导航系统2软件功能描述在近一个星期的努力下，我编写的校园导航系统软件终于能够成功完成。采用工程思想，将系统共分一下几个模块:数据结构定义模块、导航图建立模块、求最短路径模块、主菜单；下面是具体各功能简单的实际应用： 数据结构定义模块：模块定义了导航图中各个节点的基本结构类型，主要采用邻接矩阵的存储结构来真实反映各节点到其他所有节点的路径长度（权值大小）。 导航图建立模块：采用上述结构体类型对导航图中每个节点进行赋值。包括：各定点的名称（地点名），各个节点到其他所有节点的真实路径长度（赋权值）。 求最短路径模块： 本模块的基本思想是采用迪杰斯特拉算法求最短路径。次模块是本校园导航系统的核心模块，求两点间的最短路径与求一点到其他所有点最短路径两个子功能均是在最短路径算法模块的基础上进行调用，进而实现导航功能。 主菜单：主菜单中主要是显示导航图中的所有导航节点，能够快速方便的对各个地点进行导航。以上程序的几个模块，构成了校园导航系统的基本组成部分，程序运行良好，达到了课程设计的基本要求。由于所学知识有限，功能各个方面还有欠妥之处，希望得到指出与改正。3软件总体设计31数据结构描述与定义1. 节点数据结构类型：#define MAX_V 30 /最大顶点个数typedef structchar* vexsMAX_V; /顶点向量int arcsMAX_VMAX_V;/邻接矩阵int vexnum,arcnum;/图的当前顶点数和弧数MGraph;2. 创建导航图函数：int CreateUDN(MGraph &G)函数描述：主要将每个节点进行命名、每个顶点到其他所有定点的路径值用邻接矩阵进行存储。例：G.vexs0 = 小北门; 作用：使0号定点命名为“小北门”； G.arcs01 = G.arcs10 =550;作用：使0号节点到1号节点的路径赋值为550，应为是无向图，所以1号节点到0号节点的路径长度也应赋值为550；3. 最短路径导航函数：void ShortPath(MGraph &G,int v0,int pMAX_VMAX_V,int d)函数描述：用Dijkstra算法求无向网G的V0定点到其余定点V的最短路径Pv及其带权长度Dv。若Pvw为True，则w是从V0到V当前求得最短路径上的顶点。Finalv为True当且仅当VS，即已经求得从V0到V的最短路径。4. 导航菜单函数声明void menu()函数描述：输出各个节点的编号，放便导航。32模块设计以下为迪杰斯特拉算法流程图：4测试结果与分析很高兴，这次自己设计的校园导航系统能够按照预先的设想正常运行，经过反复的调试和优化程序，使得程序的源代码更规范且易于理解，程序的输出界面更为友好，操作更简便易行。测试内容： 系统登陆界面： 导航功能1两点最短距离导航测试结果如下 导航功能2某点到其他所有点的距离5课程设计总结经过一个学期对数据结构课程的学习，我能够掌握数据结构所教会我的对待问题的方法，以及遇到问题时如何抽象出一个合理的数据结构类型。数据结构教会我的不但是每一个算法，更多的是如何解决问题的方法。例如，在本次课程设计中我做的是校园导航系统，对于校园导航问题的关键是最短路径的问题，在教材中有算法迪杰斯特拉求最短路径问题，在花了几天时间后，终于能够将算法的整个流程弄清楚，在对各个定点的存储上采用邻接矩阵的方法，在寻找各个点到其他所有点的关系的时候更为方便直观。在课程设计中遇到的一系列问题都能够在老师和同学的指导下及时解决。最后，感谢一年来为我们付出努力的老师们，感谢给过我指导意见的同学们，在这一年对数据结构的学习中，真的收获颇多，为我以后继续学习计算机的基础课程打下了坚实的基础。附录：源程序清单type.h /定义每个顶点的结构类型#include#define MAX_V 30 /最大顶点个数#define INFINITY 32767 /最大值typedef structchar* vexsMAX_V; /顶点向量int arcsMAX_VMAX_V;/邻接矩阵int vexnum,arcnum;/图的当前顶点数和弧数MGraph;Creat.cpp /创建无向图#includetype.hint CreateUDN(MGraph &G)/采用数组(邻接矩阵)表示法,构造无向网G.int i = 0,j=0;G.vexnum = 27; G.arcnum = 51;G.vexs0 = 小北门; G.vexs1 = 大北门; G.vexs2 = 东区田径场;G.vexs3 = 东区宿舍楼;G.vexs4 = 北区宿舍楼; G.vexs5 = 北区田径场;G.vexs6 = 北区超市; G.vexs7 = 北区食堂; G.vexs8 = 基础实验楼;G.vexs9 = 东西教学楼;G.vexs10 = 文理楼; G.vexs11 =医务室;G.vexs12 = 亿恒酒店; G.vexs13 = 艺术楼; G.vexs14 = 南教学楼;G.vexs15 = 自动化学院; G.vexs16 = 图书馆; G.vexs17 = 学海湾;G.vexs18 = 东区食堂; G.vexs19 = 东区超市; G.vexs20 = 东门;G.vexs21 = 经管楼; G.vexs22 = 信息楼; G.vexs23 = 天印湖;G.vexs24 = 西门; G.vexs25 = 行政楼; G.vexs26 = 南门;for(i=0;iG.vexnum;i+) /初始化路径长度for(j=0;jG.vexnum;j+)if(i=j)G.arcsij=0;else G.arcsij=INFINITY;/为每一条边赋权G.arcs01 = G.arcs10 =550;G.arcs04 = G.arcs40 =160 ;G.arcs05 = G.arcs50 =600;G.arcs12 = G.arcs21 =80;G.arcs23 = G.arcs32 =100; G.arcs211 = G.arcs112=110;G.arcs210 = G.arcs102 =130; G.arcs311 = G.arcs113 = 100;G.arcs312 = G.arcs123 = 220; G.arcs45 = G.arcs54 = 300; G.arcs47 = G.arcs74 = 300; G.arcs46 = G.arcs64 = 210;G.arcs57 = G.arcs75 = 300; G.arcs515 = G.arcs155 = 500; G.arcs67 = G.arcs76 = 60;G.arcs69 = G.arcs96 = 170; G.arcs78 = G.arcs87 = 230;G.arcs89 = G.arcs98 = 35; G.arcs814 = G.arcs148 = 35;G.arcs815 = G.arcs158 = 350; G.arcs816 = G.arcs168 = 200;G.arcs910 = G.arcs109 = 200; G.arcs914 = G.arcs149 = 100;G.arcs1011= G.arcs1110 = 50; G.arcs1013= G.arcs1310 = 50;G.arcs1112= G.arcs1211 = 85;G.arcs1213= G.arcs1312 = 160; G.arcs1218= G.arcs1812 = 20;G.arcs1219= G.arcs1912 = 130;G.arcs1317= G.arcs1713 = 100;G.arcs1318= G.arcs1813 = 230; G.arcs1417= G.arcs1714 = 100;G.arcs1516= G.arcs1615 = 310; G.arcs1521= G.arcs2115 = 250;G.arcs1524= G.arcs2415 = 400; G.arcs1617= G.arcs1716 = 160;G.arcs1622= G.arcs2216 = 200; G.arcs1621= G.arcs2116 = 100;G.arcs1623= G.arcs2316 = 200; G.arcs1624= G.arcs2416 = 400;G.arcs1723= G.arcs2317 = 140;G.arcs1819= G.arcs1918 = 90; G.arcs1820 = G.arcs2018 = 320;G.arcs1920 = G.arcs2019 = 350; G.arcs2026 = G.arcs2620 = 570;G.arcs2124 = G.arcs2421 = 260; G.arcs2223 = G.arcs2322 = 85;G.arcs2225 = G.arcs2522 = 190; G.arcs2325 = G.arcs2523 = 100;G.arcs2326 = G.arcs2623 = 620; G.arcs2425 = G.arcs2524 = 130;return 1;Short_path.cpp /采用迪杰斯特拉算法，求最短路径#includetype.hextern have30;void ShortPath(MGraph &G,int v0,int pMAX_VMAX_V,int d) /迪杰斯特拉发求最短路径int v,w,i,j,min;int finalMAX_V;int k=1;for(v=0;vG.vexnum;+v)/初始化finalv=0;dv=G.arcsv0-1v;for(w=0;wG.vexnum;+w)pvw=0;if(dvINFINITY)pvv0-1=1;pvv=1;dv0-1=0;finalv0-1=1;have0=v0-1;for(i=1;iG.vexnum;+i)/其余的vexnum-1个顶点min=INFINITY;for(w=0;wG.vexnum;+w)if(!finalw)if(dwmin) /如有W点离更近v=w;min=dw;finalv=1;havek=v;k+;for(w=0;wG.vexnum;+w)/更新当前最短路径及距离if(!finalw&(min+G.arcsvwdw)dw=min+G.arcsvw;for(j=0;jG.vexnum;j+)pwj=pvj;pww=1;Menu.cpp /程序登陆界面#includevoid menu()printf( 导航主菜单 n);printf( (1) 小北门 (2) 大北门 (3) 东区田径场 n);printf( (4) 东区宿舍楼 (5) 北区宿舍楼 (6) 北区田径场 n);printf( (7) 北区超市 (8) 北区食堂 (9) 基础实验楼 n);printf( (10) 东西教学楼 (11) 文理楼 (12) 医务室 n);printf( (13) 亿恒酒店 (14) 艺术楼 (15) 南教学楼 n);printf( (16) 自动化学院 (17) 图书馆 (18) 学海湾 n);printf( (19) 东区食堂 (20) 东区超市 (21) 东门 n);printf( (22) 经管楼 (23) 信息楼 (24) 天印湖 n);printf( (25) 西门 (26) 行政楼 (27) 南门 n);printf( nn);printf(请选择导航功能：n);printf(n);printf( (1) 两点最短距离导航 n);printf( (2) 某点到其他所有点的最短距离 n);printf( (3) 退出导航系统 n);printf(n);Main.cpp /主函数文件#include #include #include #include type.hint have30;int CreateUDN(MGraph &G);/创建导航图函数声明void ShortPath(MGraph &G,int v0,int pMAX_VMAX_V,int d);/最短路径导航函数声明void menu();/导航菜单函数声明void main() MGraph G;int v0,i,end,j;int PMAX_VMAX_V;int DMAX_V;int choice,choice1;printf(n);printf(n 欢迎光临南京工程学院，祝旅程愉