Сортировка одиночно кругового связанного списка

Question

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

void editList(node *head, int value, int newValue) 
{ 
    node *traverser = head; 
    do { 
     traverser = traverser -> next; 
    }while(traverser -> data != value); 

    traverser -> data = newValue; 

    node *index; 
    node *selection; 
    node *temp = new node; 

    for(index = head; index -> next != head; index = index -> next) { 

     for(selection = head; selection -> next != head; selection = selection -> next) { 
      if(index -> data > selection -> data) { 
       temp -> data = index-> data; 
       index -> data = selection -> data; 
       selection -> data = temp -> data; 

      } 
     }//End of outer loop 

    }//End of sorting 

    return; 
}//End of editList() 

Answer 1

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

Два вложенных цикла присутствуют, но выполняют независимые функции.

Шаг 1 - выполнение истинного вложенного цикла путем включения условия от первого ко второму циклу.

Для сортировки всего списка выбор начинается со следующего узла индекса .

for(index = head; index -> next != head; index = index -> next) { 
    // start the selection from the index->next 
    for(selection = index->next; selection -> next != head; selection = selection -> next) { 
     if(index -> data > selection -> data) { 
      temp -> data = index-> data; 
      index -> data = selection -> data; 
      selection -> data = temp -> data; 

     } 
    }//End of outer loop 
}//End of sorting 

бонус 1 - потому, что замена выполняется только на уровне data, вместо того чтобы использовать временный узел, просто использовать целое число.

// use just an integer 
int temp; 
... 
temp = index-> data; 
index -> data = selection -> data; 
selection -> data = temp; 

Вместо того, чтобы:

// allocated but never freed 
node *temp = new node; 
... 
temp -> data = index-> data; 
index -> data = selection -> data; 
selection -> data = temp -> data; 

Bonus 2 - для первого поиска, чтобы локализовать часть узла, имеющего int value быть заменены, почему не используют ту же самую структуру петли, чтобы предотвратить тем не завершение цикла, если ни один узел не имеет искомого значения.

node *traverser; 
// a ending loop to search a value into a circular-list 
for(traverser = head; traverser->next != head; traverser = traverser -> next) { 
    if (traverser -> data == value) { 
     traverser -> data = newValue; 
     break; 
    } 
} 

Вместо

node *traverser = head; 
do { 
    traverser = traverser -> next; 
}while(traverser -> data != value); 

traverser -> data = newValue;