Ошибка исключения при реализации Ханойской башни с использованием связанного списка - PullRequest
Новая
       44

Ошибка исключения при реализации Ханойской башни с использованием связанного списка

0 голосов
/ 08 октября 2018

Я пытаюсь реализовать Ханойскую башню, используя Linked List.Вот код. 

    struct tower_ {
    int size;
    node* head;
    tower_() {
        size = 0;
        head = NULL;
    }
    int pop() {
        if (size == 0)
            return -1;
        else {
            size--;
            node* iter = head;
            while (iter->next && iter->next->next != NULL)
                iter = iter->next;
            int rt = iter->next->value;
            delete iter->next;
            iter->next = NULL;
            return rt;
        }

    }
    int insert(int x) {
        node* newNode = new node;
        newNode->value = x;
        newNode->next = NULL;
        if (size == MAX_SIZE)
            return -1;
        else if (head == NULL) {
            head = newNode;
            size++;
            return 0;
        }
        else {
            node* iter = head;
            while (iter->next != NULL)
                iter = iter->next;
            iter->next = newNode;
            size++;
            return 0;
        }
    }
    void printTower() {
        node* iter = new node;
        for (iter = head; iter != NULL; iter = iter->next) {
            std::cout << iter->value << " ";
        }
        std::cout << "\n";
    }
};

void hanoi(int size, tower_ source, tower_ target, tower_ aux) {
    if (size == 1) {
    target.insert(source.pop());
    return;
}
    hanoi(size - 1, source, aux, target);
    hanoi(size - 1, aux, target, source);
}

int main() {
    tower_ A, B, C;
    A.insert(3);
    A.insert(2);
    A.insert(1);
    std::cout << "A: ";
    A.printTower();
    hanoi(3, A, C, B);
    std::cout << "\n" << "C: ";
    C.printTower();
    return 0;
}

При запуске я получаю следующий вывод: 

A: 3 2 1

C:

Кажется, я не вижу проблем с функциями pop() и insert()и я проверил их отдельно.Я отладил и обнаружил, что это может быть из-за возврата -1 функции pop() для пустого списка.С другой стороны, когда я изменил свое определение Ханоя на это: 

void hanoi(int size, tower_ source, tower_ target, tower_ aux) {
    if (size > 0) {
        hanoi(size - 1, source, aux, target);
        target.insert(source.pop());
        hanoi(size - 1, aux, target, source);
    }

Выдает ошибку исключения в следующей строке: int rt = iter->next->value; с Exception thrown: read access violation. iter->next was nullptr.

Что является правильнымспособ сделать это?Любая подсказка будет оценена.Благодаря.

1 Ответ

0 голосов
/ 08 октября 2018

Отладчик поможет.Вот что происходит, когда вы распечатываете башни каждый раз, когда они модифицируются. 

void hanoi(int size, tower_ source, tower_ target, tower_ aux) {
    if (size == 1) {
        std::cout << "target before insert: ";
        target.printTower() ;
        std::cout << std::endl;
        std::cout << "source before pop: "; 
        source.printTower() ;
        std::cout << std::endl;

        target.insert(source.pop());


        std::cout << "target after insert: ";
        target.printTower() ;
        std::cout << std::endl;
        std::cout << "source after pop: " ;
        source.printTower();
        std::cout << std::endl << "------------------------------------" <<  std::endl;
        return;
    }
    hanoi(size - 1, source, aux, target);
    hanoi(size - 1, aux, target, source);
}

A: 3 2 1 

target before insert: 

source before pop: 3 2 1 

target after insert: 1 

source after pop: 3 2 

------------------------------------
target before insert: 

source before pop: 

target after insert: -1 

source after pop: 

------------------------------------
target before insert: 3 2 

source before pop: 

target after insert: 3 2 -1 

source after pop: 

------------------------------------
target before insert: 

source before pop: 3 2 -1 

target after insert: -1 

source after pop: 3 2 

------------------------------------

C:
...