《数据结构》课程设计报告.doc

河 南 工 程 学 院课程设计报告书 姓 名 李永轩 学 号 201210913126 学 院 计算机学院 专业班级 计算机科学与技术 1242 专业课程 数据结构 指导老师 李 芳 2014年 6 月20日校园导航河南工程学院计算机学院课程设计报告书课程设计题目： 校园导航程序设计 课程设计时间： 6月16日6月20日 课程设计地点： 3号实验楼C405 课程设计单位： 计算机学院 指导教师： 李芳 学院院长： 曲宏山 本组组长刘皓冉本组成员刘皓冉、李永轩设计题目校园导航程序设计本人分工资料查询、代码编制、代码调试考核项目考核内容得分平时考核（30分）出勤情况、态度、效率、协作精神；知识掌握情况、基本操作技能、知识应用能力、获取知识能力设计思想（20分）需求分析能力，算法分析设计能力编码、调试分析（30分）编制代码能力，调试分析能力文档资料（20分）表达能力、文档写作能力和文档的规范性总评成绩指导教师评语：等 级： 评阅人： 职称： 年 月 日目 录1、设计目标12、课题分析与设计.11.课题需求分析.12.存储结构设计.43.算法设计.54.程序流程图.73、程序清单74、测试.191测试数据192.测试结果及分析.195总结.261.收获.262.不足.273.算法改进分析.27 271 设计目标1. 设计学校平面图，包含十四个景点；2. 实现景点的查询介绍；3. 设计程序求出两个景点之间最短的距离。 4. 通过实习，锻炼实际动手能力，增加相关知识，明确数据结构课程在软件开发中的重要性。2 课题分析与设计课题需求分析为完成整个导航系统的实现，需要对其所有功能清楚明白，选择正确高效的算法解决产生的问题，最后实现程序的正确运行。设计思路如下：（1）结合本校的实际情况，选出14个景点；（2）为选出的14个景点赋上相关信息内容（名称、序号、简介信息、以及路径权值等等）；（3）根据14个景点用邻接矩阵存储校园图，并依照景点相关信息进行创建。（4）把纸质上的内容，利用C编程语言编写查找景点相关信息的程序。（5）根据人为赋值的路径权值，计算任意两个景点之间的最短路径。（6）用主函数将所有板块合并，生产一个菜单界面呈现在用户面前。所以，可将系统分为以下三个核心：图的初始化、图的遍历、求最佳路线。2.1.1校园景点选取根据我校情况，选取了以下十四处景点：编号名称编号名称编号名称1大西门2小西门32号实验楼43号实验楼51-3号教学楼64-6号教学楼7B区宿舍8图书馆9南门10大学生活动中心11商业活动中心12小东门13东门14A区宿舍2.1.2图的初始化由于邻接矩阵特殊的存储方式，及便于快速的查找两个顶点之间的边上的权值。所以，校园图采用带权的邻接矩阵存储。决定了图的存储方式后，以河南工程学院14个景点地图作为蓝本，将校园地图抽象化成顶点与边构成的图形式，如图2.1.1所示，途中数字代表路线的权值。20212 21510 101543 3 420151565 5 61010020720989 8 7152520201010141011 10 14 112520201312 12 13图2.1.1 校园景点抽象图2.1.3图的遍历图的遍历是图中最基本的操作。图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。导航图需要把每条路径的信息展示出来，及需要读取每两个顶点间的路径信息。由于采用了带权的邻接矩阵存储结构进行存储，所以需要针对这一存储结构对路线进行遍历操作。其遍历算法如图2.1.2所示。插入信息内容内容For循环语句（i=0；i顶点数；i+）NFor循环语句(j=0;ji;j+)YYNY开始结束如果路径存在输出该路径信息N图2.1.2 遍历算法示意图2.1.4 求最短路径基于本程序中图的存储是邻接矩阵结构存储的图结构，因而采用适合该存储结构的迪杰斯特拉算法用于解决求最短路径的问题。迪杰斯特拉提出了一个按路径长度递增的持续产生最短路径的算法，其基本思想是：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对于viV-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v，vk，就将vk加入集合S中，并将路径v，vk，vi，与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。如图2.1.3所示。集合S集合V-SVVkVi图2.1.3 图的遍历算法执行效果示意图辅助数组distn：元素disti表示当前找到的从源点到终点vi的最短路径的长度。初态为:若从v到vi有弧，则disti为弧上的权值；否则置disti为。若当前求得的终点为vk,则根据下式进行迭代：disti=mindisti,distk+arcki 1in辅助数组pathn:元素pathi是一个串，表示当前所找到的从源点到终点vi的最短路径。初态为：若从v到vi有弧，则pathi为“vvk”，否则置pathi为空串。数组sn：存放源点和已经生成的终点（即集合S），初态为只有一个源点v。算法的伪代码描述是：1.初始化数组dist、path和s；2.while（s中的元素个数n）2.1 在distn中求最小值，其下标为k（则vk为正在生成的终点）；2.2 输出distj和pathj；2.3 修改数组dist和path;2.4 将顶点vk添加到数组s中；存储结构设计1.创建校园图：（1）依照河南工程学院的地图，先手工画好14个景点的草图，再用C语言输出抽象化的校园地图。（2）再用C语言定义节点个数N，编写函数name( )为景点赋值各类信息项，函数information( )，输入各个景点的简介。（3）读入道路的起始点，为邻接矩阵的边赋相应的值。2利用函数travgraph来查找景点信息。3创建一个校园图creat(Matrix_Graph *G)，然后为相应的边赋上现实意义上的权值。4用path( )函数来求任意两景点之间的最短路径。5. 如果不查询则调用exit( )函数退出。5用main函数来输出导游界面。算法设计1抽象数据类型图的定义ADTMgraph数据对象V:V是具有相同特性的数据元素的集合，即顶点集。数据关系：Mgraph=(V,R)。其中，R=|v,wV且P(v,w),表示从v到w的一条弧。基本操作：/ADTMgraph2 程序中包含的模块（1）主程序模块void main()/主函数定义主界面的显示； 初始化河南工程学院景点地图creat(&G)； 景点地图的输出打印printf（）； 选择景点并且打印相关信息void travgraph（）； 起点终点的选择和最短路径显示void path()； 程序的退出；void clrscr() /清屏 system(cls);typedef int AdjMatrixMAXMAX; /邻接矩阵 typedef struct /点的结构 int vexsMAX; AdjMatrix arcs;Matrix_Graph; typedef struct /景点信息结构 char name20; char information100; struct edgenode *link;vexnode; typedef struct edgenode /边和点的结构 int adjvex;int length;char info10; char info2100; struct edgenode *next;edgenode, *Node; typedef struct Edge /边的结构 int lengh; int ivex, jvex; struct Edge *next;EdgeType; typedef struct /景点代表数字和名称 int num; char name20;vertex; typedef struct /顶点和边最大值 vertex vexsMAX; int edgesMAXMAX;adjmax; void Name(int i) /景点名称的选择和输出 switch(i)void Information(inti) /景点介绍 switch(i)void travgraph(vexnode g,int n,adjmax adj) /查找指定景点信息void creat(Matrix_Graph *G)/图的初始化，权值的录入void path(Matrix_Graph *G,int s,int e) /求最短路径程序流程图程序清单/程序名称：校园导航系统 /程序员：刘皓冉、李永轩 /编写时间：2014年6月 #include #include #include #include #include#define N 14 /节点数，即景点数#define MAX 100 /最大值#define MAXedg 100 void clrscr() system(cls);typedef int AdjMatrixMAXMAX; typedef struct int vexsMAX; AdjMatrix arcs;Matrix_Graph; typedef struct /定义结构体包括名称信息和link信息 char name20; char information100; struct edgenode *link;vexnode; typedef struct edgenode int adjvex;int length;char info10; char info2100; struct edgenode *next;edgenode, *Node; typedef struct Edge int lengh; int ivex, jvex; struct Edge *next;EdgeType; typedef struct int num; char name20;vertex; typedef struct vertex vexsMAX; int edgesMAXMAX;adjmax; void Name(int i) /景点名称 switch(i) case 1:printf(1:大西门nn);break;case 2:printf(2:小西门nn);break;case 3:printf(3:2号实验楼nn);break; case 4:printf(4:3号实验楼nn);break; case 5:printf(5:1-3号教学楼nn);break; case 6:printf(6:4-6号教学楼nn);break; case 7:printf(7:B区宿舍nn);break; case 8:printf(8:图书馆nn);break; case 9:printf(9:南门nn);break; case 10:printf(10:学生活动中心nn);break;case 11:printf(11:商业活动中心nn);break;case 12:printf(12:小东门nn);break;case 13:printf(13:东门nn);break;case 14:printf(14:A区宿舍nn);break;default:printf(景点编号输入错误！请输入1-14的数字编号！nn); break; void Information(int i) /景点介绍 switch(i) case 1:printf(大西门：学校西门，正对107国道nn);break; case 2:printf(小西门：正对沙窝里商业区nn);break; case 3:printf(2号实验楼：为原老师办公处nn);break; case 4:printf(3号实验楼：为原老师办公、学生会及校广播记者站办公处nn);break; case 5:printf(1-3号教学楼：上课及自习教室nn);break; case 6:printf(4-6号教学楼：上课及自习教室nn);break; case 7:printf(B区宿舍：全部女生及部分男生宿舍nn);break; case 8:printf(图书馆：学校标志性建筑，藏书办公学习处nn);break; case 9:printf(南门：学校南门，南苑位于此处nn);break; case 10:printf(学生活动中心：大礼堂，各个社团办公室等nnn);break; case 11:printf(商业活动中心：校内超市，移动联通电信营业点，澡堂等nn);break; case 12:printf(小东门：学校小东门，正对行政楼nn);break; case 13:printf(东门：学校东门正对商业处nn);break; case 14:printf(A区宿舍：大部分男生宿舍nn);break; default:printf(景点编号输入错误！请输入1-14的数字编号！nn); break; void travgraph(vexnode g,int n,adjmax adj) /查找指定景点信息 int i=1,flag=1,len;char ch; printf(tt请输入您要查询的地点序号:nn); printf(tt1.大西门 2.小西门 3.2号实验楼n); printf(tt4.3号实验楼 5.1-3号教学楼 6.4-6号教学楼n); printf(tt7.B区宿舍 8.图书馆 9.南门n); printf(tt10.学生活动中心 11.商业活动中心 12.小东门n); printf(tt13.东门 14.A区宿舍n); printf(tt你的选择是:); scanf(%d,&len); getchar(); printf(tt此地点的名称是:); Name(len); printf(tt此地点的介绍是:); Information(len); do printf(tt是否继续? Y/N n); printf(tt你的选择是:); scanf(%c,&ch); getchar(); if(ch=Y|ch=y) clrscr(); flag=1; i=1; printf(tt请再次输入您要查询的地点序号:nn); printf(tt1.大西门 2.小西门 3.2号实验楼n); printf(tt4.3号实验楼 5.1-3号教学楼 6.4-6号教学楼n); printf(tt7.B区宿舍 8.图书馆 9.南门n); printf(tt10.学生活动中心 11.商业活动中心 12.小东门n); printf(tt13.东门 14.A区宿舍n); printf(tt你的选择是:); scanf(%d,&len); getchar(); printf(tt此地点的名称是:); Name(len); printf(tt此地点的介绍是:); Information(len); continue; else flag = 0; printf(tt请再次按回车键返回至主菜单); break;while(1); void creat(Matrix_Graph *G) /创建校园图，给相应的边赋权值 int i,j; for(i=1;ivexsi=i; for(i=1;i=N;i+) for(j=1;jarcsij=0; G-arcs12=20;G-arcs14=10;G-arcs13=10;G-arcs18=15; G-arcs24=15;G-arcs27=10; G-arcs31=10;G-arcs39=20;G-arcs35=15; G-arcs41=10;G-arcs46=15;G-arcs42=15; G-arcs53=15;G-arcs58=10; G-arcs64=15;G-arcs68=10; G-arcs72=10;G-arcs711=20;G-arcs78=20;G-arcs714=15; G-arcs85=10;G-arcs86=10;G-arcs87=20;G-arcs89=20;G-arcs810=20;G-arcs81=15; G-arcs93=20;G-arcs98=20;G-arcs910=25; G-arcs108=20;G-arcs109=25;G-arcs1014=10;G-arcs1012=20;G-arcs1013=25; G-arcs117=20;G-arcs1114=10;G-arcs1113=20; G-arcs1210=20; G-arcs1310=25;G-arcs1311=20;G-arcs1314=5; G-arcs1410=10;G-arcs1411=10;G-arcs147=15;G-arcs1413=5; for(i=1;i=N;i+) for(j=1;jarcsij=0) G-arcsij=MAX; void path(Matrix_Graph *G,int s,int e) /求任意两景点之间的最短路径 int i,j,u,c=1,t,v; int rN+1N+1; int TN,flagN,dN; for(i=0;i=N;i+) for(j=0;j=N;j+) rij=0; for(i=1;i=N;i+) Ti=-1;flagi=1;di=MAX; flags=0; while(c=N) t=MAX; for(i=1;iarcssiarcssi;v=i;rv1=v; for(i=1;i=c;i+) for(j=1;jarcsTijarcsTij;v=j; if(rv0!=-1) u=1; while(rTiu!=0) rvu=rTiu;u+; rvu=v; rv0=-1;Tc=v;flagv=0;dc=t;c+; printf(n最短路径是以下这条:n(%d),s);j=1; while(rej!=0) printf(-(%d),rej);j+;printf(nn); void main() /主函数输出导游界面system(Color B1);int i,j; Matrix_Graph G;creat(&G);int n = 0; vexnode gMAX; EdgeType eMAXedg; adjmax adj; char choice=x; while(1) clrscr(); printf(nttt欢迎使用河南工程学院校园导航系统); /主界面 printf(nnnnttt *校-园-导-航*); printf(ntt n);printf(tt 自 1. 河南工程学院地图: 博n);printf(tt 2. 校园地点简介: n); printf(tt 强 3. 查找两点间最短路径: 学 n);printf(tt 0. 退出 n); printf(tt 不 精n);printf(tt 制作人：刘皓冉、李永轩 n);printf(tt 息 艺n);printf(tt 校址：新郑龙湖中山北路1号 n); printf(tt nn); printf(tt 请输入你的选择(0-3): ); choice = getchar(); switch(choice) case 1:clrscr(); /校园地图 printf(tt *河南工程学院地图* n);printf( n); printf( #1.大西门#2.小西门# n); printf( n); printf( _ n); printf( n); printf( #3.2号实验楼#4.3号实验楼# n); printf( n); printf( n); printf( n); printf( #5.1-3号教学楼#6.4-6号教学楼#7.B区宿舍# n); printf( n); printf( _ n); printf( n); printf( #9.南门#8.图书馆# n); printf( _ n); printf( n); printf( #10.学生活动中心#14.A区宿舍#11.商业活动中心# n); printf( _ _ n);printf( n); printf( #12.小东门# #13.东门# n); printf( n); printf(tt输入回车键返回菜单);getchar();getchar();break; case 2:clrscr(); travgraph(g,n,adj);getchar();break; case 3:clrscr(); printf(tt *河南工程学院地图* n); printf( n); printf( #1.大西门#2.小西门# n); printf( n); printf( _ n); printf( n); printf( #3.2号实验楼#4.3号实验楼# n); printf( n); printf( n); printf( n); printf( #5.1-3号教学楼#6.4-6号教学楼#7.B区宿舍# n); printf( n); printf( _ n); printf( n); prin