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

Question

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

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

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

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

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 строк:

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

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

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

Answer 1

В результате новое значение будет вставлено в начало списка.

Итак, откуда:

hashtab[hashval]   -->  original_list

до:

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

до:

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

Золотое правило: если код связанного списка не имеет смысла, всегда рисовать диаграмму!

Answer 2

hashtab [hashval] является указателем, а не значением. Это указатель на адрес в памяти, где находится первый элемент этой конкретной строки в таблице указателей (статическая структура nlist * hashtab [HASHSIZE]) находится. np и np-> next также являются указателями. Вот что происходит в этих двух строках: Первая строка: указатель первого элемента в этой строке таблицы копируется в np-> next. np-> next теперь указывает на адрес в памяти, на который указывал первый элемент этой строки. Вторая строка: указатель на адрес в памяти, где находится новый * np, теперь копируется в указатель переменная hastab [hashval]. hastab [hashval] теперь снова становится указателем на то место, где находится первый элемент этой строки таблицы. Итак, как писал Оли, новый * np вставляется в начало этой конкретной строки в таблице.

Answer 3

Там уже есть узел. Этот узел является нулевым. Определяя структуру nlist как статическую, она автоматически инициирует все свои указатели элементов в NULL.

Поправь меня, если я ошибаюсь.

Answer 4

Но здесь нет оригинального списка. Это вставка узла, где ключ не найден, верно?

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