Сортировка связанных списков

Question

Я почти закончил с программой, но мне нужно отсортировать связанный список в порядке возрастания, и я стараюсь часами и не могу понять это, но остальная часть программы работает. Предполагается генерировать 6 случайных чисел и хранить их в связанном списке и выводить их каждый раз до тех пор, пока он не достигнет 6 чисел, а затем он остановится, а затем удалит каждый элемент до тех пор, пока все они не будут удалены. Но, по-видимому, нужно сортировать числа по мере их вывода. Он хранит узлы в функции push_sorted, поэтому я бы предположил, что это функция сортировки, но я снова не могу понять, как сортировать связанный список. В любом случае спасибо за любую помощь, и вот вся моя программа ...

#include <iostream> 
#include <ctime> 
#include <cstdlib> 
#include "SortedLinkedList.h" 
#include <algorithm> 
#include <list> 
#include <array> 

using namespace std; 

struct node 
{ 
    int data; 
    node *next; 
}; 

node *head = NULL; 

void push_sorted(int value) 
{ 
    node *newNode = new node; 
    newNode->data = value; 
    newNode->next = NULL; 

    if(head == NULL) 
    { 
     head = newNode; 
    } 
    else 
    { 
     node *newNode_2 = head; 
     while(newNode_2->next != NULL) 
     { 
      newNode_2 = newNode_2-> next; 
     } 
     newNode_2->next = newNode; 
    } 
} 

void pop_front() 
{ 
    node *temp; 
    temp = head; 
    head = head->next; 
    free(temp); 
} 

void pop_back(int pos) 
{ 
    node *temp =head; 
    struct node *t = NULL; 
    if(head->next==NULL) 
    { 
    free(head); 
    head=NULL; 
    } 
    else 
    { 
    while(temp->next != NULL) 
    { 
     t=temp; 
     temp=temp->next; 
    } 
    free(t->next); 
    t->next=NULL; 
    }  


} 



bool isEmpty(int count) 
{ 
    if(count == 0) 
    { 
     return false; 
    } 

    else 
    { 
     return true; 
    } 

} 

void print() 
{ 
    node* current = head; 
    while(current != NULL) 
    { 
     cout << current-> data << " "; 
     current = current->next; 
    } 
    cout << endl; 
} 
int main() 
{ 
    int pos = 4; 
    int count = 6; 
    const int NUMS = 6;  //insert elements into the sorted linked list in an ascending order 
    const int RANGE = 21; //each element is in the range [-10, 10] 
    /*SortedLinkedList mylist;*/ 
    srand(time(0)); 
    for (int i = 0; i < NUMS; i++) 
    { 
     int data = (rand() % RANGE) - 10; 
     cout << "Adding " << data << " to the sorted linked list: " << endl; 
     push_sorted(data); 
     print(); 
    } 

    while ((isEmpty(count) == true)) 
    { 
     cout << "Removing from front..." << endl; 
     pop_front(); 
     print(); 
     count --; 
     /*if (count == 1) 
     { 
      break; 
     }*/ 
     cout << "Removing from back..." << endl; 
     pop_back(pos); 
     print(); 
     count --; 
     pos-= 2; 
    } 
    system("pause"); 
    return 0; 
} 

Answer 1

Вы должны использовать std::list как это было предложено. Но если предположить, что вам нужно это по другим причинам, вы можете изменить функцию для сравнения значений и поменять местами узлы следующим образом:

void push_sorted(int value) 
{ 
    node *n = new node; 
    n->data = value; 
    n->next = NULL; 
    if (!head) 
    { 
     head = n; 
    } 
    else 
    { 
     node *cursor = head; 
     if (head->data > value) 
     { 
      node *temp = head; 
      head = n; 
      n->next = temp; 
      return; 
     } 
     while (cursor->next) 
     { 
      if (cursor->next->data > value) 
      { 
       node *temp = cursor->next; 
       cursor->next = n; 
       n->next = temp; 
       return; 
      } 
      cursor = cursor->next; 
     } 
     cursor->next = n; 
    } 
} 

Или просто использовать

std::list<int> lst; 
lst.push_back(data); 
lst.sort(); 

Вы можете также рассмотреть вопрос std::vector который из выполняет std::list большую часть времени.