实验报告
【实验名称】项目一迷宫问题的求解
【实验目的】
1.了解栈的基本操作以及充分理解栈的特点。熟悉掌握栈的基本操作和结构体
的运用。
2.学会用栈或者递归方法解决迷宫问题。
【实验原理】
1.本次实验中，以二维数组maze[row][col]表示迷宫，0表示通路，1表示墙，在构建迷宫时，为了清晰显示，在最外层添加一圈墙。
2.算法的核心思想是利用栈后进先出的特点，对迷宫进行探索，如果此路可行，则将此坐标的信息入栈，如果此路不通，则将此坐标的信息出栈。
3.输入形式：根据控制台的提示，依次输入迷宫的行数、列数，然后输入迷宫，再输入入口和出口坐标。
4.输出形式：由用户选择，由递归、非递归两种求解方式输出一条迷宫通路。以非递归方式会显示一种求解方案，并给出相应的三元组序列和迷宫方阵；以递归方式则会显示出所有的路线。
【实验内容】
1.需求分析
（1）问题描述
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
要求以递归和非递归两种方式分别输出一条迷宫的通路，以带方向坐标和迷宫图像表示。
（2）基本要求
（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。
（2）编写递归形式的算法，求得迷宫中所有可能的通路。
（3）以方阵形式输出迷宫及其通路。
2.概要设计
（1）栈的抽象数据类型
ADT Stack{
数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}
数据关系：R1={
约定an端为栈顶，a1端为栈底。
基本操作：
InitStack( &S )
操作结果：构造一个空栈S。
DestroyStack ( &S )
初始条件：栈S已存在。
操作结果：销毁栈S。
ClearStack( &S )
初始条件：栈S已存在。
操作结果：将S清为空栈。
StackEmpty( S )
初始条件：栈S已存在。
操作结果：若S为空栈，则返回TRUE，否则返回FALSE。
StackLength( S )
初始条件：栈S已存在。
操作结果：返回S的数据元素个数，即栈的长度。
GetTop( S, &e )
初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
Push( &S, e )
初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop( &S, &e )
初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
}ADT Stack
（2）程序模块
A.主程序模块：
int main()
{
}
B.栈模块：
实现栈抽象数据类型
C.迷宫模块：
实现迷宫抽象数据类型
3.详细设计
（1）类型定义
typedef struct
{
int x;
int y;
}coordinate; //迷宫中坐标类型
typedef struct
{
int x; //x行
int y; //y列
int d; //下一步的位置
}SElemType;//数据类型
typedef struct Stack
{
SElemType elem;
struct Stack *next;
}Stack,*LinkStack; //链栈定义
（2）递归求解算法
void MazePath2(int maze[M][N],int a,int b,coordinate end,int m,int n)
//采用递归的方式进行四个方向的探索
{
maze[a][b]=-1; //起点标记为-1，即一定正确的通路，每次递归便将递归的坐标标记为正确的通路
if(a==end.x&&b==end.y)
{
printf("find a access:\n");
PrintMaze2(maze,m,n); //找到了路径，绘制地图
}
if(maze[a][b+1]==0)
MazePath2(maze,a,b+1,end,m,n); //向右探索
if(maze[a+1][b]==0)
MazePath2(maze,a+1,b,end,m,n); //向下探索
if(maze[a-1][b]==0)
MazePath2(maze,a-1,b,end,m,n); //向上探索
if(maze[a][b-1]==0)
MazePath2(maze,a,b-1,end,m,n); //向左探索
maze[a][b]=0;//如果当前道路不通，则回溯重新探索
}
（3）非递归求解算法
Status MazePath(coordinate start,coordinate end,int maze[M][N]) //迷宫求解函数{
int row,col,k,a,b,trg=1;//行、宽、新行、新宽、判断标志
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
//行增量和列增量数组方向依次为东西南北
SElemType elem,elem2;//elem用于存储当前的地址信息，elem2用于最后将栈逆置输出
LinkStack S1, S2; //S1用于存放迷宫路径，S2用于逆置
InitStack(S1);
InitStack(S2); //栈的初始化
maze[start.x][start.y]=2; //标记初始位置
elem.x=start.x;
elem.y=start.y;
elem.d=-1;
Push(S1,elem); //进行第一次入栈，代表从起点出发
while(!StackEmpty(S1)) //栈不为空有可行路径
{
Pop(S1,elem); //出栈，获取当前坐标及方向信息
row=elem.x;
col=elem.y;
k=elem.d+1; //下一个方向
while(k<4) //试探东南西北各个方向（0-东，1-南，2-西，3北）
{
a=row+add[k][0]; //新的行坐标
b=col+add[k][1]; //新的列坐标
if(a==end.x && b==end.y && maze[a][b]==0) //找到出口
{
elem.x=row;
elem.y=col;
elem.d=k; //4代表找到了出口
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=4;
Push(S1,elem);//终点入栈
printf("\nFind a access,the access is(row,col,direct):\n");
while(S1) //逆置链栈
{
Pop(S1,elem2);
maze[elem2.x][elem2.y]=3;
//区分可行的路径，用于最后的输出
Push(S2,elem2);
}
while(S2) //以三元组形式输出迷宫路径序列
{
Pop(S2,elem2);
if(trg==1)
{
printf("(%d,%d,%d)",elem2.x,elem2.y,elem2.d);
trg++;
}
else
{
printf(",(%d,%d,%d)",elem2.x,elem2.y,elem2.d);
trg++;
}
if(trg%5==0)
printf("\n");
}
printf("\n");
return OK; //跳出循环
}
if(maze[a][b]==0) //在未找到出口的情况下，寻找通路
{
maze[a][b]=2; //标记已经走过此点
elem.x=row;
elem.y=col;
elem.d=k;
Push(S1,elem); //将当前位置入栈
row=a;
col=b;//赋予新的初始横纵坐标
k=-1; //k值初始化
}
k++; //k每次循环加1，到4跳出循环，代表没有找到通路
}
}
printf("\nYour maze don't have a access！\n");
return FALSE;
}
4.测试结果
实验测试数据：
测试截图：
输入迷宫并制定入口和出口：
选择以栈方式求解迷宫（0-东，1-南，2-西，3-北）：
选择递归方式求解迷宫：
【总结】
本次实验是程序设计与算法综合训练的第一次实验，实验要求栈和递归两种方式求解迷宫路径问题，整体难度中等。在实验初期，由于缺乏经验，致使出现了一些不必要的书写错误，经过检查修改后无误，通过两种方式求出了迷宫路径，对栈和递归的使用有了更深层次的理解。
【附录-代码】
//Stack.h
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED
#include
#include
#include
#define M 20
#define N 20//行宽的最大限制
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef struct
{
int x;
int y;
}coordinate; //迷宫中坐标类型
typedef struct
{
int x; //x行
int y; //y列
int d; //下一步的位置
}SElemType;//数据类型
typedef struct Stack
{
SElemType elem;
struct Stack *next;
}Stack,*LinkStack; //链栈定义
Status InitStack(LinkStack &S)//构造空栈
{
S=NULL;
return OK;
}
Status StackEmpty(LinkStack S)//判断栈是否为空。返回TRUE为空，返回FALSE为不空
{
if(S==NULL)
return TRUE;
else
return FALSE;
}
Status Push(LinkStack &S, SElemType e)//入栈操作
{
LinkStack p;
p=(LinkStack)malloc(sizeof(Stack));
p->elem=e;
p->next=S;
S=p;
return OK;
}
int Pop(LinkStack &S,SElemType &e) //元素出栈操作
{
LinkStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return OK;
}
else
return ERROR;
}
//MAZE.h
#ifndef MAZE_H_INCLUDED
#define MAZE_H_INCLUDED
Status MazePath(coordinate start,coordinate end,int maze[M][N]) //迷宫求解函数
{
int row,col,k,a,b,trg=1;//行、宽、新行、新宽、判断标志
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量数组方向依次为东西南北
//例k=0时，a=row+add[k][0]表明横坐标在原有基础上增加0，即横坐标不发生变动，
//而b=col+add[k][1]则表明纵坐标+1，即向东行走SElemType elem,elem2;//elem用于存储当前的地址信息，elem2用于最后将栈逆置输出
LinkStack S1, S2; //S1用于存放迷宫路径，S2用于逆置
InitStack(S1);
InitStack(S2); //栈的初始化
maze[start.x][start.y]=2; //标记初始位置
elem.x=start.x;
elem.y=start.y;
elem.d=-1;
Push(S1,elem); //进行第一次入栈，代表从起点出发
while(!StackEmpty(S1)) //栈不为空有可行路径
{
Pop(S1,elem); //出栈，获取当前坐标及方向信息
row=elem.x;
col=elem.y;
k=elem.d+1; //下一个方向
while(k<4) //试探东南西北各个方向（0-东，1-南，2-西，3北）
{
a=row+add[k][0]; //新的行坐标
b=col+add[k][1]; //新的列坐标
if(a==end.x && b==end.y && maze[a][b]==0) //找到了出口
{
elem.x=row;
elem.y=col;
elem.d=k; //4代表找到了出口
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=4;
Push(S1,elem);//终点入栈
printf("\nFind a access,the access is(row,col,direct):\n");
while(S1) //逆置链栈
{
Pop(S1,elem2);
maze[elem2.x][elem2.y]=3;//区分可行的路径，用于最后的输出
Push(S2,elem2);
}
while(S2) //以三元组形式输出迷宫路径序列
{
Pop(S2,elem2);
if(trg==1)
{
printf("(%d,%d,%d)",elem2.x,elem2.y,elem2.d);
trg++;
}
else
{
printf(",(%d,%d,%d)",elem2.x,elem2.y,elem2.d);
trg++;
}
if(trg%5==0)
printf("\n");
}
printf("\n");
return OK; //跳出循环
}
if(maze[a][b]==0) //在未找到出口的情况下，寻找通路
{
maze[a][b]=2; //标记已经走过此点
elem.x=row;
elem.y=col;
elem.d=k;
Push(S1,elem); //将当前位置入栈
row=a;
col=b;//赋予新的初始横纵坐标
k=-1; //k值初始化
}
k++; //k每次循环加1，到4跳出循环，代表没有找到通路
}
}
printf("\nYour maze don't have a access！\n");
return FALSE;
}
void InitMaze(int maze[M][N],int m,int n) //迷宫初始化函数
{
int i,j; //计数值
printf("\nPlease painting you maze:\nthe '0' represent ceesee,the '1' represent wall.\n");//0代表通路，1代表墙体
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
} //构造迷宫，0代表通路，1代表不可通过的墙体
printf("The maze that you input is:\n");
for(i=0;i<=m+1;i++) //在外围加一圈围墙
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=1;j<=n;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
{
if(maze[i][j]==0)
printf(" ");
else if(maze[i][j]==1)
printf("■"); //▉代表墙体
}
printf("\n");
}
printf("\n");
}
void PrintMaze(int maze[M][N],coordinate start,coordinate end,int m,int n) //打印迷宫函数{
int i,j; //计数值
for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
{
if(i==start.x&&j==start.y)
printf("起");//打印起点
else if(i==end.x&&j==end.y)
printf("终");//打印终点
else if(maze[i][j]==3)
printf("√");//打印正确的路径
else if(maze[i][j]==0||maze[i][j]==2)
printf(" ");//打印其他路径
else if(maze[i][j]==1)
printf("■"); //打印墙体
}
printf("\n");
}
printf("\n");
}
#endif // MAZE_H_INCLUDED
//MAZE2.h
#ifndef MAZE2_H_INCLUDED
#define MAZE2_H_INCLUDED
void PrintMaze2(int maze[M][N],int m,int n) //绘制迷宫
{
int i,j;
for(i=0;i<=m+1;i++)
{
for(j=0;j<=n+1;j++)
{
if(maze[i][j]==1)
printf("■"); //■代表不可通过的墙体
else if(maze[i][j]==-1)
printf("√"); //√代表正确通路
else
printf(" "); //代表通路
}
printf("\n");
}
}
void MazePath2(int maze[M][N],int a,int b,coordinate end,int m,int n) //采用递归的方式进行四个方向的探索{
maze[a][b]=-1; //起点标记为-1，即一定正确的通路，每次递归便将递归的坐标标记为正确的通路if(a==end.x&&b==end.y)
{
printf("find a access:\n");
PrintMaze2(maze,m,n); //绘制地图
}
if(maze[a][b+1]==0)
MazePath2(maze,a,b+1,end,m,n); //向下探索
if(maze[a+1][b]==0)
MazePath2(maze,a+1,b,end,m,n); //向右探索
if(maze[a-1][b]==0)
MazePath2(maze,a-1,b,end,m,n); //向左探索
if(maze[a][b-1]==0)
MazePath2(maze,a,b-1,end,m,n); //向上探索
maze[a][b]=0;//如果当前道路不通，则回溯重新探索
}
#endif // MAZE2_H_INCLUDED
//Main.cpp
#include"Stack.h"
#include"MAZE.h"
#include"MAZE2.h"
int main()
{
int maze[M][N];
int i=1;
int m,n,a,b,trg;
coordinate start,end; //start,end入口和出口的坐标
while(i)
{
printf("Please input the maze's row and column(<20):");
scanf("%d %d",&m,&n);//输入迷宫的长宽
if(m>=20||n>=20||m<=0||n<=0)
printf("Your input is error!\n");
else
i=0;
}
InitMaze(maze,m,n);//建立迷宫
printf("\nPlease input the coordinate of entry:");
scanf("%d %d",&start.x,&start.y);//输入起点坐标
a=start.x;
b=start.y;
printf("Please input the coordinate of exit:");
scanf("%d %d",&end.x,&end.y); //输入终点坐标
printf("Please choose the way:\n1.Stack way \n2.Recursive way.\n");
scanf("%d",&trg);
switch(trg)
{
case 1:
if(MazePath(start,end,maze))
PrintMaze(maze,start,end,m,n);
break;
case 2:
MazePath2(maze,a,b,end,m,n);
}
printf("\n");
printf("\nPress any key to end!\n");
getchar();
getchar(); //防止程序完成后闪退
return 0;
}
#include
Status StackEmpty(LStack s) //若栈s为空栈，则返回TRUE，否则FALSE { if(s.top->next==NULL) return TRUE; return FALSE; } Status Push(LStack &s,SElemType e)//插入元素e成为新的栈顶元素 { struct LNode *p; p=(LNode *)malloc(sizeof(LNode)); if(!p) exit(OVERFLOW); s.top->data=e; p->next=s.top; s.top=p; return OK; } Status Pop(LStack &s,SElemType &e)//删除s的栈顶元素，并且用e返回其值{ struct LNode *p; if(!(s.top->next)) exit(UNDERFLOW); p=s.top; s.top=p->next; e=s.top->data; free(p); return OK; } Status DestroyStack(LStack &s)//操作结果：栈s被销毁 { struct LNode *p; p=s.top; while(p) { s.top=p->next; free(p); p=s.top; } return OK; } //-----栈结束------ //-----迷宫开始------- #define MAXLEN 10// 迷宫包括外墙最大行列数 typedef struct{ int r;
数据结构课程设计_迷宫问题 /* Name:迷宫 Author:wujilin Description:输入时候一圈都应该是# 入口为（1,1) 如果有出口出口为(M-2,M-2) Date: 16-07-06 20:54 Copyright:wujilin */ #include
#include
C语言课程设计报告题目：迷宫问题 姓名： 班级： 学号： 组员： 指导教师： 学院： 专业：
课程设计（报告）任务及评语
目录 第1章课程设计的目的与要求 (1) 1.1 课程设计目的 (1) 1.2 课程设计的实验环境 (1) 1.3 课程设计的预备知识 (1) 1.4 课程设计要求 (1) 第2章课程设计内容 (2) 2.1程序功能介绍 (2) 2.2程序整体设计说明 (2) 2.2.1设计思路 (2) 2.2.2数据结构设计及用法说明 (3) 2.2.3程序结构（流程图） (4) 2.2.4各模块的功能及程序说明 (6) 2.2.5程序结果 (7) 2.3程序源代码及注释 (7) 第3章课程设计总结 (17) 参考资料 (18)
第1章课程设计的目的与要求 1.1 课程设计目的 本课程设计是计算机科学与技术专业重要的实践性环节之一，是在学生学习完《程序设计语言(C)》课程后进行的一次全面的综合练习。本课程设计的目的和任务： 1. 巩固和加深学生对C语言课程的基本知识的理解和掌握 2. 掌握C语言编程和程序调试的基本技能 3. 利用C语言进行基本的软件设计 4. 掌握书写程序设计说明文档的能力 5. 提高运用C语言解决实际问题的能力 1.2 课程设计的实验环境 硬件要求能运行Windows 2000/XP操作系统的微机系统。C语言程序设计及相应的开发环境。 1.3 课程设计的预备知识 熟悉C语言及C语言开发工具。 1.4 课程设计要求 1. 分析课程设计题目的要求 2. 写出详细设计说明 3. 编写程序代码，调试程序使其能正确运行 4. 设计完成的软件要便于操作和使用 5. 设计完成后提交课程设计报告
基于栈的C语言迷宫问题与实现 一．问题描述 多年以来，迷宫问题一直是令人感兴趣的题目。实验心理学家训练老鼠在迷宫中寻找食物。许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用“栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。 迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。 一个迷宫可用上图所示方阵[m,n]表示，0表示能通过，1 表示不能通过。现假设耗子从左上角[1,1]进入迷宫，编写算法，寻求一条从右下角[m,n] 出去的路径。下图是一个迷宫的示意图： 迷宫示意图 二．算法基本思想 迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。 在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前
一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向，栈中保存的就是一条迷宫的通路。 为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺序逐一生成候选者并检验。 三．主要数据结构 1.方阵栈： #define STACK_INI_SIZE 100 typedef struct { int *top; //指向栈的顶端域 int *base; //指向栈的低端域 int length; //栈的长度 int stacksize; //栈的最大长度 }sqstack; 2．产生迷宫的矩阵二维数组 为了使每一个迷宫存在迷宫的边界和两个端口：入口、出口，设置了一个二维数组，在迷宫的周边定义为1，使得迷宫存在边界，并在（1,1），（x-2,y-2）初定义为0，即定义迷宫的出口，大大减小了无解的情况。 for(i=0;i /*迷宫游戏by CDQ*/ /* vc++ 6.0 编译成功 本程序参照网上一个特殊算法随机生成迷宫 该算法优点： 效率高，从入口到出口只有唯一路径，入口出口自己设定 该算法缺点： 宽度高度都必须为奇数，只能生成n*m矩阵迷宫 */ #include 求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。 首先用如图所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。 为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图所示的迷宫,对应的迷宫数组mg如下: int mg[M+1][N+1]={ /*M=10,N=10*/ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; 伪代码： c语言描述如下： void mgpath() /*路径为:(1,1)->(M-2,N-2)*/ { int i,j,di,find,k; top++; /*初始方块进栈*/ Stack[top].i=1; Stack[top].j=1; 求迷宫问题就是求出从入口到出口的路径。在求解时, 通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通, 则继续往前走；否则沿原路退回,换一个方向再继续试探, 直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回（称为回溯）, 需要用一个后进先出的栈来保存从入口到当前位置的路径。 首先用如图3.3 所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径, 即在求得的路径上不能重复出现同一通道块。 为了表示迷宫, 设置一个数组mg,其中每个元素表示一个方块的状态, 为0 时表示对应方块是通道, 为1 时表示对应方块为墙, 如图3.3 所示的迷宫, 对应的迷宫数组mg如下: int mg[M+1][N+1]={ /*M=10,N=10*/ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; 伪代码： c 语言描述如下： void mgpath() /* 路径为:(1,1)->(M-2,N-2)*/ { int i,j,di,find,k; top++; /* 初始方块进栈*/ Stack[top].i=1; Stack[top].j=1; Stack[top].di=-1; mg[1][1]=-1; while (top>-1) /* 栈不空时循环*/ { i=Stack[top].i; j=Stack[top].j; di=Stack[top].di; if (i==M-2 && j==N-2) /* 找到了出口, 输出路径*/ { printf(" 迷宫路径如下:\n"); for (k=0;k<=top;k++) { printf("\t(%d,%d)",Stack[k].i,Stack[k] .j); if ((k+1)%5==0) printf("\n"); } 数据结构试验——迷宫问题 （一）基本问题 1.问题描述 这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。 简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。 入口 出口 图1 迷宫示意图 迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北(为了清晰，以下称“上下左右”)。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。 2.数据结构设计 以一个m×n的数组mg表示迷宫，每个元素表示一个方块状态，数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为1。根据题目中的数据，设置一个数组mg如下 int mg[M+2][N+2]= { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1}, {1,0,0,1,0,0,0,1}, {1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1} };在算法中用到的栈采用顺序存储结构，将栈定义为 Struct { int i; //当前方块的行号 int j; //当前方块的列号 int di; //di是下一个相邻的可走的方位号 }st[MaxSize];// 定义栈 int top=-1 //初始化栈 3设计运算算法 要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步（称为回溯），重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。 方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把上、右、下、左（即顺时针方向）依次编号为0、1、2、3.其增量数组move[4]如图3所示。 move[4] x y 0 -1 0 1 0 1 2 1 0 3 0 -1 图2数组move[4] 方位示意图如下： 通路：通路上的每一个点有3个属性：一个横坐标属性i、一个列坐标属性j和一个方向属性di，表示其下一点的位置。如果约定尝试的顺序为上、右、下、左（即顺时针方向），则每尝试一个方向不通时，di值增1，当d增至4时，表示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一条迷宫通路。 （1）下面介绍求解迷宫（xi,yj）到终点（xe,ye）的路径的函数：先将入口进栈（其初始位置设置为—1），在栈不空时循环——取栈顶方块（不退栈）①若该方块为出口，输出所有的方块即为路径，其代码和相应解释如下： 迷宫c语言 #include <stdio.h> #include <conio.h> #include <windows.h> #include <time.h> #define Height 31 //迷宫的高度，必须为奇数#define Width 25 //迷宫的宽度，必须为奇数 #define Wall 1 #define Road 0 #define Start 2 #define End 3 #define Esc 5 #define Up 1 #define Down 2 #define Left 3 #define Right 4 int map[Height+2][Width+2]; void gotoxy(int x,int y) //移动坐标 { COORD coord; coord.X=x; coord.Y=y; SetConsoleCursorPosition( GetStdHandle( STD_OUTPUT_HANDLE ), coord ); } void hidden()//隐藏光标 { HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE); CONSOLE_CURSOR_INFO cci; GetConsoleCursorInfo(hOut,&cci); cci.bVisible=0;//赋1为显示，赋0为隐藏 SetConsoleCursorInfo(hOut,&cci); } void create(int x,int y) //随机生成迷宫 { int c[4][2]={0,1,1,0,0,-1,-1,0}; //四个方向 int i,j,t; //将方向打乱 for(i=0;i<4;i++) { j=rand()%4; C语言编写的迷宫小游戏源代码 #include C语言走迷宫之完美版 #include<stdio.h> #include<time.h> #include<stdlib.h> int maze[100][100];//定义最大迷宫数组 int m,n;//定义行列 typedef struct pos//定义位置的结构体 { int x;//定义行 int y;//定义列 }pos; typedef struct//定义顺序栈 { pos base[100];//定义顺序栈存储结构 int top;//头指针 }stack; int isEmpty(stack);//定义判断栈是否为空的函数 void push(stack *,int,int);//入栈 void pop(stack *,int *,int *);//出栈 int isEmpty(stack s1)//判断栈是否为空的函数 { if(s1.top==0)//当头指针指向首地址时栈为空并返回1 return 1;//返回1 return 0;//否则返回0 } void push(stack *s1,int x,int y)//入栈 { (s1->base[s1->top]).x=x;//将当前行坐标存入栈 (s1->base[s1->top]).y=y;//y同上 s1->top++;//指针指向下一个位置 } void pop(stack *s1,int *x,int *y)//出栈 { s1->top--;//指针指向前一个位置 *x=(s1->base[s1->top]).x;//将当前行坐标赋给x所指向的元素*y=(s1->base[s1->top]).y;//y同上 } void main()//主函数 { void InitMaze();//初始化迷宫 /*注：本程序探索迷宫的优先顺序=> 1-下、2-右、3-上、4-左<=总体趋势：下右，逆时针方向。因为出口就在右边下方*/ #include 基于栈的C语言迷宫问题与实现 一. 问题描述 多年以来，迷宫问题一直是令人感兴趣的题目。实验心理学家训练老鼠在迷宫中寻找食物。 许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是，老鼠过迷宫问题就此产生, 这是一个很有趣的计算机问题，主要利用“栈”是老鼠通过尝试的办法从入口穿过迷宫走到岀口。 迷宫只有两个门，一个叫做入口，另一个叫做岀口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一岀口处放置了 一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。 一个迷宫可用上图所示方阵［m,n］表示，0表示能通过，1表示不能通过。现假设耗子从左上 角［1,1］进入迷宫，编写算法，寻求一条从右下角［m,n］岀去的路径。下图是一个迷宫的示意图： 算法基本思想 迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口岀发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换 下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到 入口点。 在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进 的方向，栈中保存的就是一条迷宫的通路。 为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按 迷宫示意图 C语言课程设计-迷宫游戏 设计报告 题目:完整的二维迷宫游戏 学院:工商管理学院 专业:信息系统与信息管理 班级:050507 姓名:孙月 指导教师:张首伟 设计日期:2004年12月10日 题目:完整的二维迷宫游戏 一、选题背景: 问题的提出:我们在玩迷宫游戏的时候,常常在过了一关之后就结束了～这里设计的迷宫游戏足够多～难以程度也不尽相同～可以过瘾的玩。模仿的有那么一点意思～还请多多指教: 二、设计思想: ,1,.问题描述 用一个m行n列的二维数组来表示迷宫。数组中每个元素的取值为0或1～其中值0表示通路～值1表示阻塞～入口在左上方,1～1,处～出口在右下方,m,n,处～如图所示。要求求出从迷宫入口到出口有无通路～若有通路则指出其中一条通路的路径～即输出找到通路的迷宫数组～其中通路上的“0”用另一数字,例如8,替换～同时打印出所走通路径上每一步的位置坐标及下一步的方向。 ,2,(求解方法说明: 1(为使问题一般化～假设以二维数组maze(1:m,1:n)表示迷宫～并设maze(i,j)表示任一位置。 2(对每个位置maze(i,j)～可移动的八个方向从正东起顺时 针方向顺序为:E～SE～S～SW～W～NW～N～NE。再用一个二维数组move表示这八个方向上坐标的增量～如下表所示～move(v,1)表示第v个方向上i的增量, move(v,2)表示第v个方向上j的增量。 三、程序流程图 四、程序清单: 一、 二、 #include 数据结构与算法实验报告 基于栈的C语言迷宫问题与实现 一．问题描述 多年以来，迷宫问题一直是令人感兴趣的题目。实验心理学家训练老鼠在迷宫中寻找食物。许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用“栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。 迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。 一个迷宫可用上图所示方阵[m,n]表示，0表示能通过，1 表示不能通过。现假设耗子从左上角[1,1]进入迷宫，编写算法，寻求一条从右下角[m,n] 出去的路径。下图是一个迷宫的示意图： 迷宫示意图 二．算法基本思想 迷宫求解问题是栈的一个典型应用。基本算法思想是：在某个点上，按照一定的顺序（在本程序中顺序为上、右、下、左）对周围的墙、路进行判断（在本程序中分别用1、0）代替，若周围某个位置为0，则移动到该点上，再进行下一次判断；若周围的位置都为1（即没有通路），则一步步原路返回并判断有无其他通路，然后再次进行相同的判断，直到走到终点为止，或者确认没有任何通路后终止程序。 要实现上述算法，需要用到栈的思想。栈里面压的是走过的路径，若遇到死路，则将该位置 （在栈的顶层）弹出，再进行下一次判断；若遇到通路，则将该位置压栈并进行下一次判断。如此反复循环，直到程序结束。此时，若迷宫有通路，则栈中存储的是迷宫通路坐标的倒序排列，再把所有坐标顺序打印后，即可得到正确的迷宫通路。 三．程序具体部分的说明 1.迷宫的生成 根据题目的要求，迷宫的大小是自定义输入的。所以在程序中用malloc申请动态二维数组。数组中的元素为随机生成的0、1。数组周围一圈的元素全部定义为1，以表示边界。 2.栈的C语言实现 为了实现栈的功能，即清空、压栈、弹出、返回栈顶元素，在程序中编写了相应的函数。 MakeNULL 清空栈 Push 将横、纵坐标压栈 Topx 返回栈顶存储的横坐标 Topy 返回栈顶存储的纵坐标 Pop 弹出栈顶元素 3.具体的判断算法 当位置坐标（程序中为X Y）移到某一位置时，将这个位置的值赋值为1并压栈，以说明该点已经走过。接着依次判断该点的上、右、下、左是否为0，若有一方为0，则移动到该位置上，进行下次判断；若为周围位置全部是1，则将该点压栈后不断弹出，每次弹出时判断栈顶元素（即走过的路）周围有无其他通路。如果有的话，则选择该方向继续走下去；如果栈已经为空仍然没有找到出路，则迷宫没有出口程序结束。 当X Y走到出口坐标时，程序判断部分结束。栈里面存储的是每个走过的点的坐标，将这些横纵坐标分别存储在两个数组中，最后将数组中的坐标元素倒序输出，即得到了完整的路径。 四．程序源代码及注释 // Maze.cpp : 定义控制台应用程序的入口点。 // #include"stdafx.h" #include 本程序代码为C语言解决数据结构（严蔚敏）中关于迷宫的问题。程序不仅实现迷宫路径查找，还实现文字描述路径功能 可以直接粘贴到vc6.0中运行 【代码如下】 # include int listlen; }sqlist; int topelem[2]; //栈顶元素 void creatstack(sqlist *mazepath); //创建一个存储路径的栈 void creatmap(int (*mazemap)[10]); //创建迷宫图纸 void printmap(int (*mazemap)[10]); void footprint(int x,int y,int k,int (*mazemap)[10]); int position(int x,int y); //判断是否到终点 int passroad(int x,int y,int (*mazemap)[10]); void findpath(int (*mazemap)[10],sqlist *mazepath); //在mazemap当中寻找mazepaht void printpath(sqlist *mazepath); void roadinwords(sqlist *mazepath); //文字叙述如何走迷宫 void push(int x,int y,sqlist *mazepath); //栈操作 void pop(sqlist *mazepath); void gettop(sqlist *mazepath); void main() 基于栈的C语言迷宫问题与实现 数据结构与算法实验报告 基于栈的C语言迷宫问题与实现 一．问题描述 多年以来，迷宫问题一直是令人感兴趣的题目。实验心理学家训练老鼠在迷宫中寻找食物。许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用“栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。 迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。 一个迷宫可用上图所示方阵[m,n]表示，0表示能通过，1 表示不能通过。现假设耗子从左上角[1,1]进入迷宫，编写算法，寻求一条从右下角 [m,n] 出去的路径。下图是一个迷宫的示意图： 迷宫示意图 二．算法基本思想 迷宫求解问题是栈的一个典型应用。基本算法思想是：在某个点上，按照一定的顺序（在本程序中顺序为上、右、下、左）对周围的墙、路进行判断（在本程序中分别用1、0）代替，若周围某个位置为0，则移动到该点上，再进行下一次判断；若周围的位置都为1（即没有通路），则一步步原路返回并判断有无其他通路，然后再次进行相同的判断，直到走到终点为止，或者确认没有任何通路后终止程序。 要实现上述算法，需要用到栈的思想。栈里面压的是走过的路径，若遇到死路，则将该位置（在栈的顶层）弹出，再进行下一次判断；若遇到通路，则将该位置压栈并进行下一次判断。如此反复循环，直到程序结束。此时，若迷宫有通路，则栈中存储的是迷宫通路坐标的倒序排列，再把所有坐标顺序打印后，即可得到正确的迷宫通路。 三．程序具体部分的说明 1.迷宫的生成 根据题目的要求，迷宫的大小是自定义输入 的。所以在程序中用malloc申请动态二维 数组。数组中的元素为随机生成的0、1。数组周围一圈的元素全部定义为1，以表示边 界。 2.栈的C语言实现 为了实现栈的功能，即清空、压栈、弹出、返回栈顶元素，在程序中编写了相应的函 数。 C语言迷宫问题代码如下： #include for(i=0;i迷宫游戏C语言代码讲解
求解迷宫问题(c语言,很详细哦)
求解迷宫问题(c语言,很详细哦)
c语言实现 迷宫问题.
迷宫c语言
C语言编写的迷宫小游戏_源代码
C语言走迷宫之完美版
迷宫(C语言版)
C语言迷宫程序
C语言课程设计-迷宫游戏
基于栈的C语言迷宫问题与实现
c语言~走迷宫
基于栈的C语言迷宫问题与实现
c语言迷宫问题代码实现
相关主题
文本预览