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

У меня были проблемы с программированием двусвязного списка. Проблема состоит в том, что моя функция 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

}

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

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

1

Решение

Вы смешиваете вместе 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 */
}

}

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

0

Другие решения

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

    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, что означает, что одна из ссылок будет указывать на другую часть списка.

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

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector