Сортировка связанного списка в порядке возрастания в C

Я работаю над программой для моего курса программирования C, который должен дать нам опыт использования связанных списков. Одна из последних частей задания просит нас взять связанный список и отсортировать его в порядке возрастания, используя функции preend или append, которые мы ранее писали в нашей программе.Сортировка связанного списка в порядке возрастания в C

struct lnode 
{ 
    int datum; 
    struct lnode *next; 
}; 


struct lnode* 
prepend(struct lnode *list, int x) 
{ 
    struct lnode *node = (struct lnode *)malloc(sizeof(struct lnode)); 
    node -> datum = x; 
    node -> next = list; 
    list = node; 
    return list; 
} 

struct lnode* 
append(struct lnode *list, int x) 
{ 
    if(list==NULL){ 
    list = (struct lnode *)malloc(sizeof(struct lnode)); 
    list -> datum = x; 
    list -> next = NULL; 
    }else{ 
    list -> next = append(list->next,x);li 
    } 
    return list; 
}

Выше представлены функции добавления и добавления, которые мы разработали в нашем классе.

Ниже удаления фикцию, что-то мы сделали в классе:

struct lnode* 
delete(struct lnode *list, int x) 
{ 
    struct lnode* tmp; 
    if(list == NULL){ 
    return list; 
    }else if(list-> datum == x){ 
    tmp = list -> next; 
    list -> next = NULL; 
    free(list); 
    list = tmp; 
    return list; 
    }else{ 
    list->next = delete(list->next,x); 
    return list; 
    } 
} 

int 
find_smallest(struct lnode*list) 
{ 
    int smallest; 
    smallest = list->datum; 
    while(list!=NULL){ 
    if(list->datum < smallest){ 
     smallest = list->datum; 
    } 
    list = list->next; 
    } 
    return smallest; 
}

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

Наконец, сортировка, которая приведена ниже, должна создать новый связанный список new_list и должна добавить значение наименьшего целого в списке, а затем удалить это значение из списка, пока в списке больше нет значений.

struct lnode* 
sort(struct lnode *list) 
{ 
    struct lnode *new_list; 
    while(list != NULL && list->next != NULL){ 
    new_list = append(new_list, find_smallest(list)); 
    list = delete(list, find_smallest(list)); 
    } 
    return new_list; 
}

Проблема, с которой я сталкиваюсь, заключается в том, что, похоже, я получаю бесконечный цикл. Я запустил тестовый файл, где я распечатал элементы списка после каждого запуска цикла, где был изначально выбран список 5 4 1 2 3, и что распечатывалось 5 4 2 3 снова и снова, пока я не заставил программу остановиться. Поэтому я считаю, что он работает только один раз?

источник

2015-03-02 Zakery Alexander Fyke

Вы также можете отправить свою функцию 'delete()'? – wimh

Возможно, вам стоит опубликовать обзоры кода или предоставить ссылку с полным кодом на ideone или в любом другом онлайн-редакторе, чтобы другим было легко найти ошибку таким образом. – sashas

@sasha codereview.stackexchange.com предназначен только для кода, который работает по назначению , Это вне темы. Также прочитайте [Будьте осторожны, рекомендуя обзор кода для адеков] (http://meta.stackoverflow.com/questions/253975/be-careful-when-recommending-code-review-to-askers) –

Переменная new_list не инициализируется функцией sort. Функция append затем неправильно добавляет к несуществующему узлу.

Изменить

struct lnode *new_list;

struct lnode *new_list = NULL;

в функции sort.

источник

2015-03-02 21:02:08 alain

Сортировка связанного списка в порядке возрастания в C

ответ

Смежные вопросы