Función de instalación de búsqueda de tabla de k & r

Question

Sección 6.6 de K & R analiza una tabla hash utilizando una lista vinculada.

En resumen, una tabla hash es una matriz de punteros. Los punteros apuntan a una lista vinculada. La lista enlazada es una estructura que se parece a:

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

es ordenado el nombre, y este hash determina el índice en la tabla. Luego, el capítulo muestra el código para añadir un par nombre/defn a la mesa:

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

Todo tiene sentido, excepto para los siguientes 2 líneas:

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

Cuando trato de entender esto, me siguen llegando a la conclusión de que la lista ahora se vincula a sí misma y si tratas de atravesar la lista enlazada será como un perro persiguiendo su propia cola. Esperaría que el código establezca np-> al lado de NULL.

¿Qué no entiendo? ¿Cómo es que funciona este código?

Answer 1

Resulta en el nuevo valor insertado al principio de la lista.

Así que va desde:

hashtab[hashval] --> original_list 

a:

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

a:

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

La regla de oro es, si el código de lista enlazada no tiene sentido, ¡Dibuja siempre un diagrama!

Answer 2

Pero no hay lista original aquí. Está insertando un nodo donde no se encuentra ninguna clave, ¿verdad?

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

Answer 3

Ya hay un nodo allí. Ese nodo es nulo. Al definir la estructura nlist como estática, inicia automáticamente todos los punteros a NULL.

Corrígeme si me equivoco.

Answer 4

hashtab [hashval] es un puntero, no un valor. Es un puntero a la dirección en la memoria donde reside el primer elemento de esa fila en particular en la tabla de punteros (static structlist * hashtab [HASHSIZE]). np y np-> next también son punteros. Así que aquí está lo que sucede en estas dos líneas: Primera línea: el puntero del primer elemento en esa fila de la tabla se copia en np-> siguiente. np-> siguiente ahora apunta a la dirección en la memoria donde el primer elemento de esa fila solía apuntar. Segunda línea: el puntero a la dirección en la memoria donde reside el nuevo * np ahora se copia en el puntero variable hastab [hashval]. hastab [hashval] ahora una vez más se convierte en el puntero al lugar donde reside el primer elemento de esa fila de la tabla. Entonces, tal como escribió Oli, el nuevo * np se inserta al comienzo de esa fila en particular en la tabla.