Что ожидается, когда мне скажут «Сортировка отдельно связанного списка»

Question

Это может быть для педантичных целей, но не для домашних заданий. У меня вопрос ниже: «Сортировка односвязного списка» (любой вид списка). Предположим, что для этих вопросов мы хотим сортировать в порядке возрастания значений в каждом узле.

Означает ли этот вопрос, что я просто сортирую список, заменяя значения каждого узла в списке, чтобы значения были в некотором порядке (восходящий/нисходящий). Здесь исходные значения узлов (перед сортировкой) будут изменены, чтобы отразить отсортированный список. Здесь возвращается прежний указатель головы, но теперь он имеет самый маленький элемент в нем, который может отличаться от предыдущего элемента.

Как это C код, который я ниже (ниже код не может скомпилировать как есть, но у меня он работает отлично Опубликовано здесь в качестве иллюстрации, чтобы очистить мою точку зрения.):

struct lnk_lst 
{ 
    int val; 
    struct lnk_lst *next; 
}; 

main() 
{ 

    //Assume curr is the head node of the singly linked list created with some values 
curr = llist_bubble_sort(curr); 

} 

struct lnk_lst* llist_bubble_sort(struct lnk_lst *lst) 
{ 
    int i,n=0,tmpint; 
    struct lnk_lst *tmp=lst,*tmp2=lst; 

    while(tmp->next) 
    { 
     lst = tmp2; 
     while(lst->next) 
     { 
      if(lst->val > lst->next->val) 
      { 
       tmpint = lst->val; 
       lst->val = lst->next->val; 
       lst->next->val = tmpint; 
      } 
      lst = lst->next; 
     } 
     tmp = tmp->next; 
    } 

    return tmp2; 

} 

ИЛИ

Ожидается ли, что указатель на узел с наименьшим элементом (в порядке возрастания) в исходном порядке перемещается как новый головной узел, тогда узел, имеющий следующий наименьший элемент, связан с головным узлом и так далее, список переупорядочивается полностью, и теперь возвращенный головной узел не тот же указатель, что и раньше.

Если интерпретация сортировки списка - это вторая, то я должен увидеть, как сделать эту идею в коде.

Answer 1

Вся идея связанных списков заключается в том, что ссылки могут быть изменены без ущерба для содержимого. Изменение указателя иногда включает в себя создание указателя на переменную указателя. Кроме того: если вы только меняете содержимое, вы можете просто оставить указатели -> Следующие указатели, вместо этого использовать массив и поменять содержимое массива.

IMHO natural способ сортировки связанного списка объединяется. Фрагмент ниже разбивает список на две части: узлы, которые уже на месте, а те, которые не являются. Второй список сортируется, и два списка объединяются. Оба слияния & слияния включают в себя некоторые переменные-указатели на указатели.

#include <stdio.h> 
#include <string.h> 

struct llist { 
     struct llist *next; 
     char *payload; 
     }; 

int llist_cmp(struct llist *l, struct llist *r); 
struct llist * llist_split(struct llist **hnd 
         , int (*cmp)(struct llist *l, struct llist *r)); 
struct llist * llist_merge(struct llist *one, struct llist *two 
         , int (*cmp)(struct llist *l, struct llist *r)); 
struct llist * llist_sort(struct llist *ptr 
         , int (*cmp)(struct llist *l, struct llist *r)); 

struct llist * llist_split(struct llist **hnd, int (*cmp)(struct llist *l, struct llist *r)) 
{ 
struct llist *this, *save, **tail; 

for (save=NULL, tail = &save; this = *hnd;) { 
     if (! this->next) break; 
     if (cmp(this, this->next) <= 0) { hnd = &this->next; continue; } 
     *tail = this->next; 
     this->next = this->next->next; 
     tail = &(*tail)->next; 
     *tail = NULL; 
     } 
return save; 
} 

struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r)) 
{ 
struct llist *result, **tail; 

for (result=NULL, tail = &result; one && two; tail = &(*tail)->next) { 
     if (cmp(one,two) <=0) { *tail = one; one=one->next; } 
     else { *tail = two; two=two->next; } 
     } 
*tail = one ? one: two; 
return result; 
} 

struct llist * llist_sort(struct llist *ptr, int (*cmp)(struct llist *l, struct llist *r)) 
{ 
struct llist *save; 

    save=llist_split(&ptr, cmp); 
    if (!save) return ptr; 

    save = llist_sort(save, cmp); 

    return llist_merge(ptr, save, cmp); 
} 

int llist_cmp(struct llist *l, struct llist *r) 
    { 
    if (!l) return 1; 
    if (!r) return -1; 
    return strcmp(l->payload,r->payload); 
    } 


struct llist lists[] = 
{{ lists+1, "one" } 
,{ lists+2, "two" } 
,{ lists+3, "three" } 
,{ lists+4, "four" } 
,{ lists+5, "five" } 
,{ lists+6, "six" } 
,{ lists+7, "seven" } 
,{ lists+8, "eight" } 
,{ NULL, "nine" } 
     }; 

int main() 
{ 
struct llist *root,*tmp; 

root = lists; 

fprintf(stdout, "## %s\n", "initial:"); 
for (tmp=root; tmp; tmp=tmp->next) { 
     fprintf(stdout, "%s\n", tmp->payload); 
     } 

fprintf(stdout, "## %s\n", "sorting..."); 
root = llist_sort(root, llist_cmp); 

for (tmp=root; tmp; tmp=tmp->next) { 
     fprintf(stdout, "%s\n", tmp->payload); 
     } 
fprintf(stdout, "## %s\n", "done."); 

return 0; 
} 

РЕЗУЛЬТАТ:

## initial: 
one 
two 
three 
four 
five 
six 
seven 
eight 
nine 
## sorting... 
eight 
five 
four 
nine 
one 
seven 
six 
three 
two 
## done. 

Answer 2

Правильный способ сортировки связанного списка является вторым. Это также имеет смысл, потому что часто вы хотите сортировать объекты по некоторому атрибуту, сохраняя при этом свои другие значения атрибутов. В этом случае первый подход мало помогает.

Идея похожа на традиционные подходы к сортировке. Например, вы можете использовать сортировку вставки, итерируя ее через элементы, а затем вставляя следующий элемент в нужную позицию в правильно отсортированном связанном списке до этого элемента. Подробный код на C вы можете увидеть на странице Википедии here.