以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 基本要求： （1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。 （2）编写递归形式的算法，求得迷宫中所有可能的通路。 （3）以方阵形式输出迷宫及其通路。用c语言来实现

以下是基于链表实现的栈类型的代码：

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

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

typedef struct StackNode {
    int x; // 横坐标
    int y; // 纵坐标
    int dir; // 方向
} StackNode;

typedef struct Stack {
    StackNode data[MAXSIZE];
    int top; // 栈顶指针
} Stack;

void initStack(Stack *stack) {
    stack->top = -1;
}

int isStackEmpty(Stack *stack) {
    return stack->top == -1;
}

int isStackFull(Stack *stack) {
    return stack->top == MAXSIZE - 1;
}

void push(Stack *stack, StackNode node) {
    if (isStackFull(stack)) {
        printf("栈满\n");
        return;
    }
    stack->top++;
    stack->data[stack->top] = node;
}

StackNode pop(Stack *stack) {
    if (isStackEmpty(stack)) {
        printf("栈空\n");
        exit(1);
    }
    StackNode node = stack->data[stack->top];
    stack->top--;
    return node;
}

接下来是求解迷宫的非递归程序的代码：

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

#define ROW 6
#define COL 6

int maze[ROW][COL] = {
    {0, 0, 0, 0, 0, 0},
    {0, 1, 1, 0, 1, 0},
    {0, 0, 1, 0, 0, 0},
    {1, 0, 0, 1, 1, 1},
    {0, 1, 0, 0, 0, 0},
    {0, 1, 1, 1, 0, 0}
};

int mark[ROW][COL]; // 标记数组，记录当前位置是否已经走过
Stack path; // 存储路径的栈

void printPath() {
    printf("路径：");
    while (!isStackEmpty(&path)) {
        StackNode node = pop(&path);
        printf("(%d,%d,%d) ", node.x, node.y, node.dir);
    }
    printf("\n");
}

void mazePath(int x, int y, int dir) {
    StackNode node = {x, y, dir};
    push(&path, node); // 将当前位置压入栈中
    mark[x][y] = 1; // 标记为已走过
    if (x == ROW - 1 && y == COL - 1) { // 如果到达终点，输出路径
        printPath();
        return;
    }
    // 枚举四个方向
    if (x > 0 && maze[x-1][y] == 0 && mark[x-1][y] == 0) { // 上
        mazePath(x-1, y, 1);
    }
    if (y < COL - 1 && maze[x][y+1] == 0 && mark[x][y+1] == 0) { // 右
        mazePath(x, y+1, 2);
    }
    if (x < ROW - 1 && maze[x+1][y] == 0 && mark[x+1][y] == 0) { // 下
        mazePath(x+1, y, 3);
    }
    if (y > 0 && maze[x][y-1] == 0 && mark[x][y-1] == 0) { // 左
        mazePath(x, y-1, 4);
    }
    mark[x][y] = 0; // 标记为未走过，以便回溯
    pop(&path); // 弹出当前位置
}

int main() {
    initStack(&path);
    mazePath(0, 0, 1); // 从起点开始搜索，初始方向为向上
    return 0;
}

上述代码中，我们使用一个6x6的二维数组来表示迷宫，其中0表示可走，1表示墙壁。使用一个6x6的整型标记数组mark来记录当前位置是否已经走过。使用一个基于链表的栈类型path来存储路径。在mazePath函数中，我们从起点(0,0)开始，枚举四个方向，如果下一步可走且未走过，则将当前位置压入栈中，标记为已走过，继续搜索下一步。如果到达终点(5,5)，则输出路径。如果当前位置的四个方向都走不通，则将当前位置标记为未走过，弹出栈顶元素，以便回溯。