4

K＆Rで説明されているように、単純なハッシュルックアップアルゴリズムのリンクリスト/構造体実装の次のコードを理解しようとしています。

struct nlist *lookup(char *);
char *strdup(char *);
/* install: put (name, defn) in hashtab */
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;

私が理解していないいくつかのこと。この行：

np = (struct nlist *) malloc(sizeof(*np));

ifステートメントが値lookup(name)をnpに割り当てた後に発生します。では、このmalloc割り当ては何をするのでしょうか？値を再初期化しますか？もしそうなら、次の行はどうですか？

if ((np = lookup(name)) == NULL)

mallocが再初期化した場合、常にNULLになりませんか？または、mallocは、以前にnpに割り当てられた値をいじることなく、単にメモリを割り当てますか？その場合、最初のifステートメントですでにnpがNULLであるかどうかを再度チェックするのはなぜですか？

コードに関してはnp->next、私は完全に迷っています。np-> nextがそれ自体を参照しているように見えるのはなぜですか？

lookup（）関数のコードは次のとおりです。

/* lookup: look for s in hashtab */
    struct nlist *lookup(char *s)
    {
    struct nlist *np;
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
            return np; /* found */
    return NULL; /* not found */
}

nlist構造体は次のとおりです。

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

1 に答える 1

12 
if ((np = lookup(name)) == NULL)

2つのことを行います。まず、の結果をに割り当てlookup(name)ますnp。次に、その割り当ての結果をテストして、それがであるかどうかを確認しますNULL。

そのifステートメントが真である場合、それはであるという意味npなNULLので、それらはその値に進みmallocます。

ここで、mallocメモリの割り当てに失敗すると、を返しますNULL。strdup内部でを呼び出すmallocので、次の行は

if (np == NULL || (np->name = strdup(name)) == NULL)

発生したばかりの両方の割り当てが成功したことを確認しています。

まず、ハッシュテーブルは次のようになります。リンクリストへのポインタのテーブルです。配列へのインデックスはハッシュ値です。

ここに画像の説明を入力してください

新しいエントリを追加すると、次のようになります。

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

hashtab[hashval]はすでに同じハッシュを持つエントリのリストの始まりです。NULLの可能性があります。このコードは、リストの先頭に新しいエントリを追加します。したがって、新しいエントリのnextポインタを既存のリストにポイントし、ハッシュテーブルを新しいエントリをポイントするように設定して、新しいエントリが最初になるようにします。

ここに画像の説明を入力してください

それらはノードをリストの先頭に追加するので、挿入はO（1）操作です。

于 2013-03-10T05:10:42.180 に答える