Chức năng tra cứu bảng tra cứu từ k & r

Question

Mục 6.6 của K & R thảo luận về bảng băm bằng danh sách được liên kết.

Tóm lại, bảng băm là một mảng con trỏ. Các con trỏ trỏ đến một danh sách liên kết. Danh sách được liên kết là cấu trúc trông giống như:

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

Tên được băm và hàm băm này xác định chỉ mục trong bảng. Chương sau đó cho thấy mã để thêm một cặp tên/defn để bàn:

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

Tất cả những gì có ý nghĩa ngoại trừ 2 dòng sau:

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

Khi tôi cố gắng để hiểu điều này, tôi tiếp tục đến để kết luận rằng danh sách bây giờ liên kết lại cho chính nó và nếu bạn cố gắng đi qua danh sách liên kết nó sẽ giống như một con chó đuổi theo đuôi của nó. Tôi mong đợi mã để thiết lập np-> bên cạnh NULL.

Tôi không hiểu gì? Mã này hoạt động như thế nào?

Answer 1

Kết quả là giá trị mới được chèn vào đầu danh sách.

Vì vậy, nó đi từ:

hashtab[hashval] --> original_list 

tới:

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

tới:

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

Quy tắc vàng là, nếu mã danh sách liên kết không có ý nghĩa, luôn vẽ ra một sơ đồ!

Answer 2

Nhưng không có danh sách gốc ở đây. Nó đang chèn một nút mà không tìm thấy khóa nào, đúng không?

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

Answer 3

Đã có nút ở đó. Nút đó là null. Bằng cách định nghĩa cấu trúc nlist là tĩnh, nó sẽ tự động khởi tạo tất cả các phần tử con trỏ của nó tới NULL.

Sửa lỗi nếu tôi sai.

Answer 4

hashtab [hashval] là một con trỏ, không phải là giá trị. Nó là một con trỏ đến địa chỉ trong bộ nhớ nơi phần tử đầu tiên của hàng cụ thể đó trong bảng con trỏ (cấu trúc tĩnh nlist * hashtab [HASHSIZE]) nằm. np và np-> tiếp theo cũng là con trỏ. Vì vậy, đây là những gì sẽ xảy ra trong hai dòng: Dòng đầu tiên: Con trỏ của phần tử đầu tiên trong hàng của bảng được sao chép vào np-> tiếp theo. np-> next bây giờ trỏ vào địa chỉ trong bộ nhớ, nơi phần tử đầu tiên của hàng đó được sử dụng để trỏ. Dòng thứ hai: Con trỏ trỏ đến địa chỉ trong bộ nhớ nơi hiện tại * np mới được sao chép vào con trỏ biến hastab [hashval]. hastab [hashval] bây giờ một lần nữa trở thành con trỏ tới nơi phần tử đầu tiên của hàng trong bảng đó. Vì vậy, như Oli đã viết, * np mới được chèn vào đầu hàng cụ thể đó trong bảng.