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

1、课程设计报告设计名称：数据结构课程设计选题名称：系（院）:连云港市景点导游咨询计算机工程学院设计时间：2012。 12。 242013。 1.4设计地点：软件工程实验室、教室成绩:指导教师评语:签名： 1 .课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编 程水平，并在此过程中培养他们严谨的科学态度和良好的

2、工作作风。2. 课程设计任务与要求：任务根据教材数据结构一C语言描述（耿国华主编）和参考书数据结构题集（C语言版）（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构 的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取，每班每题不得超过2人.学生自选课题学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算

3、法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率在程序设计阶段应尽量利用已有的标准函数,加大代码的重用率。2、.设计的题目要求达到一定工作量 （300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用 C/C+,程序书写规范，源程序需加必要的注释；4、 每位同学需提交可独立运行的程序；5、 每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少 于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核3. 课程设计说明书*” awe y

4、 pyTF !a we*ey !>t！IF b!i awe*e! awe*eb!i awe*e w riiHiiTRHa b!ia vb*fb!ia ve*eb!ia ve*ef b!is»hf b!ia vb一需求分析连云港作为一个著名的旅游城市，每年都有大量的国内外游客来港城旅游，大多数外地游客对连云港的旅游景点的相关信息不是非常了解，所以我们可以为他们设计一个方便在连云港外出旅游的咨询程序，即连云港市景点导游咨询程序。连云港市导游咨询程序需要把连云港市的主要景点，都包括在一个平面图内。(1) 以图中各顶点存放连云港的各景点名称，代号，简介等相关信息(2) 程序中，以各个旅

5、游景点名称为图的顶点，各个顶点的信息是景点的简要描述，权值就是任意 两个景点间的路径长度。(3) 以边存放路径及路径长度等相关信息，游客可根据图所提供的景点来查询各个景点的相关信息 及各景点的路径查询。(4) 提供两个景点间的所有路径并提示最短路径，为游客的旅游带来方便，游客可根据实际情况选 择最佳的游览路线。二概要设计1、抽象数据类型图的定义如下：ADT Graph数据对象V : V是具有相同特性的数据元素的集合，称为顶点集。数据关系R:R=VR VR= (v, w) |v, w V, (v, w)表示v和w之间存在路径基本操作P:path(MGraph g , int i,int j,in

6、t 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,i nt dist , i nt path1 ,int s , int

7、 n,i nt v0 , int i )初始条件：定义一个图，用disti 存放顶点i的当前最短路径长度，path1 : i存放顶点i的当前 最短路径上该点的前趋顶点，n为景点个数，v0与i分别为起点与终点操作结果：由path1计算出从v0到i的最短路径Dijkstra ( MGraph g,int v0,int p)初始条件：定义图与起点与终点操作结果：采用迪杰斯特拉算法求从顶点V0到顶点p的最短路径Search name( MGraph g)初始条件：定义一个图操作结果：查询景点的信息Searchpath1(MGraph g )初始条件：定义一个图操作结果：查询两个景点间的所有路径Sear

8、chpath2(MGraph g )初始条件：定义一个图操作结果：查询两个景点间的最短路径 ADT Graph2、系统中子程序及功能要求： path (MGraph g,int i,int j , int k):确定路径上第 k+1个顶点的序号，k初始值为0 disppath(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 , i

9、nt v0 , int i ):由 path1 计算从 v0 到 i的最短路径 Dijkstra(MGraph g , int v0,int p):采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径 Search name (MGraph g):查询景点的信息 Searchpath1(MGraph g):查询两个景点间的所有路径 Searchpath2(MGraph g):查询两个景点间的最短路径 Searchpath3(MGraph g):添加动态景点 3、各程序模块之间的调用关系函数的调用关系图mainSearch name Searchpath1Searchpath2 Searchpath

