このリンクリストでK＆Rは何をしていましたか？

Question

Cで辞書を使ってhackerRankチャレンジをしていましたが、K & R本からいくつかのコードを抜きました。私はどのように彼らがハッシュテーブル内のリンクリストのバケットをこれで確立しているのかわからないのですか？リンクされたリストの先頭に次のポインタをリンクしているように見えます。彼らは何らかの形でバケツを作っているのですか？ npは文字列（name、defn）と次へのポインタを含む3つのメンバ構造体であり、lookupはnpが辞書に存在するかどうかを調べます。

if ((np = lookup(name)) == NULL){ // file not found 
    np = (struct nlist *) malloc(sizeof(*np)); 
    if (NULL == np || (np->name = strdup(name)) == NULL){ 
     return NULL; 
    } 
    hashval = hash(name); 
    np->next = hashtab[hashval]; // WHAT THE HECK ARE THEY DOING HERE?!?! 
    hashtab[hashval] = np; 
}else{ // already there 
    free((void *)np->defn); 
} 
if((np->defn = strdup(defn)) == NULL){ 
    return NULL; 
} 
return np; 

次のように私はそれを動作させるためにコードを変更し、私は彼らが作るしようとしていたポイントを逃したことをしつこい感じを持っています。

if ((np = lookup(name)) == NULL) { // not found 
    np = (struct nlist *) malloc(sizeof(*np)); 
    if (np == NULL || (np->name = strdup(name)) == NULL) 
     return NULL; 
    hashval = hash(name); 
    phE->next = NULL; //if first entry set next to NULL, MOD HERE 
    tmpNode = hashtab[hashval]; 
    if (tmpNode == NULL){ // EMPTY SPOT IN HASHTABLE 
     hashtab[hashval] = np; 
    }else{       //HASH COLLISION, ADD NODE TO LIST END 
     while (tmpNode->next != NULL){ 
      tmpNode = tmpNode->next; 
     } 
     tmpNode->next = np; 
    } 
}else{ 
    free((void *) np->defn); 
} 
if ((np->defn = strdup(defn)) == NULL){ 
    return NULL; 
} 
return np; 

Answer 1

のは、それが何をするかを確認するには、このコードをトレースしてみましょう：最初は、私たちのハッシュテーブルは、このようなものになります

np->next = hashtab[hashval]; // WHAT THE HECK ARE THEY DOING HERE?!?! 
hashtab[hashval] = np; 

は：

+---+---+---+--- ---+---------+---+---+---+ 
    | | | | ... | hashval | | | | 
    +---+---+---+--- ---+---------+---+---+---+ 
           | 
           | 
           |  +------+ +-----+ 
           +----> | head | -> | ... | 
            +------+ +-----+ 

をここにnpです：

+---+---+---+--- ---+---------+---+---+---+ 
    | | | | ... | hashval | | | | 
    +---+---+---+--- ---+---------+---+---+---+ 
           | 
           | 
       +-----+  |  +------+ +-----+ 
      np -> |  |  +----> | head | -> | ... | 
       +-----+    +------+ +-----+ 

今、私たちはnp->next = hashtab[hashval]と設定します。今、物事は次のようになります。

+---+---+---+--- ---+---------+---+---+---+ 
    | | | | ... | hashval | | | | 
    +---+---+---+--- ---+---------+---+---+---+ 
           | 
           | 
       +-----+  |  +------+ +-----+ 
      np -> |  |------+----> | head | -> | ... | 
       +-----+    +------+ +-----+ 

さて、新しく作成されたセルの次のポインタと同じことにhashtab[hashval]ポイントの両方。 npの観点からは、新しいセルを先行させ、次にすべての既存のセルを使用して形成されるリストを指すようになります。

最後に、我々はこのようになります。これは、hashtab[hashval] = npの操作を行います。これは、リンクリストの先頭に新しい要素をスプライスする

+---+---+---+--- ---+---------+---+---+---+ 
    | | | | ... | hashval | | | | 
    +---+---+---+--- ---+---------+---+---+---+ 
           | 
        +---------+ 
        | 
        v   
       +-----+    +------+ +-----+ 
      np -> |  |-----------> | head | -> | ... | 
       +-----+    +------+ +-----+ 

。

つまり、これはリンクリストポインターの配列を使用することで少し前をついたかなり典型的なリストです。

Answer 2

あなたが見るものは、新しいノードを最初のノードとしてリストに挿入するための基本的なイディオムです。

リスト（空のリストの場合はnullポインタ）と新しいノードへnodeポイントの現在の先頭にheadポイントは、その後、あなたがする必要があるすべては

node->next = head; 
head = node; 

であり、あなたが行われている場合。

これらの2行は、引用したK & Rコードでの表示とまったく同じです。

ご使用のバージョンのコードでは、リストの最後に新しいノードを挿入することをお勧めします。ハッシュセットの基本的な実装では、バケット内の要素の順序は重要ではありません。その理由は、K & Rの実装では、単に新しいノードを各バケットの先頭に挿入するだけです。あなたが見るように、それは非常に簡単で効率的です。

各バケットのノードを到着順に格納する場合は、リストの最後に新しいノードを追加する必要があります。これは実装ではあまり効率的ではありません。あなたがそれを主張するなら、あなたは空のバケツ

struct nlist **pnext = &hashtab[hashval]; 
for (; *pnext != NULL; pnext = &(*pnext)->next); 

*pnext = np; 
np->next = NULL; 

もちろんのための特別なif枝を避けることができ、それを行うための他の慣用的な方法を、使用することができ、すべてこれを行うためのより効率的な方法は、保存することです各バケットの2つのポインタ：リストの最初の要素と最後の要素の両方。