リンクリストの並べ替え

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を実行するアウトstd::vectorを考慮することができる

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

を使用しますほとんどの時間。