Funkcja instalacji wyszukiwania tabeli z k & r

Question

Sekcja 6.6 K & R omawia tablicę skrótów za pomocą połączonej listy.

W skrócie, tablica skrótów jest tablicą wskaźników. Wskaźniki wskazują na połączoną listę. Połączony lista jest struktura, która wygląda następująco:

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

Nazwa jest mieszany, a to hash określa indeks w tabeli. Rozdział następnie pokazuje kod, aby dodać parę nazwa/defn do stołu:

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; 
} 

Wszystko ma sens, z wyjątkiem następujących 2 linie:

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

Kiedy próbuję zrozumieć to, trzymam nadchodzi do wniosku, że lista jest teraz powiązana z samym sobą, a jeśli spróbujesz przejść na połączoną listę, będzie to wyglądało jak pies goniący swój własny ogon. Oczekuję, że kod ustawi np-> obok NULL.

Czego nie rozumiem? Dlaczego ten kod działa?

Answer 1

Powoduje wstawienie nowej wartości na początku listy.

Więc to idzie od:

hashtab[hashval] --> original_list 

do:

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

do:

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

Złota zasada jest, jeśli kod linkowane lista nie ma sensu, zawsze rysuj schemat!

Answer 2

Ale tutaj nie ma oryginalnej listy. Wstawia węzeł, w którym nie znaleziono żadnego klucza, prawda?

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

Answer 3

Istnieje już węzeł. Ten węzeł ma wartość NULL. Definiując strukturę nlist jako statyczną, automatycznie inicjuje wszystkie wskaźniki elementów do wartości NULL.

Popraw mnie, jeśli się mylę.

Answer 4

hashtab [hashval] to wskaźnik, a nie wartość. Jest to wskaźnik do adresu w pamięci, w którym znajduje się pierwszy element tego konkretnego wiersza tabeli wskaźnika (statyczna struktura nlist * hashtab [HASHSIZE]). np. I np-> dalej są również wskaźniki. Oto, co dzieje się w tych dwóch liniach: Pierwsza linia: Wskaźnik pierwszego elementu w tym wierszu tabeli jest kopiowany do np-> next. np-> next teraz wskazuje na adres w pamięci, gdzie pierwszy element tego wiersza wskazywał. Druga linia: Wskaźnik do adresu w pamięci, w którym znajduje się nowy * np, jest teraz kopiowany do zmiennej zmiennej hastab [hashval]. hastab [hashval] znów staje się wskaźnikiem, gdzie znajduje się pierwszy element tego wiersza tabeli. Tak więc, tak jak napisał Oli, nowe * np jest wstawiane na początku tego konkretnego wiersza w tabeli.