我正在为学校做作业，并且有一些愚蠢的事情使我无法取得进步。我在 SO 和网络的其他部分进行了搜索，但找不到适合我的答案。
问题是使用 Stacks 和 Queues 的 Rat-In-A-Maze 算法设计问题。我已经设计了我的 Stack（基于数组）和 Queue（链表）类，现在正在设计 searchStack() 和 searchQueue() 中的算法。
我的问题是：
1) 如何在我的 ratInMaze 类中声明堆栈或队列？我包括了 Stack.h 和 Queue.h 文件，但是当我尝试实例化它们时仍然出现错误
2) 我如何参考教授在 Main.cpp 中为我的方法中的操作提供的迷宫？IE 在我的代码中我希望它被称为 map[x][y] 并能够基于它执行操作。
这是我的ratInMaze.cpp：（尚未完成，但足以提供上下文）
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <string>
#include "RatInMaze.h"
#include "Queue.h"
#include "Stack.h"
using namespace std;
bool RatInMaze::isValidIndex(int x, int y)
{
// 12 x 14 array
if (x < 0 || y < 0 || x > 13 || y >15)
return false;
return true;
}
bool RatInMaze::searchStack(int fromX, int fromY, int toX, int toY)
{
int backX;
int backY;
int traveled;
int thePath;
//Matrix is 12x14, check dimensions
if (!isValidIndex(fromX,fromY))
{
cout<<"Not valid starting point"<<endl;
return false;
}
else if (!isValidIndex(toX, toY))
{
cout<<"Not a valid ending point";
return false;
}
Stack<int> ratStack(20); //throws error
//Create stack? //ATTENTION
// Load Map? //ATTENTION
//Set map variables
int x = fromX;
int y = fromY;
map[x][y]='S'; //Mark starting point
ratStack->push(y); //First coordinates in
ratStack->push(x); //the stack are starting points
//Load map? Attention
while ( !(x==toX || y==toY))
{
//Try to move right
if(isValidIndex(map[x][y+1]) && map[x][y+1] < 1)
{
//stack->Push coordinates onto stack
ratStack->push(y);
ratStack->push(x);
y=y+1;
map[x][y]='R';
traveled++;
}
//Try to move down
else if(isValidIndex(map[x+1][y]) && map[x+1][y] < 1)
{
ratStack->push(y);
ratStack->push(x);
x=x+1;
map[x][y]='D';
traveled++;
}
//Try move left
else if(isValidIndex(map[x][y-1]) && map[x][y-1] < 1)
{
ratStack->push(y);
ratStack->push(x);
y=y-1;
map[x][y]='L';
traveled++;
}
//Try move up
else if(isValidIndex(map[x+1][y]) && map[x+1][y] < 1)
{
ratStack->push(y);
ratStack->push(x);
x=x-1;
map[x][y]='U';
traveled++;
}
//Else you can't make any move, must retrace steps
else
{
//Pop off last coordinates on stack to get the previous square
backX = ratStack->pop();
backY= ratStack->pop();
//If we came from right, go back left, block off this square from revisiting
if(map[backX][backY]=='R')
{
map[backX][backY]=2;
y=y-1;
traveled--;
}
//If we came from above, go back up, block off this square from revisiting
else if(map[backX][backY]=='D')
{
map[backX][backY]=2;
x=x+1;
traveled--;
}
//If we came from left, go back right if we can, block off this square from revisiting
else if(map[backX][backY]=='L')
{
map[backX][backY]=2;
y=y+1;
traveled--;
}
//If we came from below, go back up, block off this square from revisiting
else if(map[backX][backY]=='U')
{
map[backX][backY]=2;
x=x+1;
traveled--;
}
//return to top of loop and we are now at the spot we came from before running into jam
//try to move right, down, left, up again as usual
//if not, we pop off another set of coordinates and repeat until we can move
}
} //End while loop
if (x==toX && y==toY)
{
cout<<"We found the cheese! "<<"It took us "<<ratStack->size()<<"squares and we traveled through" << traveled<<endl;
return true;
}
else
return false;
} //End method
/*
SearchQueue
"Sprawling rats"
start at the point, stack->push coordinates into queue stack->push(x) stack->push(y)
checke every direction possible and change the letter RLUD to indicate where you came from
and stack->push each one of those pairs to the queue
When at the end, trace back based on the RLUD until you get to where you started ('4')
*/
bool searchQueue(int fromX, int fromY, int toX, int toY)
{
int currentX;
int currentY;
//Matrix is 12x14, check dimensions
if (fromX < 0 || fromX >13 || fromY < 0 || fromY >15)
{
cout<<"Not valid starting point"<<endl;
return false;
}
else if (toX < 0 || toX > 13 || toY < 0 || toY > 15 )
{
cout<<"Not a valid ending point";
return false;
}
//Valid index, we can proceed
//Create Queue, starting points assigned
Queue<int> ratQueue;
int x = fromX;
int y = fromY;
myQueue->push(x);
myQueue->push(y);
bool found = false;
traveled=0;
while (!found)
{
currentX=myQueue->pop();
currentY=myQueue->pop();
if (currentX==toX && currentY==toY)
{
found = true;
break;
}
//Check right move
if (map[currentX][currentY+1] < 1)
{
myQueue->push(x);
myQueue->push(y+1);
map[x][y+1]='R';
traveled++;
}
//Check down move
if (map[currentX+1][currentY] < 1)
{
myQueue->push(x+1);
myQueue->push(y);
map[x+1][y]='D';
traveled++;
}
//Check left move
if (map[currentX][currentY-1] < 1)
{
myQueue->push(x);
myQueue->push(y-1);
map[x][y-1]='L';
traveled++;
}
//Check up move
if (map[currentX-1][currentY] < 1)
{
myQueue->push(x-1);
myQueue->push(y);
map[x-1][y] = 'U';
traveled++;
}
} //End while loop
//Cheese is now found
x=currentX;
y=currentY;
thePath = 0;
while( x == fromX || y == fromY)
{
//Check if we came from left
if (map[x][y]=='R')
{
map[x][y]=2;
y=y-1;
thePath++;
}
//Check if we came from above
else if (map[x][y]=='D')
{
map[x][y]=2;
x=x-1;
thePath++;
}
//Check if we came from right
else if (map[x][y]=='L')
{
map[x][y]=2;
y=y+1;
thePath++;
}
//Check if we came from below
else if (map[x][y]=='U')
{
map[x][y]=2;
x=x+1;
thePath++;
}
}
//Clean up array, leaving only 1s for the walls and 2 to show our path
for(int i=0; i <13; i++)
{
for( int j=0; i<15; j++)
{
if (map[i][j]!=1 && map[i][j]!=2)
map[i][j]=0;
}
}
cout<<"Found the cheese! We traveled "<<traveled<<" squares and the path took "<<thePath<<" squares"<<endl;
return true;
} //End searchQueue method
这是我的 Stack.cpp：
#include "Stack.h"
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
template<class T>
Stack<T>::Stack(int initialCapacity)
{
stackSize = initialCapacity;
emptyStack=-1;
stackTop=emptyStack;
stack = new int[initialCapacity];
}
template<class T>
Stack<T>::~Stack() { delete [] stack;}
template<class T>
void Stack<T>::push(const int& theElement)
{
stackTop++;
stack[stackTop]=theElement;
}
template<class T>
bool Stack<T>::empty() const
{
return stackTop==emptyStack;
}
template<class T>
int Stack<T>::size() const
{
return stackTop+1;
}
template<class T>
int Stack<T>::top()
{
return stack[stackTop];
}
template<class T>
void Stack<T>::pop()
{
stack[stackTop]=NULL;
stackTop--;
}
这是我的 Queue.cpp：
#include <stdio.h>
#include <ostream>
#include <sstream>
#include "Queue.h"
#include <cstddef>
using namespace std;
template <class T>
Queue<T>::Queue()
{
first,last=NULL;
}
template <class T>
Queue<T>::~Queue()
{
}
template <class T>
bool Queue<T>::empty()
{
return (first==NULL && last==NULL);
}
template <class T>
int Queue<T>::size()
{
int count=0;
tempNode = first;
while (tempNode->next !=NULL)
{
count++;
tempNode = tempNode->next;
}
return count;
}
template <class T>
int& Queue<T>::back()
{
return first;
}
template <class T>
int& Queue<T>::front()
{
return last;
}
template <class T>
void Queue<T>::pop()
{
if (first==NULL)
return;
else if (last==NULL)
return;
else
{
last = last->prev;
last->next=NULL;
}
}
template <class T>
void Queue<T>::push(T element)
{
if(first==NULL)
{
first=new Node<T>(element);
last=first;
first->next=NULL;
first->prev=NULL;
}
else
{
tempNode = first;
first = new Node<T>(element);
first->next = tempNode;
tempNode->prev = first;
}
}
这是教授的 Main.cpp：
#include <iostream>
#include "RatinMaze.h"
using namespace std;
void print_header (string h, int fromX,int fromY,int toX,int toY) {
cout << h << "from " << "(" << fromY << "," << fromX << ") to ("
<< toY << "," << toX << "):" << endl;
}
int main (){
RatInMaze* rim = new RatInMaze();
char maze[13][15]={
'0','0','0','1','0','0','0','0','0','0','1','0','0','0','0',
'0','0','0','1','0','0','1','0','0','0','0','0','0','0','0',
'0','0','0','0','0','0','0','1','1','1','1','1','1','1','1',
'0','0','0','1','1','1','0','0','1','0','0','1','0','0','0',
'0','0','0','0','0','1','1','0','0','1','0','0','1','0','0',
'1','1','0','0','0','1','1','0','0','1','0','0','0','0','0',
'0','1','1','0','0','1','1','0','0','1','0','0','0','0','0',
'0','0','1','0','0','1','1','0','0','1','0','0','0','0','0',
'0','1','1','0','0','1','0','0','0','0','0','0','0','0','0',
'0','0','1','0','0','0','1','1','1','1','1','1','1','1','1',
'0','0','1','0','1','0','0','0','0','0','0','0','0','0','0',
'0','0','1','0','1','0','0','0','1','0','0','0','0','0','0',
'0','0','0','0','1','0','0','1','0','0','0','0','0','0','0' };
rim->load(maze,13,15);
print_header("Queue search ", -1,1,10,10);
rim->print(rim->searchQueue(-1,1,10,10));
rim->load(maze,13,15);
print_header("Stack search ", 0,0,41,1);
rim->print(rim->searchStack(0,0,41,1));
int fromX = 0;
int fromY = 7;
int toX = 14;
int toY = 6;
rim->load(maze,13,15);
print_header("Rat (stack) searching ",fromX,fromY,toX,toY);
rim->print(rim->searchStack(fromX,fromY,toX,toY));
rim->load(maze,13,15);
print_header("Multiple rats searching ",fromX,fromY,toX,toY);
rim->print(rim->searchQueue(fromX,fromY,toX,toY));
rim->load(maze,13,15);
print_header("Smart rat searching ",fromX,fromY,toX,toY);
rim->print(rim->searchStackSmart(fromX,fromY,toX,toY));
}
我是这门语言的新手，我敢肯定有很多事情不是我要问的；我感谢任何建设性的反馈，并将努力解决您真正认为需要它的任何问题。提前致谢！
编辑：添加 Stack.h 和 Queue.h 以进行澄清
队列.h：
#ifndef QUEUE_H
#define QUEUE_H
#include <cstddef>
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <string>
//Create node struct to implement from linked list
template<class T>
struct Node
{
T data;
Node* next;
Node* prev;
Node(T d, Node* n=NULL): data(d), next(n){}
};
template<class T>
class Queue
{
private:
Node<T> *first;
Node<T> *last;
Node<T> *tempNode;
Node<T> *deleteNode;
public:
Queue();
~Queue();
bool empty();
int size();
int& front();
int& back();
void pop();
void show();
void push (T data);
}; //End of class queue
#endif
堆栈.h：
#ifndef STACK_H
#define STACK_H
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <string>
template<class T>
class Stack
{
int stackTop; //Top of stack
int stackSize; //Total stack size
int emptyStack; //emptyStack
T* ratStack; //A stack
public:
Stack(int initialCapacity); //Constructor
~Stack(); //Destructor
bool empty() const; //Returns true if stack is empty
int size() const; //Returns size of stack
int top(); //Returns top of stack
void pop(); //Deletes top element
void push(const int& theElement); //Puts theElement at the top
}; //End stack class
#endif