利用自定义栈实现的走迷宫程序_C++ 利用自定义栈实现的走迷宫程

利用自定义栈实现的走迷宫程序_C++

程序纲要

自定义栈
寻路类
完整实现
最后

程序纲要程序利用了栈先进后出的特点，相比用数组，简化了设计程序的思考过程
利用寻路函数可以判断前进后退，方向等等
自定义栈

typedef struct Position { int x; int y; bool operator == (Position &a) { if (this->x == a.x && this->y == a.y) return true; else return false; } }Position; typedef struct Pos { Position P; Pos *Next; }Pos; class Stack { private: Pos *Head; Pos *End; public: Stack(); ~Stack(); bool IsEmpty() { return Head == nullptr; } Pos GetTop(); void Push(Pos New); void Push(Position New); void Pop(); };

Position和Pos为链表栈的链表结构
Stack类为自定义的栈，Head为栈底，End为栈顶
IsEmpty判断栈是否为空
GetTop获得栈顶的元素
Push将元素压入栈，两个重载函数压入的类型不一样
Pop删除栈顶的元素
寻路类

class Find { private: Stack stack; //stack类 Position Start; //起点 Position Target; //终点 int maze[Maze_Rows][Maze_Cols]; //存放迷宫的数组 public: Find(int maze[][10],Position Start,Position Target); ~Find(); Position Next_Step(); void Go_Next(Position Next); void Go_Back(); bool IsArrive(); bool AutoFind(); };

Next_Step为判断在该位置下一步的坐标
Go_Next走向给定的坐标
Go_Back原路返回一格
IsArrive判断是否到达
AutoFind调用直接寻路
在走下一步的时候，要在刚刚的地方放“障碍物”，以防会绕回来造成死循环
退一步的时候就不必把放的“障碍物”拿掉，因为防止以后又走到死胡同里面去
完整实现

//Find.cppconst int Maze_Rows = 10; //迷宫的行数 const int Maze_Cols = 10; //迷宫的列数Find::Find(int maze[][10], Position Start, Position Target) { for(int i = 0; i < Maze_Rows; i++) for (int j = 0; j < Maze_Cols; j++) { this->maze[i][j] = maze[i][j]; } this->Start = Start; this->Target = Target; stack.Push(Start); }Find::~Find() { }Position Find::Next_Step() { Pos Now = stack.GetTop(); if (maze[Now.P.y][Now.P.x + 1] != 1) { Now.P.x = Now.P.x + 1; return Now.P; } else if (maze[Now.P.y + 1][Now.P.x] != 1) { Now.P.y = Now.P.y + 1; return Now.P; } else if (maze[Now.P.y][Now.P.x - 1] != 1) { Now.P.x = Now.P.x - 1; return Now.P; } else if (maze[Now.P.y - 1][Now.P.x] != 1) { Now.P.y = Now.P.y - 1; return Now.P; } else { return Now.P; //返回原地，表示没有路可走 } }void Find::Go_Next(Position Next) { Pos Now = stack.GetTop(); maze[Now.P.y][Now.P.x] = 1; stack.Push(Next); }void Find::Go_Back() { Pos Now = stack.GetTop(); maze[Now.P.y][Now.P.x] = 1; stack.Pop(); }bool Find::IsArrive() { if (Target == stack.GetTop().P) return true; else return false; }bool Find::AutoFind() { while (!IsArrive()) { Position Next = Next_Step(); Position Now = stack.GetTop().P; if (Next == Now) { Go_Back(); } else { Go_Next(Next_Step()); } std::cout << stack.GetTop().P.x << "," << stack.GetTop().P.y << std::endl; } return true; }

//Stack.cpp Stack::Stack() { Head = End = nullptr; }Stack::~Stack() { delete Head; }Pos Stack::GetTop() { return *End; }void Stack::Push(Pos New) { if (IsEmpty()) { Head = new Pos; Head->P.x = New.P.x; Head->P.y = New.P.y; Head->Next = nullptr; End = Head; } else { End->Next = new Pos; End = End->Next; End->P.x = New.P.x; End->P.y = New.P.y; End->Next = nullptr; } }void Stack::Push(Position New) { if (IsEmpty()) { Head = new Pos; Head->P.x = New.x; Head->P.y = New.y; Head->Next = nullptr; End = Head; } else { End->Next = new Pos; End = End->Next; End->P.x = New.x; End->P.y = New.y; End->Next = nullptr; } }void Stack::Pop() { if (IsEmpty()) { } else { Pos *P = Head; while (P->Next != End) { P = P->Next; } delete End; End = P; } }

//Main.cpp #include #include"Find.h" #include"stack.h"using namespace std; int M[10][10] ={{1,1,1,1,1,1,1,1,1,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,0,1,0,1,0,1,1}, {1,0,1,0,1,0,1,0,0,1}, {1,0,1,0,1,0,1,1,0,1}, {1,0,1,0,1,0,1,0,0,1}, {1,0,1,0,1,0,1,0,1,1}, {1,0,1,0,1,0,1,0,1,1}, {1,0,0,0,1,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}}; int main() { Position S,T; S.x = 1; S.y = 1; T.x = 8; T.y = 1; Find F(M, S, T); if (F.AutoFind()) cout << "Success!" << endl; return 0; }

最后 【利用自定义栈实现的走迷宫程序_C++】这是看到数据结构书里的题然后写的
我还是个学生，功力有限
望体谅
有更好的代码或者哪里有错就留言吧！