#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 );
}