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

Question

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

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

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

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

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

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

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

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

Answer 2

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

Answer 3

Добавить && std->ID == cur->ID на время цикла

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