Восходящий вид односвязного списка
Я работаю над этой программой, которая сортирует список. но проблема в том, что элемент в голове будет проигнорирован во втором рекурсивном вызове. Эс:
input: 7->1->8->0->NULL OUTPUT: 1->0->7->8->NULL.
почему 1 игнорируется?
это структура узла:
struct nodo {
int elem;
struct nodo *next;
};
и функция:
struct nodo *ordinaLista(struct nodo *head) {
//in ordine crescente
if (!head)
return NULL;
else {
if ((head->next) && (head->elem >= head->next->elem)) {
int tmp = head->elem;
head->elem = head->next->elem;
head->next->elem = tmp;
}
//printList(head);
head->next = ordinaLista(head->next);
head->next = ordinaLista(head->next);
}
return head;
}
Ответы 3
Ваша функция неправильно сортирует список: вы сортируете только первые 2 элемента и переходите к сортировке остальной части списка.
Для упрощенной реализации с экспоненциальной сложностью O(n!), вы должны сначала отсортировать остальную часть списка, затем потенциально поменять местами 2 начальных элемента, гарантируя, что первый элемент будет наименьшим, наконец, если элементы были заменены местами, повторно отсортировать остальную часть списка.
Вот модифицированная версия:
struct nodo *ordinaLista(struct nodo *head) {
//in ordine crescente
if (head && head->next) {
head->next = ordinaLista(head->next);
if (head->elem > head->next->elem) {
int tmp = head->elem;
head->elem = head->next->elem;
head->next->elem = tmp;
head->next = ordinaLista(head->next);
}
}
return head;
}
Это имеет экспоненциальную сложность.
@interjay: действительно так... ответ исправлен.
Это лучшее решение без изменения моей первоначальной «логики». Оно работает. Спасибо
Смоделируем процедуру сортировки:
7->1->8->0->НОЛЬ
1->7->8->0->НОЛЬ
На самом деле достаточно смоделировать первый шаг. Как видите, узел «1» переставляется на первую позицию, а затем программа продолжает выполняться в обратном порядке, а «1» игнорируется. На самом деле ваш алгоритм сортировки неверен. Ваш алгоритм сортировки на самом деле является «пузырем». Для завершения сортировки требуется многократное барботирование. Для конкретного алгоритма вы можете обратиться к «сортировке пузырьком».
Проблема с вашей функцией заключается в том, что вы на самом деле не выполняете сортировку. Ваша функция просто меняет значение целого числа на следующее, если оно больше.
Таким образом, на одной итерации вам гарантируется, что последний элемент в списке будет самым большим.
Почему вы вызываете функцию рекурсивно дважды? Это действие кажется мне странным.
PS: избегайте комментариев к коду на итальянском, английский всегда предпочтительнее
Это недопустимый алгоритм сортировки. После выполнения этого элемента head может быть только один из двух первых элементов в исходном списке. Даже если бы это был правильный алгоритм, он работает за экспоненциальное время. Переключитесь на известный алгоритм, такой как сортировка слиянием, сортировка выбором и т. д.