c语言迷宫问题的求解(栈和递归)

1、精选优质文档-倾情为你奉上实验报告【实验名称】项目一 迷宫问题的求解 【实验目的】 1. 了解栈的基本操作以及充分理解栈的特点。熟悉掌握栈的基本操作和结构体的运用。2. 学会用栈或者递归方法解决迷宫问题。【实验原理】1.本次实验中，以二维数组mazerowcol表示迷宫，0表示通路，1表示墙，在构建迷宫时，为了清晰显示，在最外层添加一圈墙。2.算法的核心思想是利用栈后进先出的特点，对迷宫进行探索，如果此路可行，则将此坐标的信息入栈，如果此路不通，则将此坐标的信息出栈。3.输入形式：根据控制台的提示，依次输入迷宫的行数、列数，然后输入迷宫，再输入入口和出口坐标。4.输出形式：由用户选择，由递归、

2、非递归两种求解方式输出一条迷宫通路。以非递归方式会显示一种求解方案，并给出相应的三元组序列和迷宫方阵；以递归方式则会显示出所有的路线。【实验内容】1. 需求分析（1） 问题描述以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求以递归和非递归两种方式分别输出一条迷宫的通路，以带方向坐标和迷宫图像表示。（2） 基本要求（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向

3、。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），。（2）编写递归形式的算法，求得迷宫中所有可能的通路。（3）以方阵形式输出迷宫及其通路。2. 概要设计（1） 栈的抽象数据类型ADT Stack数据对象：D=ai|aiElemSet, i=1,2, ,n, n0数据关系：R1=<ai-1,ai>|ai-1,aiD, i=1,2, ,n 约定an端为栈顶，a1端为栈底。基本操作： InitStack( &S ) 操作结果：构造一个空栈S。 DestroyStack ( &S ) 初始条件：栈S已存

4、在。 操作结果：销毁栈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

5、已存在且非空。 操作结果：删除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,*LinkStac

6、k; /链栈定义（2） 递归求解算法void MazePath2(int mazeMN,int a,int b,coordinate end,int m,int n) /采用递归的方式进行四个方向的探索 mazeab=-1; /起点标记为-1，即一定正确的通路，每次递归便将递归的坐标标记为正确的通路 if(a=end.x&&b=end.y) printf("find a access:n"); PrintMaze2(maze,m,n); /找到了路径，绘制地图 if(mazeab+1=0) MazePath2(maze,a,b+1,end,m,n); /向右

7、探索 if(mazea+1b=0) MazePath2(maze,a+1,b,end,m,n); /向下探索 if(mazea-1b=0) MazePath2(maze,a-1,b,end,m,n); /向上探索 if(mazeab-1=0) MazePath2(maze,a,b-1,end,m,n); /向左探索 mazeab=0;/如果当前道路不通，则回溯重新探索（3） 非递归求解算法Status MazePath(coordinate start,coordinate end,int mazeMN) /迷宫求解函数 int row,col,k,a,b,trg=1;/行、宽、新行、新宽、判

8、断标志int add42=0,1,1,0,0,-1,-1,0;/行增量和列增量数组 方向依次为东西南北 SElemType elem,elem2;/elem用于存储当前的地址信息，elem2用于最后将栈逆置输出 LinkStack S1, S2; /S1用于存放迷宫路径，S2用于逆置 InitStack(S1); InitStack(S2); /栈的初始化 mazestart.xstart.y=2; /标记初始位置 elem.x=start.x; elem.y=start.y; elem.d=-1; Push(S1,elem); /进行第一次入栈，代表从起点出发 while(!StackEmp

9、ty(S1) /栈不为空 有可行路径 Pop(S1,elem); /出栈，获取当前坐标及方向信息 row=elem.x; col=elem.y; k=elem.d+1; /下一个方向 while(k<4) /试探东南西北各个方向（0-东，1-南，2-西，3北） a=row+addk0; /新的行坐标 b=col+addk1; /新的列坐标 if(a=end.x && b=end.y && mazeab=0) /找到出口 elem.x=row; elem.y=col; elem.d=k; /4代表找到了出口 Push(S1,elem); elem.x=a;

10、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); mazeelem2.xelem2.y=3;/区分可行的路径，用于最后的输出 Push(S2,elem2); while(S2) /以三元组形式输出迷宫路径序列 Pop(S2,elem2); if(trg=1) printf("(%d,%d,%d)",elem2.x,elem2.y,elem2.d);

11、trg+; else printf(",(%d,%d,%d)",elem2.x,elem2.y,elem2.d); trg+; if(trg%5=0) printf("n"); printf("n"); return OK; /跳出循环 if(mazeab=0) /在未找到出口的情况下，寻找通路 mazeab=2; /标记已经走过此点 elem.x=row; elem.y=col; elem.d=k; Push(S1,elem); /将当前位置入栈 row=a; col=b;/赋予新的初始横纵坐标 k=-1; /k值初始化 k+; /

12、k每次循环加1，到4跳出循环，代表没有找到通路 printf("nYour maze don't have a access！n"); return FALSE;4. 测试结果实验测试数据：001000100010001000001101011100100001000001000101011110011100010111000000测试截图：输入迷宫并制定入口和出口：选择以栈方式求解迷宫（0-东，1-南，2-西，3-北）：选择递归方式求解迷宫：【总结】本次实验是程序设计与算法综合训练的第一次实验，实验要求栈和递归两种方式求解迷宫路径问题，整体难度中等。在实验初期，由

