数据结构课程设计报告精选.docx

数据结构课程设计报告

第一篇：数据结构课程设计报告计算机科学与工程系数据结构课程设计报告课程设计题目迷宫航班信息查询系统学号姓名班级专业网络工程完成时间2013-1-4指导教师数据结构课程设计迷宫题目一1.设计内容1.1问题描述求迷宫从入口到出口的所有路径。1.2设计要求1．迷宫中不能使用递归算法查找路径。2．试探方向限定为上、下、左、右四个方向。3．迷宫采用随机生成和手工生成两种方式。4．生成从迷宫入口到出口的最短和最长路径。5．迷宫的入口和出口由键盘输入。1.3开发环境VisualC++6.0的集成化环境1.4研究思路对这样的矩形迷宫，可以用N*M的矩阵来描述，N和M分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。为了描述迷宫中位置（i,j）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为1，否则为0。经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。2.设计步骤2.1需求分析（1）题目：迷宫的生成与路由。生成一个N*M（N行M列）的迷宫，0和1-1数据结构课程设计迷宫在该程序中，首先进入的是菜单选择，在菜单中有3种选择，选1是手动输入迷宫函数；选2是随机自动生成迷宫；选3是退出程序。在手动生成迷宫时，有两种输出方式，一是矩阵输出，二是图形输出。在矩阵输出时，直接将数组中的数进行输出，在图形输出时，则要判断该点的情况，然后输入迷宫的出入口，再调用mgpath（）函数进行判断是否存在路径，如果存在则将路径经过的点进行输出，并且将经过的点进入到辅助数组中（辅助数组是辅助图形界面的输出），并且将辅助数组初始为1，辅助数组中点为路径的重新赋值为0，然后根据情况输出图形界面。在自动生成迷宫时，用到了c语言随机函数，对于其它问题，和手动情况基本相同。2.3详细设计（1）主菜单伪代码：while(flag1){}{shuru();//输入行列数printf(“手动建立迷宫矩阵(0表示可通1表示障碍):n”);for(i=1;ifor(j=1;j数据结构课程设计迷宫和“class‘maze’hasanillegalzero-sizedarray”两行错误。双击错误信息，找到出错的程序段，经过查阅资料发现，在利用顺序栈时，没有定义顺序栈的向量空间大小，导致程序出错。但不要对向量空间定义过大，否则会浪费空间。（2）算法的时空分析：由于链栈实际上是运算受限制的单链表。所以取栈顶元素运算的算法、置空栈运算的算法执行时间与问题的规模无关，则该算法的时间复杂度为O(1)；而其入栈运算的算法与出栈运算的算法相当于在链表的表尾进行插入和删除操作，不需要移动元素，时间复杂度也为O（1）。建立迷宫矩阵的时间复杂度为O（x*y）。在查找路径的过程中，最坏的情况下可能要考察每一个非障碍的位置。因此，查找路径的时间复杂度应为O（unblocked）。链栈的入栈算法、出栈算法、取栈顶元素算法、置空栈算法执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各个算法的空间性能均较好。只是对于存放顺序栈的向量空间大小的定义很难把握好，如果定义过大，会造成不必要的空间浪费。所以在定义时要慎重考虑。3.用户使用说明运行该程序，运行的界面的会出现菜单界面，然后用户可根据界面的提示进行相应的操作，生成迷宫的方式有两种方式，手动生成和自动生成，手动生成时、，用户可根据自己的要求输入迷宫的格式，还需输入相应的入出口，确认程序就会生成相应的路径图形；自动生成只需输入所需的行数和列数，就会生成迷宫，接下来的操作和手动操作相同了。图数据结构课程设计迷宫图1-2图1-3退出5.总结与心得体会本次课程设计过程中由于掌握的知识不牢固，在编程序的过程中得到了同学的帮助和指导，在此表示感谢。课程设计的过程中，遇到了一些问题，大部分是课本中的知识掌握的不牢固，还有就是在以前学习C++的过程中相关的知识掌握的不够全面。在以后的学习过程中，自己一定要把各种知识掌握牢固。{}mg[i][j]=1;//初始化矩阵,将最外围置为1printf(“n输入迷宫入口：n”);scanf(“%d%d”,&x1,&y1);printf(“输入迷宫出口：n”);scanf(“%d%d”,&x2,&y2);}mlink;mlink*stack;//定义一个栈intm,n,x1,x2,y1,y2;//定义全局变量}voidshowplay(intmg[][M+2])//迷宫输出{n“);for(i=1;iprintf(”n“);for(j=