数据结构课程设计报告_校园导游图.doc

淮 海 工 学 院 计算机工程学院课程设计报告设计名称： 数据结构课程设计 选题名称： 校园导游图 姓 名： 聂睿 学号： 2012122631 专业班级： 系 （院）： 计算机工程学院 设计时间： 2011.12.192011.12.30 设计地点： 软件工程实验室、教室 成绩：指导教师评语： 签名： 年 月 日数据结构课程设计报告 第 39 页，共 页1课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务根据教材数据结构-C语言描述（耿国华主编）和参考书数据结构题集（C语言版）（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取，每班每题不得超过2人。学生自选课题学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3课程设计说明书一 需求分析1功能需求：用无向网表示淮海工学院的校园景点平面图，选取若干个淮海工学院有代表性的景点抽象成无向带权图，图中顶点表示校内各顶点，边上权值表示路径长度。2性能需求：（1）为来访客人查询各景点的相关信息；（2）为来访客人查询图中任意两个景点间的最短路径（3）为来访客人查询图中任意两个景点间的所有路径（7）为来访客人输出对应编号景点的信息 3数据需求：建立无向图G，图中顶点ver表示主要景点，存放景点编号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）DeleteVertex(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)显示输入两个顶点间的所有路径14、int initgraph(mgraph& G) 校园导游图的初始化15、void main( )主函数，可以调用子函数16、exit(0) 退出程序三 详细设计总体流程图：1、创建无向网图算法的伪代码描述如下：int creatgraph(mgraph &G)/构造图的邻接矩阵输入矩阵对应的顶点数G.vernum和边数G.arcnum;for(i=0;iG.vernum;i+)输入对应的景点编号、景点名称、景点简介：初始化任意景点的路径修改两顶点间的路径2、输出学校平面图的算法的伪代码描述如下: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、求无向图的最短路径的算法的伪代码描述如下: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(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;/初始化数组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)for(i=m;i景点数G.vernum ;i+)更改景点的名称strcpy(G.,G.vexs i+1.name);更改顶点的简介strcpy(G.roduction,G.vexsi+1.introduction);删除该景点所在矩阵的行 删除该景点所在矩阵的 G.vernum-;边数减少111、初始化导游图算法伪代码描述如下：int initgraph(mgraph& G)/校园导游图的初始化设置景点数G.vernum=10;设置路径数G.arcnum=15;/初始化景点平面图设置景点编号值，名称，简介初始化边矩阵12、打印无向图邻接矩阵算法的伪代码描述如下：void printmatrix(mgraph G)/打印图的邻接矩阵；根据路径的初始化信息输出一个n行n列的矩阵（n是景点的个数），矩阵中的元素是路径的长度，如果两景点间无长度，则输出0；13、景点定位的算法的伪代码描述如下：int locatevex(mgraph c,int v)/景点的定位传入要查找的顶点位置v如果找到改点，返回改点14、更新校园导游图景点信息算法的伪代码描述如下：int newgraph(mgraph &G)/更新景点的信息输入更改的景点数n;for(int i=0;in;i+)/修改景点信息逐个输入景点的编号、景点的名称：、景点的简介输入更改的路径数n;int distance,v0,v1;输入更新的路径的信息for(i=0;i 文通楼 图书馆，路径总长度为35操作成功，与预期结果一致。4、景点信息查询：比如：查询景点为1的景点信息，预期结果应为：景点序号（position）景点名称(name)景点介绍(intoduction)1计算机楼计算机学院学生学习基地,楼高6层与预期结果一致。查询成功。5、更改图的信息：更改图信息主页面：5.1重新建图 比如重新建一个有3个景点和3条路径的无向图：景点信息分别为：景点序号（position）景点名称(name)景点介绍(intoduction)0计算机楼信息中心1第一食堂饮食中心2B#宿舍男生宿舍矩阵关系为：015251505025500 与预期结果一致，重新建图成功。5.2删除景点：比如删除景点编号为1的景点：则输出的矩阵中应失去原第一行第一列，并且其信息不再出现在校园导游中：删除景点前的图信息：删除景点前的矩阵：删除景点后的图的信息和矩阵：与预期结果一致，删除景点成功。5.3删除两景点间的路径：比如删除编号为0和2的两景点间的路径，则打印出来的矩阵在第0行第2列和第2行第0列的值应为0。删除路径前的矩阵： 删除路径后的矩阵： 与预期结果一致，删除路径成功。54增加景点信息比如增加一个景点，其信息为：景点序号（position）景点名称(name)景点介绍(intoduction)10A#7宿舍楼计算机学院女生宿舍对应的矩阵中应增加一行一列，第10行和第10列上所有元素都应为0，输出的图信息中最后应增加上述的信息。增加景点前的图信息：增加景点前的矩阵：增加景点后的图信息和矩阵：与预期结果一致，增加景点成功。5.5增加一条路径比如在景点0和4之间加一条长度为10的路径，则在第0行第4列与第4行第0列元素应为10。增加路径前的矩阵： 增加路径后的矩阵： 与预期结果一致，增加路径成功。5.6更新图信息比如要更新一个景点和一条路径的信息，将景点信息：景点序号（position）景点名称(name)景点介绍(intoduction)1计算机楼计算机学院学生学习基地,楼高6层改为：景点序号（position）景点名称(name)景点介绍(intoduction)1B#8男生宿舍更改顶点编号为0和3路径长度，路径由30改为15。更改后的图中编号为1的信息应变为：景点序号（position）景点名称(name)景点介绍(intoduction)1B#8男生宿舍矩阵中第0行第3列和第3行第0列元素应由30变为15.更改景点前的图信息：更改路径前的矩阵： 更新后的图信息和矩阵：6、查找两顶点间的所有路径比如查找1,3两点间的所有路径，所有路径为： 五 用户手册1、进入本系统后，随即显示系统主菜单页面。用户可在此菜单下输入各子菜单对应的数字，并按回车键，执行相应的子菜单命令。2、查询、修改、增加、删除景点以及景点间的路径，都是通过输入景点的编号来实现的，进入主菜单时，用户最好先选择“1、学校景点介绍”和“2、打印邻接矩阵”，方便用户了解景点信息以及路径信息。六 测试成果操作主界面查看淮工景点平面图打印无向图邻接矩阵查询两顶点间的最短路径按编号查询景点信息查询两顶点间的所有路径： 更改图信息：退出系统七 附录（源程序清单）#include #include#include#includeusing namespace std;#define max_ver_num 20#define OK 1#define FALSE 0#define Error -1#define A 1000#define TRUE 1typedef struct arcnode/设置边的权值信息 int adj;/路径权值arcnode,adjarcsmax_ver_nummax_ver_num;typedef struct verdata/设置景点信息int position;char name60;char introduction1000;verdata;typedef struct mgraph verdata vexsmax_ver_num; adjarcs arcs; int vernum,arcnum;mgraph;/全局变量int visited20;int d35;mgraph g;int initgraph(mgraph& G)/校园导游图的初始化int i,j;G.vernum=10;G.arcnum=20;/初始化景点平面图for(i=0;iG.vernum;i+)G.vexsi.position=i;strcpy(G.,淮工主楼); strcpy(G.,计算机楼);strcpy(G.,行政楼); strcpy(G.,图书馆); strcpy(G.,文通楼); strcpy(G.,文渊楼);strcpy(G.,大活中心); strcpy(G.,淮工西门); strcpy(G.,实验楼); strcpy(G.,体育馆);strcpy(G.roduction,淮海工学院标志建筑，楼高10层); strcpy(G.roduction,计算机学院学生学习基地,楼高6层);strcpy(G.roduction,校领导日常工作之处，楼高5层); strcpy(G.roduction,楼高5层，藏书逾十万); strcpy(G.roduction,文通楼，楼高6层，学生学习自习地点); strcpy(G.roduction,文渊楼，楼高5层，教师办公室);strcpy(G.roduction,内设大量娱乐设施，学生周末娱乐场所); strcpy(G.roduction,淮工西门是车站，学生在这里坐公交到达火车的站); strcpy(G.roduction,做实验的地点，楼高6层，内有大量先进实验仪器); strcpy(G.roduction,学生体育锻炼地点);/初始化边矩阵for(i=0;iG.vernum;i+)for(j=0;jG.vernum;j+)G.arcsij.adj=A;G.arcs01.adj=15;G.arcs02.adj=25;G.arcs03.adj=30;G.arcs14.adj=15;G.arcs17.adj=20;G.arcs19.adj=40;G.arcs25.adj=10;G.arcs28.adj=15;G.arcs36.adj=30;G.arcs38.adj=20;G.arcs47.adj=10;G.arcs49.adj=60;G.arcs58.adj=25;G.arcs68.adj=50;G.arcs79.adj=35;G.arcs45.adj=20;G.arcs56.adj=25;G.arcs57.adj=30;G.arcs67.adj=15;G.arcs69.adj=20;G.arcs78.adj=40;G.arcs89.adj=10;G.arcs29.adj=15;G.arcs39.adj=30;G.arcs34.adj=20;G.arcs48.adj=10;G.arcs45.adj=60;G.arcs59.adj=25;G.arcs18.adj=50;G.arcs17.adj=35;for(j=0;jG.vernum;j+)for(i=0;iG.vernum;i+)G.arcsij.adj=G.arcsji.adj;return 1;int locatevex(mgraph c,int v)/景点的定位int i;for(i=0;ic.vernum;i+)if(v=c.vexsi.position) return i;return -1;void printmatrix(mgraph G)/打印图的邻接矩阵；int i,j;cout对应的矩阵为：endl;for(i=0;iG.vernum;i+)for(j=0;jG.vernum;j+)if(G.arcsij.adjA)coutsetiosflags(ios:left)setw(5)G.arcsij.adj;elsecoutsetiosflags(ios:left)setw(5)0;coutendl;/求最短路径，弗洛伊德算法void shortestpath_Floyd(mgraph *G) int v,u,i,w,k,j,flag=1,p101010,D1010;/D路径 for(v=0;vvernum;v+)for(w=0;wvernum;w+) Dvw=G-arcsvw.adj; for(u=0;uvernum;u+)pvwu=0; if(DvwA) pvwv=1;pvww=1; for(u=0;uvernum;u+) for(v=0;vvernum;v+) for(w=0;wvernum;w+) if(Dvu+DuwDvw) Dvw=Dvu+Duw; for(i=0;ivernum;i+) pvwi=pvui|puwi; while(flag) coutk; cout请输入目的地的编号:j; if(kG-vernum|jG-vernum) cout景点编号不存在!请重新输入出发点和目的地的编号:; coutk; cout请输入目的地的编号:j; if(k=0&kvernum&j=0&jvernum) flag=0; printf(%s,G-); for(u=0;uvernum;u+) if(pkju&k!=u&j!=u) printf(-%s,G-); printf(-%s,G-); printf( 总路线长%dmn,Dkj);/两个景点间的所有路径void Allpath(mgraph *G)int v,w,k,j,flag=1,p1010,D1010;while(flag) cout请输入出发点和目的地的编号:endl; coutk; coutj; if(kG-vernum|jG-vernum) cout景点编号不存在!请重新输入出发点和目的地的编号:endl; coutk; cout请输入目的地的编号:j; if(k=0&kvernum&j=0&jvernum) flag=0; for(v=0;vvernum;v+)for(w=0;wvernum;w+)Dvw=G-arcsvw.adj;if(Dvw!=A) pvw=1; pwv=1;if(pkj=1);; cout总路线长Dkw+Dwjendl; for(w=0;wvernum;w+) if(pkw=1&pwj=1) ;;;cout 总路线长Dkw+Dwjendl;for(v=0;vvernum;v+)for(w=0;wvernum;w+)if(pkv=1&pvw=1&pwj=1) ;;;;cout 总路线长Dkv+Dwj+Dvwendl; void displaycampus(mgraph G)/显示景点信息，显示景点信息平面图；int i;cout景点编号 景点名称 景点简介 endl;for(i=0;iG.vernum;i+)cout G.vexsi.position ;coutG. ;coutG.roduction endl;int creatgraph(mgraph &G)/构造无向图的邻接矩阵int i,n,m,distance,v0,v1;coutG.vernum;coutG.arcnum;for(i=0;iG.vernum;i+)coutG.vexsi.position; coutG.; coutG.roduction;for(i=0;iG.vernum;i+)for(int j=0;jG.vernum;j+)G.arcsij.adj=0;for(i=0;iG.arcnum;i+)cout输入第iv0;cout输入第iv1; cout输入第idistance;m=locatevex(G,v0);n=locatevex(G,v1);if(m=0&n=0)G.arcsmn.adj=G.arcsnm.adj=distance;displaycampus(G); printmatrix(G);return 1;int DeleteVertex(mgraph &G)/删除景点信息int i,j,v,m;coutv;m=locatevex(G,v);int flag=1;while(flag)if(m0)coutv;m=locatevex(G,v);if(m0)for(i=m;iG.vernum ;i+)strcpy(G.,G.vexs i+1.name);strcpy(G.roduction,G.vexsi+1.introduction);flag=0;for(i=m;iG.vernum;i+)/删除行for(j=0;jG.vernum;j+)G.arcsij=G.arcsi+1j; for(i=m;iG.vernum;i+)/删除列 for(j=0;jG.vernum;j+) G.arcsji=G.arcsji+1; G.vernum-; displaycampus(G); printmatrix(G); return 1;int DeleteplanArc(mgraph &G)/删除图一条边信息；int i,j,v0,v1;int flag=1;while(flag) cout请输入要删除的一条边对应的两个顶点编号:v0v1;if(v0G.vernum|v0G.vernum) coutv0v1;if(v0=0&v0=0&v1G.vernum)flag=0; i=locatevex(G,v0);j=locatevex(G,v1);G.arcsij.adj=A;G.arcsji.adj=A;G.arcnum-; displaycampus(G); printmatrix(G);return 1;int enverx(mgraph &G)/增加景点int i;cout请输入要添加的景点的信息：endl;coutG.vexsG.vernum.position;coutG.vexsG.;coutG.vexsG.roduction;coutendl;G.vernum+;for(i=0;iG.vernum;i+)G.arcsiG.vernum-1.adj=G.arcsiG.vernum-1.adj=A;displaycampus(G);printmatrix(G);return 1;int enarc(mgraph &G)/增加路径int v0,v1,distance;coutv0;cout请输入增加路径的终点编号:v1;cout请输入增加路径长度distance;G.arcsv0v1.adj=G.arcsv1v0.adj=distance;displaycampus(G);printmatrix(G);return 1;void seaabout(mgraph G)/景点信息查询；int n,flag=1;coutn;while(flag)if(nG.vernum)coutn;elsecout景点编号 景点名称 景点简介 endl;cout G.vexsn.position ;coutG. ;coutG.roduction endl;flag=0;int newgraph(mgraph &G)/更新景点的信息int n,m,t;cout请输入要更新的景点数：n;while(nG.vernum)cout该景点不存在，请重新输入：n;for(int i=0;in;i+)/修改景点信息cout输入景点的编号：m;t=locatevex(G,m);cout输入景点的名称：G. ; cout输入景点的简介：G.roduction ;cout请输入要更改的边数：n;int distance,v0,v1;while(nG.arcnum)cout该路径不存在，请重新输入：n;cout输入更新的路径的信息：endl;for(i=0;in;i+)/修改路径信息cout起始景点编号v0:v0;cout终点景点编号v1:v1;cout路劲长度:distance;m=locatevex(G,v0);t=locatevex(G,v1);if(m=0&t=0)G.arcsmt.adj=G.arcstm.adj=distance;displaycampus(G);printmatrix(G);return 1;int changegraph(mgraph G)/更改图的信息int i; cout1、重新建图 2、删除结点 e