29迷宫问题940411326.doc

迷宫问题 一．实验目的 本次实习的目的在于使读者深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方式的理解。 二．实验内容 【问题描述】以一个m*n的长方阵表示迷宫，0和1分别表示迷宫的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得到没有通路的结论。 【基本要求】首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中，（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。 三．实验步骤（可选） #includestdio.h #include malloc.h #include stdlib.h #include string.h #includeiostream using namespace std; //函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define RANGE 100 //迷宫大小 typedef int Status; //函数的返回值 typedef int DirectiveType; //下一个通道方向 //stack.h #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 //栈的顺序存储实现 typedef struct{ int row; int col;}PosType; typedef struct{ int step; //当前位置在路径上的序号 PosType seat; //当前的坐标位置 DirectiveType di; //往下一个坐标位置的方向 }SElemType; typedef struct{ SElemType *base; SElemType *top; int stacksize;}SqStack; //栈的基本操作的算法实现 Status InitStack(SqStack s){ s.base = (SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!s.base) return OVERFLOW; s.top=s.base; s.stacksize=STACK_INIT_SIZE; return OK;} Status GetTop(SqStack s, SElemType e ){ if(s.top==s.base) return ERROR; e=*(s.top-1); return OK;} Status Push(SqStack s, SElemType e){ if(s.top-s.base = s.stacksize){ //栈满，追加存储空间 s.base = (SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!s.base)return OVERFLOW; s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT;} *s.top++ = e;return OK;} Status Pop(SqStack s, SElemType e){ if(s.top==s.base)return ERROR; e = * --s.top;return OK;} int StackEmpty(SqStack s){ return s.base==s.top;} Status ClearStack(SqStack s){ s.top = s.base; return OK;} //-------------------- 迷宫程序 ---------------------------------- #define ROW 9 //迷宫的行数 #define COL 8 //迷宫的列数 typedef struct{ int m,n,arr[RANGE][RANGE];}MazeType; //迷宫类型 Status InitMaze(MazeType maze, int