数据结构课程设计报告公园导游图

1、课 程 设 计 报 告课程名称 数据结构 课题名称 公园导游图 专 业 计算机科学与技术 班 级 计算机0702 学 号 姓 名 指导教师 2009年 10月 26日湖南工程学院课 程 设 计 任 务 书课程名称 数据结构 课 题 公园导游图 专业班级 计算机0702 学生姓名 学 号 指导老师 审 批 任务书下达日期 2009 年 10 月 8 日任务完成日期 2009 年 11 月 8 日1设计内容与设计要求1.1设计内容1.1.1 算术24游戏演示由系统随机生成4张扑克牌，用户利用扑克牌的数字及运算符号“+”、“”、“*”、“/”及括号“（”和“）”从键盘上输入一个计算表达式，系统运行后

2、得出计算结果，如果结果等于24，则显示“congratulation!”，否则显示“incorrect!”设计思路：从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达式，利用后缀表达式求值。1.1.2 迷宫探索随机生成一个迷宫图，迷宫大小为n*n，n预定义为常数，修改n的值可以改变迷宫的大小。用白色表示可走的路，蓝色表示墙壁不可以通过。系统设计两种运行方式：一种是系统自动探索（用递归方法实现）；另一种是由人工操作探索通路。设计思路：程序首先要考虑迷宫的表示，这是一个二维关系图，所以可选择二维数组来存储。数组元素只有两种值0和1，分别代表通路和墙壁。图形的显示可以根据数组元素的值来确定。如果是

3、人工探索，则依据按键来确定探索物的位置坐标，利用循环语句实现。如果是系统自动探索，可采用递归算法实现。1.1.3 二叉树遍历演示演示遍历二叉树的过程，所以首先建立二叉树，并用图形显示出树的形状。建立的过程是采用前序便利的方法来创建，设计两种生成树的方式：一种是系统随机生成，另一种是人工输入。考虑到屏幕界面的有限性，限定二叉树不超过5层，最多26个字符，输入字符小数点“.”代表null。初始树为某种颜色的结点，三种情况的遍历采用填充另外一种醒目的颜色，来表示当前遍历的结点，同时显示该结点的访问序号。同时在遍历的过程中在遍历图形的下方显示出遍历序列。1.1.4 数组应用按照行优先顺序将用户随机输入

4、的数据建成2维数组并以图形方式逐步显示出来，然后再按照列优先顺序以图形方式逐步输出相应数组。1.1.5 拓扑排序演示演示拓扑排序的过程。按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。要求每输出一个顶点后就演示从图中删去此顶点以及所有以它为尾的弧。1.1.6 图的遍历演示图的深度优先, 广度优先遍历过程，并输出原图结构及遍历结果。要求图的结点数不能少于6个。可以由系统随机生成图，也可以由用户手动输入图。报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一步改进图的效果。1.1.7 八皇后问题演示在8*8的棋盘上摆放8

5、个皇后，使他们不在同一条对角线上和不在一行和列上。 解决8皇后时，在安放第i行皇后时，需要在列的方向从1到n试探(j =1, n)：首先在第j列安放一个皇后，如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第j列安放的皇后。如果没有出现攻击，在第j列安放的皇后不动，递归安放第i+1行皇后。 该课题要求求解可能的方案及方案数并逐步演示摆放皇后的过程。1.1.8 双链表创建演示建立一个递增有序的双链表。功能是随机生成8个结点数据，每生成一个结点则申请空间得到一个指针，将数据存放到指针所指的数据域中，然后将结点插入到已经排好序的双链表中。所以第一步工作是判断新结点的插入位置，第二不演示

6、插入过程中指针的变化，第三步显示插入后的链表结果。1.1.9 公园导游图给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。要求用图示展示最佳路径。1.2 选题方案：所选题目根据学号确定，学号模9加1，即（学号%9+1）。如你的学号为12，则所选题目号为：12%9+1（题目4）。注意，所有的课题都要求用图形方式演示步骤和结果。有兴趣的同学可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法，但要预先告知老师，经过审批，方可确定课题。1.3设计要求：1.3.1 课程

