リンクリストcstring挿入ソート

Question

これは、挿入ソートのコードで、ノードのcstringメンバーを使ってソートします。現在のコードは頭の前にのみ挿入されます。コメントにカプセル化されたコードは、私が作業しようとしているソートされた挿入です。私は前身と後継ポインタを使用しなければならないと思っていますが、多分それは私を混乱させる比較です。どんな助けもありがとう。ありがとう！

#include <iostream> 
#include "groclist.h" 

void insert_item(Grocery_Item_Ptr &head, int quantity, const char name[]) 
{ 
bool exists = false; 
bool done = false; 
Grocery_Item_Ptr temp = NULL; 
Grocery_Item_Ptr current = NULL; 
Grocery_Item_Ptr pred = NULL; 
Grocery_Item_Ptr succ = NULL; 

if (head == NULL) { 
    head = new Grocery_Item; 
    head->quantity = quantity; 
    strncpy(head->name, name, MAX_ITEM_NAME_LEN); 
    head->next = NULL; 
    return; 
} 
else { 
    current = head; 
    while (current != NULL) { 
     if (strncmp(current->name, name, MAX_ITEM_NAME_LEN) == 0) { 
      current->quantity += quantity; 
      exists = true; 
     } 
     current = current->next; 
    } 

    if (exists) { 
     current = NULL; 
     return; 
    } 
    else { 
     current = head; 
    } 

    if (!exists) { 
     temp = new Grocery_Item; 
     temp->quantity = quantity; 
     strncpy(temp->name, name, MAX_ITEM_NAME_LEN); 
/*                                 
     while (!done || current != NULL) {                      
      if (strncmp(current->name, name, MAX_ITEM_NAME_LEN) < 0) {                            
       pred = current; 
       succ = current->next; 
       current->next = temp; 
       temp->next = succ; 

       done = true;                         
      }                             
      if (!done) {                          
       current = current->next;                      
      }                             
     }                              
*/ 

     temp->next = head; 
     head = temp; 
     temp = NULL; 
    } 
} 

return; 
} 

Answer 1

私は、あなたの入力の連中に感謝場合にのみ、私はさまざまな方法でそれについて考えたため。しかし、私の結果はまったく異なり、ホワイトボードに本当に感謝しなければなりません。

if (strncmp(name, head->name, MAX_ITEM_NAME_LEN) < 0) { 
    temp->next = head; 
    head = temp; 
    temp = NULL; 
} 
else { 
    pred = head; 
    current = head->next;  
    do { 
     if (strncmp(name, current->name, MAX_ITEM_NAME_LEN) < 0) { 
      pred->next = temp; 
      temp->next = current; 
      done = true; 
     } 
     else if (current->next == NULL) { 
      current->next = temp; 
      done = true; 
     } 
     else { 
      pred = current; 
      current = current->next; 
     } 
     if (done) { 
      pred = NULL; 
      current = NULL; 
     } 
    } while (!done && current != NULL); 
} 

Answer 2

欠けているものは、検索中に前任者への参照を保持することです。これはチェーンを損なわないために必要です。ここで

は動作するはずのドラフトである（現在はテストされていない！）：

while (!done || current != NULL) 
{ 
    //If we found the place to insert 
    if (strncmp(current->name, name, MAX_ITEM_NAME_LEN) < 0) 
    { 
     //If the place to insert was at head 
     if(pred == NULL) 
     { 
      //The new node becomes the head 
      head = temp; 
     } 
     else 
     { 
      //Set the previous nodes next to point at this node. 
      pred->next = temp; 
     } 

     //Always set the node to be inserted's next 
     //pointing to the node we should be inserted before 
     temp->next = current; 
    done = true;   
    }      
    if (!done) 
    { 
     //No match, keep looking but keep an updated pred pointer 
     pred = current; 
     current = current->next; 
    } 
} 

Answer 3

It's just pseudocode, but maybe it helps: 

if(head == NULl) 
    { 
      //make newnode as head 
} 

if(head.name == new name) 
    { 
    //update quantity 
    } 

if(head.name <new name) 
    { 
    //insert newnode before head 
    //make newnode as head 
    } 

if (new name > head.name) 

{ 
    current = head; 
    succ = current.next; 

    while (succ && new name <succ.name) 
     { 
       curent = succ; 
     succ = succ.next 
     } 


    if(succ = NULL) 
     current->next = newnode 
    else 
     if new name = succ->name 
      update quantity 
     else 
      curent->next = newnode 
      newnode->next = succ; 
}