实验2-1 栈与迷宫求解【实验目的】1.熟悉C语言的上机环境VC6，掌握C语言程序设计方法与特点。2.掌握栈的顺序存储结构的定义及C语言实现。3.掌握栈的顺序存储结构上的各种基本操作。4.应用栈实现迷宫通路算法。5.迷宫求解的关键结构定义及C语言实现。【问题说明】一个迷宫可用n阶方阵表示，1表示能通过，0 表示不能通过。现假设老鼠从左上角[1,1]进入迷宫，编写算法，寻求一条从右下角[n,n] 出去的路径。下图是一个迷宫的示意图： 迷宫示意图【算法基本思想】迷宫求解是栈的一个典型应用。基本算法思想是：（1）若当前位置“可通”，则纳入“当前路径”，并继续朝着“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；（2）若当前位置“不可通过”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；（3）若该通道块的四周4个方块均“不可通过”，则应从“当前路径”上删除该通道块。注：（1）下一位置：“当前位置”四周4个方向（东南西北）上相邻的方块。（2）假设用栈记录当前路径，则栈顶存放的是“当前路径上最后一个通道块”。（3）纳入路径：当前位置入栈。（4）从当前路径上删除前一通道块：出栈。 求迷宫中一条从入口到出口的路径的算法，具体请参见p51。【实验内容】1.    顺序栈的初始化、元素的入栈、出栈、以及栈的判空。2.    迷宫关键操作：a)    迷宫的初始化b)    判断当前位置可否通过c)    为能通过的地方留下足迹，为当前走过的有效的步骤数d)    探索下一位置并返回下一位置的坐标e)    曾走过但不通的地方也留下足迹，为-1f)    关键算法：迷宫存在从入口到出口的通道，则求得一条存放在栈中，并返回tureg)    输出迷宫3. 测试：不同入口和出口的迷宫问题求解路径。【实验重点】1、    C语言定义顺序栈2、    会多文件组织方式编写程序3、    顺序栈的初始化、元素的入栈、出栈、以及栈的判空操作4、    迷宫的关键算法。【实验步骤与代码指导】1.    定义相关结构：（1）定义位置类型typedef struct{    int r;              //迷宫矩阵的行    int c;              //迷宫矩阵的列}PosType;（2）定义栈的元素类型typedef struct{      int ord;             //通道块在路径上的“序号”    PosType seat;        //通道块在迷宫中的“坐标位置”    int di;              //从此通道块走向下一通道块的“方向”,1-4表示东南西北    }SElemType;         （3）定义顺序/栈类型typedef struct{    SElemType *base;     //栈底指针，栈构造前和销毁后，base为NULL    SElemType *top;      //栈顶指针    int stacksize;       //当前已分配的存储空间，以元素为单位}SqStack;                （4）定义迷宫类型typedef int MazeType[MAXLEN][MAXLEN]; //MAXLEN*MAXLEN二维数组 2．建立头文件maze.h如下：#ifndef _MAZE_H#define  _MAZE_H#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include "common.h"#define STACK_INIT_SIZE 100   //存储空间初始化分配量#define STACK_INCREMENT 10    //存储空间分配增量#define MAXLEN 10typedef struct{    int r;              //迷宫矩阵的行    int c;              //迷宫矩阵的列}PosType;typedef struct{      int ord;             //通道块在路径上的“序号”    PosType seat;        //通道块在迷宫中的“坐标位置”    int di;              //从此通道块走向下一通道块的“方向”,1-4表示东南西北    }SElemType;              //栈的元素类型typedef struct{    SElemType *base;     //栈底指针，栈构造前和销毁后，base为NULL    SElemType *top;      //栈顶指针    int stacksize;       //当前已分配的存储空间，以元素为单位}SqStack;                //栈类型-顺序存储typedef int MazeType[MAXLEN][MAXLEN]; //MAXLEN*MAXLEN二维数组 //迷宫类型Status InitStack(SqStack &S);        //初始化栈Status DestroyStack(SqStack &S);     //销毁栈Status Push(SqStack &S,SElemType e);  //向栈顶插入元素Status Pop(SqStack &S,SElemType &e);  //出栈Status StackEmpty(SqStack S);       //栈是否为空Status InitMaze(MazeType &maze);                         //初始化迷宫Status Pass(MazeType &maze,PosType curpos);               //判断当前位置可否通过Status FootPrint(MazeType &maze,PosType curpos,int curstep);  //留下足迹，足迹为步骤数PosType NextPos(PosType curpos,int i);             //探索下一位置并返回下一位置的坐标Status MarkPrint(MazeType &maze,PosType curpos);            //曾走过但不通留下标记-1//迷宫maze存在从入口start到end的通道则求得一条存放在栈中Status MazePath(MazeType &maze,PosType start,PosType end);    void PrintMaze(MazeType &maze);                               //输出迷宫#endif3. 再建立一个头文件common.h如下：#ifndef _COMMON_H#define  _COMMON_H#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;#endif4. 将实现放在Maze.cpp里，文件内容如下：#include <time.h>#include "maze.h"Status InitStack(SqStack &S){    S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));    if(!S.base) exit(OVERFLOW);    S.top=S.base;    S.stacksize=STACK_INIT_SIZE;    return OK;}Status DestroyStack(SqStack &S){    if (S.base!=NULL){        free(S.base);        S.stacksize=0;        printf("顺序栈已经销毁\n");        return OK;    }    else return FALSE;}Status Push(SqStack &S,SElemType e){    if (S.top-S.base>=S.stacksize ){        S.base=(SElemType *) realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));        if(!S.base) exit(OVERFLOW);        S.top=S.base+S.stacksize;        S.stacksize+=STACK_INCREMENT;    }    *S.top++=e;    return OK;}Status Pop(SqStack &S,SElemType &e){    if(S.top==S.base) return ERROR;    e=*--S.top;    return OK;             }Status StackEmpty(SqStack S){    if (S.base==S.top) return TRUE;    else return FALSE;}//定义墙值为0，可通过路径为1，不可通过路径为-1Status InitMaze(MazeType &maze){     int i,j;                for(i=0;i<MAXLEN;i++){                     //迷宫行外墙        maze[0][i]=0;        maze[MAXLEN-1][i]=0;    }    for(i=0;i<MAXLEN;i++){                     //迷宫列外墙        maze[i][0]=0;        maze[i][MAXLEN-1]=0;    }        srand((unsigned)time(NULL));  //随机种子    for(i=1;i<MAXLEN-1;i++)        for(j=1;j<MAXLEN-1;j++)            maze[i][j]=1;    //初始化迷宫                for(i=1;i<MAXLEN-1;i++){            for(j=1;j<MAXLEN-1;j++){                int n=rand()%29;               //利用随机函数随机生成n值                if(n<MAXLEN-1)    maze[i][j]=0;  //随机设置通道块上的不通的路块            }        }        maze[1][1]=1;        maze[MAXLEN-2][MAXLEN-2]=1;                    return OK;            }void PrintMaze(MazeType &maze){     int i,j;    printf("用递增的数字代表迷宫的从入口到出口的一条路径\n");    printf("用0代表墙和不通的地方用\n用-1代表曾走过的通道块但不通\n");    printf("用1代表可以通过的通道块\n");    printf("  ");    for(i=0;i<MAXLEN;i++)  //打印列数名        printf("%4d",i);    printf("\n\n");    for(i=0;i<MAXLEN;i++){        printf("%2d",i);  //打印行名         for(j=0;j<MAXLEN;j++)            printf("%4d",maze[i][j]); //输出迷宫//当前位置的标记                  printf("\n\n");    }}Status Pass(MazeType &maze,PosType curpos){    if(maze[curpos.r][curpos.c]==1)  //可通        return TRUE;    else        return FALSE;    }Status FootPrint(MazeType &maze,PosType curpos,int curstep){    maze[curpos.r][curpos.c]=curstep;  //记录可通足迹    return OK;    }PosType NextPos(PosType curpos,int i){    PosType cpos=curpos;    switch(i){        //1.2.3.4分别表示东,南,西,北方向    case 1 : cpos.c+=1; break;    case 2 : cpos.r+=1; break;    case 3 : cpos.c-=1; break;    case 4 : cpos.r-=1; break;    default: exit(ERROR);      }    return cpos;    }Status MarkPrint(MazeType &maze,PosType curpos){    maze[curpos.r][curpos.c]=-1;   //-1表示曾走过但不通        return OK;}Status MazePath(MazeType &maze,PosType start,PosType end){        //若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底到栈顶），并返回TRUE；否则返回FALSE    SqStack S; InitStack(S); //初始化栈        PosType curpos=start;  //设置"当前位置"为"入口位置"        int curstep=1;   //探索第一步    SElemType e;        do{           if(Pass(maze,curpos)){      //当前位置可以通过,即未曾走过的通道块            FootPrint(maze,curpos,curstep); //留下足迹                        e.ord=curstep; e.seat=curpos; e.di=1;            Push(S,e);              //加入路径            if(curpos.r==end.r && curpos.c==end.c)    return TRUE; //到达出口                         curpos=NextPos(curpos,1); //下一位置是当前位置的东邻            curstep++;       //探索下一步                                    }        else{        //当前位置不通            if(!StackEmpty(S)){                     Pop(S,e);                curstep--;                while(e.di==4 && !StackEmpty(S)){                    MarkPrint(maze,e.seat); //留下不能通过的标记,并退一步                    Pop(S,e);                      curstep--;                }//while                if(e.di<4){                                        e.di++;    //换下一个方向探索                    Push(S,e);                     curstep++;                    curpos=NextPos(e.seat,e.di);  //设定当前位置是该新方向上的相邻                }            }        }    }while(!StackEmpty(S));     return FALSE;    }5. 主函数：#include <stdio.h>#include "maze.h" void main(){    MazeType maze;    PosType start,end;    InitMaze(maze);                //初始化并创建迷宫    start.r=1; start.c=1;          //迷宫入口坐标    end.c=MAXLEN-2;end.r=MAXLEN-2; //迷宫出口坐标        PrintMaze(maze);    if(MazePath(maze,start,end)){        printf("存在从入口到出口的迷宫路径！\n");        PrintMaze(maze);          //打印路径**/        }else printf("迷宫路径不存在！\n");    }【实验总结】【实验心得】