13、于缺乏经验，致使出现了一些不必要的书写错误，经过检查修改后无误，通过两种方式求出了迷宫路径，对栈和递归的使用有了更深层次的理解。【附录-代码】/Stack.h#ifndef STACK_H_INCLUDED#define STACK_H_INCLUDED#include<stdio.h>#include<malloc.h>#include<stdlib.h> /工程所需头文件#define M 20#define N 20/行宽的最大限制#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#defi

14、ne INFEASIBLE -1#define OVERFLOW -2typedef 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; retur

15、n 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) /元素出栈操作 Link

16、Stack 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_INCLUDEDStatus MazePath(coordinate start,coordinate end,int mazeMN) /迷宫求解函数 int row,col,k,a,b,trg=1;/行、宽、新行、新宽、判断标志 int add42=0,1,1,0,0,-1,-1,0;/行增量

17、和列增量数组 方向依次为东西南北 /例k=0时，a=row+addk0表明横坐标在原有基础上增加0，即横坐标不发生变动， /而b=col+addk1则表明纵坐标+1，即向东行走 SElemType elem,elem2;/elem用于存储当前的地址信息，elem2用于最后将栈逆置输出 LinkStack S1, S2; /S1用于存放迷宫路径，S2用于逆置 InitStack(S1); InitStack(S2); /栈的初始化 mazestart.xstart.y=2; /标记初始位置 elem.x=start.x; elem.y=start.y; elem.d=-1; Push(S1,el

18、em); /进行第一次入栈，代表从起点出发 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+addk0; /新的行坐标 b=col+addk1; /新的列坐标 if(a=end.x && b=end.y && mazeab=0) /找到了出口 elem.x=row; elem.y=col; elem.d=

19、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); mazeelem2.xelem2.y=3;/区分可行的路径，用于最后的输出 Push(S2,elem2); while(S2) /以三元组形式输出迷宫路径序列 Pop(S2,elem2); if(trg=1) printf("(%d,%

20、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(mazeab=0) /在未找到出口的情况下，寻找通路 mazeab=2; /标记已经走过此点 elem.x=row; elem.y=col; elem.d=k; Push(S1,elem); /将当前位置入栈 row=a

21、; col=b;/赋予新的初始横纵坐标 k=-1; /k值初始化 k+; /k每次循环加1，到4跳出循环，代表没有找到通路 printf("nYour maze don't have a access！n"); return FALSE;void InitMaze(int mazeMN,int m,int n) /迷宫初始化函数 int i,j; /计数值 printf("nPlease painting you maze:nthe '0' represent ceesee,the '1' represent wall.n&

22、quot;);/0代表通路，1代表墙体 for(i=1;i<=m;i+) for(j=1;j<=n;j+) scanf("%d",&mazeij); /构造迷宫，0代表通路，1代表不可通过的墙体 printf("The maze that you input is:n"); for(i=0;i<=m+1;i+) /在外围加一圈围墙 mazei0=1; mazein+1=1; for(j=1;j<=n;j+) maze0j=1; mazem+1j=1; for(i=0;i<=m+1;i+) /输出迷宫 for(j=0;

23、j<=n+1;j+) if(mazeij=0) printf(" "); else if(mazeij=1) printf(""); /代表墙体 printf("n"); printf("n");void PrintMaze(int mazeMN,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&

24、;&j=start.y) printf("起");/打印起点 else if(i=end.x&&j=end.y) printf("终");/打印终点 else if(mazeij=3) printf("");/打印正确的路径 else if(mazeij=0|mazeij=2) printf(" ");/打印其他路径 else if(mazeij=1) printf(""); /打印墙体 printf("n"); printf("n"

25、;);#endif / MAZE_H_INCLUDED/MAZE2.h#ifndef MAZE2_H_INCLUDED#define MAZE2_H_INCLUDEDvoid PrintMaze2(int mazeMN,int m,int n) /绘制迷宫 int i,j; for(i=0;i<=m+1;i+) for(j=0;j<=n+1;j+) if(mazeij=1) printf(""); /代表不可通过的墙体 else if(mazeij=-1) printf(""); /代表正确通路 else printf(" &quo

26、t;); /代表通路 printf("n"); void MazePath2(int mazeMN,int a,int b,coordinate end,int m,int n) /采用递归的方式进行四个方向的探索 mazeab=-1; /起点标记为-1，即一定正确的通路，每次递归便将递归的坐标标记为正确的通路 if(a=end.x&&b=end.y) printf("find a access:n"); PrintMaze2(maze,m,n); /绘制地图 if(mazeab+1=0) MazePath2(maze,a,b+1,end

27、,m,n); /向下探索 if(mazea+1b=0) MazePath2(maze,a+1,b,end,m,n); /向右探索 if(mazea-1b=0) MazePath2(maze,a-1,b,end,m,n); /向左探索 if(mazeab-1=0) MazePath2(maze,a,b-1,end,m,n); /向上探索 mazeab=0;/如果当前道路不通，则回溯重新探索#endif / MAZE2_H_INCLUDED/Main.cpp#include"Stack.h"#include"MAZE.h"#include"MAZE2.h"int main() int mazeMN; int