数据结构课程设计报告校园导游图.docx
- 文档编号:11179393
- 上传时间:2023-05-29
- 格式:DOCX
- 页数:47
- 大小:721.55KB
数据结构课程设计报告校园导游图.docx
《数据结构课程设计报告校园导游图.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计报告校园导游图.docx(47页珍藏版)》请在冰点文库上搜索。
数据结构课程设计报告校园导游图
淮海工学院计算机工程学院
课程设计报告
设计名称:
数据结构课程设计
选题名称:
校园导游图
姓名:
学号:
专业班级:
系(院):
计算机工程学院
设计时间:
2011.12.19~2011.12.30
设计地点:
软件工程实验室、教室
成绩:
指导教师评语:
签名:
年月日
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)为来访客人查询图中任意两个景点间的所有路径
(4)为来访客人修改图中顶点和边的信息
(5)为来访客人增加景点和路径
(6)为来访客人删除景点和路径
(7)为来访客人输出对应编号景点的信息
3.数据需求:
建立无向图G,图中顶点ver表示主要景点,存放景点编号position、名称name、简介introduction等信息,图中边arc表示景点间的道路,存放路径长度信息distance。
二概要设计
1.ADTGraph
数据对象V:
V具有相同特性的数组元素的集合,称为顶点集
数据关系R:
R={VR}
VR={
ADTGraph{
数据对象V:
一个集合,该集合中的所有元素具有相同的特性
数据关系R:
R={VR}
VR={
基本操作:
(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)显示输入两个顶点间的所有路径
5、intchangegraph(mgraphG)更改图的信息
6、intlocatevex(mgraphc,intv)景点的定位
7、voidcreatgraph(mgraph&G)创建图的邻接矩阵
8、voidprintmatrix(mgraphG)打印图的邻接矩阵;
9、intDeleteplanArc(mgraph&G)删除图一条边;
10、intDeleteVertex(mgraph&G)删除景点
11、intenarc(mgraph&G)增加路径
12、intenverx(mgraph&G)增加结点
13、intnewgraph(mgraph&G)更新景点的信息
14、intinitgraph(mgraph&G)校园导游图的初始化
15、voidmain()主函数,可以调用子函数
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、创建无向网图算法的伪代码描述如下:
intcreatgraph(mgraph&G)//构造图的邻接矩阵
{
输入矩阵对应的顶点数G.vernum和边数G.arcnum;
for(i=0;i { 输入对应的景点编号、景点名称、景点简介: } 初始化任意景点的路径 修改两顶点间的路径 } 2、输出学校平面图的算法的伪代码描述如下: voiddisplaycampus(mgraphG)//显示景点信息; { 对应输出景点编号,景点名称,景点简介 } 3、按编号查询景点的相关信息的算法的伪代码描述如下: voidseaabout(mgraphG)//景点信息查询; { 请输入要查询的景点编号n; if(n<0||n>11) 该景点不存在,请重新输入: 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,j if(k<0||k>G->vernum||j<0||j>G->vernum) 景点编号不存在! 请重新输入出发点和目的地的编号: k,j if(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]用于存放两顶点间的路径长度; while(flag) { 输入出发点和目的地的编号k,j; if(k<0||k>顶点数目||j<0||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,及边的长度distance G.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(m<0) 重新输入 if(m>0) { 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;i { 逐个输入景点的编号、景点的名称: 、景点的简介 } 输入更改的路径数n; intdistance,v0,v1; 输入更新的路径的信息 for(i=0;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 体育馆 学生体育锻炼地点 实际输出的信息为: 操作成功,与预期结果一致。 2.打印校园导游图的邻接矩阵: 操作成功,与预期结果一致。 3、查询景点间最短路径: 比如: 20 15 查询景点1(计算机楼)和3(图书馆)之间的最短路径,预期结果应为: 计算机楼—>文通楼—>图书馆, 路径总长度为35 操作成功,与预期结果一致。 4、景点信息查询: 比如: 查询景点为1的景点信息,预期结果应为: 景点序号(position) 景点名称(name) 景点介绍(intoduction) 1 计算机楼 计算机学院学生学习基地,楼高6层 与预期结果一致。 查询成功。 5、更改图的信息: 更改图信息主页面: 5.1重新建图 比如重新建一个有3个景点和3条路径的无向图: 景点信息分别为: 景点序号(position) 景点名称(name) 景点介绍(intoduction) 0 计算机楼 信息中心 1 第一食堂 饮食中心 2 B#宿舍 男生宿舍 矩阵关系为: 0 15 25 15 0 50 25 50 0 与预期结果一致,重新建图成功。 5.2删除景点: 比如删除景点编号为1的景点: 则输出的矩阵中应失去原第一行第一列, 并且其信息不再出现在校园导游中: 删除景点前的图信息: 删除景点前的矩阵: 删除景点后的图的信息和矩阵: 与预期结果一致,删除景点成功。 5.3删除两景点间的路径: 比如删除编号为0和2的两景点间的路径,则打印出来的矩阵在第0行第2列和第2行第0列的值应为0。 删除路径前的矩阵: 删除路径后的矩阵: 与预期结果一致,删除路径成功。 5.4增加景点信息 比如增加一个景点,其信息为: 景点序号(position) 景点名称(name) 景点介绍(intoduction) 10 A#7宿舍楼 计算机学院女生宿舍 对应的矩阵中应增加一行一列,第10行和第10列上所有元素都应为0,输出的图信息中最后应增加上述的信息。 增加景点前的图信息: 增加景点前的矩阵: 增加景点后的图信息和矩阵: 与预期结果一致,增加景点成功。 5.5增加一条路径 比如在景点0和4之间加一条长度为10的路径,则在第0行第4列与第4行第0列元素应为10。 增加路径前的矩阵: 增加路径后的矩阵: 与预期结果一致,增加路径成功。 5.6更新图信息 比如要更新一个景点和一条路径的信息,将景点信息: 景点序号(position) 景点名称(name) 景点介绍(intoduction) 1 计算机楼 计算机学院学生学习基地,楼高6层 改为: 景点序号(position) 景点名称(name) 景点介绍(intoduction) 1 B#8 男生宿舍 更改顶点编号为0和3路径长度,路径由30改为15。 更改后的图中编号为1的信息应变为: 景点序号(position) 景点名称(name) 景点介绍(intoduction) 1 B#8 男生宿舍 矩阵中第0行第3列和第3行第0列元素应由30变为15. 更改景点前的图信息: 更改路径前的矩阵: 更新后的图信息和矩阵: 6、查找两顶点间的所有路径 比如查找1,3两点间的所有路径,所有路径为: 五用户手册 1、进入本系统后,随即显示系统主菜单页面。 用户可在此菜单下输入各子菜单对应的数字,并按回车键,执行相应的子菜单命令。 2、查询、修改、增加、删除景点以及景点间的路径,都是通过输入景点的编号来实现的,进入主菜单时,用户最好先选择“1、学校景点介绍”和“2、打印邻接矩阵”,方便用户了解景点信息以及路径信息。 六测试成果 操作主界面 查看淮工景点平面图 打印无向图邻接矩阵 查询两顶点间的最短路径 按编号查询景点信息 查询两顶点间的所有路径: 更改图信息: 退出系统 七附录(源程序清单) #include #include #include #include usingnamespacestd; #definemax_ver_num20 #defineOK1 #defineFALSE0 #defineError-1 #defineA1000 #defineTRUE1 typedefstructarcnode//设置边的权值信息 { intadj;//路径权值 }arcnode,adjarcs[max_ver_num][max_ver_num]; typedefstructverdata//设置景点信息 { intposition; charname[60]; charintroduction[1000]; }verdata; typedefstructmgraph { verdatavexs[max_ver_num]; adjarcsarcs; intvernum,arcnum; }mgraph; //全局变量 intvisited[20]; intd[35]; mgraphg; intinitgraph(mgraph&G)//校园导游图的初始化 { inti,j; G.vernum=10; G.arcnum=20; //初始化景点平面图 for(i=0;i G.vexs[i].position=i; strcpy(G.vexs[0].name,"淮工主楼"); strcpy(G.vexs[1].name,"计算机楼"); strcpy(G.vexs[2].name,"行政楼"); strcpy(G.vexs[3].name,"图书馆"); strcpy(G.vexs[4].name,"文通楼"); strcpy(G.vexs[5].name,"文渊楼"); strcpy(G.vexs[6].name,"大活中心"); strcpy(G.vexs[7].name,"淮工西门"); strcpy(G.vexs[8].name,"实验楼"); strcpy(G.vexs[9].name,"体育馆"); strcpy(G.vexs[0].introduction,"淮海工学院标志建筑,楼高10层"); strcpy(G.vexs[1].introduction,"计算机学院学生学习基地,楼高6层"); strcpy(G.vexs[2].introduction,"校领导日常工作之处,楼高5层"); strcpy(G.vexs[3].introduction,"楼高5层,藏书逾十万"); strcpy(G.vexs[4].introduction,"文通楼,楼高6层,学生学习自习地点"); strcpy(G.vexs[5].introduction,"文渊楼,楼高5层,教师办公室"); strcpy(G.vexs[6].introduction,"内设大量娱乐设施,学生周末娱乐场所"); strcpy(G.vexs[7].introduction,"淮工西门是车站,学生在这里坐公交到达火车的站"); strcpy(G.vexs[8].introduction,"做实验的地点,楼高6层,内有大量先进实验仪器"); strcpy(G.vexs[9].introduction,"学生体育锻炼地点"); //初始化边矩阵 for(i=0;i for(j=0;j G.arcs[i][j].adj=A; G.arcs[0][1].adj=15; G.arcs[0][2].adj=25; G.arcs[0][3].adj=30; G.arcs[1][4].adj=15; G.arcs[1][7].adj=20; G.arcs[1][9].adj=40; G.arcs[2][5].adj=10; G.arcs[2][8].adj=15; G.arcs[3][6].adj=30; G.arcs[3][8].adj=20; G.arcs[4][7].adj=10; G.arcs[4][9].adj=60; G.arcs[5][8].adj=25; G.arcs[6][8].adj=50; G.arcs[7][9].adj=35; G.arcs[4][5].adj=20; G.arcs[5][6].adj=25; G.arcs[5][7].adj=30; G.arcs[6][7].adj=15; G.arcs[6][9].adj=20; G.arcs[7][8].adj=40; G.arcs[8][9].adj=10; G.arcs[2][9].adj=15; G.arcs[3][9].adj=30; G.arcs[3][4].adj=20; G.arcs[4][8].adj=10; G.arcs[4][5].adj=60; G.arcs[5][9].adj=25; G.arcs[1][8].adj=50; G.arcs[1][7].adj=35; fo
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告 校园 导游