Заказ связанного списка по значению -

Question

Пожалуйста, несите меня, я новичок в stackoverflow, поэтому позвольте мне попытаться объяснить мою проблему, если есть какие-то моменты, которые я мог бы улучшить в моем вопросе, пожалуйста, комментарии, и я буду редактировать постановка вопроса

Хорошо, так что я получил себе Связанный список, я хочу заказать его значение в списке, который, случается, цена:

tmpPtr->item->price; 

Проблема, с которой я столкнулась, заключается в переключении позиций, вот код:

struct inventory *sort_list() { 
     struct inventory *tmpPtr = pFirstNode; 
     struct inventory *temp = NULL; 
     struct inventory *tmpNxt = pFirstNode->next; 
     int tmp; 
     while(tmpNxt != NULL){ 
       while(tmpNxt != tmpPtr){ 
         if(tmpNxt->item->price < tmpPtr->item->price){ 
           // if next item price is smaller than current 
           // temp for the next item 
           // heres the problem.... 
           temp = tmpNxt->next; 
           tmpNxt->next = tmpPtr; 
           tmpPtr->next = temp; 
         } 
         else{ 
          // if not any smaller continue  
          tmpPtr = tmpPtr->next; 

         } 
       } 
       tmpPtr = pFirstNode; 
       tmpNxt = tmpNxt->next; 
     } 
     return tmpPtr; 
    } 

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

struct inventory *sort_list() { 
     struct inventory *tmpPtr = pFirstNode; 
     struct inventory *temp = NULL; 
     struct inventory *tmpNxt = pFirstNode->next; 
     while(tmpNxt != NULL){ 
       while(tmpNxt != tmpPtr){ 
         if(tmpNxt->item->price < tmpPtr->item->price){ 
           // if next item price is smaller than current 
           // temp for the next item 
           if(tmpPtr == pFirstNode){ 
            tmpPtr = pFirstNode->next; // tmpPtr is now second node 
            pFirstNode->next = tmpPtr->next; 
            tmpPtr->next = pFirstNode; 
            pFirstNode = tmpPtr; 
           } 

           tmpNxt = tmpPtr->next; 
           tmpPtr->next = tmpNxt->next; 
           tmpNxt->next = tmpPtr; 
           temp->next = tmpNxt; 
         } 

       } 
        temp = tmpPtr; 
     } 
     return tmpPtr; // Place holder 
    } 

Answer 1

Когда вы во внутренней, если условие, то есть следующее состояние:

Node1 -> tmpPtr -> tmpNxt -> Node2

То, что вы хотите достичь, это:

Node1 -> tmpNxt -> tmpPtr -> Node2

Тогда у вас есть следующий код:

1. temp = tmpNxt->next; // делает temp = Node2
2. tmpNxt->next = tmpPtr; // Список изменений в Node1 -> tmpPtr <-> tmpNxt,
3. tmpPtr->next = temp; // изменяет список Node1 ->tmpPtr и tmpNxt -> tmpPtr -> Node2

Итак, как вы можете видеть, вам не хватает ссылки от Node1 -> tmpNext. Вы можете это сделать и проверить свои результаты.

Answer 2

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

1. Глава списка дел и правого угла; своп list_head и list_head->next

   assert(list_head->next); 
   next = list_head->next; 
   list_head->next = next->next; 
   next->next = list_head; 
   list_head = next; 
   

2. Другие случаи & RightArrow; своп cur и cur->next

   assert(prev->next == cur && cur->next); 
   next = cur->next; 
   cur->next = next->next; 
   next->next = cur; 
   prev->next = next; 
   

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

void swap_cur_with_next (node **pnext, node *cur) { 
    assert(*pnext == cur && cur->next); 
    node *next = cur->next; 
    cur->next = next->next; 
    next->next = cur; 
    *pnext = next; 
} 

/* swap list_head with list_head->next */ 
swap_cur_with_next(&list_head, list_head); 

/* swap cur with cur->next */ 
swap_cur_with_next(&prev->next, cur); 

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

void bubble_up(node **pnext, node *cur) { 
    while (cur->next) { 
     if (need_to_swap(cur)) { 
      swap_cur_with_next(pnext, cur); 
     } 
     pnext = &(*pnext)->next; 
     cur = *pnext; 
    } 
} 

node **pnext = &list_head; 
while (*pnext) { 
    bubble_up(pnext, *pnext); 
    pnext = &(*pnext)->next; 
} 

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

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