Что ожидается, когда мне говорят "Сортировать односвязный список"

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

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

ИМХО естественный способ сортировки связанного списка - это mergesort. Приведенный ниже фрагмент разбивает список на две части: узлы, которые уже есть, и узлы, которые не находятся. Второй список отсортирован, и два списка объединены. При разделении и объединении используются переменные указатель-указатель.

#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 вы можете найти на странице Википедии здесь .