добавление элементов списка или узлов в связанный список

Question

Я пытаюсь использовать следующий код c ++ для сортировки связанных элементов списка при вставке значения с клавиатуры. Здесь я хочу вставить значения в начале, где-то посередине и в конце в одну функцию вставки, используя while l oop. мое внимание сосредоточено только на том, как вставить и удалить, находя точное положение с помощью логических операций. Не могли бы вы помочь мне в кодировании связанного списка, который можно сортировать при вставке элемента в c ++

#include <iostream>
using namespace std;

struct listItem
    {
    //creating a node
    int data;
    struct listItem *next;
    };
//function declaration
bool Initialize(listItem *head);
char menu();
void insertFirst(listItem *&head, listItem *&temp, int item);
void Insert(listItem *&head, listItem *&temp, int item);
void search(listItem *&head, listItem *&temp);
void deleteItem(listItem *&head, listItem *&temp);
void traverse(listItem *curr);

//function definition
bool Initialize(listItem *head)
    {
    //Initialize head and temp value to null
    listItem *head = NULL;
    listItem *temp = NULL;
    }

char menu()
    {
    //menus 
    char choice;
    cout<<"~~~~~~~~~~~~~~~~~~~~~~~~\n";
    cout<<"        Menu"<<endl;
    cout<<"       ........\n";
    cout<<"1. Add an Item\n";
    cout<<"2. Remove an Item\n";
    cout<<"3. Search an Item\n";
    cout<<"4. Traverse an Item\n";
    cout<<"5. Exit\n";
    cout<<"~~~~~~~~~~~~~~~~~~~~~~~~\n";

    cin>>choice;
    return choice;
    }
//function to insert items 
void Insert(listItem *&head, listItem *&temp, int item)
    {
    // check if the linked list is null
    listItem *curr = new listItem;
    if(head == NULL)
        {
        curr->data = item;
        curr->next =NULL;
        temp = curr;
        head = curr;
        }
        //check if linked list is not empty and chose the right location
        else if(head->data > item)
            {
            curr->data = item;
            curr->next = temp->next;
            temp = curr;
            }
        //check if linked list is not empty and chose the right location
        else if(head->data < item && curr->next != NULL)
            {
            while (curr->data < item)
            curr = curr->next;
            temp->next = curr;
            curr->data = item;
            curr->next = temp;
            temp = curr;
            }
        //check if linked list is not empty and chose the right location
        else if(head->data < item)
            {
            while(head->data < item && curr->next == NULL)
            curr = curr->next;
            curr->data = item;
            curr->next = NULL;
            temp = curr;
            }
        else
            cout<<item<<" is already there!!!\n";
    }

void search(listItem *&head, listItem *&temp)
    {
    cout<<"NO code for searching item"<<endl;
    }
void deleteItem(listItem *&head, listItem *&temp)
    {
    if(Initialize(head))
        cout<<"The list is already Empty\n";
    else if(head == temp)
        {
        delete head;
        head = NULL;
        temp = NULL;
        }
    else
        {
        listItem *curr = new listItem;
        head = head->next;
        delete curr;
        }
    }
void traverse(listItem *curr)
    {
    if(Initialize(curr))
        cout<<"The list is already Empty\n";
    else
        {
        cout<<"The list contains:\n";
        while(curr != NULL)
            {
            cout<<curr->data<<endl;
            curr = curr->next;
            }
        }
    }

int main()
    {

    bool Initialize(head)

    char choice;
    int item;
    do
        {
        choice = menu();
        switch(choice)
            {
            case '1': cout<<"Please enter a number :";
                    cin>>item;
                    Insert(head, temp, item);
                    break;
            case '2': //cout<<"Enter a number to delete :";
                    //cin>>item;
                    deleteItem(head, temp);
                    break;
            case '3': search(head, temp);
                    break; 
            case '4': traverse(head);
                    break;
            default: cout<<"System exit\n";
            }
        }
        while(choice != '5');
        return 0;
    }

Answer 1

Вставка узлов. Сначала ... Код!

#include <iostream>

struct listItem
    {
    //creating a node
    int data;
    struct listItem *next;
    };

//function to insert items
void Insert(listItem *&head, int item)
    {
    listItem **curr = &head; // start at head
    while (*curr != NULL // while there is a node
            && (*curr)->data <= item ) //  and the node goes before the new node
        {
        curr = &(*curr)->next; // get next node
        }
    *curr = new listItem{item, *curr}; // insert the new node
    }

int main()
    {

    listItem * head = NULL; // empty linked list head

    Insert(head, 1); // test insert to empty list
    Insert(head, 0); // insert at head
    Insert(head, 3); // insert at end
    Insert(head, 2); // insert in the middle
    }

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

Код почти не требует пояснений: L oop в списке, пока мы не найдем, куда вставить узел, а затем вставить узел, но есть две маленькие хитрости.

Это узел head и узел next. Оба выполняют одну и ту же работу: укажите на следующий узел в списке. Поскольку у них разные имена, нам нужен другой код для их работы. Но что, если бы мы могли сделать head и все узлы next имели бы одинаковые имена? Тогда они могут иметь точно такой же код. Это работа curr. Теперь не имеет значения, является ли curr head или next. Большая часть кода функции просто ... исчезает. И код, который не существует, не имеет ошибок.

Другая проблема с вставкой в ​​односвязный список, если вы выполняете итерацию на узле, который нужно вставить впереди, вы потеряли отслеживание узла перед ним. , Чтобы сохранить связь, вы должны иметь указатель next предыдущего узла (или head). Вы можете сохранить указатель на предыдущий узел, но это не работает с head, так как нет узла head, поэтому вы испортили первый трюк и получили почти дублированный код. Но если вы абстрагируете узел и сохраняете адрес head или указатель next, у вас есть две части информации в одной: точка вставки и узел после точки вставки. С

listItem **curr;

curr указывает, где мы хотим разместить новый узел, а *curr является узлом после него. Так что

while (*curr != NULL // while there is a node
        && (*curr)->data <= item ) //  and the node goes before the new node
    {
    curr = &(*curr)->next; // get next node
    }

Работает по списку, пока мы не найдем либо последний узел в списке, *curr равен NULL, либо данные в *curr идут после узла, который мы хотим вставить, и затем

*curr = new listItem{item, *curr};

создает новый узел, связанный с последующим узлом, и этот новый узел назначается указателю в точке вставки.

*curr, указатель на следующий элемент в списке установлен на new listItem, как и любое другое использование new.

Твист - это listItem - очень простая структура данных, которая может использовать совокупную инициализацию для инициализации listItem членов. В фигурных скобках содержатся нужные мне значения в новом listItem в том порядке, в котором они объявлены в структуре. Первая переменная-член data установлена ​​на item, а вторая next установлена ​​на текущее значение *curr, следующий элемент в списке.

Для крошечного экземпляра времени у вас будет *curr и next нового listItem, указывающего на тот же listItem, тогда оператор = обновляет *curr, чтобы указывать на вновь созданный listItem.

Нарисуйте его на листе бумаги, и вы увидите, что происходит.