Сортировка с использованием связанного списка

Question

У меня есть два поля, а именно ID и имя.Вставив узел в связанный список, я бы хотел отсортировать его по идентификатору в порядке убывания.Предполагая, что возможно, что разные люди могут иметь один и тот же идентификатор.Например,

1001 CHARICE -> 1001 JUSTIN -> 1001 ANNA -> 1000 CHYNA -> 888 MIKEY -> NULL

Окончательный список должен выглядеть следующим образом:

1001 ANNA -> 1001 CHARICE -> 1001 JUSTINE -> 1000 CHYNA -> 888 MIKEY -> NULL

Я сортирую имена с одинаковым идентификатором в порядке возрастания, а идентификаторы сортируются в порядке убыванияВот мой код:

NODE* insert_std(NODE *head, NODE* std){
     NODE *prev, *cur;
     if(head==NULL) return std; 
     cur = head;
     while (cur != NULL &&  std->ID < cur->ID){  
         prev = cur;
         cur = cur->next;
     }
     if(std->ID == cur->ID){
         while (cur != NULL &&  strcmp(std->name, cur->name)>=0){
             prev = cur;
             cur = cur->next;
         }
     }    
     if (head==cur){
         if(std->ID >= head->ID) {
         std->next = head;
         head = std;
         }
     } else {
         std->next = cur;
         prev->next = std;
     }
     return head;
}

Но это не сортируется так, как я хочу.Что я делаю не так?

Answer 1

Просто замените ваши сравнения на значения ID и примите во внимание и имя (например, используя strcmp), когда значения ID совпадают.Самый простой способ - написать отдельную функцию для сравнения двух записей, которая выполняет эту работу.

Answer 2

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

Это равносильно изменению std->ID <= cur->ID и std->ID > head->ID. На вашем месте я написал бы вспомогательную функцию, которая бы взяла два указателя на NODE (назовите их A и B), сравните их описанным выше способом и верните true, если узел A предшествует узлу B. Функция в вашем insert_std тогда тривиальна.

Answer 3

Добавить && std->ID == cur->ID к циклу while

 while (cur != NULL &&  std->ID == cur->ID && strcmp(std->name, cur->name)>=0)