Выбор сортировки со связанным списком

Question

У меня есть следующая структура данных:

struct scoreentry_node {
    struct scoreentry_node *next;
    int score;
    char name[1];    
};  
typedef struct scoreentry_node *score_entry;

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

Я попробовал ваши предложения:

void selectionsort(score_entry *a) {
    for (; *a != NULL; *a = (*a)->next) {
        score_entry *minafteri = a;
        // find position of minimal element
        for (score_entry j = (*a)->next; j != NULL; j = j->next) {
            if (strcmp(j->name, (*minafteri)->name) == -1) {
                *minafteri = j;
            }
        }
        // swap minimal element to front
        score_entry tmp = *a;
        a = minafteri;
        *minafteri = tmp;
    }
}

Я тестирую приведенный выше код со следующим:

score_entry x = add(8, "bob", (add( 8 , "jill", (add (2, "alfred", NULL)))));
iprint("",x);
selectionsort(&x);
iprint("", x);
clear(x); //Frees the whole list

iprint() печатает поля оценки и имени в структуре.Моя функция добавления выглядит следующим образом:

score_entry add(int in, char *n, score_entry en) {      
   score_entry r = malloc(sizeof(struct scoreentry_node) + strlen(n));
   r->score = in;
   strcpy(r->name, n);
   r->next = en;  
   return r;   
}

Я получаю кучу ошибок, и мой второй отпечаток не печатает отсортированный список, он ничего не печатает.Что я делаю не так, и что я могу сделать, чтобы это исправить?

Answer 1

Помимо передачи указателя по адресу (см. Комментарии ниже), вам также необходимо исправить способ, которым вы тоже меняете элементы

void selectionsort(score_entry *a) {
  for (; *a != NULL; *a = (*a)->next) 
  {
     score_entry *minafteri = a;
     // find position of minimal element
     for (score_entry j = (*a)->next; j != NULL; j = j->next) {
       if (strcmp(j->name, (*minafteri)->name) == -1) {
         *minafteri = j;
       }
      }
     // swap minimal element to front
     score_entry tmp = *a;
     a = minafteri; // put the minimal node to current position
     tmp->next = (*a)->next ; //fix the links
     (*minafteri)->next=tmp; //fix the links
  }
}

Answer 2

Вот Java-реализация сортировки выбора в связанном списке:

• Сложность времени: O (n ^ 2)
• Сложность пространства: O (1) - сортировка выбора по алгоритму сортировки по месту

class Solution 
{
    public ListNode selectionSortList(ListNode head)
    {
        if(head != null)
        {
            swap(head, findMinimumNode(head));
            selectionSortList(head.next);
        }
        return head;
    }

    private void swap(ListNode x, ListNode y)
    {
        if(x != y)
        {
            int temp = x.val;
            x.val = y.val;
            y.val = temp;    
        }
    }

    private ListNode findMinimumNode(ListNode head)
    {
        if(head.next == null)
            return head;

        ListNode minimumNode = head;

        for(ListNode current = head.next; current != null; current = current.next)
        {
            if(minimumNode.val > current.val)
                minimumNode = current;
        }
        return minimumNode;
    }
}

Answer 3

В вашем коде есть несколько проблем:

• if (strcmp(j->name, (*minafteri)->name) == -1) { неверно: strcmp() не обязательно возвращает -1, когда первая строка меньше второй, она может вернуть любой минусзначение.
• Неправильный способ настройки ссылок для перемещения нижней записи: вы не можете обновить ссылку с предыдущего узла на тот, который вы переместили в начало.Список поврежден.

Вот улучшенная версия:

void selectionsort(score_entry *a) {
    for (; *a != NULL; a = &(*a)->next) {
        // find position of minimal element
        score_entry *least = a;
        for (score_entry *b = &(*a)->next; *b != NULL; b = &(*b)->next) {
            if (strcmp((*b)->name, (*least)->name) < 0) {
                least = b;
            }
        }
        if (least != a) {
            // swap minimal element to front
            score_entry n = *least;
            *least = n->next;   /* unlink node */
            n->next = *a;       /* insert node at start */
            *a = n;
        }
    }
}

Answer 4

Этот код отвратителен! Вы не только не предоставили нам все необходимое для воспроизведения вашей проблемы (мы не можем это скомпилировать!), Но вы скрыли абстракции указателей за typedef (для нас это тоже кошмар). Вообще говоря, нельзя даже использовать связанные списки в C больше не говоря уже о sort их ...

Тем не менее, здесь есть два ответа.

---

*minafteri = j; найденный в вашем цикле find фактически изменяет ваш список! Почему ваш find цикл изменяет ваш список?

Ответ: не должно! Вместо этого, назначив minafteri = &j->next, вы не будете изменять список с помощью цикла поиска ...

---

Кроме того, вы можете выполнить обмен внутри этого цикла.

*minafteri = j; потребуется поменять местами следующее в следующем порядке:

• (*minafteri)->next и j->next
• *minafteri и j

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

---

Следующая попытка замены элементов выглядит следующим образом:

score_entry *minafteri = a; // half of assigning `a` to `a`
/* SNIP!
 * Nothing assigns to `minafteri`  in this snippet.
 * To assign to `minafteri` write something like `minafteri = fubar;` */
score_entry tmp = *a;       // half of assigning `*a` to `*a`
a = minafteri;              // rest of assigning `a` to `a`
*minafteri = tmp;           // rest of assigning `*a` to `*a`

Это действительно просто присвоение *a *a и a a ... Как вы думаете, вам нужно это сделать?

Я бы подумал, что вы заметите , что , когда создавали свой MCVE ... Ох, подождите минуту! Позор вам!

---

Сосредоточьтесь на том, чтобы поменять местами два узла в списке как меньшую задачу. Как только вы это сделаете, подумайте над выполнением этой задачи.

Answer 5

Вы должны передать аргумент selectionsort по ссылке :

void selectionsort(score_entry *a) {
    for (; *a != NULL; *a = (*a)->next) 
    {
      score_entry *minafteri = a;
      // find position of minimal element
      for (score_entry j = (*a)->next; j != NULL; j = j->next) {
      if (strcmp(j->name, (*minafteri)->name) == -1) {
         *minafteri = j;
      }
    }
     // swap minimal element to front
      score_entry tmp = *a;
      a = minafteri;
      *minafteri = tmp;
  }
}