Алгоритм — реализация Ханойского C ++ со стеками
Я написал следующий код для рекурсивного алгоритма ToH со стеками и не могу понять, почему он не работает. Нет ошибок компиляции, но как только программа действительно начинает работать, она немного «думает», а затем вылетает. Есть идеи?
Соответствующий код:
void algoritmoDeTorres(int numDiscos, pila &origen, pila &aux, pila &meta)
{
GotoXY(0,0);
if(numDiscos==1)
{
int item;
item = origen.pop(); //crashes in this function
lista laux;
laux.insertaInicio(item);
meta.push(item);
return;
}
algoritmoDeTorres(numDiscos - 1, origen, aux, meta);
origen.imprimePila();
cout << endl;
aux.imprimePila();
cout << endl;
meta.imprimePila();
algoritmoDeTorres(numDiscos -1, aux, meta, origen);
}class pila
{
private:
lista lisst;
public:
int pop()
{
int tam;
tam = lisst.regresaItem();
lisst.borraInicio();
return tam;
}
};
class lista
{
private:
nodo *cabeza;
public:
lista()
{
cabeza = NULL;
}
void borraInicio()
{
nodo * aux;
aux = cabeza->next;
delete cabeza;
cabeza = aux;
}
int regresaItem()
{
return cabeza->item; //crashes here specifically
}
};
class nodo
{
public:
int item;
nodo* next;
nodo(int a,nodo * siguiente)
{
item = a;
next = siguiente;
}
};
int main()
{
pila ORIGEN,AUX,META;
ORIGEN.push(3);
ORIGEN.push(2);
ORIGEN.push(1);
algoritmoDeTorres(ORIGEN.Size(),ORIGEN,AUX,META);
ORIGEN.destruirPila();
AUX.destruirPila();
META.destruirPila();
return 0;
}
PS: Извините за Spanglish, мой класс на испанском, но многие идеи все еще представлены на английском языке, отсюда и фанки.
Важные переводы, если они необходимы:
aloritmoDeTorres — Алгоритм Башни
Дискотеки — Диски
Пила — Стек
Ориген — Происхождение
Мета — Направление / Цель
InsertaInicio — Вставить (в) Начало
Imprime — Печать
Регреса — Возвращение
Борра — Стереть / Удалить
Нодо — Узел
Кабеза — руководитель
Siguiente — Next
Решение
В основном это просто перестановка классов и заполнение пробелов:
#include <iostream>
using namespace std;
class nodo
{
public:
int item;
nodo* next;
nodo(int a,nodo * siguiente)
{
item = a;
next = siguiente;
}
};
class lista
{
private:
nodo* cabeza;
nodo* p;
public:
lista()
{
cabeza = NULL;
p = NULL;
}
void insertaInicio(int n)
{
//create a new node
cabeza = new nodo(n, p);
//set next pointer to head
p = cabeza;
}
void borraInicio()
{
nodo * aux;
aux = cabeza->next;
delete cabeza;
cabeza = aux;
}
int regresaItem()
{
return cabeza->item;
}
};
class pila
{
private:
//sz (with getters and setters) used to keep track of the size of the stack
//(incremented in push, decremented in pop)
int sz;
lista lisst;
public:
pila()
{
sz = 0;
}
int size()
{
return sz;
}
void setsize(int size)
{
sz = size;
}
void push(int n)
{
lisst.insertaInicio(n);
sz++;
}
int pop()
{
int tam;
tam = lisst.regresaItem();
lisst.borraInicio();
sz--;
return tam;
}
void imprimePila()
{
//a lengthy way to print the stack
//was abit unusual as the pop function
//was removing elements from the stack,
//when all that was necessary was to print them.
//this was a workaround that just copied the stack,
//printed (and removed) elements from original stack,
//but set the empty to stack to the copy,
//to leave it unchanged.
//feel free to find a better way for this
lista copy;
cout << '[';
int lsize = this->size();
int arr[3] = {};
int ind = 2;
while (this->size() != 0){
int item = this->pop();
arr[ind] = item;
cout<< item;
cout << ',';
ind--;
}
for (int i = ind; i < 3; i++){
copy.insertaInicio(arr[i]);
}
cout << ']';
lisst = copy;
this->setsize(lsize);
}
};
//the stacks are instantiated globally so they can be printed at every
//recursive step from algoritmoDeTorres()
pila ORIGEN, AUX, META;
void algoritmoDeTorres(int numDiscos, pila &origen, pila &aux, pila &meta)
{
//if statement used to rearrange discs ONLY if there are any (if numdiscos is more than 0)
if (numDiscos > 0){
//move (numDiscos - 1) discs from origen to aux, so they are out of the way
algoritmoDeTorres(numDiscos - 1, origen, meta, aux);
//move the exposed disc from origen to meta
int item;
item = origen.pop();
//lista laux;
//laux.insertaInicio(item);
//commented this list out since the item
//is added to the list of stack its being added to in the push call
meta.push(item);
ORIGEN.imprimePila();
AUX.imprimePila();
META.imprimePila();
cout << endl;
//now move the (numDiscos - 1) discs that we left on aux onto meta
algoritmoDeTorres(numDiscos - 1, aux, origen, meta);
}
}
int main()
{
ORIGEN.push(3);
ORIGEN.push(2);
ORIGEN.push(1);
ORIGEN.imprimePila();
AUX.imprimePila();
META.imprimePila();
cout << endl;
algoritmoDeTorres(ORIGEN.size(), ORIGEN, AUX, META);
//objects not allocated with 'new' don't need to be explicitly destroyed
//ORIGEN.destruirPila();
//AUX.destruirPila();
//META.destruirPila();
return 0;
}
Другие решения
Других решений пока нет …