C++ - добавление узла в круговой связанный список с сортировкой

Question

Я должен создать круговой связанный список с функцией, которая добавляет узел на определенной позиции (список должен быть отсортирован в порядке возрастания по значению переменной info). Функция называется add_node. Я подумал, что лучше всего было бы создать два указателя - на заголовок и на следующий узел, а затем использовать цикл while для сравнения следующих элементов с новым узлом, и, если он попадает в нужное место, - поместить его между этими двумя. К сожалению, функция работает только тогда, когда я добавляю элементы с меньшими значениями, чем самые большие в списке. Как должна выглядеть эта функция, чтобы правильно расположить узлы?

Код:

#include<iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

class Circular
    {
        struct node
        {
            int info;
            struct node *next;
        }*head;

    public:
        void create_node(int value);
        void add_node(int value);
        void display_list();
        Circular()
        {
            head = nullptr;
        }
    };

void Circular::create_node(int value)
{
    node *newnode;
    newnode = new node;
    newnode->info = value;
    if (head == nullptr)
    {
        head = newnode;
        newnode->next = head;
    }
    else
    {
        newnode->next = head->next;
        head->next = newnode;
        head = newnode;
    }
}

void Circular::add_node(int value)
{
    if (head == nullptr)
    {
        cout<<"List has not been created yet"<<endl;
        return;
    }

    node *newnode, *ptr2, *ptr1;
    newnode = new node;
    newnode->info = value;
    newnode->next=nullptr;

    ptr1=head;
    ptr2=head->next;
    while(newnode->info > ptr2->info)
    {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;

        if(ptr2 == head) break;
    }
    ptr1->next = newnode;
    newnode->next = ptr2;

}
void Circular::display_list()
{
    node *s;
    if (head == nullptr)
    {
        cout<<"List is empty"<<endl;
        return;
    }
    s = head->next;
    cout<<"Circular Link List: "<<endl;
    while (s != head)
    {
        cout<<s->info<<"->";
        s = s->next;
    }
    cout<<s->info<<endl<<endl;

}

int main()
{
    int choice, element;
    Circular cl;
    while (1)
    {
        cout<<"1.Create node"<<endl;
        cout<<"2.Add node"<<endl;
        cout<<"3.Display"<<endl;
        cout<<"9.Quit"<<endl;
        cout<<"Enter your choice : ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Enter the element: ";
            cin>>element;
            cl.create_node(element);
            cout<<endl;
            break;
        case 2:
            cout<<"Enter the element: ";
            cin>>element;
            cl.add_node(element);
            cout<<endl;
            break;
        case 3:
            cl.display_list();
            break;
        case 9:
            exit(1);
            break;
        default:
            cout<<"Wrong choice"<<endl;
        }
    }
    return 0;
}

Answer 1

Я придумал это:

void Circular::add_node(int value)
{
    node *newnode, *ptr2, *ptr1, *temp;
    newnode = new node;
    newnode->info = value;
    newnode->next=nullptr;

    if (head == nullptr)
    {
        head = newnode;
        newnode->next = head;
    }

    ptr1=head;
    ptr2=head->next;
    while(newnode->info > ptr2->info)
    {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;

        if(ptr2 == head) break;
    }
    if( ptr2->info < newnode->info )
    {
        temp=new node;
        temp->info= ptr2->info;
        temp->next= ptr2->next;
        ptr2->next=newnode;
        newnode->next=temp->next;
        head=newnode;

        delete temp;
    }
    else
    {
        ptr1->next = newnode;
        newnode->next = ptr2;
    }

}

Кажется, это работает. Однако мне интересно, есть ли лучший способ сделать это?

Answer 2

Если узел вставляется перед заголовком, то следующий указатель последнего узла не обновляется, чтобы указывать на новый узел заголовка, и в настоящее время в коде нет простого способа найти последний узел в списке.

Обычный способ справиться с этим также имеет указатель хвоста (указатель на последний узел). Поскольку это круговой список, вам нужно только поддерживать указатель хвоста для класса, так как заголовок может быть создан в любое время, используя head = tail->next;

Необязательно: add_node может быть обновлен для обработки пустого списка, устраняя необходимость в create_node.