欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言數(shù)據(jù)結(jié)構(gòu)之迷宮求解問題

 更新時間:2020年06月16日 11:45:16   作者:飛起的牛  
這篇文章主要為大家詳細介紹了C語言數(shù)據(jù)結(jié)構(gòu)之迷宮求解問題,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下

現(xiàn)在網(wǎng)上各種對于迷宮的求解,版本多的數(shù)不勝數(shù)。本人小白一枚,貼上自己對迷宮的求解這個小項目,自己寫的。望能幫助一些同樣有困難的人,畢竟我當(dāng)時費解了好一會兒時間呢。

首先,先標(biāo)明對于迷宮求解這個項目,首先我提出自己的思路,利用“窮舉求解”的方法(嚴蔚敏老師數(shù)據(jù)結(jié)構(gòu)一書中提到,一開始不知方法其名。)其實簡單來說就是一條路一條路去試,當(dāng)然不能隨便試,我的方法是按照從入口出發(fā),順一個方向向前探索,走得通就繼續(xù)向前走;否則留下標(biāo)記沿原路退回并換一個方向繼續(xù)探索,直到所有的路都走完為止。還是用棧的先進后出的結(jié)構(gòu)保存一路的路線。代碼用到了棧的順序?qū)崿F(xiàn)數(shù)組格式的結(jié)構(gòu)(對于棧并沒有詳細闡述)。

//調(diào)用頭文件
#ifndef AFXSTD_H
#define AFXSTD_H 
 
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<iostream>
using namespace std; 
// cout; cin;C++的輸入輸出
#endif
//迷宮的結(jié)構(gòu)體的創(chuàng)建
#ifndef MAZE_H
#define MAZE_H
 
#define ROWSIZE 10 //迷宮大小
#define COLSIZE 10
#define Reachable 0 //可以到達的結(jié)點
#define Bar  1 //障礙物
#define Foot 2 //足跡
#define Mark 3 //不可通路標(biāo)記
typedef int MapType[ROWSIZE][COLSIZE]; // 地圖類型 
 
typedef struct 
{
 int row;// x
 int col;// y;
}PosType;   //坐標(biāo)結(jié)構(gòu)體
 
typedef struct
{
 int ord;  //通道塊在道路上的序號
 PosType seat; //小人坐標(biāo)
 int di; // 方向 // 1 2 3 4
}MElemType; //試迷宮小人的結(jié)構(gòu)
 
typedef MElemType SElemType; // 和stack 關(guān)聯(lián)
 
 
 
bool MazePass(MapType maze,PosType curpos);
void FootPrint(MapType maze,PosType curpos); //足跡打印
PosType NextPos(PosType curpos,int di);  //下一個位置
void MarkPrint(MapType maze,PosType curpos);  //打印不可通標(biāo)記
bool MazePath(MapType maze,PosType start,PosType end); //迷宮解謎核心
void PrintMap(MapType maze);    //打印地圖
 
 
#endif
//棧的結(jié)構(gòu)體
#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

以上是頭文件的創(chuàng)建,和結(jié)構(gòu)體的創(chuàng)建,現(xiàn)在真的深切感到結(jié)構(gòu)體的重要性。結(jié)構(gòu)體創(chuàng)建不好就是自己給自己挖坑,切記切記!!

現(xiàn)在貼出函數(shù)的代碼,解釋我會盡力都寫清楚。(棧的問題我后續(xù)會重新再仔細闡述的,這次的重點在于迷宮的求解,所以直接貼出棧的詳細代碼,望諒解。)

//這里是棧的實現(xiàn)代碼
#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;
}
//調(diào)用前面創(chuàng)建的頭文件
#include"AfxStd.h"
#include"Maze.h"
#include"Stack.h"
 
 
/////////////////////////////////////////////////
 
bool MazePass(MapType maze,PosType curpos) //判斷是否可以通過
{
 return maze[curpos.row][curpos.col] == Reachable; //判斷當(dāng)前結(jié)點是否能通過
}
void FootPrint(MapType maze,PosType curpos) //打印足跡 
{
 maze[curpos.row][curpos.col] = Foot; 
}
PosType NextPos(PosType curpos,int di)  //對下一個結(jié)點方向的判斷
{
 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)  //不能通過的結(jié)點留下不能通過的標(biāo)記
{
 maze[curpos.row][curpos.col] = Mark;
}
 
