Функция установки поиска по таблице из k & r

В разделе 6.6 K&R обсуждается хеш-таблица с использованием связанного списка.

Короче говоря, хеш-таблица - это массив указателей. Указатели указывают на связанный список. Связанный список - это структура, которая выглядит так:

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

Имя хешируется, и этот хеш определяет индекс в таблице. Затем в главе показан код для добавления пары name / defn в таблицу:

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->next = hashtab[hashval];
hashtab[hashval] = np;

Когда я пытаюсь понять это, я все время прихожу к выводу, что список теперь содержит ссылки обратно к себе, и если вы попытаетесь пройти по связанному списку, это будет похоже на собаку, преследующую собственный хвост. Я ожидаю, что код установит np-> рядом с NULL.

Что я не понимаю? Почему этот код работает?

8
задан c_newb 10 August 2011 в 17:00
поделиться