k＆rからのテーブル検索インストール機能

Question

K &のセクション6.6では、リンクリストを使用したハッシュテーブルについて説明しています。

つまり、ハッシュテーブルはポインタの配列です。ポインタは、リンクされたリストを指します。リンクされたリストは次のような構造体です。

struct nlist {    /* table entry: */ 
    struct nlist *next; /* next entry in chain */ 
    char *name;   /* defined name */ 
    char *defn;   /* replacement text */ 
}; 

名前はハッシュされており、このハッシュはテーブルのインデックスを決定します。私はこれを理解しようとすると、私は来続ける

np->next = hashtab[hashval]; 
hashtab[hashval] = np; 

：

struct nlist *install(char *name, char *defn) { 
    struct nlist *np; 
    unsigned hashval; 
    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); 
     np->next = hashtab[hashval]; 
     hashtab[hashval] = np; 
    } else /* already there */ 
     free((void *) np->defn); /*free previous defn */ 
    if ((np->defn = strdup(defn)) == NULL) 
     return NULL; 
    return np; 
} 

すべては、以下の2行を除き、理にかなって：章では、テーブルに名前/ DEFNのペアを追加するためのコードを示します結論として、リストは現在自身にリンクしており、リンクされたリストをトラバースしようとすると、それは自分の尾を追う犬のようになります。私はコードがNULLの隣にnp->を設定すると期待します。

私は何を理解していませんか？どのようにこのコードが動作するのですか？

Answer 1

この結果、新しい値がリストの先頭に挿入されます。

hashtab[hashval] --> original_list 

へ：

hashtab[hashval] --> original_list 
np->next   --> original_list 

へ：

だから、それから行く

hashtab[hashval] --> *np 
     np->next --> original_list 

黄金律で、リンクされたリストのコードが意味をなさない場合、常に図を描く！

Answer 2

ただし、元のリストはありません。キーが見つからないノードを挿入しています。

if ((np = lookup(name)) == NULL) { /* not found */ 

Answer 3

すでにノードがあります。そのノードはnullです。 nlist構造体をstaticとして定義すると、NULLへのすべての要素ポインタが自動的に開始されます。

私が間違っている場合は私を修正してください。

Answer 4

hashtab [hashval]は値ではなくポインタです。 ポインタテーブル （静的struct nlist * hashtab [HASHSIZE]）のその特定の行の最初の要素が存在するメモリ内のアドレスへのポインタです。 npとnp-> nextもポインタです。 ここでは、これらの2行で何が起こるのですか： 最初の行：テーブルのその行の最初の要素のポインタがnp-> nextにコピーされます。 np-> nextは、その行の最初の要素が指し示していたメモリ内のアドレスを指します。 2行目：新しい* npが存在するメモリ内のアドレスへのポインタが、ポインタ 変数hastab [hashval]にコピーされるようになりました。 hastab [hashval]は、再びそのテーブル行の最初の要素が存在する場所へのポインタになります。 したがって、Oliが書いたのと同じように、新しい* npはテーブルのその特定の行の先頭に挿入されます。