栈的迷宫问题c语言

前言

栈是一种常用的数据结构，特别适合用来解决迷宫问题。在这个问题中，我们需要使用栈来实现迷宫的搜索和寻找路径的功能。本文将使用C语言来实现栈的迷宫问题，并对代码进行详细的分析和解释。

代码实现

#include<stdio.h>
#define MAX_ROWS 10
#define MAX_COLS 10

typedef struct {
    int row;
    int col;
} Position;

typedef struct {
    Position data[MAX_ROWS * MAX_COLS];
    int top;
} Stack;

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

void push(Stack *s, Position p) {
    if (s->top == MAX_ROWS * MAX_COLS - 1) {
        printf("Stack is full\n");
    } else {
        s->top++;
        s->data[s->top] = p;
    }
}

Position pop(Stack *s) {
    Position p;
    if (s->top == -1) {
        printf("Stack is empty\n");
    } else {
        p = s->data[s->top];
        s->top--;
    }
    return p;
}

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

void findPath(int maze[MAX_ROWS][MAX_COLS], int startRow, int startCol, int endRow, int endCol) {
    Stack s;
    initStack(&s);
    Position start = {startRow, startCol};
    push(&s, start);
    
    int visited[MAX_ROWS][MAX_COLS] = {0};
    visited[startRow][startCol] = 1;
    
    while (!isStackEmpty(&s)) {
        Position current = pop(&s);
        int row = current.row;
        int col = current.col;
        
        if (row == endRow && col == endCol) {
            printf("Path found!\n");
            return;
        }
        
        // Check neighbors
        if (row > 0 && maze[row-1][col] == 0 && visited[row-1][col] == 0) {
            Position neighbor = {row-1, col};
            push(&s, neighbor);
            visited[row-1][col] = 1;
        }
        if (row < MAX_ROWS-1 && maze[row+1][col] == 0 && visited[row+1][col] == 0) {
            Position neighbor = {row+1, col};
            push(&s, neighbor);
            visited[row+1][col] = 1;
        }
        if (col > 0 && maze[row][col-1] == 0 && visited[row][col-1] == 0) {
            Position neighbor = {row, col-1};
            push(&s, neighbor);
            visited[row][col-1] = 1;
        }
        if (col < MAX_COLS-1 && maze[row][col+1] == 0 && visited[row][col+1] == 0) {
            Position neighbor = {row, col+1};
            push(&s, neighbor);
            visited[row][col+1] = 1;
        }
    }
    
    printf("Path not found.\n");
}

代码解释和规范

我们定义了两个结构体，Position用于表示迷宫中的坐标，Stack用于表示栈。其中Stack的data数组存储了栈中的元素，top表示栈顶的索引。

initStack函数用于初始化栈，将栈的top设置为-1，表示栈为空。

push函数用于将元素压入栈中，需要判断栈是否已满。如果栈已满，则打印"Stack is full"的提示信息；否则，将元素添加到栈顶，并更新top的值。

pop函数用于弹出栈顶的元素，需要判断栈是否为空。如果栈为空，则打印"Stack is empty"的提示信息；否则，返回栈顶的元素，并更新top的值。

isStackEmpty函数用于判断栈是否为空。如果栈的top为-1，表示栈为空，返回1；否则，返回0。

findPath函数用于寻找迷宫的路径。它首先初始化栈和visited数组。然后，从起始位置开始，将起始位置压入栈中，并将其标记为已访问。接下来，使用while循环，直到栈为空。

循环中，首先弹出栈顶的元素，获取它的行和列。如果当前位置和目标位置相同，则打印"Path found!"的提示信息并返回。

然后，检查邻居的位置。如果邻居的位置合法（即不越界），且邻居位置的值为0（表示可以通过），且邻居位置未访问过，则将邻居位置压入栈中，并将其标记为已访问。

如果循环结束后仍未找到路径，则打印"Path not found."的提示信息。

总结

本文介绍了使用C语言实现栈的迷宫问题。代码中使用了栈来实现搜索和寻找路径的功能。通过压入起始位置并不断检查邻居位置，直到目标位置被找到或栈为空，从而寻找迷宫的路径。