7、设计报告规范（1）需求分析a. 程序的功能。b. 输入输出的要求。（2）概要设计a. 程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。b. 课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。（3）详细设计a. 采用c语言定义相关的数据类型。b. 写出各模块的类c码算法。c. 画出各函数的调用关系图、主要函数的流程图。（4）调试分析以及设计体会a. 测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b. 程序调试中遇到的问题以及解决问题的方法。c. 课程设计过程经验教训、心得体会。

8、（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。 （6）书写格式a. 设计报告要求用a4纸打印成册：b. 一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。（7）附录a. 源程序清单（带注释）1.3.2 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤 （占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地

9、运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。（5）独立完成情况（占10%）。1.3.3 课程验收要求（1）运行所设计的系统。（2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。2 进度安排2.1 计算机0701/0702班：第 7 周：星期一 8：0012：00 上课 星期一 14：0016：00 上课 星期五 18：0022：00 上机第 8 周：星期六 14：0018：00 上机 星期日 8：0012：00 上

10、机 星期日 18：0022：00 上课第 9 周：星期六 8：0012：00 上机 星期日 14：0018：00 上机2.2 计算机0703班： 第 7 周：星期一 8：0012：00 上课 星期一 14：0016：00 上课 星期六 8：0012：00 上机 星期日 14：0018：00 上机第 8 周：星期六 8：0012：00 上机 星期日 14：0018：00 上机第 9 周：星期六 14：0018：00 上机 星期日 18：0022：00 上机。 目 录1需求分析11.1课程设计内容和要求11.2 输入输出的要求12概要设计22.1 主要程序功能模22.2 课题涉及的数据结构和数据库

11、结构23详细设计43.1 c语言定义的相关数据类型43.2 各模块的类c码算法43.3 各函数的调用关系图、主要函数的流程图74调试分析以及设计体会114.1测试数据114.2程序调试中遇到的问题以及解决问题的方法154.3经验教训、心得体会155使用说明166附录171 需求分析1.1课程设计内容和要求。程序要能够显示出地图，要能够查找出地图中任意两点间的最短距离，以及不重复遍历全图的最短路径，并且在查找及遍历的每个过程都在图中显示出暂时的结果，以便演示整过过程。1.2输入输出的要求。程序执行要求有描述地图的两个文件，并放到相应位置。其中一个文件存放有描述地图各个景点之间距离的矩阵，另一个文

12、件存有地图中各景点在显示器上显示的位置。两个地图文件不允许有错误。执行相应功能前要求先选择。查找任意两点间的最短距离，要求输入要查找最短路径的两点。在运行各个小过程后要求输出暂时结果。2 概要设计2.1 程序模块程序共有主模块、查找两点最短路径并输出具体过程、寻找不重复遍历全图图路径并输出遍历过程、三个模块。主模块包含、载入地图、显示地图、功能选择与调用三部分。查找两点最短路径并输出具体过程模块中的输出具体过程为显示地图模块模块结构如图：功能调用输出图形查找两点最短路径并输出具体过程寻找不重复遍历全图路径并输出遍历过程载入图形主模块图2.12.2 课题涉及的数据结构和数据库结构程序主要用了图和

13、栈两种数据结构，采用矩阵来保存图形结构的地图，用栈保存遍历时经过的结点用以遍历的回溯，以及存储最终路径。图的抽象数据类型：adt graph数据对象:d=a1|1in，n0数据关系:r=|ai,ajd,1jn,1jn,其中每个元素可以有零个或多个前驱，可以有零个或多个后继基本运算：loadimg(*g)：从相应文件中载入图数据初始化图g。outputimg(*g)把图输出到屏幕。bestpath（）不重复遍历图。floyed（）计算图中所有点的两两最短路径。 栈的抽象数据类型：adt list数据对象：d=ai|1in，n0，数据关系：r=|ai,ai+1d，i=1，n-1基本运算：push（

14、*s，e）：进栈：将元素e查到栈s中作为栈顶元素。 pop（*s，*e）：出栈：从栈s中退出栈顶元素，并将其值赋予e。copsta(*s1, *s)：把栈s中的内容复制到栈s1。3 详细设计3.1采用c语言定义相关的数据类型。图的定义：typedef struct int edgesmaxmax; int n; /* n 顶点数*/int e; /* e 边数 */mgraph;栈的定义：typedef struct int bodymax; int top;stack;3.2写出各模块的类c码算法。3.2.1读取地图：把保存在文件中的地图数据载入到程序中相应的数据结构,图结构体g及顶点位置数

