（1）问题描述 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和故障。设计一个程序，对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 （2）基本要求 首先实现一个以链表做存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,k）的形式输出，其中：（i,j）指迷宫中的一个坐标，d表示走到下一坐标的方向。c语言

以下是基于栈类型的非递归求解迷宫的程序，其中使用了深度优先搜索算法：

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100 // 栈的最大容量

typedef struct {
    int x;
    int y;
    int dir;
} PosType; // 位置类型，包括x坐标、y坐标和方向

typedef struct {
    PosType data[MAX_STACK_SIZE];
    int top;
} SqStack; // 栈类型，使用顺序存储结构

void InitStack(SqStack *S) { // 初始化栈
    S->top = -1;
}

int StackEmpty(SqStack S) { // 判断栈是否为空
    if (S.top == -1) {
        return 1;
    } else {
        return 0;
    }
}

int Push(SqStack *S, PosType e) { // 入栈操作
    if (S->top == MAX_STACK_SIZE - 1) {
        return 0; // 栈满，入栈失败
    }
    S->top++;
    S->data[S->top] = e;
    return 1; // 入栈成功
}

int Pop(SqStack *S, PosType *e) { // 出栈操作
    if (S->top == -1) {
        return 0; // 栈空，出栈失败
    }
    *e = S->data[S->top];
    S->top--;
    return 1; // 出栈成功
}

int GetTop(SqStack S, PosType *e) { // 获取栈顶元素
    if (S.top == -1) {
        return 0; // 栈空，获取失败
    }
    *e = S.data[S.top];
    return 1; // 获取成功
}

int Maze[10][10] = { // 迷宫地图，0表示通路，1表示障碍
    {0, 1, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
    {0, 0, 0, 0, 1, 0, 1, 0, 1, 0},
    {1, 1, 1, 0, 1, 0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0, 0, 1, 0, 1, 0},
    {0, 1, 1, 1, 1, 1, 0, 1, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 0}
};

int Visited[10][10] = {0}; // 标记数组，0表示未访问，1表示已访问

int Go[S][2] = { // 方向数组，表示向上、向右、向下、向左四个方向的行列坐标变化
    {-1, 0},
    {0, 1},
    {1, 0},
    {0, -1}
};

void PrintPath(SqStack S) { // 输出路径
    int i;
    PosType e;
    printf("迷宫路径为：\n");
    for (i = 0; i <= S.top; i++) {
        Pop(&S, &e);
        printf("(%d,%d,%d)\n", e.x, e.y, e.dir);
    }
}

int MazePath(int xi, int yi, int xe, int ye) { // 求解迷宫路径
    SqStack S;
    InitStack(&S);
    PosType e;
    int i, j, di, find;
    e.x = xi;
    e.y = yi;
    e.dir = -1;
    Push(&S, e);
    Visited[xi][yi] = 1;
    while (!StackEmpty(S)) {
        GetTop(S, &e);
        i = e.x;
        j = e.y;
        di = e.dir + 1;
        if (i == xe && j == ye) { // 到达终点，成功找到路径
            PrintPath(S);
            return 1;
        }
        find = 0;
        while (di < 4 && !find) { // 没有找到下一个可行方向
            int r = i + Go[di][0];
            int c = j + Go[di][1];
            if (r >= 0 && r < 10 && c >= 0 && c < 10 && !Maze[r][c] && !Visited[r][c]) { // 下一个位置可行
                e.x = r;
                e.y = c;
                e.dir = di;
                Push(&S, e);
                Visited[r][c] = 1;
                find = 1;
            } else {
                di++;
            }
        }
        if (!find) { // 四个方向都不可行，回退
            Pop(&S, &e);
            Visited[e.x][e.y] = 0;
        }
    }
    return 0; // 无法找到路径
}

int main() {
    int xi = 0, yi = 0, xe = 9, ye = 9;
    if (!MazePath(xi, yi, xe, ye)) {
        printf("无法找到迷宫路径！\n");
    }
    return 0;
}

这里假设迷宫地图是一个10×10的矩阵，入口为左上角，出口为右下角。在程序中，我们使用一个栈来存储走过的路径，使用一个标记数组来记录已访问的位置。深度优先搜索算法会依次尝试向上、向右、向下、向左四个方向前进，如果找到了一条通路，就输出路径；如果所有方向都无法前进，就回退到上一个位置重新选择方向。