У меня были проблемы с программированием двусвязного списка. Проблема состоит в том, что моя функция 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 — заголовок веса.
Еще раз спасибо за вашу помощь.
Вы смешиваете вместе 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 */
}
}
Конечно, идеальным решением было бы написать связанный список классов ….
Я понял, в чем проблема. В конце каждого цикла у меня было
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, что означает, что одна из ссылок будет указывать на другую часть списка.
Что касается семантического аргумента в терминологии «Двойной связанный список», мой профессор в Структуре данных ссылается на структуру данных, в которой узел имеет две ссылки в виде Двойного связанного списка. Является ли это правильным или нет, спор о семантике мало помог и не сделал ничего для решения проблемы.