bool MazePath(MapType maze,PosType start,PosType end)//(核心)迷宮解謎
{
 bool res = false;    //定義一個res參數(shù)為布爾型
 PosType curpos = start;   //初始當(dāng)前位置為入口
 int curstep = 1;    // 初始探索方向為1
 SeqStack st;     //路徑存儲棧
 MElemType e;     //初始探索小人
 Init_Stack(st);     //初始化棧
 do{
 if(MazePass(maze,curpos))   //當(dāng)前位置可通過,即是未曾走到過的坐標(biāo)
 {
 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))  //當(dāng)前位置不能通過
 {
 Stack_Pop(st,e);
 while(e.di == 4 && !Stack_Empty(st))
 {
 MarkPrint(maze,e.seat); 
 Stack_Pop(st,e);  // 留下不能通過的標(biāo)記,并退回一步
 }
 if(e.di < 4)
 {
 e.di+=1;   // 換下一個方向探索
 Stack_Push(st,e);  //再次記錄路徑
 curpos = NextPos(e.seat,e.di); // 當(dāng)前位置設(shè)為新方向的相鄰塊
 }
 }
 }
 }while(!Stack_Empty(st)); //當(dāng)??沾輾?,返回失敗參數(shù)
 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 ={   //一開始地圖的創(chuàng)建
 {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;
}

以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • C++實現(xiàn)高校教室管理系統(tǒng)

    C++實現(xiàn)高校教室管理系統(tǒng)

    這篇文章主要為大家詳細介紹了C++實現(xiàn)高校教室管理系統(tǒng),文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • C++ 中的Swap函數(shù)寫法匯總

    C++ 中的Swap函數(shù)寫法匯總

    這篇文章主要介紹了C++ 中的Swap函數(shù)寫法匯總,本文通過實例代碼給大家介紹的非常詳細,具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-02-02
  • C語言鏈表實現(xiàn)簡易通訊錄

    C語言鏈表實現(xiàn)簡易通訊錄

    這篇文章主要為大家詳細介紹了C語言鏈表實現(xiàn)簡易通訊錄,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-05-05
  • 通過c語言調(diào)用系統(tǒng)curl動態(tài)庫的示例詳解

    通過c語言調(diào)用系統(tǒng)curl動態(tài)庫的示例詳解

    這篇文章中我們將通過一個簡單的示例來講解如何在Ubuntu系統(tǒng)中通過C語言調(diào)用動態(tài)庫(共享庫)的方法,我們將使用libcurl庫,這是一個基于客戶端的URL傳輸庫,廣泛用于各種程序和應(yīng)用中以訪問網(wǎng)頁和服務(wù)器數(shù)據(jù),需要的朋友可以參考下
    2024-03-03
  • C++?Qt開發(fā)之運用QJSON模塊解析數(shù)據(jù)

    C++?Qt開發(fā)之運用QJSON模塊解析數(shù)據(jù)

    JSON(JavaScript?Object?Notation)是一種輕量級的數(shù)據(jù)交換格式,它易于人閱讀和編寫,也易于機器解析和生成,本文主要介紹了Qt如何運用QJson組件的實現(xiàn)對JSON文本的靈活解析功能,需要的可以參考下
    2024-01-01
  • C++基礎(chǔ)算法基于哈希表的索引堆變形

    C++基礎(chǔ)算法基于哈希表的索引堆變形

    這篇文章主要為大家介紹了C++基礎(chǔ)算法,基于哈希表的索引堆變形示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步
    2021-10-10
  • 基于C++實現(xiàn)的各種內(nèi)部排序算法匯總

    基于C++實現(xiàn)的各種內(nèi)部排序算法匯總

    這篇文章主要介紹了基于C++實現(xiàn)的各種內(nèi)部排序算法,非常經(jīng)典,需要的朋友可以參考下
    2014-08-08
  • C語言實現(xiàn)經(jīng)典24點算法

    C語言實現(xiàn)經(jīng)典24點算法

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)經(jīng)典24點算法,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-10-10
  • 詳解C語言讀取文件求某一列的平均值

    詳解C語言讀取文件求某一列的平均值

    本文粗淺比較了C語言中常用的幾種讀取文件的函數(shù)的效率,并給出了幾段求取某列平均值的代碼,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多度進步
    2022-02-02
  • C++獲得其他程序窗體控件中信息的方法

    C++獲得其他程序窗體控件中信息的方法

    這篇文章主要介紹了C++獲得其他程序窗體控件中信息的方法,涉及windows控件句柄的獲取技巧,需要的朋友可以參考下
    2015-05-05

最新評論