Как вставить значения в один связанный список

Question

Я пытаюсь выучить некоторые основы о связанных списках, поэтому я решил создать некоторый код.К сожалению, я дал конструктору следовать.

До сих пор я создал все методы, которые хотел.К сожалению, похоже, что моя вставка не работает, поэтому я даже не могу проверить, работают ли другие методы.Ofc роль метода вставки заключается в добавлении числа в отсортированный список L. Этот номер должен быть помещен перед первым номером, если он больше или в конце списка, если такого числа нет.

#include <iostream>
#include <cassert>
using namespace std;

struct lnode
{
    int key;
    lnode* next;
    lnode(int k, lnode* n=nullptr):key(k),next(n){}
};

void insert( lnode* &L, int x)
{
    while(L)
    {
        if(x >= L->key)
        {
            L = L->next;
        }
        else
        {
            lnode* temp = L;
            L = new lnode(x, nullptr);
            L->next = temp;
            break;
        }
    }


}

int main()
{
    lnode* t = nullptr;

    insert(t,3);
    insert(t,4);
    insert(t,1);
    insert(t,7);
    insert(t,-4);
    insert(t,9);
    insert(t,2);

        while(L) {
        std::cout << L->key << " ";
    }
}

* 1005Что я ожидаю?Я ожидаю увидеть элементы моего списка.На данный момент ничего нет.Нет ошибок, нет результатов.

Answer 1

Хитрость в написании простого односвязного кода, модифицирующего список, заключается в использовании указателя на текущий узел указателя для указания вашей позиции:

void insert( lnode* &L, int x)
{
    lnode **pos = &L;
    while (*pos && (*pos)->key <= x) {
        pos = &((*pos)->next);
    }
    *pos = new lnode(x,*pos);
}

Поскольку вы, как вы говорите, начинающий, возможно,Вы должны начать с версии для начинающих:

void insert( lnode* &L, int x)
{
    if (!L || L->key > x) {
        //insert at head
        L = new lnode(x, L);
        return;
    }
    lnode *previous=L;
    lnode *current=L->next;
    while(current && current->key <= x) {
        previous = current;
        current = current->next;
    }
    //insert between previous and current
    previous->next = new lnode(x, current);
}

По сравнению с предыдущей вы видите преимущество использования lnode ** для отслеживания позиции вставки при поиске:

• без специальныхкейс для вставки в голову
• без отдельных переменных для предыдущего и следующего

Answer 2

Этот код должен работать. Исправлена ​​ошибка компиляции, а также логика обхода при печати поверх кода Мэтта.

#include <iostream>
#include <cassert>
using namespace std;

struct lnode
{
    int key;
    lnode* next;
    lnode(int k, lnode* n = nullptr) :key(k), next(n) {}
};

void insert(lnode* &L, int x)
{
    lnode **pos = &L;
    while (*pos && (*pos)->key <= x) {
        pos = &((*pos)->next);
    }
    *pos = new lnode(x, *pos);
}

int main()
{
    lnode * t = nullptr;

    insert(t, 3);
    insert(t, 4);
    insert(t, 1);
    insert(t, 7);
    insert(t, -4);
    insert(t, 9);
    insert(t, 2);

    while (t) {
        std::cout << t->key << " ";
        t = t->next;
    }
}