数据结构--栈和队列及应用--迷宫问题

r囧r小猫 2023-07-03 14:26 37阅读 0赞

# 数据结构–栈和队列及应用–迷宫问题 #

## 【实验目的】 ##

使学生深入了解栈和队列的特性，以便在实际问题背景下灵活运用它们，同时还将巩固对这两种结构的构造方法的掌握及基本操作的实现。

## 【实验内容】 ##

１、问题描述：以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得到没有通路的结论。  
２、基本要求：  
首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2)…  
３、测试数据：迷宫的测试数据如下：左下角(1,1)为入口，右下角(8,9)为出口。  
0 0 1 0 0 0 1 0  
0 0 1 0 0 0 1 0  
0 0 0 0 1 1 0 1  
0 1 1 1 0 0 1 0  
0 0 0 1 0 0 0 0  
0 1 0 0 0 1 0 1  
0 1 1 1 1 0 0 1  
1 1 0 0 0 1 0 1  
1 1 0 0 0 0 0 0

４、实现提示：计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。  
可以二维数组存储迷宫数据，通常设定入口点的下标为(1,1)，出口点的下标为(n,n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。

\#\#【实验数据】

#include <stdio.h>
    #include <math.h>
    #define M 8
    #define N 8
    #define MaxSize 100
    
    typedef int ElemType;
    
    int a[M+2][N+2]=
    {
        
        {
        1,1,1,1,1,1,1,1,1,1},
        {
        1,0,1,1,0,0,0,1,0,1},
        {
        1,0,1,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,0,1,0,0,0,0,0,2,1},
        {
        1,1,1,1,1,1,1,1,1,1}
    };
    
    typedef struct
    {
        
        int i;              //当前方块的行号
        int j;              //当前方块的列号
        int d;             //di是下一可走相邻方位的方位号     1为向右走  2为向下走   3为向左走  4为向上走
    } Box;
    
    typedef struct
    {
        
        Box base[MaxSize];
        int top;            //栈顶指针
    } SqList;
    
    void MazePath(SqList S)
    {
        
        int q=0,m,n,k=0;  //q 为计数器
        m=1;
        n=1;
        S.top=-1;
        do
        {
        
            k++;
            if(a[m][n]==0)
            {
        
                a[m][n]=1;
                S.top++;
                S.base[S.top].i=m;
                S.base[S.top].j=n;
                S.base[S.top].d=1;
                n=n+1;
                q=q+1;
                continue;
            }
            if(a[m][n]==1)
            {
        
                if(S.base[S.top].d==1)
                {
        
                    n=n-1;
                    S.base[S.top].d=2;
                    m=m+1;
                    continue;
                }
                if(S.base[S.top].d==2)
                {
        
                    m=m-1;
                    S.base[S.top].d=3;
                    n=n-1;
                    continue;
                }
                if(S.base[S.top].d==3)
                {
        
                    n=n+1;
                    S.base[S.top].d=4;
                    continue;
                }
                if(S.base[S.top].d==4)
                {
        
                    S.top--;
                    q--;
                    continue;
                }
            }
            if(a[m][n]==2)
            {
        
                printf(" 步数为:%d\n",q);
                break;
            }
        }
        while(S.top>-1);
        printf("执行了%d次循环\n",k);
    }
    
    int main()
    {
        
        void MazePath(SqList S);
        SqList S;
        MazePath(S);
        return 0;
    }

## 【实验结果】 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200207113317483.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk=,size_16,color_FFFFFF,t_70