Сортировка связанного списка (таинственный сегмент)

Question

В настоящее время я работаю над сортировкой связанного списка в C как домашнее задание.Я не ищу фрагмент кода в качестве ответа, так как я понимаю ценность выяснения этого самостоятельно.Я получаю segfault, используя функцию ниже, и я был бы очень признателен, если бы кто-нибудь хотя бы сказал мне, почему.Лучшее, что я мог понять, - это сбой при достижении следующей строки:

if (head-> value> head-> next-> value) {

РЕДАКТИРОВАТЬ: Изменил эту строку на if (head-> next! = NULL && head-> value> head-> next-> value) {и больше не получаю ошибки сегмента.Тем не менее, мой указатель выходной головы дает мне последний узел в связанном списке.HALP.

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

struct node *sort_list(struct node *head) {
    bool swapped ;
    struct node * tmp , * orig ;
    orig = head ;

    if ( head == NULL || head->next == NULL ) return head ;
    else {
            do {
                    swapped = false ;
                    if ( head->next != NULL && head->value > head->next->value ) {
                            tmp = head ;
                            head = head->next ;
                            tmp->next = head->next ;
                            head->next = tmp ;

                            swapped = true ;
                    }
                    head = head->next ;
            } while ( swapped == true && head != NULL ) ;
    }
    return orig ;
}

Answer 1

Когда вы входите в цикл do, вы знаете, что head->next - это не NULL, а как насчет следующего раунда или когда вы доберетесь до финального предмета?Последний элемент не имеет ничего после него.

РЕДАКТИРОВАТЬ:

Предположим, у вас есть 3 элемента в последовательности, A, B и C, где head == B,и вы хотите поменять местами элементы B и C.Вы не учитываете, что вам также нужно сделать A->next = C.

Answer 2

Как только head становится последним элементом в связанном списке, вы получаете свой segfault.
Я не хочу писать код, так как это домашнее задание, но добавлю условие, чтобы проверить, является ли head-> next нулевым. Если это так, вам нужно вернуться к началу списка.

Для сортировки по пузырькам потребуется несколько проходов через связанный список. Если вы инициализируете свой связанный список со значениями 5,4,3,2,1, а также печатающей головкой и печатающими темпом и головкой. Вы, вероятно, увидите 5,4 5,3 5,2 5,1 segfault

Кроме того, ваша формула сортировки выглядит немного не так Если у вас есть данные, такие как 2,3,1. Ваш код будет видеть 2 и 3, swapped станет true и функция вернет true.

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

do{
    for 1 pass through linked list (this can be a for or while loop)
        swap if necessary; set swapped to true
}while(swapped is true)

Надеюсь, это поможет.

Редактировать

После

tmp = head;

Добавить

head = head->next  
if(tmp == orig)  
    orig = head;  

Вам нужно сохранить указатель на голове.
В случае 5,4,3,6. Это будет отсортировано следующим образом
4,5,3,6
4,3,5,6
3,4,5,6
Но ваш указатель orig никогда не обновлялся, поэтому ваш вывод будет усечен до 4,5,6.

Answer 3

head->next вероятно ноль.Вы проверяете, находится ли он перед циклом, но условие while не выполняет эту проверку.

И вы должны найти учебник gdb, это невероятно мощный инструмент для подобных вещей.

Answer 4

Это скорее всего вызвано разыменованием нулевого указателя.

Вы не проверяете, является ли head->next NULL в вашем цикле. После 1-й итерации head становится head->next, и ваше условие (if (head->value > head->next->value)) разыменовывается head для доступа к value и next->value.