Очередь не правильно вставляет указатели - PullRequest
Новая
       7

Очередь не правильно вставляет указатели

0 голосов
/ 02 июня 2018

Я пытаюсь воссоздать очередь в C ++, и у меня возникают проблемы с правильной вставкой указателей.Взгляните 

#include "stdafx.h"
#include <iostream>

using namespace std;

class Node {
public:
    int value;
    Node * next_node = nullptr;
    Node * previous_node = nullptr;
};

class Queue {
public:
    Node * front_node = nullptr;
    Node * back_node = nullptr;

    void insert(int number) {

        Node * NewNode = new Node{};
        NewNode->value = number;


        if (front_node == nullptr) {
            front_node = NewNode;
        }

        else if (back_node == nullptr) {
            back_node = NewNode;
        }

        else if (front_node->previous_node == nullptr) {
            front_node->previous_node = back_node;
            back_node = NewNode;

        }

        else {
            Node * temp_node = new Node{};
            temp_node = front_node->previous_node;
            while (1 == 1) {
                if (temp_node->previous_node == nullptr) {
                    temp_node->previous_node = back_node;
                    back_node = NewNode;
                    break;
                }
                else {
                    temp_node = temp_node->previous_node;
                }
            }

        }

    }

    int deque() {

        if (front_node == nullptr) {
            if (back_node != nullptr) {
                int return_value = back_node->value;
                back_node = nullptr;
                return return_value;
            }
            return 0;
        }

        else {
            int return_value = front_node->value;
            front_node = front_node->previous_node;
            return return_value;

        }

    }
};



int main()
{
    Queue queue;
    queue.insert(10);
    queue.insert(9);
    queue.insert(8);
    queue.insert(7);
    queue.insert(6);
    cout << queue.deque() << endl;
    cout << queue.deque() << endl;
    cout << queue.deque() << endl;
    cout << queue.deque() << endl;
    cout << queue.deque() << endl;

    system("PAUSE");
    return 0;
}

В соответствии с функцией вставки по мере продолжения front_node является nullptr, поэтому первый узел будет вставлен туда, и он получится корректным.Следующим был бы задний узел, и это получилось бы прекрасно и модно.Когда дело доходит до третьего узла, я вставляю указатель заднего узла в предыдущий указатель переднего узла, а новый узел - в указатель back_node.Новый узел помещается в задний узел, но указатель переднего узла-> предыдущий_узел выглядит как nullptr.

Редактировать 1: я изменил if с front_node! = Nullptr на front_node! = Nullptr и back_node ==nullptr.Кажется, он все еще не вставляется в предыдущий узел front_node

Редактировать 2: Я воспользовался советом, чтобы переписать его, и теперь у меня есть функция вставки, работающая правильно, но теперь, кажется, разматывание в третьем деке сходит на нет.

Редактировать 3: Моя последняя ошибка была в том, что вместо front_node-> previous_node = back_node я сделал front_node = back_node.Спасибо всем, кто помог.

Ответы [ 2 ]

0 голосов
/ 02 июня 2018

Вот еще одна вставка с использованием механизма зацикливания. 

void insert()
{
    Node * NewNode = new Node{};
    NewNode->value = number;

    if (front_node == nullptr)
    {
        front_node = NewNode;
        back_node = NewNode;
        return;
    }

    Node* node = nullptr;
    for (node = front_node; node->next_node != nullptr; node = node->next_node);

    node->next_node = NewNode;
    NewNode->previous_node = node;
    NewNode->next_node = nullptr;
    back_node = NewNode;
}

Наслаждайтесь ...:)

Теперь используем указатель back_node, чтобы сделать это более эффективным для достаточно длинных очередей. 

void insert(int number) {
    Node * NewNode = new Node{};
    NewNode->value = number;

    if (front_node == nullptr)
    {
        front_node = NewNode;
        back_node = NewNode;
        return;
    }

    Node* node = back_node;
    node->next_node = NewNode;
    back_node = NewNode;
    back_node->previous_node = node;
}

Так лучше ---;)

0 голосов
/ 02 июня 2018

Правильный метод вставки: 

void insert(int number) {
    Node *NewNode = new Node{};
    NewNode->value = number;
    if (front_node == nullptr) {
        NewNode->previous_node = nullptr;
        front_node = NewNode;
    }
    else{
        NewNode->previous_node = back_node;    
        back_node->next_node = NewNode;
    }
    back_node = NewNode;
}

Здесь сначала я проверяю, пусто ли front_node, если это - NewNode - первый узел, а также последний.Иначе, мы должны добавить Node после back_node (back_node's next_node).Не забудьте обновить previous_node и back_node next_node.Затем установите back_node на NewNode.

...