用C语言写数据结构用栈求解迷宫问题所有路径及最短路径程序

以下是使用栈来求解迷宫问题的所有路径及最短路径的C语言程序：

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

#define ROW 5 // 迷宫行数
#define COL 5 // 迷宫列数

struct Point {
    int x; // 横坐标
    int y; // 纵坐标
};

struct Stack {
    struct Point data[ROW * COL]; // 栈数据
    int top; // 栈顶指针
};

// 初始化栈
void initStack(struct Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
bool isEmpty(struct Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
bool isFull(struct Stack *s) {
    return s->top == ROW * COL - 1;
}

// 入栈
void push(struct Stack *s, struct Point p) {
    if (isFull(s)) {
        printf("Stack is full!\n");
        return;
    }
    s->top++;
    s->data[s->top] = p;
}

// 出栈
struct Point pop(struct Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        exit(-1);
    }
    struct Point p = s->data[s->top];
    s->top--;
    return p;
}

// 判断当前位置是否合法
bool isValid(int maze[][COL], int x, int y) {
    if (x < 0 || x >= ROW || y < 0 || y >= COL || maze[x][y] == 1) {
        return false;
    }
    return true;
}

// 求解所有路径
void findAllPaths(int maze[][COL], int startX, int startY, int endX, int endY) {
    struct Stack s;
    initStack(&s);
    struct Point start = {startX, startY};
    push(&s, start);
    while (!isEmpty(&s)) {
        struct Point cur = pop(&s);
        if (cur.x == endX && cur.y == endY) { // 到达终点，输出路径
            for (int i = 0; i <= s.top; i++) {
                printf("(%d, %d) ", s.data[i].x, s.data[i].y);
            }
            printf("(%d, %d)\n", endX, endY);
        } else { // 继续搜索
            maze[cur.x][cur.y] = 1; // 标记已经走过
            if (isValid(maze, cur.x - 1, cur.y)) { // 上
                struct Point next = {cur.x - 1, cur.y};
                push(&s, next);
            }
            if (isValid(maze, cur.x, cur.y + 1)) { // 右
                struct Point next = {cur.x, cur.y + 1};
                push(&s, next);
            }
            if (isValid(maze, cur.x + 1, cur.y)) { // 下
                struct Point next = {cur.x + 1, cur.y};
                push(&s, next);
            }
            if (isValid(maze, cur.x, cur.y - 1)) { // 左
                struct Point next = {cur.x, cur.y - 1};
                push(&s, next);
            }
            maze[cur.x][cur.y] = 0; // 恢复标记
        }
    }
}

// 求解最短路径
void findShortestPath(int maze[][COL], int startX, int startY, int endX, int endY) {
    struct Stack s1, s2;
    initStack(&s1);
    initStack(&s2);
    struct Point start = {startX, startY};
    push(&s1, start);
    while (!isEmpty(&s1)) {
        struct Point cur = pop(&s1);
        if (cur.x == endX && cur.y == endY) { // 到达终点，输出路径
            push(&s2, cur);
            for (int i = 0; !isEmpty(&s1); i++) {
                push(&s2, cur);
                cur = pop(&s1);
            }
            push(&s2, cur);
            while (!isEmpty(&s2)) {
                struct Point p = pop(&s2);
                printf("(%d, %d) ", p.x, p.y);
            }
            printf("\n");
            return;
        } else { // 继续搜索
            maze[cur.x][cur.y] = 1; // 标记已经走过
            if (isValid(maze, cur.x - 1, cur.y)) { // 上
                struct Point next = {cur.x - 1, cur.y};
                push(&s1, next);
            }
            if (isValid(maze, cur.x, cur.y + 1)) { // 右
                struct Point next = {cur.x, cur.y + 1};
                push(&s1, next);
            }
            if (isValid(maze, cur.x + 1, cur.y)) { // 下
                struct Point next = {cur.x + 1, cur.y};
                push(&s1, next);
            }
            if (isValid(maze, cur.x, cur.y - 1)) { // 左
                struct Point next = {cur.x, cur.y - 1};
                push(&s1, next);
            }
            maze[cur.x][cur.y] = 0; // 恢复标记
        }
    }
}

int main() {
    int maze[ROW][COL] = { // 迷宫地图，1表示障碍，0表示可以通过
        {0, 1, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 0, 0},
        {1, 1, 1, 0, 0},
        {0, 0, 0, 0, 1}
    };
    printf("All paths:\n");
    findAllPaths(maze, 0, 0, 4, 4);
    printf("Shortest path:\n");
    findShortestPath(maze, 0, 0, 4, 4);
    return 0;
}

上述程序中，我们使用了一个结构体`Point`来表示迷宫中的坐标，使用一个结构体`Stack`来表示栈。`findAllPaths`函数用来求解所有路径，`findShortestPath`函数用来求解最短路径。在搜索过程中，我们使用一个二维数组`maze`来标记哪些位置已经走过，避免重复搜索。