C语言数据结构迷宫问题

迷宫问题是一个经典的数据结构问题，通常使用图论和搜索算法来解决。在C语言中，可以使用结构体和栈来实现迷宫问题的解决。下面是一个简单的迷宫问题的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "maze.h"

// 初始化栈
void InitStack(Stack* s)
{
    s->_array = (DataType*)malloc(Stack_size * sizeof(DataType));
    s->_top = 0;
    s->_end = Stack_size;
}

// 销毁栈
void DestroyStack(Stack* s)
{
    free(s->_array);
    s->_array = NULL;
    s->_top = s->_end = 0;
}

// 判断栈是否为空
int IsEmpty(Stack* s)
{
    return s->_top == 0;
}

// 判断栈是否已满
int IsFull(Stack* s)
{
    return s->_top == s->_end;
}

// 入栈
void Push(Stack* s, DataType data)
{
    if (IsFull(s))
    {
        printf("Stack is full!\n");
        return;
    }
    s->_array[s->_top++] = data;
}

// 出栈
void Pop(Stack* s)
{
    if (IsEmpty(s))
    {
        printf("Stack is empty!\n");
        return;
    }
    --s->_top;
}

// 获取栈顶元素
DataType Top(Stack* s)
{
    if (IsEmpty(s))
    {
        printf("Stack is empty!\n");
        return (DataType){-1, -1};
    }
    return s->_array[s->_top - 1];
}

// 判断当前位置是否为迷宫的出口
int IsExit(maze* m, pos p)
{
    return p.row == N - 1 && p.col == N - 1;
}

// 判断当前位置是否为迷宫的入口
int IsEntry(maze* m, pos p)
{
    return p.row == m->entry.row && p.col == m->entry.col;
}

// 判断当前位置是否为迷宫的通路
int IsPass(maze* m, pos p)
{
    return p.row >= 0 && p.row < N && p.col >= 0 && p.col < N && m->mz[p.row][p.col] == 0;
}

// 打印路径
void PrintPath(Stack* s)
{
    printf("Path: ");
    for (size_t i = 0; i < s->_top; i++)
    {
        printf("(%d,%d) ", s->_array[i].row, s->_array[i].col);
    }
    printf("\n");
}

// 搜索迷宫的通路
void SearchPath(maze* m)
{
    Stack path, shortpath;
    InitStack(&path);
    InitStack(&shortpath);

    pos cur = m->entry;
    Push(&path, cur);

    while (!IsEmpty(&path))
    {
        cur = Top(&path);
        if (IsExit(m, cur))
        {
            if (IsEmpty(&shortpath) || path._top < shortpath._top)
            {
                memcpy(&shortpath, &path, sizeof(Stack));
            }
            Pop(&path);
            continue;
        }

        pos next = {cur.row, cur.col + 1};
        if (IsPass(m, next) && !IsEntry(m, next))
        {
            Push(&path, next);
            m->mz[next.row][next.col] = 2;
            continue;
        }

        next = (pos){cur.row + 1, cur.col};
        if (IsPass(m, next) && !IsEntry(m, next))
        {
            Push(&path, next);
            m->mz[next.row][next.col] = 2;
            continue;
        }

        next = (pos){cur.row, cur.col - 1};
        if (IsPass(m, next) && !IsEntry(m, next))
        {
            Push(&path, next);
            m->mz[next.row][next.col] = 2;
            continue;
        }

        next = (pos){cur.row - 1, cur.col};
        if (IsPass(m, next) && !IsEntry(m, next))
        {
            Push(&path, next);
            m->mz[next.row][next.col] = 2;
            continue;
        }

        Pop(&path);
    }

    PrintPath(&shortpath);

    DestroyStack(&path);
    DestroyStack(&shortpath);
}

上述代码中，使用了结构体`pos`来记录迷宫中每个点的坐标，使用结构体`Stack`来实现栈。`maze`结构体表示迷宫，其中`mz`数组表示迷宫地图，`entry`表示迷宫的入口点。`SearchPath`函数使用栈和搜索算法来搜索迷宫的通路，并打印出最短路径。