простая вставка сортировки по односвязному списку c ++ - PullRequest
Новая
       19

простая вставка сортировки по односвязному списку c ++

0 голосов
/ 25 апреля 2011

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

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, поэтому мне нужно отсортировать его по мере чтения. Узел представляет собой struct btw.Может ли кто-нибудь помочь мне, пожалуйста?

Ответы [ 2 ]

0 голосов
/ 25 апреля 2011

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

template<class T> std::list<T>::iterator insert( std::list<T> &my_list, const T &value )
{
  return my_list.insert( std::lower_bound( my_list.begin(), my_list.begin(), value ), value );
}
0 голосов
/ 25 апреля 2011

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

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

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

...