C++數(shù)據(jù)結(jié)構(gòu)關于棧迷宮求解示例
更新時間：2021年11月27日 16:51:58 作者：笑霸final
這篇文章主要為大家介紹了C++數(shù)據(jù)結(jié)構(gòu)關于棧的迷宮求解示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
一、實驗目的
理解棧的抽象數(shù)據(jù)類型定義及操作特點。掌握順序棧的存儲結(jié)構(gòu)的描述。掌握順序棧的基本操作的實現(xiàn)方法。理解棧的廣泛應用。
二、預備知識
閱讀課程教材P44~45頁內(nèi)容，掌握棧的邏輯定義及“后進先出”的特點，理解抽象數(shù)據(jù)類型棧的定義。閱讀課程教材P45~47頁內(nèi)容，理解順序棧的存儲特點及存儲表示，掌握順序棧各種基本操作（InitStack、StackEmpty、GetTop、Push、Pop等）的實現(xiàn)方法。閱讀課程教材P50~52頁內(nèi)容，理解“迷宮求解”問題的含義，體會求解過程中棧的應用。仔細分析主要實現(xiàn)算法，理解求解步驟和方法。
三、實驗內(nèi)容
按如下要求編寫程序，進行調(diào)試，寫出調(diào)試正確的源代碼，給出測試結(jié)果。
1．完成順序棧的存儲表示，實現(xiàn)順序棧的各種基本操作，包括InitStack、StackEmpty、GetTop、Push、Pop等操作。
2．利用順序棧求解迷宮中從入口到出口的一條路徑，并輸出結(jié)果。
說明：
（1）使用二維數(shù)組maze描述迷宮，迷宮的規(guī)模及初態(tài)自定。
（2）路徑的輸出形式可用文字描述，也可用圖形描述。
定義一些代碼：
#include<iostream>
#include<cstdlib>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct {//棧元素類型
int x;//坐標
int y;//坐標
int di;//方向
}position;
using namespace std;
typedef struct {//棧
position *base;
position *top;
int stacksize;
}Stack;
/*************************迷宮**********************************/
int Maze[10][10] = {//迷宮 Maze（妹子）原型如下圖：1表示路不通0表示可以通過。
// 0 1 2 3 4 5 6 7 8 9
{1,1,1,1,1,1,1,1,1,1},//0
{1,0,0,1,0,0,0,1,0,1},//1
{1,0,0,1,0,0,0,1,0,1},//2
{1,0,0,0,0,1,1,0,0,1},//3
{1,0,1,1,1,0,0,0,0,1},//4
{1,0,0,0,1,0,0,0,0,1},//5
{1,0,1,0,0,0,1,0,0,1},//6
{1,0,1,1,1,0,1,1,0,1},//7
{1,1,0,0,0,0,0,0,0,1},//8
{1,1,1,1,1,1,1,1,1,1} //9
};
定義類
class boos {//創(chuàng)建了一個角色類
private:
Stack sq_stack;//棧
position temp;
public:
/******************************棧的基本方法*******************/
void InitStack() {//創(chuàng)建棧
bool StackEmpty()//判斷是否空棧
bool GetTop(position &temp)//獲得棧頂
bool Push(position &temp)//入
bool Pop(position &temp)//出棧
void free_Stack()//釋放?？臻g
/******************************走迷宮方法*******************/
bool findMaze(int star_x, int star_y, int endr_x, int end_y)
//迷宮的入口和出口坐標
};
類的成員函數(shù)的一些說明：
這是一些基礎方法 用于對棧的操作。
void InitStack() {//創(chuàng)建空的棧
sq_stack.base = (position *)malloc(sizeof(Stack)*STACK_INIT_SIZE);
if (!sq_stack.base) exit(-1);
sq_stack.top = sq_stack.base;/*FHL*/
sq_stack.stacksize = STACK_INIT_SIZE;
cout << "棧創(chuàng)建成功" << endl;
}
bool StackEmpty() {判斷是否空棧
if (sq_stack.top == sq_stack.base)return 1;
else
return 0;
}
bool GetTop(position &temp) {//得到棧頂元素
if (StackEmpty())return false;
temp= *(sq_stack.top-1);
return true;
}
bool Push(position &temp){//入棧/*FHL*/
if (sq_stack.top - sq_stack.base >= sq_stack.stacksize) {
sq_stack.base = (position*)realloc(sq_stack.base
sizeof(position)*(sq_stack.stacksize + STACKINCREMENT));
if(!sq_stack.base) exit(-1);/*FHL*/
sq_stack.top = sq_stack.base + sq_stack.stacksize;
sq_stack.stacksize += STACKINCREMENT;
}
*sq_stack.top = temp;
sq_stack.top++;
return true;
}
bool Pop(position &temp) {//出棧
if (StackEmpty()) return 0;
sq_stack.top--;
temp = *sq_stack.top;
return 1;
}
void free_Stack() {
free(sq_stack.base);
}
找迷宮的方法（dfs算法）
bool findMaze(int star_x, int star_y, int endr_x, int end_y) {//迷宮的入口和出口坐標
int i, j, k = 0;//i j表示目前的坐標
int tep_di,next_x,tep_y;//下一步的坐標
bool flag;
position fan_maze[200];
InitStack();//先創(chuàng)建空棧
temp.x = star_x, temp.y = star_y, temp.di - 1;//開始位置
Push(temp);//入棧操作。/*FHL*/
Maze[star_x][star_y]=-1;//-1表示走過；
while (!StackEmpty()) {//棧不為空
GetTop(temp);/*FHL*/
i = temp.x, j = temp.y , tep_di=temp.di;
if (i == endr_x && j == end_y) {
cout << "找到走出迷宮的路" << endl;
k = 0;
while (!StackEmpty()) {
Pop(temp);
fan_maze[k] = temp;
k++;//k指向下一個被插入的位置；
}
cout <<"起點："<< "(" << fan_maze[k-1].x << ',' << fan_maze[k-1].y << ")->" << endl;
int count = 1;
for(k-=2;k>0;k--) {
cout<<"(" << fan_maze[k].x <<','<< fan_maze[k].y<<")->";
if (count % 3 == 0) cout << endl;
count++;
}
cout << "(" << fan_maze[0].x << ',' << fan_maze[0].y << ")" << "終點" << endl;//出口的位置
free_Stack();//釋放申請的堆空間
return true;
}/*FHL*/
flag = 0;
while (tep_di < 4 && !flag) {
tep_di++;
if (tep_di == 0){ next_x = i; tep_y = j + 1;}
else if (tep_di == 1) { next_x = i + 1;tep_y = j; }
else if (tep_di == 2) { next_x = i;tep_y = j - 1; }
else { next_x = i - 1; tep_y = j; }
if( Maze[next_x][tep_y] == 0 ) flag = 1;
}
if(flag) {
(sq_stack.top-1)->di = tep_di;//記錄上次坐標走的方向。
temp.x = next_x, temp.y = tep_y,temp.di=-1;
Push(temp);//這次坐標入棧
Maze[next_x][tep_y] = -1;//當前坐標標記為走過。
}
else {
Pop(temp);
Maze[temp.x][temp.y] = 0;
}
}/*FHL*/
cout << "沒有找到對應的出口" << endl;
free_Stack();//釋放申請的堆空間
return false;
}
};
主函數(shù)(創(chuàng)建對象)
int main() {
boos L1;
L1.findMaze(1,1,8,8);
system("pause");/*FHL*/
return 0;
}
運行的一些截圖：
1.當入口和終點一樣時：
int main() {
boos L1;
L1.findMaze(1,1,1,1);
system("pause");
return 0;
}
2.終點是可以到達的路徑
2.1（8,8）是終點
int main() {
boos L1;
L1.findMaze(1,1,8,8);
system("pause");
return 0;
}
2.2（8,2）是終點
int main() {
boos L1;
L1.findMaze(1,1,8,2);
system("pause");
return 0;
}
3.出口不通的情況
int main() {
boos L1;
L1.findMaze(1,1,9,9);
system("pause");
return 0;
}
以上就是C++數(shù)據(jù)結(jié)構(gòu)關于棧迷宮求解示例的詳細內(nèi)容，更多關于C++數(shù)據(jù)結(jié)構(gòu)棧迷宮的資料請關注腳本之家其它相關文章！
相關文章
本文主要介紹了QChart繪制折線圖，Qt Charts基于Qt的Graphics View架構(gòu)，其核心組件是QChartView 和 QChart，感興趣的可以了解一下2022-04-04
文章給大家分享了用C語言音樂播放器的實例代碼，對此有需要的朋友參考學習下。2018-07-07
這篇文章主要為大家詳細介紹了C語言代碼實現(xiàn)簡易掃雷，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-01-01
以下文章是對C/C++中判斷某一文件或目錄是否存在的實現(xiàn)代碼進行了詳細的分析介紹，需要的朋友可以參考下2013-07-07
這篇文章主要介紹了C/C++中異常處理詳解及其作用，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09
C?語言提供了豐富的操作符，有：算術操作符，移位操作符，位操作符，賦值操作符，單目操作符，關系操作符，邏輯操作符，條件操作符等。因為篇幅過大將分兩篇講解，讓我們通讀本篇來詳細了解吧2022-04-04
C++設計模式之工廠方法模式的實現(xiàn)及優(yōu)缺點
工廠方法模式是一個創(chuàng)建型設計模式,通過定義一個創(chuàng)建對象的接口，讓其子類決定實例化哪一個工廠類,這篇文章主要給大家介紹了關于C++設計模式之工廠方法模式的實現(xiàn)及優(yōu)缺點,需要的朋友可以參考下2021-06-06
C語言提供了多種預處理功能,如宏定義、文件包含、條件編譯等,下面這篇文章主要給大家介紹了關于C語言進階教程之預處理的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-02-02
這篇文章主要介紹了c++函數(shù)指針使用示例,需要的朋友可以參考下2014-03-03
快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采用，再加上快速排序思想----分治法也確實實用，因此很多軟件公司的筆試面試，包括像騰訊，微軟等知名IT公司都喜歡考這個，還有大大小的程序方面的考試如軟考，考研中也常常出現(xiàn)快速排序的身影2022-05-05