数据结构课程设计报告-校园导游图

淮海工学院计算机工程学院课程设计报告设计名称：数据结构课程设计选题名称：校园导游图姓名：聂睿学号：2012122631专业班级：系（院）：计算机工程学院设计时间：2011.12.19~2011.12.30设计地点：软件工程实验室、教室指导教师评语：签名：年月日成绩：数据结构课程设计报告第1页，共页1．课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2．课程设计任务与要求：任务根据教材《数据结构-C语言描述》（耿国华主编）和参考书《数据结构题集（C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取，每班每题不得超过2人。学生自选课题学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。3．课程设计说明书数据结构课程设计报告第2页，共页一需求分析1．功能需求：用无向网表示淮海工学院的校园景点平面图，选取若干个淮海工学院有代表性的景点抽象成无向带权图，图中顶点表示校内各顶点，边上权值表示路径长度。2．性能需求：（1）为来访客人查询各景点的相关信息；（2）为来访客人查询图中任意两个景点间的最短路径（3）为来访客人查询图中任意两个景点间的所有路径（7）为来访客人输出对应编号景点的信息3．数据需求：建立无向图G，图中顶点ver表示主要景点，存放景点编号position、名称name、简介introduction等信息，图中边arc表示景点间的道路，存放路径长度信息distance。二概要设计1．ADTGraph数据对象V：V具有相同特性的数组元素的集合，称为顶点集数据关系R：R={VR}VR={x,y|P(x,y)^(x,y属于V)}ADTGraph{数据对象V：一个集合，该集合中的所有元素具有相同的特性数据关系R：R={VR}VR={x,y|P(x,y)^(x,y属于V)}基本操作：（1）initgraph(&G)；（2）creatgraph(mgraph&G)；（3）DeleteplanArc(mgraph&G)；（4）DeleteVertex(mgraph&G)；（5）enarc(mgraph&G)；（6）enverx(mgraph&G)；}ADTGraph基本操作：1、voiddisplaycampus(mgraphg)输出所有顶点信息（即将展示校园全景图）2、voidseaabout(mgraphG)根据输入编号用来查询各个景点信息3、voidshortestpath_Floyd(mgragh*g)用弗洛伊德阿算法求两个景点间最短路径4、voidAllpaths(mgragh*g)显示输入两个顶点间的所有路径14、intinitgraph(mgraph&G)校园导游图的初始化15、voidmain()主函数，可以调用子函数16、exit(0)退出程序三详细设计总体流程图：数据结构课程设计报告第3页，共页开始while循环控制语句输入kk=2,printmatrix(g)k=1,displaycampus(g)k=5,changegraph(g)k=4,seaabout(g)k=3,shortestpath_Floyd(&g)i=7,exit(0)k=6,Allpath(&g)结束1、创建无向网图算法的伪代码描述如下：intcreatgraph(mgraph&G)//构造图的邻接矩阵{输入矩阵对应的顶点数G.vernum和边数G.arcnum;for(i=0;iG.vernum;i++){输入对应的景点编号、景点名称、景点简介：}初始化任意景点的路径修改两顶点间的路径}2、输出学校平面图的算法的伪代码描述如下:voiddisplaycampus(mgraphG)//显示景点信息；{对应输出景点编号，景点名称，景点简介数据结构课程设计报告第4页，共页}3、按编号查询景点的相关信息的算法的伪代码描述如下:voidseaabout(mgraphG)//景点信息查询；{请输入要查询的景点编号n;if(n0||n11)该景点不存在，请重新输入：else根据编号输出对应的景点信息；}4、更改图的信息的算法的伪代码描述如下：intchangegraph(mgraphG){重新建图输入1删除结点输入2删除边输入3增加结点输入4增加边输入5更新图信息输入6打印邻接矩阵输入7返回程序输入8}5、求无向图的最短路径的算法的伪代码描述如下:voidshortestpath_Floyd(mgraph*G){定义数组三维p[10][10][10],用于寻找任意两景点间最短路径中的景点，定义二维数组D[10][10]用于存放两顶点间的最短路径;初始化任意两景点间的最短路径和最短路径上的景点{D[v][w]=G-arcs[v][w].adj;//把v,w路径的值放到D[v][w]中v,w是，v,w路径上的景点，所以p[v][w][v]=1;p[v][w][w]=1;}如果u到v,w之间的两条路径之和小于v,w之间的路径，则使D[v][w]=D[v][u]+D[u][w]若i是v,u上的最短路径的景点，或是u，w之间最短路径的景点，则i是v,w之间最短路径上的景点}intflag=1；while(flag){输入出发点和目的地的编号:k,jif(k0||kG-vernum||j0||jG-vernum)景点编号不存在!请重新输入出发点和目的地的编号:k,jif(k=0&&k顶点数目&&j=0&&j顶点数目)flag=0;}逐个输出最短路径上的景点名字以及总路线长}6、求无向图的所有路径的算法的伪代码描述如下:voidAllpath(mgraph*G){intv,w,k,j,flag=1,定义数组三维p[10][10][10],用于寻找任意两景点间路径中的景点，定义二维数组D[10][10]用于存放两顶点间的路径长度;数据结构课程设计报告第5页，共页while(flag){输入出发点和目的地的编号k,j;if(k0||k顶点数目||j0||j顶点数目){重新输入出发点和目的地的编号:k,j;}D[v][w]=G-arcs[v][w].adj;//初始化数组D[v][w]{if(D[v][w]!=A)如果这两个顶点间存在路径，则使p[v][w]为1，否则为0；{p[v][w]=1;p[w][v]=1;}}if(p[k][j]==1)如果这两个景点间有路径，则输出路径中的所有景点和长度}7、增添路径的信息的算法的伪代码描述如下：intenarc(mgraph&G)//增加路径{输入增加边的起始点v0，终点v1，及边的长度distanceG.arcs[v0][v1].adj=G.arcs[v0][v1].adj=distance;设置增加的路径长度；}8、增添景点的信息的算法的伪代码描述如下：intenverx(mgraph&G)//增加结点{输入要添加的景点的信息：包括编号，名称，简介G.vernum++;增加一条边G.arcs[i][G.vernum-1].adj=G.arcs[i][G.vernum-1].adj=A;//修改矩阵信息return1;}9、删除路径的信息的算法的伪代码描述如下：intDeleteplanArc(mgraph&G)//删除图一条边；{输入要删除的一条边对应的两个顶点v0,v1调用locatevex函数找到这两个点的位置更改边的信息边数减少1；}10、删除景点的信息的算法的伪代码描述如下：intDeleteVertex(mgraph&G)//删除景点{输入要删除的景点编号v调用locatevex函数找到这个点的位置if(m0)数据结构课程设计报告第6页，共页重新输入if(m0){for(i=m;i景点数G.vernum;i++){更改景点的名称strcpy(G.vexs[i].name,G.vexs[i+1].name);更改顶点的简介strcpy(G.vexs[i].introduction,G.vexs[i+1].introduction);}}删除该景点所在矩阵的行删除该景点所在矩阵的G.vernum--;边数减少1}11、初始化导游图算法伪代码描述如下：intinitgraph(mgraph&G)//校园导游图的初始化{设置景点数G.vernum=10;设置路径数G.arcnum=15;//初始化景点平面图设置景点编号值，名称，简介初始化边矩阵}12、打印无向图邻接矩阵算法的伪代码描述如下：voidprintmatrix(mgraphG)//打印图的邻接矩阵；{根据路径的初始化信息输出一个n行n列的矩阵（n是景点的个数），矩阵中的元素是路径的长度，如果两景点间无长度，则输出0；}13、景点定位的算法的伪代码描述如下：intlocatevex(mgraphc,intv)//景点的定位{传入要查找的顶点位置v如果找到改点，返回改点}14、更新校园导游图景点信息算法的伪代码描述如下：intnewgraph(mgraph&G)//更新景点的信息{输入更改的景点数n;for(inti=0;in;i++)//修改景点信息{逐个输入景点的编号、景点的名称：、景点的简介}输入更改的路径数n;intdistance,v0,v1;输入更新的路径的信息数据结构课程设计报告第7页，共页for(i=0;in;i++)//修改路径信息{逐条输入起始景点编号v0、终点景点编号v1、路劲长度distance}}四设计与调试分析1.校园导游图景点介绍（输出各景点信息）：应输出所有景点的信息，如下：景点编号（position）景点名称(name)景点介绍(intoduction)0淮工主楼淮海工学院标志建筑，楼高10层1计算机楼计算机学院学生学习基地,楼高6层2行政楼校领导日常工作之处，楼高5层3图书馆楼高5层，藏书逾十万4文通楼文通楼，楼高6层，学生学习自习地点5文渊楼文渊楼，楼高5层，教师办公室6大活中心内设大量娱乐设施，学生周末娱乐场所7淮工西门淮工西门是车站，学生在这里坐公交到达火车的站8实验楼做实验的地点，楼高6层，内有大量先进实验仪器9体育馆学生体育锻炼地点实际输出的信息为：数据结构课程设计报告第8页，共页操作成功，与预期结果一致。2.打印校园导游图的邻接矩阵：操作成功，与预期结果一致。3、查询景点间最短路径：比如：查询景点1（计算机楼）和3（图书馆）之间的最短路径，预期结果应为：计算机楼—文通楼—图书馆，路径总长度为351520数据结构课程设计报告第9页，共页操作成功，与预期结果一致。4、景点信息查询：比如：查询景点为1的景点信息，预期结