10、2 disppathDijkstrapathdispathIpathppath；Ppath主函数调用可调用可调用 可调用可调用可调用 可调用可调用三详细设计顶点、边和图的类型：typedef structint num ; / *顶点编号* /char nameMAXSIZE;/*顶点名称* /char discriptionMAXLEN: ;/ *顶点信息描述* /VertexType ;typedef structint edgesMAXV : MAXV;int vexnum , arcnum;VertexType vexs MAXV； MGraph;int visited: MAXV ;

11、in t pMAXV;创建连云港市景点地图：int i , j;int b11: =1 , 2, 3, 4,5 , 6,7,8 , 9,10,11;char *c11: =/ *各个景点名称* /;char *d : 11= /*字符串指针数组，用来给每个顶点的简介信息进行赋值*/ ;MGraph g; /*创建一个无向网* /int A 11: 11 : = / *景点的相关简介进行赋值*/ ;g。vexnum=顶点个数；g。玄切口口=顶点边数;/ *建立无向网的邻接矩阵 */for（i=0 ; i图的顶点个数；i+ ）/*给每个顶点一个编号*/ *通过字符串复制函数给每个顶点一个名称*/

12、*通过字符串复制函数给每个顶点加上信息，即作为景点的简介信息*/查询景点的信息：int i ;char s;while （1）/ *可提供循环查询,当输入为N或'n'时，结束循环*/printf（ ” ttt请输入你要查询的景点：”）；seanf （” d"，& i ）;for(int j=0; j 图的顶点个数；j+)/ *输出信息*/printf(”继续查询?(y 或 n):");scanf(” % s”，& s);if(s= ' N' | | s='n')break ；查询景点间的游览路径：void Se

13、archpath1 ( MGraph g)int i ，j;char s ；while(1 )/*可提供循环查询，当输入为'N '或n'时，结束循环*/ *输入起点与终点*/;disppath ( g,i , j ) ;/ *调用disppath函数，用来输出两个景点间的所有路径*/printf(”继续查询？ ( y 或 n):");scanf (” %s",&s);if(s= ' N' | | s=' n')break ；查询最短路径：int i , j ;char s;while(1)/*可提供循环查询，当

14、输入为N'或'n'时,结束循环* /*输入起点与终点* /Dijkstra ( g,i,j) ; /*调用Dijkstra 函数，用来输出两个景点间的最短路径*/printf("继续查询？ ( y 或 n): ”)；scanf (” s" , &s);if (s=' N' | |s= ' n')break ；(6)添加动态景点：(7 )主函数：int select;/*定义一个整型变量，用来输入不同的选择*/do/ *可提供循环输入选择，当输入的选择为4时,退出循环*/switch(select)/*判断sel

15、ect的值,根据其值跳转到相应的子模块继续执行*/case 1/*查询景点的信息*/break ；case 2:；/*查询景点间的游览路径*/break ；case 3/*查询景点间的最短游览路径*/Case 4/*添加动态景点* /break;case 5:/* 退出程序* /break;while(select!=5) ; / *当select的值不为5时，继续循环*/四设计与调试分析1。菜单项运行主函数时菜单项完整输出结果正确2. 查询景点选出系统给出的景点名称如：1、锦屏山系统输出信息如下：名称：锦屏山简介：因山色锦绣，美如画屏，而被康熙皇帝命名为锦屏山票价：10结果正确。3. 查询最

16、短路径如:选择出发地：古城目的地：玉女峰系统输出如下：古城-> 孔子忘角一-玉女峰路径长度：25公里4. 查询所有路径女口：选出出发地：孔望山目的地：连岛系统输出如下：孔望山-连岛孔望山- >前三岛一-枫树湾连岛孔望山前三岛- >枫树湾-> 桃花涧一-连岛孔望山-> -前三岛 枫树湾> 桃花涧一-> 东海温泉一- >连岛结果正确5. 动态添加景点动态添加，目前只能添加进信息，方便查询，还未实现求路径的功能。五用户手册本程序界面如下：按序号进行操作!六测试成果1、查询景点最止:山崖望峰山公 屏军城于女岭杲囉 喘嗨:±汛:3曲廉鴻1 :?:

17、3:|:5:6:7:8:k査询景点的信息2. 査询景点间的裤随路各3. 査询最点间的最短游览路径4. 输入您要添加的景点.5. 退出谙输入您的选择，诸输入你更査询的景瓠1 锦屏山简介：称介价名简票園聽锦藉 美如画屏，而被康鯉帝離为镐屏山10ITF2、查询所有路径回*G：2222sfDebug3 .exeF1；锦屏山2：將军崖岩画3:舌城4：孔子望角5;玉女峰6:江岭7：花果山8：猴囉公园选择出发景点：1选择目地景点：3从锦屏山到古城的所有游览路径有：I第1条:锦屏山T将军崖岩画古城第2条:鞘屏山O将军崖薯画-江峻O玉女峰孔子璽角- 古城第3条:锦屏山-将军崖岩画-江岭-玉女峰-花果山-古城第4

