数据结构课程设计报告模板.doc

课程设计报告设计名称： 数据结构课程设计 选题名称： 连云港市景点导游咨询 系 （院): 计算机工程学院 设计时间： 2012。12。242013。1.4 设计地点： 软件工程实验室、教室 成绩：指导教师评语： 签名： 年 月 日1课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题. 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4。训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务根据教材数据结构C语言描述（耿国华主编）和参考书数据结构题集(C语言版）（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取，每班每题不得超过2人.学生自选课题学生原则上可以结合个人爱好自选课题,要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效.要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率.在程序设计阶段应尽量利用已有的标准函数,加大代码的重用率。 2、.设计的题目要求达到一定工作量(300行以上代码）,并具有一定的深度和难度。3、程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释；4、每位同学需提交可独立运行的程序;5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3课程设计说明书一 需求分析连云港作为一个著名的旅游城市，每年都有大量的国内外游客来港城旅游，大多数外地游客对连云港的旅游景点的相关信息不是非常了解，所以我们可以为他们设计一个方便在连云港外出旅游的咨询程序，即连云港市景点导游咨询程序。连云港市导游咨询程序需要把连云港市的主要景点,都包括在一个平面图内。（1） 以图中各顶点存放连云港的各景点名称,代号，简介等相关信息 （2）程序中，以各个旅游景点名称为图的顶点，各个顶点的信息是景点的简要描述，权值就是任意两个景点间的路径长度。(3) 以边存放路径及路径长度等相关信息，游客可根据图所提供的景点来查询各个景点的相关信息及各景点的路径查询。(4) 提供两个景点间的所有路径并提示最短路径，为游客的旅游带来方便，游客可根据实际情况选择最佳的游览路线。二 概要设计1、抽象数据类型图的定义如下: ADT Graph数据对象V：V是具有相同特性的数据元素的集合,称为顶点集。数据关系R：R=VRVR=（v，w）|v，wV，(v，w）表示v和w之间存在路径基本操作P： path(MGraph g，int i,int j,int k）初始条件：要查询的起点i与终点j，k初始值为0操作结果：确定路径上第k+1个顶点的序号，找到从vi到vj的所有路径 disppath（MGraph g,int i,int j）初始条件：定义一个图与起点i终点j操作结果：初始化访问标志与路径条数，并调用path（）函数 ppath（MGraph g,int path1，int i,int v0)初始条件:定义一个图，path1i存放顶点i的当前最短路径上该点的前趋顶点，i为终点，v0为起点操作结果：输出最短路径 dispath（MGraph g,int dist，int path1,int s，int n,int v0，int i）初始条件：定义一个图,用disti存放顶点i的当前最短路径长度，path1i 存放顶点i的当前最短路径上该点的前趋顶点，n为景点个数，v0与i分别为起点与终点操作结果:由path1计算出从v0到i的最短路径 Dijkstra（MGraph g,int v0,int p)初始条件：定义图与起点与终点操作结果:采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径 Searchname（MGraph g）初始条件：定义一个图操作结果：查询景点的信息 Searchpath1(MGraph g）初始条件：定义一个图操作结果:查询两个景点间的所有路径 Searchpath2(MGraph g）初始条件:定义一个图操作结果：查询两个景点间的最短路径ADT Graph2、系统中子程序及功能要求：path（MGraph g,int i,int j，int k)：确定路径上第k+1个顶点的序号，k初始值为0disppath(MGraph g，int i，int j）：初始化访问标志与路径条数,并调用path（）函数ppath(MGraph g，int path1，int i，int v0）：输出最短路径dispath（MGraph g,int dist,int path1,int s，int n，int v0，int i）：由path1计算从v0到i的最短路径Dijkstra(MGraph g，int v0,int p)：采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径Searchname（MGraph g)：查询景点的信息Searchpath1(MGraph g)：查询两个景点间的所有路径Searchpath2(MGraph g):查询两个景点间的最短路径Searchpath3(MGraph g）：添加动态景点3、 各程序模块之间的调用关系:函数的调用关系图mainSearchname Searchpath1 Searchpath2 Searchpath2 disppath Dijkstra path dispath path ppath Ppath 主函数调用 可调用 可调用可调用 可调用 可调用可调用 可调用三 详细设计顶点、边和图的类型：typedef structint num；/顶点编号/ char nameMAXSIZE;/顶点名称/ char discriptionMAXLEN;/顶点信息描述/VertexType； typedef structint edgesMAXVMAXV； int vexnum，arcnum;VertexType vexsMAXV； MGraph；int visitedMAXV;int pMAXV;创建连云港市景点地图：int i，j;int b11=1，2，3，4,5，6,7,8，9,10,11;char *c11=/各个景点名称/；char *d11=/*字符串指针数组,用来给每个顶点的简介信息进行赋值*/；MGraph g；/*创建一个无向网/ int A1111=/景点的相关简介进行赋值/ ； g。vexnum=顶点个数；g。arcnum=顶点边数;/建立无向网的邻接矩阵*/for(i=0；i孔子忘角-玉女峰 路径长度：25公里 4.查询所有路径如：选出出发地：孔望山 目的地：连岛系统输出如下: 孔望山-连岛 孔望山-前三岛-枫树湾-连岛 孔望山-前三岛-枫树湾-桃花涧-连岛 孔望山-前三岛-枫树湾-桃花涧-东海温泉-连岛 结果正确5. 动态添加景点 动态添加,目前只能添加进信息，方便查询,还未实现求路径的功能。五 用户手册本程序界面如下：按序号进行操作！六 测试成果1、 查询景点2、 查询所有路径3、 查询最短路径4、 添加景点七 附录（源程序清单）includestdio。h#includestring。hinclude stdlib.hdefine MAXV 11/*最多顶点个数/#define MAXSIZE 20/字符串成员name的最大长度/define MAXLEN 500/*字符串成员content的最大长度/#define INF 32768/*用32768表示/int a=0；/*全局变量，用来记录每对顶点之间的所有路径的条数*/static n=8；typedef structint num; char nameMAXSIZE; char discriptionMAXLEN; VertexType；/*顶点的结构定义*/ typedef structint edgesMAXVMAXV; int vexnum,arcnum; VertexType vexsMAXV;MGraph;/*网的结构定义*/int visitedMAXV;/*全局数组，用来记录各顶点被访问的情况/int pMAXV；/全局数组,用来存放路径上的各顶点/void path(MGraph g,int i,int j,int k) /*i为要查询是起始点，j为要查询的终点,相当于深度优先遍历/int s;if（pk=j)a+;printf（第%d条：”,a）；for（s=0；s”,g.vexsps.name）；printf（sn，g。vexsps.name)；s=0；while（sg。vexnum）if（s！=i)/*保证找到的是简单路径,保证没有回路/if(g.edgespks!=INF&visiteds=0)visiteds=1；pk+1=s；path(g，i,j,k+1);visiteds=0；s+;void disppath（MGraph g，int i，int j)int k； p0=i； for(k=0；kg.vexnum;k+)visitedi=0；a=0;path(g,i,j，0）;void ppath(MGraph g，int path1,int i,int v0)int k；k=path1i； if（k=v0)return；ppath(g,path1,k，v0）;printf（”s,g.vexsk。name)；/*输出最短路径/void dispath(MGraph g,int dist,int path1,int s,int n，int v0,int i)if（si=1&i！=v0）printf(”从s到s的最短游览路径是：n,g.vexsv0。name，g.vexsi.name）;printf（”s-”，g.vexsv0。name)； ppath(g,path1，i，v0）; printf(”s ，g.vexsi。name）； printf(”路径长度：%d公里n,disti);/*由path1计算从v0到i的最短路径/void Dijkstra(MGraph g,int v0，int p）/采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径/int distMAXV，path1MAXV；int sMAXV； int mindis,i,j，u，n=g。vexnum;for（i=0；in;i+）disti=g.edgesv0i;si=0；if(g。edgesv0iINF）path1i=v0;else path1i=1;sv0=1；path1v0=0;for(i=0；in；i+）mindis=INF；u=-1；for（j=0；jn;j+）if(sj=0&distjmindis) u=j;mindis=distj;su=1;for(j=0；jn；j+)if(sj=0）if（g.edgesujINFdistu+g.edgesujdistj)distj=distu+g。edgesuj；path1j=u；dispath(g,dist，path1，s，n，v0，p）;/输出最短路径/void Searchname(MGraph g)/*查询景点的信息/printf（景点：n）； printf(”-n）；printf(”tt1：锦屏山ntt2：将军崖岩画n”）;printf（tt3：古城ntt4：孔子望角ntt5：玉女峰ntt6：江岭ntt7：花果山n）；printf(”tt8：猴嘴公园n”)； printf（”-n”); int i； char s; while(1）/可提供循环查询，当输入为N或n时，结束循环/printf（ttt 请输入你要查询的景点：）； scanf(d”，i）；for(int j=0；jg。vexnum；j+）if（i=g.vexsj.num）printf（%s简介：n”,g.vexsj.name）; printf(”-n”);printf（s”,g。vexsj.discription)；printf(n)； printf（-n”)；printf（继续查询？(y或n):”)；scanf(s”，&s)；if（s=Ns=n)break；void Searchpath1（MGraph g)/*查询两个景点间的所有路径*/ printf（景点：n”）； printf（”-n）；printf(”tt1:锦屏山ntt2：将军崖岩画n”);printf(tt3:古城ntt4：孔子望角ntt5:玉女峰ntt6：江岭ntt7:花果山n”);printf（”tt8：猴嘴公园n）; printf(-n）; int i,j; char s； while(1)printf（ttt 选择出发景点：”）; fflush(stdin)； scanf（”d”,i）;printf（”ttt 选择目地景点：）; fflush（stdin）;scanf（”d,j）;for(int k=0;kg。vexnum;k+）if(i=g.vexsk。num） i=k;for（int l=0;lg.vexnum；l+)if(j=g。vexsl.num） j=l；printf（”从s到%s的所有游览路径有:n，g。vexsi.name，g。vexsj.name)；disppath（g，i,j);printf（”-n）；printf（继续查询？（y或n)：”）；scanf(s，&s);if（s=N|s=n）break；void Searchpath2(MGraph g)/查询两个景点间的最短路径/ printf(景点：n”）; printf（”-n”)；printf（”tt1:锦屏山ntt2:将军崖岩画n”)；printf（”tt3:古城ntt4：孔子望角ntt5:玉女峰ntt6：江岭ntt7:花果山n)；printf(”tt8:猴嘴公园n”）; printf（”-n）; int i,j; char s; while(1)printf(”ttt 选择出发景点：);fflush(stdin）;scanf（”d”，i）；printf(”ttt 选择目地景点:）;fflush（stdin)； scanf（d”，j)； for（int k=0;kg.vexnum；k+)if(i=g。vexsk.num) i=k;for（int l=0;lg。vexnum；l+)if（j=g.vexsl。num) j=l;Dijkstra(g,i，j）;printf(”-n)；printf（”继续查询?（y或n)：）；scanf（”%s”,s）;if（s=N|s=n）break；void Searchpath3(MGraph g，char c，char *d） / 动态添加景点printf(请输入你想添加的景点：n）;printf(”-n”）;char s;while（1）printf（”景点名称：n);int i=0;while（in1)i+；scanf(”%s”，&（g。vexsi。name）)；ci=g.vexsi.name; printf（”景点简介：n)；scanf（”%s，&(g.vexsi.discription)）；di=g。vexsi.discription；printf（继续查询?(y或n）:”);scanf（”%s”，s）；if（s=N|s=n) break;void main(）/*主函数/int i，j；int b11=1,2，3,4,5,6,7,8；char c11=锦屏山,”将军崖岩画”,古城，孔子望角，玉女峰，江岭”，”花果山”，”猴嘴公园；char d11=名称：锦屏山n简介：因山色锦绣，美如画屏,而被康熙皇帝命名为锦屏山n票价： 10”, 名称：将军崖岩画n简介:这是我国迄今发现的最古老时代岩画，是东南沿海地区首次发现的岩画n票价：20, 名称：古城n简介：古城为黄土夯成，当年建筑时留下来的孔穴和层层夯印，现在仍历历在目n票价:30, 名称：孔子望角n简介：这座由花岗岩、片麻岩构成的古老体，距今已有18亿年的历史n票价：40, 名称：玉女峰n简介：岩壁秀润光洁，宛如玉石雕就,乘坐竹筏从水上望去，俨然是一位秀美绝伦的少女n票价：50”, 名称：江岭n简介：河边聚集的三、四个村庄,四周围绕着青山,构成了一副极美的婺源农村风光画卷n票价：60， 名称：花果山n简介：景区内峭壁悬崖,层峦叠嶂，巍峨壮观，且植被丰富，景色秀丽，一年四季皆有特色n票价:70， ”名称：猴嘴公园n简介：街道巷闾，纵横交错，高楼广厦，鳞次栉比，令人心旷神怡n票价：80;MGraph g； int A1111= INF，13,INF，INF，INF,INF,INF,15， 13,INF,5,INF,INF,15,12,INF， INF,5,INF，15，INF，INF,INF，5， INF,INF，15，INF,10,INF,INF,INF， INF,INF,INF,10,INF，10，8，INF， INF,15,INF,INF,10，INF，INF，12, INF,INF，8,INF,INF，18，INF，INF, INF，INF，INF，18，INF,10，15，INF; g。vexnum=n; g.arcnum=14; for（i=0；ig.vexnum；i+) for（j=0;jg。vexnum;j+） g。edgesij=Aij;/建立无向网的邻接矩阵/ for(i=0;ig.vexnum；i+） g.vexsi.num=bi； strcpy（g.vexsi。name，ci）; strcpy(g.vexsi。discription,di); int select； do system(”cls”）； printf(-连云港市导游咨询程序-n”); printf(”本程序能够：n”)； printf（n n”）； printf（ n）； printf(” 1、查询景点的信息 n”）； printf（” 2、查询景点间的游览路径 n)； printf(” 3、查询景点间的最短游览路径 n); printf（” 4、输入您要添加的景点 n); printf（ 5、退出 n）; printf(” n)； printf（” n）; printf（-n”)； printf(” 请输入您的选择：”); scanf(”d”,select）; switch(select) case 1： Searchname（g）；/查询景点的信息/ break； case 2: Searchpath1（g）;/查询景点间的游览路径/ break； case 3： Searchpath2（g）;/查询景点间的最短游览路径*/ break； case 4: n=n+1; Searchpath3(g,c，d）；/*查询动态添加的景点到各景点间的游览路径/ int w； printf（”n加了该新景点后的信息为:n”）; for(w=0;wn;w+） printf(%sn,cw）； printf(”sn”，dw)； break; case 5:/退出本程序/ break; while（select！=4); /当select的值不为4时，继续循环/4. 课程设计心得 这次课程设计运用到了大学c+语言和大二所学习到的数据结构知识点,课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力。刚开始拿到题目时，完全不知道如何下手，开始在网上找类似的，结果还真的找到了两份，这两份的思想是完全不一样的,起初想着参考一下，各取一半的思想，本来以为很简单就可以把程序调出来，可结果是没那么简单。慢慢的按照老师计划书上的指示一步来一步来,首先，我必须先对我选的这个题目进行概要的分析、设计，分析出这个程序是干什么用的，应该实现什么功能,这些功能应该包含哪些函数，函数之间应该是怎样的调用关系.比如说我做的连云港市导游咨询，我就做的包括三方面：1、查询景点信息2、查询景点间的游览路径3、查询景点间的最短游览路径。4、添加动态景点。首先我必须知道景点的信息包括哪些，必须清楚的了解好信息才可以下手。 在主函数中主要调用了三个函数，分别是 Searchname（g）、Searchpath1(g)、Searchpath2（g），也就是通过这三个函数来实现我们要求的三个查询功能。比较难的是后两个，它们，调用的函数比较多，并且考虑的方面也要全面，在Searchpath1（g）调用的函数中，特别是path（MGraph g，int i，int j,int k