C++リンクされたリストにソートされた順に追加

Question

こんにちは、私は構造体を使用してリンクリストを持っています。今、私は最後にすべての要素を追加するようにしました。しかし、IDに基づいてソート順に各要素を追加したいと思います。構造体には、文字列名とロングIDという2つの要素があります。

node* temp = new node; 
temp->name = nameRead; 
temp->id = idRead; 

//check if first item, if so add as head 
if(head == NULL) 
{ 
    head = temp; 
} 
else 
{ 
    node* temp2 = head; 
    while(temp2->next != NULL) 
    { 
     temp2 = temp2->next; 
    } 
    temp2->next = temp; 
} 

Answer 1

node* temp = new node; 
temp->name = nameRead; 
temp->id = idRead; 

node* temp2 = head; 
node** temp3 = &head; 
while(temp2 != null && temp2->id < temp->id) 
{ 
    temp3 = &temp2->next; 
    temp2 = temp2->next; 
} 
*temp3 = temp; 
temp->next = temp2; 

EDIT：説明： 'TEMP' は行く必要があるだろうどこに 'TEMP3' ポインタポイント。 head2にtemp2を初期化し、リストの最後に到達するまで、またはtemp2のidがtempのidより大きいまでループを維持します。ループの各反復で、temp3とtemp2の両方を進めます。

ループの最後に、 'temp3'はtempが置かれるポインタのアドレスを保持します。したがって、tempを指すように* temp3を代入し、temp-> nextをtemp2に代入します（この時点では、nullになるか、temp-> idよりも大きなidを持つ項目を指します）。

Answer 2

ほとんどのコードを変更するのはかなり簡単です。IDに基づいた比較を追加するだけで、挿入する必要がある新しいIDより大きなIDを持つノードに到達するまでリストを通るだけですまたはリストの最後に到達する）。

これはやや難解なところです：あなたがリストの適切な場所に到達したことを「認識」する前に、既に1つのノードが遠すぎています（単独でリンクされたリストでは、バック）。これを修正する方法は非常に簡単です。新しい（空の）ノードを割り当て、見つけた大きすぎるノードの後に​​挿入します。余りにも大きいノードの内容を挿入したばかりの新しいノードにコピーして、新しいノードのデータを直前の場所にコピーします。

しかし、これはすべて、ほとんどが疑問点です。アイテムのソートされたコレクションが必要な場合、リンクされたリストは通常​​、本当にひどい選択です。宿題のような何かをやっているのではなく、あなたが割り当てられた脳死のことを何でもする必要がある場合は、 [編集：std::multiset、重複が許可されている場合はstd::mapまたはstd::multimap IDに基づいてノードを見つけることができるようにする]、自分で実装することを忘れてしまいます。私の学生のノートPCから撮影

Answer 3

：

void addSorted(node * head, int id){ 
     node* newNode = new node; 
     newNode->number = n; 
     newNode->next = NULL; 

     if(head == NULL || head->number >= id ){ 
      newNode->next = head; 
      head = newNode; 
      return; 
     }else if(head->next != NULL && head->next->id >= id){ 
      node * nextNode = head->next; 
      newNode->next = nextNode; 
      head->next = newNode; 
      return; 
     }else{ 
      node * left; 
      node * right = head; 
      while(right != NULL && right->next->id <= id){ 
       left = right; 
       right = right->next; 
      } 
      left->next=newNode; 
      newNode->next = right; 
     } 
    }