溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
不懂C語言數據結構怎么實現迷宮求解？其實想解決這個問題也不難，下面讓小編帶著大家一起學習怎么去解決，希望大家閱讀完這篇文章后大所收獲。
首先，先標明對于迷宮求解這個項目，首先我提出自己的思路，利用“窮舉求解”的方法（嚴蔚敏老師數據結構一書中提到，一開始不知方法其名。）其實簡單來說就是一條路一條路去試，當然不能隨便試，我的方法是按照從入口出發，順一個方向向前探索，走得通就繼續向前走；否則留下標記沿原路退回并換一個方向繼續探索，直到所有的路都走完為止。還是用棧的先進后出的結構保存一路的路線。代碼用到了棧的順序實現數組格式的結構（對于棧并沒有詳細闡述）。
//調用頭文件 #ifndef AFXSTD_H #define AFXSTD_H #include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<iostream> using namespace std; // cout; cin;C++的輸入輸出 #endif
//迷宮的結構體的創建
#ifndef MAZE_H
#define MAZE_H
#define ROWSIZE 10 //迷宮大小
#define COLSIZE 10
#define Reachable 0 //可以到達的結點
#define Bar 1 //障礙物
#define Foot 2 //足跡
#define Mark 3 //不可通路標記
typedef int MapType[ROWSIZE][COLSIZE]; // 地圖類型
typedef struct
{
int row;// x
int col;// y;
}PosType; //坐標結構體
typedef struct
{
int ord; //通道塊在道路上的序號
PosType seat; //小人坐標
int di; // 方向 // 1 2 3 4
}MElemType; //試迷宮小人的結構
typedef MElemType SElemType; // 和stack 關聯
bool MazePass(MapType maze,PosType curpos);
void FootPrint(MapType maze,PosType curpos); //足跡打印
PosType NextPos(PosType curpos,int di); //下一個位置
void MarkPrint(MapType maze,PosType curpos); //打印不可通標記
bool MazePath(MapType maze,PosType start,PosType end); //迷宮解謎核心
void PrintMap(MapType maze); //打印地圖
#endif//棧的結構體
#include"Maze.h"
#ifndef SEQSTACK_H
#define SEQSTACK_H
#define STACKSIZE 100
//typedef int SElemType;
struct SeqStack
{
SElemType *data;
int maxsize;
int top;
};
void Init_Stack(SeqStack &st);
void Destroy_Stack(SeqStack &st);
void Stack_Clear(SeqStack &st);
bool Stack_Empty(SeqStack &st);
bool Stack_Full(SeqStack &st);
int Stack_Size(SeqStack &st);
bool Stack_Push(SeqStack &st,const SElemType &x);
bool Stack_Pop(SeqStack &st, SElemType &x);
SElemType GetTop(SeqStack &st);
void Pop(SeqStack &st);
#endif以上是頭文件的創建，和結構體的創建，現在真的深切感到結構體的重要性。結構體創建不好就是自己給自己挖坑，切記切記！！
現在貼出函數的代碼，解釋我會盡力都寫清楚。（棧的問題我后續會重新再仔細闡述的，這次的重點在于迷宮的求解，所以直接貼出棧的詳細代碼，望諒解。）
//這里是棧的實現代碼
#include"AfxStd.h"
#include"Stack.h"
bool Stack_Resize(SeqStack &st)
{
SElemType *s = (SElemType*)malloc(sizeof(SElemType)*st.maxsize * 2);
if(NULL == s) return false;
for(int i = 0;i<= st.top;++i)
{
s[i] = st.data[i];
}
free(st.data);
st.data = s;
st.maxsize = st.maxsize * 2;
return true;
}
void Init_Stack(SeqStack &st)
{
st.maxsize = STACKSIZE;
st.top = -1;
st.data = (SElemType*)malloc(sizeof(SElemType)*st.maxsize);
if(NULL == st.data)
{
exit(0);
}
}
void Destroy_Stack(SeqStack &st)
{
free(st.data);
st.data = NULL;
st.maxsize = 0;
st.top = -1;
}
void Stack_Clear(SeqStack &st)
{
st.top = -1;
}
bool Stack_Empty(SeqStack &st)
{
return Stack_Size(st) == 0;
}
bool Stack_Full(SeqStack &st)
{
return Stack_Size(st) == st.maxsize;
}
int Stack_Size(SeqStack &st)
{
return st.top + 1;
}
bool Stack_Push(SeqStack &st,const SElemType &x)
{
if(Stack_Full(st) && ! Stack_Resize(st))
{
return false;
}
st.data[++st.top] = x;
return true;
}
bool Stack_Pop(SeqStack &st, SElemType &x)
{
if(Stack_Empty(st))
{
return false;
}
x = st.data[st.top--];
return true;
}//調用前面創建的頭文件
#include"AfxStd.h"
#include"Maze.h"
#include"Stack.h"
/////////////////////////////////////////////////
bool MazePass(MapType maze,PosType curpos) //判斷是否可以通過
{
return maze[curpos.row][curpos.col] == Reachable; //判斷當前結點是否能通過
}
void FootPrint(MapType maze,PosType curpos) //打印足跡
{
maze[curpos.row][curpos.col] = Foot;
}
PosType NextPos(PosType curpos,int di) //對下一個結點方向的判斷
{
switch(di)
{
case 1: curpos.row+=1; break;// 1
case 2: curpos.col-=1; break;// 2
case 3: curpos.row-=1; break;// 3
case 4: curpos.col+=1; break;// 4
}
return curpos;
}
void MarkPrint(MapType maze,PosType curpos) //不能通過的結點留下不能通過的標記
{
maze[curpos.row][curpos.col] = Mark;
}
bool MazePath(MapType maze,PosType start,PosType end)//（核心）迷宮解謎
{
bool res = false; //定義一個res參數為布爾型
PosType curpos = start; //初始當前位置為入口
int curstep = 1; // 初始探索方向為1
SeqStack st; //路徑存儲棧
MElemType e; //初始探索小人
Init_Stack(st); //初始化棧
do{
if(MazePass(maze,curpos)) //當前位置可通過，即是未曾走到過的坐標
{
FootPrint(maze,curpos); //留下足跡
e.di = 1, e.seat = curpos,e.ord = curstep++;
Stack_Push(st,e); //加入路徑中
if(curpos.row == end.row && curpos.col == end.col)
{
res = true;
break;
} //到達終點
curpos = NextPos(curpos,1); //探索下一位置
}
else
{
if(!Stack_Empty(st)) //當前位置不能通過
{
Stack_Pop(st,e);
while(e.di == 4 && !Stack_Empty(st))
{
MarkPrint(maze,e.seat);
Stack_Pop(st,e); // 留下不能通過的標記，并退回一步
}
if(e.di < 4)
{
e.di+=1; // 換下一個方向探索
Stack_Push(st,e); //再次記錄路徑
curpos = NextPos(e.seat,e.di); // 當前位置設為新方向的相鄰塊
}
}
}
}while(!Stack_Empty(st)); //當棧空摧毀棧，返回失敗參數
Destroy_Stack(st);
return res;
}
void PrintMap(MapType maze) //打印地圖
{
for(int i = 0;i<ROWSIZE;++i)
{
for(int j = 0;j<COLSIZE;++j)
{
printf("%2d",maze[i][j]);
}
printf("\n");
}
printf("\n");
}以上就是迷宮的詳細解釋，希望能幫助到大家。后面再添加我的測試文件。
#include"AfxStd.h"
#include"Maze.h"
int main()
{
MapType maze ={ //一開始地圖的創建
{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,1,1,1,1,0,1},
{1,0,0,0,1,1,1,1,0,1},
{1,0,1,1,1,1,0,0,0,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,1,1,1},
{1,0,1,1,1,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1},
};
PosType start={1,1},end={8,8};
PrintMap(maze); //打印初始地圖
MazePath(maze,start,end);
PrintMap(maze); //打印迷宮解法
return 0;
}感謝你能夠認真閱讀完這篇文章，希望小編分享C語言數據結構怎么實現迷宮求解內容對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，遇到問題就找億速云，詳細的解決方法等著你來學習!
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
