《数据结构课程设计报告校园导游图》由会员分享，可在线阅读，更多相关《数据结构课程设计报告校园导游图（40页珍藏版）》请在金锄头文库上搜索。
1、淮 海 工 学 院 计算机工程学院课程设计报告设计名称： 数据结构课程设计 选题名称： 校园导游图 姓 名： 学 号： 专业班级： 系 （院）： 计算机工程学院 设计时间： 2011.12.192011.12.30 设计地点： 软件工程实验室、教室 成绩：指导教师评语： 签名： 年 月 日数据结构课程设计报告 第 10 页，共 页1课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系
2、统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务根据教材数据结构-C语言描述（耿国华主编）和参考书数据结构题集（C语言版）（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取，每班每题不得超过2人。学生自选课题学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在1
3、8周前报课程设计指导教师批准方可生效。要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少
4、于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3课程设计说明书一 需求分析1功能需求：用无向网表示淮海工学院的校园景点平面图，选取若干个淮海工学院有代表性的景点抽象成无向带权图，图中顶点表示校内各顶点，边上权值表示路径长度。2性能需求：（1）为来访客人查询各景点的相关信息；（2）为来访客人查询图中任意两个景点间的最短路径（3）为来访客人查询图中任意两个景点间的所有路径（4）为来访客人修改图中顶点和边的信息（5）为来访客人增加景点和路径（6）为来访客人删除景点和路径（7）为来访客人输出对应编号景点的信息 3数据需求：建立无向图G，图中顶点ver表示主要景点，存
5、放景点编号position、名称name、简介introduction等信息，图中边arc表示景点间的道路，存放路径长度信息distance。 二 概要设计1ADT Graph数据对象V：V具有相同特性的数组元素的集合，称为顶点集数据关系R：R=VR VR=|P(x,y)(x,y属于V)ADT Graph 数据对象V：一个集合，该集合中的所有元素具有相同的特性 数据关系R：R=VR VR=|P(x,y)(x,y属于V) 基本操作：（1）initgraph(&G)；（2） creatgraph(mgraph &G)；（3） DeleteplanArc(mgraph &G) ；（4）DeleteV
6、ertex(mgraph &G)；（5） enarc(mgraph &G)；（6） enverx(mgraph &G)；ADT Graph基本操作：1、void displaycampus(mgraph g)输出所有顶点信息（即将展示校园全景图）2、void seaabout(mgraph G)根据输入编号用来查询各个景点信息3、void shortestpath_Floyd(mgragh *g)用弗洛伊德阿算法求两个景点间最短路径4、void Allpaths(mgragh *g)显示输入两个顶点间的所有路径5、int changegraph(mgraph G) 更改图的信息6、int lo
7、catevex(mgraph c,int v)景点的定位7、void creatgraph(mgraph &G) 创建图的邻接矩阵8、void printmatrix(mgraph G) 打印图的邻接矩阵；9、int DeleteplanArc(mgraph &G) 删除图一条边；10、int DeleteVertex(mgraph &G) 删除景点11、int enarc(mgraph &G) 增加路径12、int enverx(mgraph &G) 增加结点13、int newgraph(mgraph &G) 更新景点的信息14、int initgraph(mgraph& G) 校园导游图
8、的初始化15、void main( )主函数，可以调用子函数16、exit(0) 退出程序各程序模块之间的调用关系主函数可调用子程序：1，2，3，4，5，8，14，16子程序5可调用子程序:,7,8，9,10,11,12,13子程序9,10,11,12,13可调用子程序:6三 详细设计总体流程图：1、创建无向网图算法的伪代码描述如下：int creatgraph(mgraph &G)/构造图的邻接矩阵输入矩阵对应的顶点数G.vernum和边数G.arcnum;for(i=0;iG.vernum;i+)输入对应的景点编号、景点名称、景点简介：初始化任意景点的路径修改两顶点间的路径2、输出学校平面
9、图的算法的伪代码描述如下:void displaycampus(mgraph G)/显示景点信息；对应输出景点编号，景点名称，景点简介3、按编号查询景点的相关信息的算法的伪代码描述如下:void seaabout(mgraph G)/景点信息查询；请输入要查询的景点编号n;if(n11)该景点不存在，请重新输入：else 根据编号输出对应的景点信息；4、更改图的信息的算法的伪代码描述如下 ：int changegraph(mgraph G)重新建图输入1 删除结点输入2 删除边输入3 增加结点输入4 增加边输入5 更新图信息输入6 打印邻接矩阵输入7 返回程序 输入8 5、求无向图的最短路径的
10、算法的伪代码描述如下:void shortestpath_Floyd(mgraph *G) 定义数组三维p101010,用于寻找任意两景点间最短路径中的景点，定义二维数组D1010 用于存放两顶点间的最短路径; 初始化任意两景点间的最短路径和最短路径上的景点 Dvw=G-arcsvw.adj;/把v,w路径的值放到Dvw中 v,w是，v,w路径上的景点，所以pvwv=1;pvww=1; 如果u到v,w之间的两条路径之和小于v,w之间的路径，则使Dvw=Dvu+Duw 若i是v,u上的最短路径的景点，或是u，w之间最短路径的景点，则i是v,w之间最短路径上的景点int flag=1；while(
11、flag) 输入出发点和目的地的编号:k, jif(kG-vernum|jG-vernum)景点编号不存在!请重新输入出发点和目的地的编号:k, j if(k=0&k=0&j顶点数目) flag=0; 逐个输出最短路径上的景点名字以及总路线长6、求无向图的所有路径的算法的伪代码描述如下:void Allpath(mgraph *G)int v,w,k,j,flag=1,定义数组三维p101010,用于寻找任意两景点间路径中的景点，定义二维数组D1010 用于存放两顶点间的路径长度; while(flag) 输入出发点和目的地的编号k,j; if(k顶点数目|jarcsvw.adj;/初始化数组
12、Dvwif(Dvw!=A)如果这两个顶点间存在路径，则使pvw为1，否则为0； pvw=1;pwv=1; if(pkj=1)如果这两个景点间有路径，则输出路径中的所有景点和长度 7、增添路径的信息的算法的伪代码描述如下：int enarc(mgraph &G)/增加路径输入增加边的起始点v0，终点v1，及边的长度distance G.arcsv0v1.adj=G.arcsv0v1.adj=distance;设置增加的路径长度；8、增添景点的信息的算法的伪代码描述如下：int enverx(mgraph &G)/增加结点输入要添加的景点的信息：包括编号，名称，简介G.vernum+;增加一条边G.arcsiG.vernum-1.adj=G.arcsiG.vernum-1.adj=A;/修改矩阵信息return 1;9、删除路径的信息的算法的伪代码描述如下：int DeleteplanArc(mgraph &G)/删除图一条边；输入要删除的一条边对应的两个顶点v0,v1 调用locatevex函数找到这两个点的位置 更改边的信息边数减少1；10、删除景点的信息的算法的伪代码描述如下：int DeleteVertex(mgraph &G)/删除景点输入要删除的景点编号v调用locatevex函数找到这个点的位置if(m0)
