Я новичок в программировании. Списки. Вопрос сортировки. Как сортировать его пузырьком, если нужен предыдущий элемент?
1 ответ
Откуда такие извращения берутся ?
Если брать примитивные сортировки, то линейный односвязный список естественно сортировать вставками.
Исключаете элементы из исходного и вставляете их в новый (строящийся, отсортированый). Потом возвращаете новый список или меняете указатель в голове списка (зависит от используемой Вами структуры списков).
-
В дополнение к предудущему посту, могу сказать, что для сортировки пузырьком (если захочется поизвращаться) нужен как минимум двусвязный список. Но, действительно, правильным будет метод вставок. +1 20 мар 2012 в 23:54
-
1@nikita_sergeevich, если пузырьковая сортировка, это перестановка неупорядоченной пары (честно,не помню точно, что такое "пузырек"), то для односвязного тоже реализуется. Просто сравниваете p->data с p->next->data и обмениваете указатели (естественно для первого элемента списка особый случай), ну и делаете p = p->next (переход к следующему в списке во внутреннем цикле сортировки), только если обмена не было. Дело в коэффициенте при O(n^2).– avp21 мар 2012 в 7:54
-
чтобы поменять значения местами, как я понимаю для "первого" поля нужно иметь указатель на "второй" чтобы сравнить и обменять, а "второй" должен иметь указатель на предыдущий "первый", чтобы заменить. А это уже двусвязный. Хотя, могу ошибаться. 21 мар 2012 в 23:45
-
1Не совсем так. В структуре, описывающей элемент списка достаточно указателя на следующий. Просто для p->data, p->data->next забыл написать о еще одном важном указателе (назовем pp). Это указатель на предыдущий элемент в списке (p на текущий). В начале просмотра, устанавливаете его в NULL. Перед p=p->next пишите pp = p. При обмене ими надо аккуратно манипулировать, особенно в начале и конце списка. Кстати, та же идея используется для удаления элемента из односвязного списка.– avp22 мар 2012 в 8:53