Я пытаюсь сортировать один связанный список

Question

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

Иногда кажется, что он работает нормально, например: я ввел 4, 6, 7, 2, и он действительно показал себя в отсортированном списке. но после ввода 3 он не отобразил 3 в списке.

Вот мой код:

if(head == NULL)  
{ 
    head = info;  
    last = info; 
    info->next = NULL; 
} 
else 
{ 
    if(info->number > last->number) 
    { 
     last->next = info; 
     last = info;    
     info->next = NULL; 
    } 
    else if (info->number < head->number) 
    {   
     info -> next = head;  
     head = info;    
    } 

    prev = head; 

    for(temp = head-> next ; temp!= NULL; temp = temp->next) 
    { 
     prev = prev->next; 
     if(info->number >temp->number) 
     { 
      temp->next = info;       
     } 
     else 
     { 
      temp-> prev = info; 
      info = prev; 
     } 
    } 
} 

Answer 1

Вы не сортируете «одиночный связанный список». Вы пытаетесь сохранить список, отсортированный по мере ввода пользователем. Кроме того, список, над которым вы работаете, не похож ни на один связанный список. Он имеет указатели «next» и «prev», поэтому он должен быть «двойным связанным списком».

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

Answer 2

if(head == NULL)  
{ 
    head = info;  
    last = info; 

    info->next = NULL; 
} 
else 
{ 
    if(info->number >= last->number) <-- CHANGE:: > changed to >= to take care of same number (as earlier stored number) being entered 
    { 
     last->next = info; 
     last = info;    
     info->next = NULL; 
     return; <-- CHANGE:return added here, no need to proceed further 
    } 
    else if (info->number <= head->number) <-- CHANGE:: < changed to <= to take care of same number (as earlier stored number) being entered 
    {   
     info -> next = head;  
     head = info; 
     return; <-- CHANGE:return added here, no need to proceed further 
    } 

    prev = head; 

    for(temp = head->next ; temp != NULL; temp = temp->next) 
    { 
     if(temp->number >= info->number) <-- CHANGE: modified code when insertion happens between head and last 
     { 
      prev->next = info; 
      info->next = temp; 
      break; 
     } 

     prev = temp; 
    } 
} 

В исходном коде, окончательное еще случай:

else 
{ 
    temp-> prev = info; 
    info = prev; 
} 

Этот код не делает никакого смысла, так как вы упомянули односвязанны список, но здесь вы использовали «temp-> prev».

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

Answer 3

if(head == NULL)  
{ 
    head = info;  
    last = info; 
    info->next = NULL; 
    last=info; 
} 
else 
{ 
    if(info->number>head->number){ 
     info->next=head; 
     head = info;  
    } 
    else{ 
     tmp=prev=head; 
     while(tmp && (info->number < tmp->number) ) 
     { 
      prev=tmp; 
      tmp=tmp->next; 
     } 

     info->next=prev->next; 
     prev->next=info; 

     if(!tmp) last=info; 

    } 
} 

Answer 4

Рассмотрим построение его как массив, сортировка массива и использование его оттуда.

Answer 5

Вы используете сортировку пузырьков, которая не является самым быстрым способом сортировки.

К счастью, ваша библиотека C, скорее всего, обеспечит эффективный алгоритм быстрой сортировки (qsort). Чтобы использовать эту функцию связанного списка:

• Выделяют (с использованием malloc) и массив указателей размера, равное числу элементов в связанном списке.
• Traverse связанного списка, что делает каждую запись точки массива до элемента в связанном списке
• Сортировать указатели с использованием qsort и определенное сравнения рутинной
• перебирать массив, установка предыдущего и следующий указатель каждого элемента (т. е. полностью игнорировать предыдущие связи).
• Освобождает массив

Это почти всегда быстрее, что замена фактического элемента next и prev указателей вокруг, и меньше ошибок.

Если вы настаиваете на использовании сортировки пузырьков, вы можете просто заменить третий шаг своей сортировкой пузырьков.