私は学校の課題に取り組んでいますが、進歩を妨げている愚かなことがいくつかあります。SO や Web の他の部分を検索しましたが、自分に合った答えが見つかりません。
問題は、スタックとキューを使用した 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 を追加
Queue.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
Stack.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