Добавление функции в двусвязный список приводит к бесконечному циклу

У меня возникли проблемы с программированием двусвязного списка. Проблема в том, что моя функция Add приводит к бесконечному циклу, когда я проверяю ссылки на nullptr. Когда я этого не делаю, это дает мне ошибку. Я пытался исправить это, и для жизни я не могу понять это. Ниже приведен метод добавления:

    void Add(string n, int w) //Method to add a node to the Linked List and maintain the order.
{

    node * nd = new node(n, w, nullptr, nullptr);

    if (nHead == nullptr && wHead == nullptr) //If there is nothing in the Linked List
    {
        nHead = nd; //Add a node
        wHead = nd;
    }

    else //If there is something in the linked List
    {
        node * ntraverse = nHead; //variable to traverse down the name links

        while (nd->name > ntraverse->name && ntraverse->wLink != nullptr)
        {
            ntraverse = ntraverse->nLink; // Traverses down the name links until nd's name is smaller than a links
        }

        nd->nLink = ntraverse; // Here, the namelink for nd is set to ntraverse, since ntraverse is less than or equal to nlink
        ntraverse->nLink = nd; // So here, since nd is the new value appended to the rest of the list, we set ntraverse = nlink.

                               // note at this point, we have not handled weight

        node * wtraverse = wHead; //variable to traverse down the weight links

        while (nd->weight > wtraverse->weight && wtraverse->wLink != nullptr)
        {
            wtraverse = wtraverse->wLink; // Traverses down the weight links until nd's weight is smaller than a links
        }

        nd->wLink = wtraverse; // Here, the namelink for nd is set to ntraverse, since ntraverse is less than or equal to nlink
        wtraverse->wLink = nd; // So here, since nd is the new value appended to the rest of the list, we set ntraverse = nlink.

        //at this point, nd holds both the correct nlink and wlink

    }

    cout << "Added: " << nd->name << " " << nd->weight << "\n";
    cout << "Current nlist:\n";
    nPrint();
    cout << "Current wlist:\n";
    wPrint();

    size++; //increment size

}

Любая помощь приветствуется. Если вам нужно, чтобы я что-то ответил, пожалуйста, дайте мне знать. Node работает нормально, он хранит 4 значения: имя, вес, nLink и wLink, где nLink хранит список, упорядоченный по имени, а wLink сохраняет список, упорядоченный по весу. Для LinkedList nHead — заголовок имени, а wHead — заголовок веса.

Еще раз спасибо за вашу помощь.


person Paul    schedule 07.10.2016    source источник
comment
Я предполагаю, что это C или C++? Пожалуйста, добавьте соответствующие теги. Если да, то что такое nullptr   -  person Stephen Reindl    schedule 07.10.2016
comment
C++, Причина, по которой я добавил nullptr, заключается в том, что я подумал, что что-то может пойти не так при проверке ссылок на nullptr.   -  person Paul    schedule 08.10.2016


Ответы (2)


Вы смешиваете wLink и nLink вместе

node * ntraverse = nHead; //variable to traverse down the name links

while (nd->name > ntraverse->name && ntraverse->wLink != nullptr)

В приведенном выше примере вы просматриваете ссылки имен и проверяете, находитесь ли вы в конце списка весов.

Это не двусвязный список, это два односвязных списка, и вы должны обрабатывать каждый список отдельно.

Другими словами, ваш код должен выглядеть примерно так:

    void Add(string n, int w) //Method to add a node to the Linked List and maintain the order.
{

    node * nd = new node(n, w, nullptr, nullptr);

    if (nHead == nullptr ) //If there is nothing in the Linked List
    {
        nHead = nd; //Add a node
    }


    else //If there is something in the linked List
    {
       /* Code to handle nLink with no mention of wLink */
    }

    if (wHead == nullptr ) //If there is nothing in the Linked List
    {
        wHead = nd; //Add a node
    }


    else //If there is something in the linked List
    {
       /* Code to handle wLink with no mention of nLink */
    }

}

Конечно, идеальным решением было бы написать класс связанного списка....

person Paranoid    schedule 07.10.2016
comment
Эй, приятель, спасибо за твой ответ. Во-первых, это метод внутри класса Linked List. Во-первых, когда я изменил while (nd->name > ntraverse->name && ntraverse->wLink != nullptr) на while (nd->name > ntraverse->name && ntraverse->nLink != nullptr), это все равно приводит к бесконечному циклу. Во-вторых, это двусвязный список. Node имеет четыре значения: Name, Weight, nLink и wLink, где nLink указывает на следующий узел, упорядоченный по имени, а wLink указывает на следующий узел, упорядоченный по весу, поэтому я не разделяю оператор if. - person Paul; 07.10.2016
comment
В двусвязном списке каждый узел будет иметь указатель на следующий узел и указатель на предыдущий узел. Это означает, что верно следующее (за исключением конечных узлов): ` n-›Next-›Prev == n` У вас есть односвязный список имен и односвязный список весов. - person Paranoid; 07.10.2016
comment
Определение двусвязного узла состоит в том, что он имеет две связи. Он не обязательно должен иметь прямую ссылку и обратную ссылку, хотя обычно он используется именно так. В этом случае узел хранит 2 связи, каждая из которых упорядочена по разным переменным. - person Paul; 08.10.2016

Так я понял в чем проблема. В конце каждого цикла у меня было

    nd->wLink = wtraverse; // Here, the namelink for nd is set to ntraverse, since ntraverse is less than or equal to nlink
    wtraverse->wLink = nd; // So here, since nd is the new value appended to the rest of the list, we set ntraverse = nlink.

Это создавало круговую петлю. ссылка nd хранит wtraverse, а ссылка wtraverse хранит nd, что означает, что одна из ссылок будет указывать на другую часть списка.

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

person Paul    schedule 08.10.2016