数据结构之栈的应用—-迷宫

这个用到了一些C++的知识了，因为需要用到动态建立数组和类的一些知识。

以前遇到类似的问题就很头疼，而且也不愿意去写，可是现在觉得只要肯花时间，

写起来并不那么困难，虽然一次性完美的写出来，不出错不可能，但是在调试错误的过程中同样能感觉到快乐。

考虑到节约时间，我就随机生成了一个地图，矩阵的大小可以输入。1为可走，0为走不通。

代码并没有完善到我想要的目的，例如目前只能寻找一条路线，多条路线还没有思路。

代码的主要思想就是压栈和出栈

/*************************************************************************
    > File Name: maze.cpp
    > Author: Darin
    > Mail: dyy726@qq.com 
    > Created Time: 2013年06月08日 星期四 06时36分24秒
 ************************************************************************/
#include <iostream>
#include <stdlib.h> 
#include <time.h>
using namespace std;
#define orientationNum 4
int MazeMapLineNumber = 0;
typedef struct Position {
    int xcoordinate;
    int ycoordinate;
}POSITION;

typedef struct Node {
    POSITION Pos;
    struct Node *pNext;
}NODE,*PNode;

class CStack {
    public: 
        PNode pTop;
        PNode pBottom;
    public: 
            CStack();
            bool IsNull();
            void Push(POSITION pos);
            void Pop();
            POSITION GetTop();
            void clear();
            void ShowWay();
            ~CStack();
};

CStack::CStack(){
    pTop = pBottom = new NODE;
    pTop->pNext = NULL;
}

bool CStack::IsNull() {
    if (pTop == pBottom)
        return true;
    return false;
}

void CStack::Push(POSITION pos) {
    PNode p = new NODE;
    p->Pos = pos;
    p->pNext = pTop;
    pTop= p;
}

void CStack::Pop(){
    if(!IsNull()) {
        PNode p = pTop;
        pTop = p->pNext;
        delete(p);
    } else cout<<"The stack is null "<<endl;
}

void CStack::ShowWay() {
    PNode p = pTop;
    while(p->pNext != pBottom) {
        cout<<"("<<p->Pos.xcoordinate<<","<<p->Pos.ycoordinate<<") -> ";
        p = p->pNext;
    }
    cout<<"("<<p->Pos.xcoordinate<<","<<p->Pos.ycoordinate<<")";
}

POSITION CStack::GetTop() {
    return pTop->Pos;
}

void CStack::clear() {
    while(!IsNull()) Pop();
}

CStack::~CStack() {
    clear();
}
bool isOutOfborder(POSITION pos) {
    if(pos.ycoordinate<0 || pos.ycoordinate>=MazeMapLineNumber
        ||pos.xcoordinate<0 || pos.xcoordinate>=MazeMapLineNumber)
        return true;
    return false;
}

bool isequal(POSITION pos1,POSITION pos2) {
    if(pos1.xcoordinate == pos2.xcoordinate && 
        pos1.ycoordinate == pos2.ycoordinate) return true;
    return false;
}

void PassMaze(int **map,POSITION Inpos,POSITION OutPos) {
    CStack *MazeWay = new CStack();
    POSITION CurPos = OutPos;
    POSITION NewPos;
    int i =0;
    bool IsFind = false;
    MazeWay->Push(CurPos);
    while((!MazeWay->IsNull())&&(!isequal(CurPos,Inpos))) {
        //(!isOutOfborder(CurPos))
        CurPos = MazeWay->GetTop();
        IsFind = false;
        for(i=0;i<orientationNum;i++) {
            if(0 == i) {
                //right
                NewPos.xcoordinate = CurPos.xcoordinate;
                NewPos.ycoordinate = CurPos.ycoordinate+1;
            }
            if(1 == i) {
                //down
                NewPos.xcoordinate = CurPos.xcoordinate+1;
                NewPos.ycoordinate = CurPos.ycoordinate;
            }
            if(2 == i) {
                //left
                NewPos.xcoordinate = CurPos.xcoordinate;
                NewPos.ycoordinate = CurPos.ycoordinate-1;
            }
            if(3 == i) {
                //up
                NewPos.xcoordinate = CurPos.xcoordinate-1;
                NewPos.ycoordinate = CurPos.ycoordinate;
            }

            if(!isOutOfborder(NewPos) && map[NewPos.xcoordinate][NewPos.ycoordinate]) {
                IsFind = true;
                CurPos = NewPos;
                map[NewPos.xcoordinate][NewPos.ycoordinate] = 0;
                break;
            }
        }
        if(IsFind) {
            MazeWay->Push(CurPos);
        } else MazeWay->Pop();

    }
    if(MazeWay->IsNull()) {
        cout<<"There is no way to go out of the maze"<<endl;
    } else MazeWay->ShowWay();
}

int main() {
    int i=0,j=0;
    srand((unsigned)time(NULL));
    cout<<"Please input the row of the maze map:";
    cin>>MazeMapLineNumber;
    POSITION inpos;
    POSITION outpos;

    int **pMap = new int *[MazeMapLineNumber];
    for (i=0;i<MazeMapLineNumber;i++) {
        pMap[i] = new int [MazeMapLineNumber];
    }

    for (i=0;i<MazeMapLineNumber;i++) {
        for (j=0;j<MazeMapLineNumber;j++) {
            pMap[i][j] = rand()%2;
            cout<<pMap[i][j]<<" ";
        }
        cout<<"\n";
    }

//     for (i=0;i<MazeMapLineNumber;i++) {
//         for (j=0;j<MazeMapLineNumber;j++) {
//             cout<<pMap[i][j]<<" ";
//         }
//         cout<<"\n";
//     }

    cout<<"Please input inpos.x :";
    cin>>inpos.xcoordinate;
    cout<<"Please input inpos.y :";
    cin>>inpos.ycoordinate;
    cout<<"Please input outpos.x :";
    cin>>outpos.xcoordinate;
    cout<<"Please input outpos.y :";
    cin>>outpos.ycoordinate;
    PassMaze(pMap,inpos,outpos);

    return 0;
}

原文链接: https://www.cnblogs.com/darin726/archive/2013/06/08/3127381.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