18、条:锦屏山将军崖岩画-江岭猴嘴公园孔子更角古城宙5条:锦屏山-将军崖岩画-江岭-猴嘴公园-孔子里角-玉女峰-花果山-古 第E条:锦抹山将军產岩画，江峻潍嘴公朋花杲山古城I第7条:锦屏山将军崖岩画心花果Llj-t城第8条:锦屏山-将军塵岩画-花果山-江岭玉女峰孔子古城 第9条:锦屏山将军崖窘画-花果山江岭骐嘴公园-礼子里角 古城 第10条期屏山-猴嘴公园-孔子望角-古城第11条:锦屏猴囉公园 孔子望角珏女峰"江岭。将军崖岩画f古城|第12条:锦屏山-潍嘴公园-孔子里角玉女峰江片将军庠岩画- 花果山吹 第13条:锦屏山-猴嘴公园 孔子璽角-玉女峰-范果山古庾第1條:锦屏山- 猴嘴公园孔子

19、望角珏女峰花果'江岭将军崖岩画 第15釜锦屏山-鴻璐公园-江峻-滞军崖岩卧古威第16条灌屏山-猴嘴公园乍江岭o将军崖岩卧花果山古城第1 了条:镌屏山猴嘴公园亠江幘玉女峰孔子里角古城 第旳条:锦屏山猴嘴公园V江岭Q玉女峰J花果A古城I第19条:锦屏山-鴻嘴公园花果山咅城I第20条:锦屏山-猴嘴公园-花果山江岭-将军崖晋画-古城 第21条:锦屏山心猴嘴公园-花lU-江岭。玉女峰 孔子望弟古城3、查询最短路径山崖望峰山公 屏军城子女峻果嘴 锦將古孔玉江花猴 9 I 123456了8e2辺爆霆交件夹d吐屈匕职y|谨云港市导源咨询程序本程序能够；k査询最点的信息2、査询景点间的瞬鳖路轻3. 資询

20、最点间的最短瞬览路経4. 输入您要添加的景点5、退出请输入您的逸择：3 I景占：选释出发景札5 选择目地最点；4 从玉女峰到孔子里角的最短游览路轻是： 玉女峰-孔子璽角路轻长度：10公里継绽査询? 或7：4、添加景点r P:2222新逢文件夹Debug3 .exe -回S3请输入你想添加的景点：谓输入您的选菇'4景点名称；桃花河景点商介：桃花涧位于锦屏山桃花涧南麓，距连云港市区9公里。继续查询?(yn):n加了该新景点后的信息为：若称：锦屏山简介：因山色锦绕，美如画屏，而被康婆皇帝俞名为锦屏山票价：10将军崖岩画名称：将军崖岩画简介：这是我国迄今发现的最古老时代岩画，是东南沿海地区首次

21、发现的岩画 票价；20古城名称：古城简介：古城为黄土夯成，肖年建筑时留下来的孔穴和层层夯印，现在仍历历在目 票价；30IIIr G:2222新建文件裘 Debug3 .exe -名祢：孔于望角简介；这座由花岗岩、片麻岩构成的古老体，距今己有18亿年的历史票价：40 玉女峰 名祢；玉女峰 简介：岩壁秀润光洁，宛如玉石雕就，乘坐竹筏从水上望去，俨然是一位秀美绝 票价：50 江岭名称；江岭简介：河边聚集的三、四个村庄，四周園绕着育山，构成了一副极美的婺源衣村 票你60花果山名祢：花果山简介：景区内哨壁悬崖，层峦SW,颯峨壮观，且植被丰富，景色秀丽，一年四票价:70猴嘴公园名称：猴嘴公园简介：街道巷闾

