手写一个链栈(算法村第四关青铜挑战)
2024-01-01 20:38:50
?本链栈用于解决迷宫问题之寻找所有路径
/**
* 存储路径坐标的结点,称为路径结点
* 因为数量无法确定,故使用链式结构
*/
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;
}
文章来源:https://blog.csdn.net/cjj2543107638/article/details/135327976
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!