溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
不懂C語言如何實現數據結構迷宮實驗？？其實想解決這個問題也不難，下面讓小編帶著大家一起學習怎么去解決，希望大家閱讀完這篇文章后大所收獲。
分析：迷宮實驗主要有兩部分操作，其一是對迷宮的生成，其二是尋路使用棧的操作。
步驟：
一、.h文件
1、首先是迷宮的生成，可以使用隨機數種子生成，但主要邏輯部分并不在此，所以在這里直接寫死，固定下來。
定義一個坐標類型的結構體，和二維數組迷宮：
typedef struct {
int x;
int y;
}Pos;
//迷宮類型
typedef struct {
int square[10][10] =
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,0,1,1,1,0,1},
{1,0,0,0,0,1,0,1,0,1},
{1,0,1,1,1,1,0,1,1,1},
{1,0,0,0,0,1,0,0,0,1},
{1,0,1,1,0,0,0,1,0,1},
{1,0,1,1,1,0,1,1,1,1},
{1,0,0,0,1,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1},
};
}Maze;
typedef Pos SElemType;2、然后是對棧的聲明，棧里儲存的元素為坐標類型
//順序棧
#define MAXSIZE 50
typedef struct {
SElemType *base;
SElemType *top; //棧頂指針
int stacksize;
}SqStack;3、棧操作函數聲明
typedef int Status; #define OK 1; #define ERROR 0; //棧的相關操作 //初始化棧 Status initStack(SqStack &s); //壓棧 Status push(SqStack &s, SElemType e); //出棧 SElemType pop(SqStack &s); //清空棧 Status clearStack(SqStack &s); //摧毀棧 void destroyStack(SqStack &s); //遍歷棧 Status stackTravel(SqStack s);
4、迷宮操作函數聲明
//初始化迷宮(同時生成起始點和終點) void initMaze(Maze &maze); //打印迷宮 void showMaze(Maze maze); //尋找出路；傳入一個迷宮和棧找出出路 void findWay(Maze &maze,SqStack &s); //判斷該點的四個方向是否有通路，有就前進 Pos isExit(Pos p, Maze maze);
二、.cpp文件
1、導入所需頭文件
#include "pch.h" #include <iostream> #include<time.h> #include<stdlib.h> using namespace std;
2、棧操作實現
//構造空棧
Status initStack(SqStack &s) {
s.base = new SElemType[MAXSIZE];
if (!s.base)
{
exit(OVERFLOW);//分配失敗
}
s.top = s.base;
s.stacksize = MAXSIZE;
return OK;
}
//入棧
Status push(SqStack &s, SElemType e) {
//判斷棧滿
if (s.top-s.base == s.stacksize)
{
return ERROR;
}
//存入元素,*為取指針的值
s.top++;
*s.top = e;
return OK;
}
//出棧,用e返回棧頂值
SElemType pop(SqStack &s) {
SElemType e;
//判斷棧為空
if (s.top == s.base)
{
//若為空則返回一個（-1，-1）的點，判斷由外部調用時進行
e.x = -1;
e.y = -1;
return e;
}
e = *s.top;
s.top--;
return e;
}
Status clearStack(SqStack &s) {
s.top = s.base;
return OK;
}
void destroyStack(SqStack &s) {
s.top = NULL;
s.stacksize = 0;
free(s.base);
}
Status stackTravel(SqStack s) {
while (s.top != s.base)
{
s.base++;
Pos p = *s.base;
//輸出走過的路徑
cout <<"("<<p.x<<","<<p.y<<")"<< "-->";
if ( p.x == 0 || p.y == 0|| p.x == 9 ||p.y == 9)
{
//終點輸出為“End”
cout << "End";
}
}
cout << endl;
return 0;
}3、迷宮操作實現
///////////////////////////////////////迷宮操作////////////////////////////////
//初始化函數，傳入一個迷宮，隨機生成起點和終點，由于起點有一定限制，所以這里起點也固定為幾個最合適的點
void initMaze(Maze &maze) {
//生成隨機數
srand((unsigned)time(NULL));
int index = rand() % 36 + 1;
int start = index % 6 + 1;
//生成起始點數值為‘s'
switch (start)
{
case 1:
maze.square[1][1] = 's';
break;
case 2:
maze.square[3][8] = 's';
break;
case 3:
maze.square[3][6] = 's';
break;
case 4:
maze.square[6][8] = 's';
break;
case 5:
maze.square[8][3] = 's';
break;
case 6:
maze.square[8][8] = 's';
break;
}
//隨機生成終點'e'表示
while (index = rand()%36+1)
{
//出口在頂部
if (index >1 &&index<10 && maze.square[1][index-1]!='s')
{
maze.square[0][index-1] = 'e';
break;
}
//出口在右側
else if (index>10 &&index <19)
{
if (maze.square[index-10][8] != 1 && maze.square[index-10][8]!='s') {
maze.square[index-10][9] = 'e';
break;
}
}
//底部出口
else if (index >19&&index<28)
{
if (maze.square[8][index - 19] != 's' && maze.square[8][index - 19] != 1) {
maze.square[9][index - 19] = 'e';
break;
}
}
//左側出口
else if (index >28 && index <=36)
{
if (maze.square[index-28][1] != 1 &&maze.square[index-28][1] != 's')
{
maze.square[index - 28][0] = 'e';
break;
}
}
}
}
void showMaze(Maze maze) {
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
if (maze.square[i][j] == 1)
{
cout << "* ";
}
else if (maze.square[i][j] == 0)
{
cout << " ";
}
else
{
cout << (char)maze.square[i][j]<<" ";
}
}
cout << endl;
}
}
//尋找迷宮路徑
void findWay(Maze &maze,SqStack &s) {
//首先遍歷找出起始點和終點并保存下來
Pos start,end;
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++) {
if (maze.square[i][j] == 's')
{ //起點壓入棧內
start.x = i;
start.y = j;
push(s, start);
}
else if (maze.square[i][j] == 'e')
{ //出口
end.x = i;
end.y = j;
}
}
}
//尋找路徑
Pos go = start;
//直到找到出口才結束
while ( s.top->x != end.x || s.top->y != end.y)
{
//獲得下一步坐標
Pos path = isExit(go, maze);
if (path.x != go.x || path.y != go.y)
{
//前進
maze.square[path.x][path.y] = 'p';
push(s, path);
go = path;
}
//如果所有放向都走不通（即返回的點是傳入的點），則將其標為“@”，出棧到上一個點，繼續判斷
else
{
//走不通pop
maze.square[path.x][path.y] = '@';
pop(s);
go = *s.top;
}
}
maze.square[end.x][end.y] = 'e';
}
//判斷返回下一步路徑（順序：右下左上），傳入所處位置，從右邊開始判斷是否又通路或者出口，有就返回哪個方向上的點
Pos isExit(Pos p,Maze maze) {
Pos tempP = p;
if (maze.square[tempP.x][tempP.y+1] == 0 || maze.square[tempP.x][tempP.y + 1] == 'e')
{
tempP.y++;
}
else if(maze.square[tempP.x+1][tempP.y] == 0 || maze.square[tempP.x +1][tempP.y] == 'e')
{
tempP.x++;
}
else if (maze.square[tempP.x][tempP.y - 1] == 0 || maze.square[tempP.x][tempP.y - 1] == 'e')
{
tempP.y--;
}
else if (maze.square[tempP.x - 1][tempP.y] == 0 || maze.square[tempP.x - 1][tempP.y] == 'e')
{
tempP.x--;
}
return tempP;
}三、main函數調用
int main()
{
while (true)
{
//創建一個迷宮
Maze maze;
initMaze(maze);
//初始化一個棧
SqStack S;
initStack(S);
cout << "*****************************" << endl;
cout << "* 1、生成迷宮 2、退出 *" << endl;
cout << "*****************************" << endl;
cout << "請輸入你的選擇：";
int select = 0;
cin >> select;
if (select == 1)
{
cout << "生成隨機起點和出口迷宮：" << endl;
showMaze(maze);
cout << "生成迷宮路徑：" << endl;
findWay(maze, S);
stackTravel(S);
showMaze(maze);
cout << endl;
}
if (select == 2)
{
clearStack(S);
break;
}
}
return 0;
}四、評價
這是個叫簡易的迷宮，但基本實現了迷宮的尋路邏輯，可改進的地方有：
1、因為很多地方寫死了，所以復用性不高，可以用循環遍歷來隨機生成起點，同理迷宮的生成也是這樣
2、判斷路徑可以用遞歸調用實現前進邏輯
感謝你能夠認真閱讀完這篇文章，希望小編分享C語言如何實現數據結構迷宮實驗？內容對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，遇到問題就找億速云，詳細的解決方法等著你來學習!
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
