使用堆栈的河内塔 C++ 实现

Question

我已经为带堆栈的递归 ToH 算法编写了以下代码，但无法弄清楚为什么会失败。没有编译错误，但是一旦程序真正开始运行，它 "thinks" 就会崩溃。有什么想法吗？

相关代码：

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：对不起，西班牙英语，我的 class 是西班牙语，但许多想法仍然以英语呈现，因此是时髦的语言。

重要的翻译应该是必要的：

aloritmoDeTorres - 塔算法

Discos - 磁盘

pila-堆栈

Origen - 起源

元 - Destination/Goal

InsertaInicio - 插入（在）开始

Imprime - 打印

Regresa - Return

博拉 - Erase/Delete

Nodo - 节点

卡贝萨 - 头

Siguiente - 下一个

Answer 1

主要是重新排列类，并填空：

#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;
}

使用堆栈的河内塔 C++ 实现

Towers of Hanoi C++ Implementation with Stacks

c++

algorithm

recursion

stack

towers-of-hanoi