Как вставить в отсортированный связанный список?

Конечно, есть надежда, нам всем нужно с чего-то начинать! :)

Прежде всего, я должен указать на опасную практику в вашей реализации, которую использовали мои собственные ученики, и обычно это приводило к множеству головокружений, чтобы найти проблему:

while ( headByName->nextByName != NULL )
{
     headByName->nextByName = tail_node;
     tail_node = next_node;
     //next_node = current_node;
}

Не используйте член списка, такой как headByName, в качестве переменной итерации в вашем цикле, если это не является абсолютно необходимым. Вы должны сначала найти соответствующий узел, используя локальную переменную, а затем изменить этот узел.

Тем не менее, Роб Кеннеди прав в том, что вы должны обрабатывать имя и рейтинг отдельно (другими словами, «чистая» реализация будет иметь два экземпляра общего класса списка, который не знает, что такое «имя» и 'оценка' означает), однако я предполагаю, что интерфейсы для списка, узла и функции выше были даны вам в назначении (если нет, проигнорируйте остальную часть моего ответа :)).

Учитывая вышеупомянутые интерфейсы, мой подход будет следующим:

void list::insert(const winery& winery)
{
    node* wineryNode = new node(winery);
    assert (wineryNode);

    // Find  a node in the list with a name greater than wineryNode's
    node* prevNode = NULL;
    node* searchNode = headByName; // Note: not using the list member itself to iterate but a local variable
    while (NULL != searchNode && 
        searchNode.winery.getName() < wineryNode.winery.getName())
    {
        // Keep iterating through the list until there are no more items, or the right node is found
        prevNode = searchNode;
        searchNode = searchNode->nextByName;
    }   

    /* At this point searchNode is either NULL 
       or it's name is greater than or equal to wineryNode's */

    // Check for the case where the list was empty, or the first item was what we wanted
    if (NULL == prevNode)
    {
        headByName = wineryNode;
    }
    else
    {
        // prevNode is not NULL, and it's Name is less wineryNode's
        prevNode-> nextByName = wineryNode;
    }
    wineryNode->nextByName = searchNode;    

    /*  Now you just need to insert sorted by rating using the same approach as above, except initialize searchNode to headByRating, 
    and compare and iterate by ratings in the while loop. Don't forget to reset prevNode to NULL */
}

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

Обычное место для вставки в связанный список, когда более конкретный порядок не требуется, находится в конце списка. Для этого необходимо выполнить следующие действия:

1. Создайте новый узел.
2. Найдите место для вставки нового узла (т. Е. Последний узел в конце списка)
3. Обновите указатель «следующий» последнего узла, чтобы он указывал на новый узел.

Когда вы вставляете то, что может быть серединой списка, как в вашем случае, тогда есть еще один шаг:

2.5. Обновите указатель «следующий» нового узла.

Причина, по которой этот шаг обычно не выполняется, заключается в том, что при вставке в конец списка «следующий» указатель нового узла уже равен нулю с момента создания нового объекта узла.

Вы уже определились с первым шагом. Фактически, вы сделали это тоже хорошо, потому что ваш код фактически создает два новых узла. Один вы храните в current_node, а другой в tail_node. Избавьтесь от второго.

Шаг 2 посвящен выяснению того, какой узел должен быть тем, который непосредственно предшествует новому узлу. При сортировке по имени это будет узел, расположенный перед первым обнаруженным узлом, имя которого после текущего имени. Вам придется пройтись по списку, возможно, просматривая каждый узел, пока не найдете тот, который принадлежит после имени нового узла. По мере продвижения по списку вам нужно будет отслеживать, какой узел появился до этого узла, потому что, как только вы найдете узел, который ищете, вы собираетесь придется отказаться.

Позаботьтесь о названии и рейтинге отдельно. Не пытайтесь решить обе части сразу. Как только вы правильно вставите название винодельни, продублируйте этот код и замените «имя» на «рейтинг». Но не создавайте другой объект узла. Продолжайте использовать тот, который вы создали ранее.

Работая над этим заданием, рисовали ли вы какие-нибудь изображения узлов со стрелками, указывающими на другие узлы? Попробуй. Вы наверняка видели это в своем учебнике или на классной доске учителя. Если проблема слишком велика, чтобы ее можно было рассуждать исключительно в голове, используйте что-нибудь, что поможет вам отслеживать вещи, находящиеся вне вашей головы. Это делают и профессионалы. Поскольку каждый узел имеет несколько указателей, вы должны либо пометить указатели, либо использовать разные цвета для имени и рейтинга.

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

Я не уверен, что правильно понимаю ваш вопрос. Идем как раз из темы "Как вставить в отсортированный связанный список?" Я бы сделал что-то вроде этого (псевдокод):

list::insert(Winery winery) {
    Winery node = getHeadNode();

    // winery comes before the head node
    if (winery.name < node.name) {
        // the old head node now goes after this new node
        // and this new node becomes the new head node
        winery.next = node;
        setHeadNode(winery);
        return;
    }

    // let's iterate over the rest of the nodes in the list
    Winery previous_node = node;
    node = node.next;
    while (node != NULL) {
        // we found our insertion point
        if (winery.name < node.name) {
            // insert our new node
            previous_node.next = winery;
            winery.next = node;
            return;
        }

        // insertion point not found, move to the next node and repeat
        previous_node = node;
        node = node.next;
    }

    // all elements visited, append our new element to the end of the list
    previous_node.next = winery;
    winery.next = NULL;
}

Вышеупомянутый алгоритм вставит ваш новый узел в соответствующее место в списке, если список отсортирован по имени.