22、，纵横交错，高楼广厦，鳞次栉比，令人心旷神怡票价；80樋枕丽桃花间位于锦屏山桃花涧南麓，距连云港市区9公里。Press any key to cord inue七附录(源程序清单)# include<stdio。h>#include<string 。 h># in elude stdlib.h ># define MAXV 11/*最多顶点个数* /#define MAXSIZE 20/ *字符串成员 name的最大长度* /# define MAXLEN 500/* 字符串成员 content的最大长度* /#define INF 32768/* 用 32768

23、 表示/int a=0 ; /*全局变量，用来记录每对顶点之间的所有路径的条数*/static n=8;typedef structint num;char nameMAXSIZE;char discription MAXLEN;VertexType ; /*顶点的结构定义*/typedef structint edges : MAXV : MAXV :;int vexnu m,arc num;VertexType vexsMAXV;MGraph;/*网的结构定义*/int visited MAXV ;/*全局数组，用来记录各顶点被访问的情况*/int p : MAXV ; / *全局数组，用

24、来存放路径上的各顶点*/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<=k-1;s+ )printf( ” s >”，g.vexs p s .name);printf (" % sn", );s=0;while (s < g。vex num)if (s! =i)/*保证找到的是简单路径，保证没有回路* /if(g.edge

25、sp :k : s!=INF&&visited:s=0)visited s =1;p k+1 =s;path(g, i,j,k+1);visiteds=0 ;s+;void disppath (MGraph g , int i , int j)int k;p 0=i ;for(k=0 ; k < g.vexnum;k+)visitedi =0;a=0;path(g,i,j , 0)void ppath(MGraph g , int pathl ,int i,int v0)int k;k=path1i；if (k=v0)return;ppath(g,path1,k, v0)

26、;printf (” s”,g.vexs );/*输出最短路径* /void dispath(MGraph g,intdist ,int path1,int s ,int n, int v0,int i)if (si =1 & & i! =v0)printf(”从 s 到% s 的最短游览路径是：n",g.vexsvO 。name, );printf (” s->”，g.vexs );ppath(g,path1, i, v0);printf( ” s ", );printf(”

27、 路径长度:%d 公里 n",disti :);/*由path1计算从v0到i的最短路径* /void Dijkstra(MGraph g,int vO , int p) /*采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径* /int dist : MAXV :, path1 : MAXV;int sMAXV;int mindis,i,j , u, n=g。 vexnum;for (i=0 ; i<n;i+ )dist i=g.edges vOi ;si=O ；if(g。 edgesv0 i<INF )path1i =v0;elsepath1i = 1;sv0 =1;

28、path1vO=O;for(i=0 ; i<n ; i+)mindis=INF ;u=-1 ；for (j=0 ; j n;j+ )if(s j=0& & distj<mindis)u=j;mindis=distj ;s : u: =1;for(j=0 ; j<n ; j+)if(s : j: =0)if (g.edges u j <INF && distu +g.edgesu j <distj)dist j =dist u +g。edgesu j;path1j=u ;dispath(g,dist, path1, s, n, vO,

29、 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'时，结

30、束循环*/printf ("ttt请输入你要查询的景点：”)；scanf(” % d ”，& i);for(int j=0 ; j g。vexnum ; j+)if (i=g.vexsj.num )printf ("%s 简介：n”， );printf( ” -n”)；printf ("%s” ，g。 vexs j .discription)；printf("n");printf (" n ” ) xi 1 / ?printf ("继续查询？(y 或 n): ” );scanf(” % s”,

31、 &s);if (s='N ' | s=' n')break；void Searchpathl ( MGraph g)/*查询两个景点间的所有路径*/printf ("景点：n ”；printf (”一 一 一 n"；printf(” tt1:锦屏山 ntt2 :将军崖岩画 n”);printf("tt3:古城 ntt4 :孔子望角 ntt5:玉女峰 ntt6 :江岭 ntt7:花果山 n”)；printf (” tt8 :猴嘴公园 n");prin tf(" -n");int i,j;char

32、 s;while(1)printf ("ttt选择出发景点：”)；fflush(stdin);scanf ("% d" , &i);printf (” ttt选择目地景点：”)；fflush (stdin);scanf ("% d", &j);for(int k=O;k<g。vexnum;k+ )if(i=g.vexsk 。num)i=k;for (int l=0;l g.vexnum ; l+)if(j=g。vexs I .num) j=l ;printf (” 从% s 到%s 的所有游览路径有:n", g。

33、vexs i .name, g。vexsj .name); disppath (g, i,j);prjntf (” 一-一 -一 -一 -n")；printf ("继续查询？ ( y 或 n)：');scanf(” % s", &s);if (s=' N'|s='n')break；void Searchpath2(MGraph g)/ *查询两个景点间的最短路径*/printf("景点:n”);printf (” 一-n ”)；計I ?printf (” tt1:锦屏山 ntt2:将军崖岩画 n”)；pri

34、ntf (” 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;k g.vexnum; k+)if(i=g。vexs k

35、.num) i=k;for (int l=0;l g。 vex num ; I+)if (j=g.vexs I。num) j=l;Dijkstra(g,i , j);printf( ”- 一 _ 一 _ 一 _ 一一 _一 一 _n")-U I丿, printf (”继续查询? ( y 或 n): ”)； scanf (” s”，& s);if (s=' N ' | |s=' n')break；/动态添加景点void Searchpath3(MGraph g , char * c , char *d )printf("请输入你想添加的

36、景点：n");printf( ”一 - 一 一 -n ” )char s;while (1)printf (” 景点名称:n");int i=0;while (i n 1)i+ ；scanf(” s”，& (g。vexs i。 name);c i =;printf (” 景点简介:n");scanf (” %s", &(g.vexs i .discription)；di=g。 vexsi.discription ；seanf (” s”，& s);if (s='N' |s=' n&#

37、39;)break;void main()/*主函数* /int i , j ;int b : 11 = 1,2, 3,4,5,6,7,8;char衣c : 11="锦屏山"，”将军崖岩画”,"古城"，”孔子望角","玉女峰"，"江岭”，”花果山”，” 猴嘴公园"char 衣 d : 11 ="名称：锦屏山n简介：因山色锦绣，美如画屏，而被康熙皇帝命名为锦屏山n票价：10” ,"名称：将军崖岩画n简介:这是我国迄今发现的最古老时代岩画，是东南沿海地区首次发现的岩画n票价：20"

38、;,"名称：古城n简介：古城为黄土夯成，当年建筑时留下来的孔穴和层层夯印，现在仍历历在目n票价:30","名称：孔子望角n简介：这座由花岗岩、片麻岩构成的古老体，距今已有18亿年的历史n票价：40","名称：玉女峰n简介：岩壁秀润光洁，宛如玉石雕就，乘坐竹筏从水上望去，俨然是一位秀美绝伦的少女n票价：50” ,"名称：江岭n简介：河边聚集的三、四个村庄，四周围绕着青山，构成了一副极美的婺源农村风光画卷n票价：60","名称：花果山n简介：景区内峭壁悬崖，层峦叠嶂，巍峨壮观，且植被丰富，景色秀丽，一年四季皆有特色n票

39、价:70",”名称：猴嘴公园n简介：街道巷闾，纵横交错，高楼广厦，鳞次栉比，令人心旷神怡n票价：80"MGraph g ;int A : 11 : 11 = 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,IN

40、F,INF , 18 , INF , INF ,INF , INF , INF , 18 , INF,10, 15 , INF;g。vexnum=n;g.arc num=14;for (i=0 ; ivg.vexnum ; i+)for (j=O;j<g。vexnum;j+ )g。edgesi j=Ai :j ;/ *建立无向网的邻接矩阵*/for(i=0;i g.vexnum ; i+)g.vexsi.num=bi;strcpy (g.vexsi。 name, c i);strcpy(g.vexsi 。 discription,d i);int select;dosystem(” ci

41、s");printf(" -连云港市导游咨询程序-n ” );printf(”本程序能够：n ”)；printf ("n,1n”)；printf ("| n");printf(”11、查询景点的信息1 n”);printf (”12、查询景点间的游览路径1 n");printf(”13、查询景点间的最短游览路径1 n");printf (”14、输入您要添加的景点1 n");printf ("15、退出1 n");printf(”11 n");printf (”1 1n");printf (" n ”)；- 一 一n y ?prin tf(”请输入您的选择：”)；seanf(” d”，& select);switch(sele