文章目錄
- 引言
- 一，問題描述
- 二，分析所用資料結構
- 三、所需函式及其功能
- 四、程式執行詳細框圖
- 五、代碼實作-詳細注釋
- 1、maze.h
- 2、maze.c
- 3、maze.c
- 六，效果展示
引言
這是一個簡單的順序堆疊的應用求解迷宮問題，主要分享的是在求解這個問題的之前的準備，
分析所需的資料，獲得正確的資料結構，分析所需要的功能，劃分模塊，再分析各模塊中，需要的具體功能，以確定功能函式，
這樣也書寫代碼時，就可以事半功倍，
一，問題描述
迷宮求解問題
提出以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙，迷宮問題要求，求出從入口(x，y)到出口(x，y)的一條通路，或得出沒有通路的結論，
基本要求：首先實作一個以鏈表作存盤結構的堆疊型別，然后撰寫一個求迷宮問題的非遞回程式，求得的通路，
要求用堆疊實作迷宮問題的求解
將要構建的迷宮：向下為x正方向；向右為y正方向
二，分析所用資料結構
迷宮結構體用于存盤構建的迷宮資料，
坐標結構體和堆疊元素結構體都是服務于堆疊結構體，
三、所需函式及其功能
這幅圖可以很清晰的，了解都有哪些函式，這些函式的功能又是什么，
圖中很多函式都是為了一個函式服務的，即求解迷宮的函式，
藍色底的函式，實作了但是沒有測驗，大家可以自行測驗
四、程式執行詳細框圖
這是整個迷宮問題專案的詳細執行程序，大家可以先看看，到時候閱讀代碼也會更加清洗直觀，
不同的顏色，是一個不同的模塊，實作相應的功能
五、代碼實作-詳細注釋
代碼相應的地方都有注釋，也體現了我思考的程序，如有錯誤或者更優解，歡迎在指正討論，
1、maze.h
#ifndef __MAZE_H__
#define __MAZE_H__
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define COLUMN 10 //列
#define ROW 10 //行
typedef struct{
char** maze; //迷宮二維陣列
int** footprint; //足跡二維陣列
int row;
int column;
}MazeType;
typedef struct{
int x;
int y;
}PosType;
typedef struct{
int ord; //通道塊在路徑上的序號
PosType seat; //通道塊在迷宮中的“坐標位置”
int di; //從此通道塊走向下一個通道塊的“方向”
}SElemType;
typedef struct{
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
//構造一個空堆疊
bool InitStack(SqStack* S);
//初始化迷宮資料
bool InitMaze(MazeType* M);
//判斷是否為空堆疊
bool IsStackEmpty(SqStack S);
//入堆疊，元素e為新的堆疊頂元素，傳入e形參拷貝值，回傳改變的堆疊S，及是否入堆疊成功
bool Push(SqStack* S, SElemType e);
//出堆疊,指標傳入地址，直接改變e變數，即回傳改變的e和堆疊S，及是否出堆疊成功
bool Pop(SqStack* S, SElemType* e);
//輸出迷宮
bool PrintfMaze(MazeType* M);
//輸出迷宮的路徑
bool PrintfFoot(MazeType* M, SqStack* S);
//將迷宮的當前位置Pos設定為“走過”，即footprint該位置為1
bool FootPrint(MazeType* M, PosType pos);
//判斷當前位置是否走過
bool Pass(MazeType* M, PosType pos);
//創建新的節點，用step,pos,d初始化該點
SElemType NewSElemType(int step, PosType pos, int d);
//將位置pos的方向設為d
PosType NextPos(PosType pos, int d);
//若迷宮maze中存在從入口start到出口end的通道，則求得一條存放在堆疊中（從堆疊底到堆疊頂）
bool MazePath(SqStack* S, MazeType maze, PosType start, PosType end);
//清空堆疊
bool ClearStack(SqStack* S);
//從堆疊底到堆疊頂依次對每個元素進行訪問
bool StackTravel(const SqStack* S);
//回傳堆疊的長度，即S元素的個數
int StackLength(SqStack S);
//若堆疊不為空，則用e回傳S的堆疊頂元素
bool GetTop(SqStack S, SElemType* e);
#endif
2、maze.c
#include "maze.h"
//構造一個空堆疊
bool InitStack(SqStack* S)
{
//100*SElemType
S->base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S->base)
{
printf("申請空間失敗，迷宮無法初始化.\n");
return false;
}
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
return true;
}
//初始化迷宮資料
bool InitMaze(MazeType* M)
{
char mz[ROW][COLUMN]={
{'#',' ','#','#','#','#','#','#','#','#'},
{'#',' ',' ','#',' ',' ',' ','#',' ','#'},
{'#',' ',' ','#',' ',' ',' ','#',' ','#'},
{'#',' ',' ',' ',' ','#','#',' ',' ','#'},
{'#',' ','#','#','#',' ',' ',' ',' ','#'},
{'#',' ',' ',' ','#',' ','#',' ','#','#'},
{'#',' ','#',' ',' ',' ','#',' ',' ','#'},
{'#',' ','#','#','#',' ','#','#',' ','#'},
{'#','#',' ',' ',' ',' ',' ',' ',' ',' '},
{'#','#','#','#','#','#','#','#','#','#'},
};
M->maze = (char **)malloc(sizeof(char*)*ROW); //相當于分配一維陣列空間，10個char*變數空間
M->footprint = (int **)malloc(sizeof(int*)*ROW); //相當于分配一維陣列空間，10個int*變數空間
if(!M->maze || !M->footprint)
{
printf("申請空間失敗，迷宮無法初始化.\n");
return false;
}
for(int i = 0; i < ROW; i++)
{
M->maze[i]=(char*)malloc(sizeof(char)*COLUMN); //相當于分配二維陣列空間，每個個char*指向，10個char大小變數空間
M->footprint[i]=(int*)malloc(sizeof(int)*COLUMN); //相當于分配二維陣列空間，每個個int*指向，10個int大小變數空間
if(!M->maze[i] || !M->footprint[i])
{
printf("申請空間失敗，迷宮無法初始化.\n");
return false;
}
}
for(int i = 0; i <ROW; i++)
{
for(int j = 0; j < COLUMN; j++)
{
M->maze[i][j] = mz[i][j];
M->footprint[i][j] = 0;
}
}
M->row = ROW;
M->column = COLUMN;
return true;
}
//判斷是否為空賬
bool IsStackEmpty(SqStack S)
{
if(S.top == S.base)
return true;
else
return false;
}
//入堆疊，元素e為新的堆疊頂元素，傳入e形參拷貝值，回傳改變的堆疊S，及是否入堆疊成功
bool Push(SqStack* S, SElemType e)
{
//結構體型別，按單位大小相減類比int型，每個int型為4byte，相減2-1也是按斯單位相減
if(S->top - S->base >= S->stacksize) //如果超出本來的長度，進行動態的添加，每一次添加10個SElemType大小空間,STACKINCREMENT=10
{
S->base = (SElemType*)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(SElemType));
if(!S->base);
{
printf("重新申請空間失敗.\n");
return false;
}
S->top = S->base + S->stacksize; //堆疊頂指標指向原先堆疊的尾部，堆疊底+堆疊長度
S->stacksize +=STACKINCREMENT; //堆疊的長度+10
}
*S->top++=e; //堆疊頂指標+1前進，并且e賦值給解參考的指標，入堆疊
//后置++/--為第一優先級，*和前置++/--為第二優先級
return true;
}
//出堆疊,指標傳入地址，直接改變e變數，即回傳改變的e和堆疊S，及是否出堆疊成功
bool Pop(SqStack* S, SElemType* e)
{
if(S->top == S->base)
{
printf("堆疊為空.\n");
return false;
}
*e = *(--S->top); //堆疊頂指標-1回傳，并且解參考賦值給e
return true;
}
//輸出迷宮
bool PrintfMaze(MazeType* M)
{
printf("%s","xy");
for(int i=0;i<M->column;i++)
{
printf("%d",i);
}
printf("\n");
for(int i=0; i<M->row; i++)
{
printf("%d ",i);
for(int j=0; j<M->column; j++)
{
printf("%c",M->maze[i][j]);
}
printf("\n");
}
printf("\n");
//footprintf
printf("%s","xy");
for(int i=0;i<M->column;i++)
{
printf("%d",i);
}
printf("\n");
for(int i=0; i<M->row; i++)
{
printf("%d ",i);
for(int j=0; j<M->column; j++)
{
printf("%d",M->footprint[i][j]);
}
printf("\n");
}
printf("\n");
return true;
}
//輸出迷宮路徑
bool PrintfFoot(MazeType* M, SqStack* S)
{
SElemType* p;
for(int i=0; i<M->row; i++) //將footprint置0
{
for(int j=0; j<M->column; j++)
{
M->footprint[i][j]=0;
}
}
p = S->base;
if(S->base == S->top)
{
printf("堆疊為空.\n");
return false;
}
while(p != S->top) //根據堆疊中存有的節點的坐標，對footprint進行1路徑賦值
{
M->footprint[p->seat.x][p->seat.y] = 1;
*p++;
}
for(int i=0; i<M->row; i++) //輸出路徑
{
for(int j=0; j<M->column; j++)
{
printf("%d",M->footprint[i][j]);
}
printf("\n");
}
return true;
}
//將迷宮的當前位置Pos設定為“走過”，即footprint該位置為1
bool FootPrint(MazeType* M, PosType pos) //FootPrint足跡
{
if((pos.x>M->row) || (pos.y>M->column))
{
printf("坐標越界.\n");
return false;
}
M->footprint[pos.x][pos.y]=1;
return true;
}
//判斷當前位置是否走過
bool Pass(MazeType* M, PosType pos)
{
if((pos.x > M->row) || (pos.y > M->column))
{
printf("坐標越界.\n");
return false;
}
if((0 == M->footprint[pos.x][pos.y])&&(M->maze[pos.x][pos.y]==' '))
return true; //通路沒走過
else
return false; //通路走過或者墻
}
//創建新的節點，用step,pos,d初始化該點
SElemType NewSElemType(int step, PosType pos, int d)
{
SElemType e;
e.ord = step;
e.seat = pos;
e.di = d;
return e;
}
//將位置pos的方向設為d
PosType NextPos(PosType pos, int d)
{
switch(d)
{
case 1: //向下
pos.x++;
break;
case 2: //向右
pos.y++;
break;
case 3: //向上
pos.x--;
break;
case 4: //向左
pos.y--;
break;
default:
printf("error.\n");
}
return pos;
}
//若迷宮maze中存在從入口start到出口end的通道，則求得一條存放在堆疊中（從堆疊底到堆疊頂）
bool MazePath(SqStack* S, MazeType maze, PosType start, PosType end)
{
int curstep = 1;
SElemType e;
PosType curpos = start;
InitStack(S);
do
{
if(true == Pass(&maze, curpos)) //通路沒走過
{
FootPrint(&maze,curpos);將當前點標記為走過
e=NewSElemType(curstep,curpos,1);//創建堆疊元素，將當前點的資訊存盤，便于出入堆疊及改變當前點的di資訊
Push(S,e);
if((curpos.x==end.x)&&(curpos.y==end.y))//終點
{
printf("迷宮路徑:\n");
PrintfFoot(&maze,S);//列印通路路徑
return true;
}
curpos = NextPos(curpos,1);//向當前點的di方向偏移 ，即下一個點
curstep++;//步數+1
}
else //通路走過或者墻
{
if(!IsStackEmpty(*S))
{
Pop(S,&e);
while(e.di==4 && !IsStackEmpty(*S)) //四個方向遍歷完，說明此點不是正確道路，，且且堆疊不為空，就一直出堆疊
{
Pop(S,&e);
}
if(e.di<4)
{
e.di++;//改變當前點的di，偏移方向
Push(S,e);//將改變了di的當前點資訊，入堆疊
curpos=NextPos(e.seat,e.di);//向當前點的di方向偏移
}
}
}
}while(!IsStackEmpty(*S));
return false;
}
//清空堆疊
bool ClearStack(SqStack* S)
{
//把堆疊S置為空堆疊
if(!S) return false;
S->top = S->base;
return true;
}
//從堆疊底到堆疊頂依次對每個元素進行訪問
bool StackTravel(const SqStack* S)
{
SElemType* p = S->base;
if(S->base == S->top)
{
printf("堆疊為空.\n");
return false;
}
printf("堆疊中元素:\n");
while(p != S->top)
{
printf("x=%d,y=%d\n",p->seat.x,p->seat.y);
*p++;
}
printf("\n");
return true;
}
//回傳堆疊的長度，即S元素的個數
int StackLength(SqStack S)
{
return S.stacksize;
}
//若堆疊不為空，則用e回傳S的堆疊頂元素
bool GetTop(SqStack S, SElemType* e)
{
if(S.top == S.base)
{
printf("堆疊為空.\n");
return false;
}
else
{
*e = *(S.top - 1);
//printf("堆疊頂元素:%c\n",*e);
return true;
}
}
3、maze.c
#include "maze.h"
int main()
{
MazeType maze;
SqStack *stack =(SqStack *)malloc(sizeof(SqStack));
PosType start,end;
start.x = 1;
start.y = 6;
end.x = 8;
end.y = 9;
InitMaze(&maze);
printf("maze:\n");
PrintfMaze(&maze);
if(true == MazePath(stack,maze,start,end))
printf("maze can out.\n");
else
printf("maze can not out.\n");
StackTravel(stack);
printf("堆疊的長度:%d\n",StackLength(*stack));
SElemType ele;
GetTop(*stack,&ele);
printf("堆疊頂元素:ord=%d,x=%d,y=%d,di=%d\n",ele.ord,ele.seat.x,ele.seat.y,ele.di);
ClearStack(stack);
GetTop(*stack,&ele);
//銷毀堆疊——銷毀free空間，需要在同一個記憶體空間銷毀
free(stack);
stack=NULL;
return 0;
}
六，效果展示
此測驗起點（1，6），終點（8，9）
相信大家看到這個結果是會有疑問的，因為雖然得到一條正確的迷宮路徑，但卻不是最優解，這是為什么呢？
依舊存在缺陷的迷宮演算法，無法獲得最優路徑解，因為遍歷的方向固定，所以大家有什么辦法可以優化它呢？
如有不足之處，還望指正 1，
如果對您有幫助可以點贊、收藏、關注，將會是我最大的動力 ??
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/236637.html
標籤：其他