15、组vl2中。void loadimg(int vl2,mgraph *g) fp=fopen(g.g2,r); fscanf(fp, %d,&(g-n); for(i=0;in; i+) fscanf(fp, %d%d,&vli0,&vli1); fclose(fp); fp=fopen(g.g1,r); for(i=0,g-e=0; in; i+) for(j=0; jn; j+) fscanf(fp, %d,&(g-edgesij);fclose(fp);3.2.2 显示地图：把地图以图形方式输出到显示器。void outputimg(int vl2,mgraph *g) for(i=0,

16、g-e=0; in; i+) for(j=0; jn; j+) if(g-edgesij!=inf & ie+;画两点间路径; for(i=0;in; i+) 画景点；3.2.3 不重复遍历全图的最短路径：寻找从起点开始不重复走完所有景点的路径，如果该路径不存在，将提示。如果存在将会最终找出符合要求的最短路径。step1： if（没遍历完）if（向前有一景点没访问过）往下走；else 回溯到上一景点点（原景点之后景点变为没访问过）；if（ 遍历到起点 且 访问其以后景点必然与以前的试探路径相同） /说明 路径不再存在；若 以前找到过遍历路径则输出最佳结果 结束；else 到step1 开始下一

17、步搜索；else 若比以前有的结果更好，则输出结果并继续试探更好的遍历方法； 3.2.4 两点间最短路径：采用弗洛伊德算法，求出每点间的最短路径，并在计算过程中输出用户所求两点间的暂时计算出的最短路径。void floyed(mgraph *g, int amax, int pathmax,int vl2) for (i=0;in;i+) /*置初值*/ for (j=0;jn;j+) aij=g-edgesij; pathij=-1; 输入两景点； for (k=0;kn;k+) for (i=0;in;i+) for (j=0;jn;j+) if(aik!=inf & akj!=inf &

18、 aij(aik+akj) aij=aik+akj; pathij=k; 输出0到k号顶点被考虑作为中间节点时两景点的最短路径图；3.3各函数的调用关系图、主要函数的流程图。3.3.1函数调用关系图： 显示地图outputimg从文件中载入地图数据loadimg不重复遍历景点bestpath查找两点最短路径floyed主函数main查询最短路径的中间节点ppath显示两点间最短路径fdispath显示遍历路径disbestpath图3.1 函数调用关系图3.3.2主函数流程图：否否否是是是开始输出地图完成遍历图功能提示用户选择相应功能输入选择的功能号aa=0？结束a=1？a=2？完成查找两点间

19、最短路径功能从文件中载入地图图3.2 主函数流程图3.3.3查找两点最短路径函数floyed（）流程图：否否是把所有景点的两两最短路径初始值设为其直接距离，中途景点设为空开始输入要查找最短路径的两点i1、j1k=0k景点数？k+显示两点间最短路径结束更新最短路径长度为lmk+lkn，更新中途景点为k考虑k号景点可以作为路径的中途景点时，对每两个景点m、n计算距离lm,k+lk,jn并与原距离l0mnlmk+lkn写成了减号-以及字符忘加引号等。输入错误在编译时一般可以排除，编译时还没排除的错误以及逻辑错误一般要在调试运行时排除。排除错误主要是通过在程序中加入大量输出函数，输出运行状态，然后根据

20、输出结果定位出错位置，找出出错原因并解决问题。但在中途还遇到过一些奇怪的问题，如函数执行完毕之后不能正常跳出。我实在是找不到错在哪里，后来我改变了函数的结构，及程序的组织方式，问题终于没有了。我自己觉得应该是对语言或编译环境的细节还了解得不够造成了这类问题不能解决。4.3经验教训、心得体会。两周的课程设计中，碰到过许多问题。首先，上课时听的理论知识，各种算法似乎很容易理解，但是在真正的运用过程中，并不能把理论知道很好的和实践结合起来。在平时做实验时，尤其是这次课程设计，总感到有些无从下手。因此，在学知识的过程中，一定要多动手、动脑，将所学的知识熟练掌握，自如运用。其次，通过这次课程设计，对自己

21、的逻辑思维能力是一个很大的锻炼，加强了我们的系统思考问题的能力，在编程方面，我们开始从整体的角度来考虑问题了，而不再像以前一样的，没有一个总体的概念。也就是因为这种习惯，使自己在课程设计过程中浪费了不少的时间。 程序设计是一个毅力的考验过程。有时候往往只是一个小小的错误，却要费很多的时间来解决。在这个过程不能过于急躁，并且要很有耐心才行程序需要反复调试，其过程很可能相当令人头疼，有时花很长时间设计出来还是需要重做，那时心中未免有点灰心，有时还特别想放弃，此时更加需要静下心，查找原因。在课程设计中，感谢老师的耐心指导，让我能能能够顺利写出程序并把程序更快的调试正确，我从中也学到了许多新的方法和知

22、识。感谢在做课程设计帮助自己的一些同学，是他们给我的意见和建议，让我的程序能够更加完善。5.使用说明把地图文件放到与程序文件相同的目录，然后运行程序，程序会提供地图的图形显示，以及两个供选择的功能，选择相应编号或即可完成对应功能，并在图上看到其完成过程。6.附录#include stdio.h#include conio.h#include graphics.h#include dos.h#define closegr closegraph#define max 12#define inf 32767/*定义图结构*/typedef struct int edgesmaxmax; int n,

23、e; /* n 顶点数 e 边数*/mgraph;/*定义栈结构*/typedef struct int bodymax; int top;stack;int push(stack *s,int n) if(s-top=max-1)return 0; s-top+; s-bodys-top=n; return 1;int pop(stack *s,int *n) if(s-top=-1) return 0; *n=s-bodys-top; s-top-; return 1;void copsta(stack *s1, stack *s) int i; s1-top=s-top; for(i=0

24、;itop;i+) s1-bodyi = s-bodyi; void initgr(void) /* bgi初始化*/ int gd = detect, gm = 0; /* 和gd = vga,gm = vgahi是同样效果*/ registerbgidriver(egavga_driver); initgraph(&gd, &gm, ); /*从文件中读取图形到程序*/void loadimg(int vl2,mgraph *g) /*vl 顶点在显示器中显示时的坐标值 */file *fp; int i,j; fp=fopen(g.g2,r); fscanf(fp, %d,&(g-n);

25、 for(i=0;in; i+) fscanf(fp, %d%d,&vli0,&vli1); fclose(fp); fp=fopen(g.g1,r); for(i=0,g-e=0; in; i+) for(j=0; jn; j+) fscanf(fp, %d,&(g-edgesij); fclose(fp);/* 在屏幕显示上图形*/void outputimg(int vl2,mgraph *g) char jd1025=enter, flower garden,zoo,roller skating,teahouse,barbecue, amusement park, verandah,

26、buffet,botanical gardens,; int radius=10; int i,j; char s50=0; setlinestyle(0,0, 2); for(i=0,g-e=0; in; i+) for(j=0; jn; j+) if(g-edgesij!=inf & ie+; line(vli0,vli1,vlj0,vlj1); sprintf(s,%d,g-edgesij); setcolor(red); outtextxy( (vli0+vlj0)/2 ,(vli1+vlj1)/2+5 ,s); setcolor(white); for(i=0;in; i+) set

27、fillstyle(solid_fill,green), fillellipse(vli0,vli1,radius,radius), sprintf(s,%d,i), setcolor(red), outtextxy(vli0-3,vli1-3,s), setcolor(white), outtextxy(vli0+10,vli1-10,jdi); /* 遍历 */*/ /*显示整个路径*/void disbestpath(stack *psta, int vl2)int i, k; char s5= ; int radius=10; outtextxy(120,300,best path i

28、s that); pop(psta,&i); setlinestyle(0,0, 3); while(pop(psta,&k) setcolor(yellow); line(vlk0, vlk1, vli0, vli1); setcolor(red); setlinestyle(0,0, 2); setfillstyle(solid_fill,green), fillellipse(vlk0,vlk1,radius,radius), setfillstyle(solid_fill,green), fillellipse(vli0,vli1,radius,radius), setlinestyl

29、e(0,0, 3); sprintf(s,%d,k), outtextxy(vlk0-3,vlk1-3,s), sprintf(s,%d,i), outtextxy(vli0-3,vli1-3,s); i=k; setcolor(white); setlinestyle(0,0, 2);int bestpath(mgraph *g, int k, int vl2) /* k 起点编号*/ int i,n, length2=0,inf,k1; /* n为 已访问顶点数*/ int verstflagmax=0; /* 该顶点下一条可访问边对应的另一顶点号*/ int verflagmax=0;

30、/* 顶点数被访问标志*/ stack sta3;/*保存路径的栈sta0随时更新、sta1保存前一条最短路径、sta2直接用于显示（显示是栈会清空）*/ int count; int radius=10; int starmax=0; /*star1指示起点与第i个顶点间的路径是否可以作为起点路径初始为（可以作为起点路径） 当试探过一次或作过遍历路径最后一段时将为（不可再作为起点路径） */ int ns=0; /*还可以作为起点路径的边数*/char s5= ; for(i=0;in; i+) if(g-edgeski !=inf & i!=k)ns+; sta0.top=-1; sta1

31、.top=-1; verflagk=1; k1=k; push(&sta0,k1); n=1;bestpathloop1: for(i=verstflagk1; in); i+) verstflagk1+; if(g-edgesk1i!=inf & i!=k1 & verflagi=0 & verstflagk1n) if(k1=k) ns-; if(stari=1)continue; verflagi=1; length0+=g-edgesk1i; push(&sta0,i); setlinestyle(0,0, 3); setcolor(yellow); line(vlk10, vlk11

32、, vli0, vli1); setcolor(white); setlinestyle(0,0, 2); setfillstyle(solid_fill,green), fillellipse(vlk10,vlk11,radius,radius), setfillstyle(solid_fill,green), fillellipse(vli0,vli1,radius,radius), setcolor(red), sprintf(s,%d,k1), outtextxy(vlk10-3,vlk11-3,s), sprintf(s,%d,i), outtextxy(vli0-3,vli1-3,

33、s), setcolor(white); for(count=0;countn & g-edgesik!=inf & verstflagk=i) ns-; stari=1; if(length0length1) copsta(&sta1, &sta0); copsta(&sta2, &sta0); push(&sta2,k); disbestpath(&sta2, vl);outtextxy(300,300,now); for(count=0;count20;count+) delay(32767); length1=length0;verstflagi=0; if(ns=0) outtext

34、xy(350,300,finally ); push(&sta1,k); disbestpath(&sta1, vl);return; setlinestyle(0,0, 3), setcolor(black), line(vlk0, vlk1, vli0, vli1), setcolor(white), setlinestyle(0,0, 2), line(vlk0, vlk1, vli0, vli1); setfillstyle(solid_fill,green), fillellipse(vlk0,vlk1,radius,radius), setfillstyle(solid_fill,

35、green), fillellipse(vli0,vli1,radius,radius), setcolor(red), sprintf(s,%d,k), outtextxy(vlk0-3,vlk1-3,s), sprintf(s,%d,i), outtextxy(vli0-3,vli1-3,s), setcolor(white); for(count=0;count20;count+) delay(32767); break; k1=i; i=verstflagi-1; if(pop(&sta0, &i)=0 | pop(&sta0, &k1)=0 ) if(sta1.top=-1)outt

36、extxy(100,300,path not exit); return; push(&sta1,k);outtextxy(250,300,finally); disbestpath(&sta1, vl);return; setlinestyle(0,0, 3), setcolor(black), line(vlk10, vlk11, vli0, vli1), setcolor(white), setlinestyle(0,0, 2); line(vlk10, vlk11, vli0, vli1); setfillstyle(solid_fill,green), fillellipse(vlk

37、10,vlk11,radius,radius), setfillstyle(solid_fill,green), fillellipse(vli0,vli1,radius,radius), setcolor(red), sprintf(s,%d,k1), outtextxy(vlk10-3,vlk11-3,s), sprintf(s,%d,i), outtextxy(vli0-3,vli1-3,s), setcolor(white); for(count=0;countedgesk1i; verflagi=0; verstflagi=0; push(&sta0, k1); n-; i=verstflagk1; goto bestpathloop1; /* 两点最短路径 */void ppath(int pathmax,i