手写一个链栈（算法村第四关青铜挑战）

?本链栈用于解决迷宫问题之寻找所有路径

/**
 * 存储路径坐标的结点，称为路径结点
 * 因为数量无法确定，故使用链式结构
 */
typedef struct Node
{
    int coordinate; //坐标
    struct Node* next;
}Node;

typedef Node* PNode;    //路径结点的指针类型
typedef Node* LinkStack;    //链栈指针,可代表栈顶指针


/**
 * 创建一个链栈，并返回栈顶指针
 */
LinkStack creatLinkStack()
{
    LinkStack top = (LinkStack)malloc(sizeof(Node));

    if(top != NULL)
        top->next = NULL;
    else
        printf("链栈创建失败");

    return top;
}

/**
 * @param top 坐标要入的栈的栈顶指针
 * @param coordinate 入栈坐标
 */
void push(LinkStack top, int coordinate)
{
    PNode pNode = (PNode)malloc(sizeof(Node));

    if(pNode == NULL)
        printf("入栈失败");
    else
    {
        pNode->coordinate = coordinate;
        //头插法
        pNode->next = top->next;
        top->next = pNode;
    }
}

/**
 * 空栈返回1，非空返回0
 */
int isEmpty(LinkStack top)
{
    return top->next==NULL ? 1 : 0;
}

/**
 * 弹出栈顶元素的坐标
 */
int pop(LinkStack top)
{
    int coordinate;

    coordinate = top->next->coordinate; //获取栈顶元素的坐标

    //删除栈顶元素，更新栈顶指针
    PNode t = top->next;
    top->next = t->next;
    free(t);

    return coordinate;
}

全部代码

// Created by Mr.Chen on 2023/12/25.

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

/**
 * 9*9迷宫(最外围是一堵墙)
 * 1代表墙，0代表空格
 * 只有东西南北4个方向可以走
 */
#define SIZE 9   //迷宫大小
int maze[SIZE][SIZE];   //迷宫

/**
 * 存储路径坐标的结点，称为路径结点
 * 因为数量无法确定，故使用链式结构
 */
typedef struct Node
{
    int coordinate; //坐标
    struct Node* next;
}Node;

typedef Node* PNode;    //路径结点的指针类型
typedef Node* LinkStack;    //链栈指针,可代表栈顶指针


/**
 * 创建一个链栈，并返回栈顶指针
 */
LinkStack creatLinkStack()
{
    LinkStack top = (LinkStack)malloc(sizeof(Node));

    if(top != NULL)
        top->next = NULL;
    else
        printf("链栈创建失败");

    return top;
}

/**
 * @param top 坐标要入的栈的栈顶指针
 * @param coordinate 入栈坐标
 */
void push(LinkStack top, int coordinate)
{
    PNode pNode = (PNode)malloc(sizeof(Node));

    if(pNode == NULL)
        printf("入栈失败");
    else
    {
        pNode->coordinate = coordinate;
        //头插法
        pNode->next = top->next;
        top->next = pNode;
    }
}

/**
 * 空栈返回1，非空返回0
 */
int isEmpty(LinkStack top)
{
    return top->next==NULL ? 1 : 0;
}

/**
 * 弹出栈顶元素的坐标
 */
int pop(LinkStack top)
{
    int coordinate;

    coordinate = top->next->coordinate; //获取栈顶元素的坐标

    //删除栈顶元素，更新栈顶指针
    PNode t = top->next;
    top->next = t->next;
    free(t);

    return coordinate;
}

/**
 * 从文件中读取迷宫
 */
void fileRead()
{
    FILE* fp;

    /* 打开用于读取的文件，路径不能有中文 */
    fp = fopen("D:\\Projects\\ClionProjects\\mazeText\\1.txt", "r");
    if(fp == NULL)
    {
        perror("打开文件时发生错误");
        return;
    }

    for(int i=0; i < SIZE; i++)
    {
        for(int j = 0;j < SIZE;j++)
            fscanf(fp,"%d",&maze[i][j]);/*每次读取一个数，fscanf函数遇到空格或者换行结束*/

        fscanf(fp,"\n");
    }

    fclose(fp);
}

/**
 * 打印迷宫
 */
void printfMaze()
{
    printf("迷宫：■(墙)  .(路)  ?(入口)  ?(出口)\n");
    printf("    ");

    for(int i = 0; i < SIZE; i++)
        printf("%d   ",i);

    printf("\n");

    for(int i = 0; i < SIZE; i++)
    {
        //可视化路径
        printf("%d   ",i);

        for(int j = 0; j < SIZE; j++)
        {
            //打印入口
            if(i == 1 && j == 1)
                printf("?   ");
                //打印出口
            else if(i == SIZE - 2 && j == SIZE - 2)
                printf("?   ");
                //打印墙
            else if(maze[i][j] == 1)
                printf("■   ");
                //打印路
            else
            {
                /*if(path[i][j] == 1)
                    printf("√   ");
                else*/
                    printf(".   ");
            }
        }
        printf("\n");
    }

}

/**
 * 递归+深度优先搜索打印所有路径
 * @param entryX 入口行坐标
 * @param entryY 入口列坐标
 * @param exitX 出口行坐标
 * @param exitY 出口列坐标
 * @param maze 迷宫
 * @param path 路径栈，path也可以用作栈顶指针
 * @param visited 访问标记数组
 */
void mazeDFS(int entryX, int entryY, int exitX, int exitY, LinkStack path, int visited[SIZE][SIZE])
{

    //递归的返回条件：到达终点。每返回一次打印一条路径
    if (entryX == exitX && entryY == exitY)
    {
        //打印出口
        printf("(%d,%d)", exitX, exitY);

        PNode p = path->next;

        while (p != NULL)
        {
            //将栈中的元素解码，得到路径上的坐标
            printf(" <- (%d,%d)", p->coordinate / SIZE, p->coordinate % SIZE);
            p = p->next;
        }

        printf("\n");   //换行，打印下一条路径
        printf("\n");
        return;
    }

    int direction[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

    for (int mov = 0; mov < 4; mov++)
    {
        //此次探访的坐标
        int nextX = entryX + direction[mov][0];
        int nextY = entryY + direction[mov][1];

        //探访位置是空格且尚未访问
        if (maze[nextX][nextY] == 0 && visited[nextX][nextY] == 0)
        {
            //将本次起点的坐标编码后压入路径栈，并将其标记为已访问
            push(path,entryX * SIZE + entryY);
            visited[entryX][entryY] = 1;

            //递归
            mazeDFS(nextX, nextY, exitX, exitY, path, visited);

            //每次搜索结束后都将上一个坐标标记为尚未未访问，这是为了换下一个方向继续探索
            visited[entryX][entryY] = 0;
            //在路径中删除该坐标
            pop(path);
        }
    }

}

int main()
{
    //从文件中读取迷宫
    fileRead();

    //将入口设置在左上角，出口设置在右下脚
    int entryX = 1;
    int entryY = 1;
    int exitX = 7;
    int exitY = 7;

    //打印迷宫结构
    printfMaze();

    //创建路径栈
    LinkStack path = creatLinkStack();

    //访问标记数组。不能在递归中初始化
    int visited[SIZE][SIZE] = {0};

    //递归+深搜，打印所有路径
    printf("所有路径如下：\n");
    mazeDFS(entryX,entryY,exitX,exitY,path,visited);

    return 0;
}