0
Мне нужно уметь сортировать или вставлять записи в связанный список в алфавитном порядке. Есть ли хороший способ сделать это?Как сортировать связанный список в C?
A
ответ
6
mergesort подходит для сортировки (добавление в уже отсортированный список еще проще, если это то, о чем вы просите).
+0
реализация mergesort, на которую вы ссылаетесь, не очень эффективна и, скорее всего, будет превзойдена рекурсивной версией; еще лучше, используйте подход на основе стека и полностью избавляйтесь от ненужных переходов списков (пример кода: http://pastebin.com/f44b2e39b) – Christoph
2
Вы можете использовать функцию qsort() в libc. По существу, вы создадите массив указателей на свои узлы и напишите функцию сравнения узлов ... Затем вы вызовите qsort() и, наконец, заново создайте свой список в новом порядке, указанном qsort().
0
Вы можете начать с сортировки вручную и получить представление о том, как бы вы сортировали, а затем можете посмотреть, можете ли вы получить это, написанное в psuedo-коде. Оттуда было бы легко преобразовать это в программу.
Чтобы получить помощь в выполнении домашних заданий, это поможет, если вы объясните, как вы хотите сделать сортировку, покажите код, который не работает, и объясните, что он должен делать, и что он делает, а затем вы можете найти помощь более ожидаемый.
Поскольку вы используете связанный список, если вы можете сделать двоичное дерево, тогда вам будет лучше выбрать двоичный тип, esp, если вы можете сортировать при вставке.
1
Для односвязного списка можно реализовать версию quicksort, но обычно это интересно только как головоломка, поскольку mergesort гораздо проще реализовать и работает одинаково хорошо (или лучше) для сортировки связанных списков.
1
Вставка проста, просто перейдите по списку, пока не найдете нужное место, разместите там свой новый узел (предыдущий узел теперь привязывается к новому узлу, новый узел - к узлу, на котором ранее указывался предыдущий узел).
Если у вас уже есть несортированный список, нет эффективного способа его сортировки в списке, что означает, что вам нужно создать вторую коллекцию и отсортировать ее, например. используя двоичное дерево или массив и quicksort.
1
Если у вас есть ваш список, который уже отсортирован и вы хотите вставить весь список предметов, возможно, лучше вставить их в начале и отсортировать впоследствии; если вы хотите вставить всего несколько элементов, возможно, лучше сохранить список отсортированным.
Мои рассуждения:
- вставки в начале представляет собой О (1);
- Вставка, содержащая отсортированный список, - O (N);
- Сортировка списка является O (N журнал N) (в лучшем случае)
Итак, целом много пунктов выше, поэтому, журнал N элементов или более и только несколько позиций составляет менее log N items.
+0
Со связанным списком лучше отсортировать новые элементы, а затем просмотреть оригинал, уже отсортированный перечислите один раз и вставьте новые элементы для исправления положения на пути. – hyde
0
В идеале попробуйте сохранить отсортированный список при вставке новых элементов.
Однако этот вопрос был дан ответ, один так или иначе, на следующие должности StackOverflow:
Inserting a node into a linked list in constant-time?
How do you insert into a sorted linked list?
0
Это не то, что вы должны переоценить (если это не вопрос о домашнем задании ...). Я использую glib, который реализует связанный список и отсортированную вставку, поэтому вам не нужно. Вот appropriate glib documentation.
0
Если ваш список дважды связан, вы можете включить его в двоичное дерево, а затем снова в связанный список.
Для этого не требуется вспомогательное хранение.
Пахнет домашней работой? – dirkgently
Какой холистический нос! – Zed
Единственный вклад dirkgently пришел от его NOSE, когда это должно было быть от его MIND. –