простая сортировка при вставке в односвязный список c

#c #insertion-sort #singly-linked-list

#c #вставка-сортировка #односвязный список

Вопрос:

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

 char c[13];
    r >> c;
    r >> NumberOfInts;

    Node *node = new Node;
    head = node; //start of linked list

    for(int i = 0; i < NumberOfInts; i  ) //this reads from the file and works
    {
        r >> node->data;
        cout << node->data << endl;
        node ->next = new Node; //creates a new node
        node = node->next;

        if(_sortRead) //true
        {
            for(int k = 0; k < i; k  )
            {
                         //insertion sort
            }
        }
    }
  

пока что я считываю его в istream, поэтому мне нужно сортировать его по мере чтения. Узел — это структура, кстати. Кто-нибудь может мне помочь, пожалуйста?

Комментарии:

1. Публикация в основном одного и того же вопроса в немного разных (но все еще непонятных) формах здесь далеко не продвинет вас.

2. я публиковал этот вопрос ранее?

Ответ №1:

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

В настоящее время вы просто добавляете каждый новый узел в конец списка.

Вместо добавления каждого узла в конец списка, вы должны выполнить итерацию по всему списку с начала и найти правильное отсортированное местоположение. Затем вставьте узел в это отсортированное местоположение, а не в конец (я полагаю, что это логика, которую вы пытались реализовать в своем //insertion sort цикле.

Ответ №2:

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

 template<class T> std::list<T>::iterator insert( std::list<T> amp;my_list, const T amp;value )
{
  return my_list.insert( std::lower_bound( my_list.begin(), my_list.begin(), value ), value );
}