网站跳出率高,做教育类网站,开发网页的工具有哪些,手机广告设计与制作软件本链栈用于解决迷宫问题之寻找所有路径
/*** 存储路径坐标的结点#xff0c;称为路径结点* 因为数量无法确定#xff0c;故使用链式结构*/
typedef struct Node
{int coordinate; //坐标struct Node* next;
}Node;typedef Node* PNode; //路径结点的指针类型
typedef Nod… 本链栈用于解决迷宫问题之寻找所有路径
/*** 存储路径坐标的结点称为路径结点* 因为数量无法确定故使用链式结构*/
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;elseprintf(链栈创建失败);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-nextNULL ? 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.#includestdio.h
#includestdlib.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;elseprintf(链栈创建失败);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-nextNULL ? 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 i0; 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;
}
