代码如下（基本与书中一致）
1 #include <stdio.h>
2 #include <string.h>
3 #include <ctype.h>
4 #include <stdlib.h>
5
6 #define HASHSIZE 101
7
8 struct nlist{
9 struct nlist *next;
10 char *name;
11 char *defn;
12 };
13
14 static struct nlist *hashtab[HASHSIZE];
15 struct nlist *lookup(char *s);
16 struct nlist *install(char *name,char *defn);
17
18 int main(int argc, const char * argv[]) {
19 struct nlist list[] = {
20 {NULL,"abc","123"},
21 {NULL,"bcd","234"},
22 {NULL,"cde","345"},
23 {NULL,"def","567"},
24 };
25 int count = sizeof(list)/sizeof(struct nlist);
26 for (int i = 0; i< count; i++) {
27 struct nlist * p = install(list[i].name, list[i].defn);
28 if (p) {
29 printf("将%s添加到了哈希表里,值为%s
",p->name,p->defn);
30 }
31 }
32 struct nlist *p = lookup("bcd");
33 if (p) {
34 printf("找到key为bcd时对应的值,值为%s
",p->defn);
35 }else{
36 printf("没有找到key为bcd时对应的值
");
37 }
38 return 0;
39 }
40
41 unsigned hash(char *s)
42 {
43 unsigned hashval;
44 for (hashval = 0; *s!=' '; s++) {
45 hashval = *s+31*hashval;
46 }
47 return hashval%HASHSIZE;
48 }
49
50 struct nlist *lookup(char *s)
51 {
52 struct nlist *np;
53 for (np = hashtab[hash(s)]; np!=NULL; np = np->next) {
54 if (strcmp(s, np->name) == 0) {
55 return np;
56 }
57 }
58 return NULL;
59 }
60
61 char *strsave(char *s)
62 {
63 char *p;
64 p = (char*)malloc(strlen(s)+1);
65 if (p!=NULL) {
66 strcpy(p, s);
67 }
68 return p;
69 }
70
71 struct nlist *install(char *name,char *defn)
72 {
73 struct nlist *np;
74 unsigned hashval;
75 if ((np=lookup(name))==NULL) {
76 np = (struct nlist*)malloc(sizeof(struct nlist));
77 if (np == NULL||(np->name = strsave(name))==NULL) {
78 return NULL;
79 }
80 hashval = hash(name);
81 np->next = hashtab[hashval];
82 hashtab[hashval] = np;
83 }else{
84 free((void*)np->defn);
85 }
86 if ((np->defn = strsave(defn))==NULL) {
87 return NULL;
88 }
89 return np;
90 }
先看下输出：
这一节就是讲了表查找，别的没啥想说的，主要看的时候卡在了install方法的这两句代码:
np->next = hashtab[hashval];
hashtab[hashval] = np;
其实这么做的原因是链表是从后向前添加的，当第一次执行install方法时，hashtab[hashval]这个值是NULL，也就是将np->next的值设为了NULL,然后hashtab[hashval] = np 这样，
当第二次执行到np->next = hashtab[hashval]时就是将第一次执行的那个节点添加到了这个节点的next上，换句话说，第一次执行install方法添加的节点是链表的最后一个节点，然后依次向前添加。