各スロットにソートされたリンクされたリストを持つハッシュマップを作成する

Question

私は、各スロットに連鎖と単独リンクリストでハッシュマップを作成しました。私が挿入を使用すると、リンクされたリストの後ろに新しいノードが送られますが、新しいノードを挿入すると、各スロットをソートする必要があります。次のinsert機能を編集するにはどうしたらよいですか？後で各スロットを並べ替えるのではなく、正しい位置に挿入するようにしてください。

void hashInsert(int key){ 
    int hashLoc = h(key); 
    HashNode* prev = NULL; 
    HashNode* entry = hTable[hashLoc]; 
    while(entry != NULL){ 
     prev = entry; 
     entry = entry->next; 
    } 
    if(entry == NULL){ 
     entry = new HashNode(key); 
     if(prev == NULL){ 
      hTable[hashLoc] = entry; 
     } 
     else{ 

      prev->next = entry; 
     } 
    } 
    else{ 
     entry->value = key; 
    } 
} 

Answer 1

各スロットの並べ替えを維持する主な方法は、正しい位置に挿入することです。この場合、最初の大きな値の直前に挿入します。

コードでは、次のwhileループを使用してリストの最後に挿入を強制します。

while(entry != NULL){ 
    prev = entry; 
    entry = entry->next; 
} 

代わりに、我々は代わりに、単にリストの最後（エントリー== NULL）を探しているのは、我々はまた、より大きな値を探すように、この条件を変更したいです。

while(entry != NULL && entry->value < value_to_insert){ 
    prev = entry; 
    entry = entry->next; 
} 

ループ用に修正これは正しく右prevとentryの間、あなたの新しいエントリを置くための正しい場所を正確に特定します。

この場合のもう1つの問題は、挿入ロジックに2つのバグがあることです。

これはあなたの挿入ロジックです：

if(entry == NULL){ 
    entry = new HashNode(key); 
    if(prev == NULL){ 
     hTable[hashLoc] = entry; 
    } 
    else{ 

     prev->next = entry; 
    } 
} 
else{ 
    entry->value = key; 
} 

主な問題は、ロジックは、if文if(entry==NULL)の他の枝には無効であるということです。

この場合、新しいエントリを作成し、prevポインタを修正し、次のポインタを修正する必要があります。

実際には、次にこれを書き換えるために簡単になります：

new_entry = new HashNode(key); 
new_entry->value = value_to_insert; 
if(prev == NULL){ 
    hTable[hashLoc] = new_entry; 
} 
else{ 
    prev->next = new_entry; 
} 

new_entry->next = entry;