计算机科学与工程系。
课程设计题目迷宫
航班信息查询系统
学号。姓名。
班级。专业网络工程
完成时间 2013-1-4
指导教师。求迷宫从入口到出口的所有路径。
1．迷宫中不能使用递归算法查找路径。
2．试探方向限定为上、下、左、右四个方向。
3．迷宫采用随机生成和手工生成两种方式。
4．生成从迷宫入口到出口的最短和最长路径。
5．迷宫的入口和出口由键盘输入。
visual c++6.0的集成化环境。
对这样的矩形迷宫，可以用n*m的矩阵来描述，n和m分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。
为了描述迷宫中位置（i,j）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为1，否则为0。
经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。
1）题目：迷宫的生成与路由。生成一个n*m（n行m列）的迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，完成迷宫的组织与存储，并实现迷宫的路由算法。
即对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
2）设计要求：(1)n和m是用户可配置的，缺省值为50和50。(2)迷宫的入口和出口分别在左上角和右下角。
(3)求得的通路以二元组( i , j )的形式输出，其中（i, j）指示迷宫中的一个坐标。(4) 以二维数组存储迷宫数据。
3）该程序是迷宫的生成与路由。生成一个n*m（n行m列）的迷宫，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
1）数据结构的选择。
解决此问题需要运用到链栈的数据结构。因为计算机解迷宫时，通常用的是“穷举求解”的方法，为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。所以，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。
2）数据结构的定义。
1）栈的定义。
栈（stack）是只能对一端的数据元素进行操作，即限定仅在表尾进行插入或删除操作的线性表。
2）迷宫坐标的定义：
typedef struct node//链栈结构。
int row; /行。
int col; /列。
struct node * next;
mlink;
用途：该结构体用来存储迷宫中的行坐标和列坐标。
3）迷宫最大行列数定义：
#define maxx 50 //迷宫最大行数。
#define maxy 50 //迷宫最大列数。
用途：用来定义迷宫的最大尺寸为50*50。
2）函数之间关系：
在该程序中，首先进入的是菜单选择，在菜单中有3种选择，选1是手动输入迷宫函数；选2是随机自动生成迷宫；选3是退出程序。在手动生成迷宫时，有两种输出方式，一是矩阵输出，二是图形输出。在矩阵输出时，直接将数组中的数进行输出，在图形输出时，则要判断该点的情况，然后输入迷宫的出入口，再调用mgpath（）函数进行判断是否存在路径，如果存在则将路径经过的点进行输出，并且将经过的点进入到辅助数组中（辅助数组是辅助图形界面的输出），并且将辅助数组初始为1，辅助数组中点为路径的重新赋值为0，然后根据情况输出图形界面。
在自动生成迷宫时，用到了c语言随机函数，对于其它问题，和手动情况基本相同。
1）主菜单伪**：
while(flag1)
2）手动建立迷宫：
shuru();输入行列数。
printf("手动建立迷宫矩阵(0表示可通1表示障碍):");
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)scanf("%d",&mg[i][j]);
showplay(mg);/迷宫输出。
churukou();迷宫出入口的输入。
x=mazepath(mg);/判断路径函数。
if(x==1)
else printf("无通路！");system("pause");
break;//除了c语言随机函数，其他与手动建立迷宫类似。
4）数据类型定义：
typedef struct node//链栈结构。
int row; /行。
int col; /列。
struct node * next;
mlink;
mlink *stack;//定义一个栈。
int m,n,x1,x2,y1,y2;//定义全局变量。
int mg[m][n];
1）调试遇到的问题分析：
1）在编译框中显示“‘time’undeclared identifier”即没有定义‘time’函数。
双击错误信息，根据编译软件的提示找到了错误信息行然后发现在程序的的开头没有输入“#include<>。加一个该函数，编译通过。
2）在编译框中显示“nonstandard extension used：zero-sized array in struct/union”
和“class ‘maze’has an illegal zero-sized array”两行错误。双击错误信息，找到出错的程序段，经过查阅资料发现，在利用顺序栈时，没有定义顺序栈的向量空间大小，导致程序出错。但不要对向量空间定义过大，否则会浪费空间。
2）算法的时空分析：
由于链栈实际上是运算受限制的单链表。所以取栈顶元素运算的算法、置空栈运算的算法执行时间与问题的规模无关，则该算法的时间复杂度为o(1)；而其入栈运算的算法与出栈运算的算法相当于在链表的表尾进行插入和删除操作，不需要移动元素，时间复杂度也为o（1）。建立迷宫矩阵的时间复杂度为o（x*y）。
在查找路径的过程中，最坏的情况下可能要考察每一个非障碍的位置。因此，查找路径的时间复杂度应为o（unblocked）。
链栈的入栈算法、出栈算法、取栈顶元素算法、置空栈算法执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各个算法的空间性能均较好。只是对于存放顺序栈的向量空间大小的定义很难把握好，如果定义过大，会造成不必要的空间浪费。所以在定义时要慎重考虑。
运行该程序，运行的界面的会出现菜单界面，然后用户可根据界面的提示进行相应的操作，生成迷宫的方式有两种方式，手动生成和自动生成，手动生成时、，用户可根据自己的要求输入迷宫的格式，还需输入相应的入出口，确认程序就会生成相应的路径图形；自动生成只需输入所需的行数和列数，就会生成迷宫，接下来的操作和手动操作相同了。
图1-1手动生成迷宫。
图1-2图1-3 退出。
本次课程设计过程中由于掌握的知识不牢固，在编程序的过程中得到了同学的帮助和指导，在此表示感谢。课程设计的过程中，遇到了一些问题，大部分是课本中的知识掌握的不牢固，还有就是在以前学习c++的过程中相关的知识掌握的不够全面。在以后的学习过程中，自己一定要把各种知识掌握牢固。
还有在进行程序设计时，要有良好的设计风格。即要有恰当的标识符即模块名、变量名、常量名、子程序名等。这些名字应能反映它所代表的实际东西，应有一定的实际意义，使其能够见名知意，这样有助于程序员和其他人对程序的理解。
同时在编写程序时，要对每一个程序段加上注释，这样可以有助于程序员和其他人对程序的理解，以便能熟练的操作程序。还有在编写程序时要注意对程序的视觉组织，因为一个程序写得密密麻麻，分不出层次常常是很难看懂的。也使得程序的正确性大大降低。
#include<>
#include<>
#define m 50
#define n 50
typedef struct node//链栈结构。
int row; /行。
int col; /列。
struct node * next;
mlink;
mlink *stack;//定义一个栈。
int m,n,x1,x2,y1,y2;//定义全局变量。
int mg[m][n];
void shuru()
printf("输入行数：");
scanf("%d",&m);
printf("输入列数：");
数据结构课程设计报告
东莞理工学院城市学院。题目 二叉排序树 专业 计算机科学与技术 本 年级 2010级计算机科学与技术专业 1 班。个人姓名 何振江。指导教师 张娟老师 时间 2010至2011第二学期第18周 地点 实验楼615机房 东莞理工学院城市学院计算机与信息科学系制。2011年 6月。实习报告的内容。一 问...
数据结构课程设计报告
设计一个校园导游程序，为来访的客人提供信息查询服务。1 设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图 无向网 以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。2 存放景点代号 名称 简介等信息供用户查询。3 为来访客人提供图中任意景点相关信息的查询。4 为来访客人提供...
数据结构课程设计报告
河北科技大学。课程设计报告。学生姓名学号。专业班级。课程名称数据结构。学年学期 2 012 2 013学年第 2 学期指导教师 黄春茹。2 0 13年 6 月。课程设计成绩评定表。一 数据结构课程设计目标。二 问题描述。三 需求分析。四 概要设计。五 详细设计。六 软件说明书 给出软件如何使用，使用...