参考文献：The C Programming Language
目录
6.6 表查找
为了对结构的更多方面进行深入的讨论，我们来编写一个表查找程序包的核心部分代码
这段代码很典型，可以在宏处理器或编译器的符号表管理例程中找到
例如，考虑 #define 语句，当遇到类似于 #define IN 1 之类的程序行时，就需要把名字 IN 和替换文本 1 存入到某个表中
此后，当名字 IN 出现在某些语句中时，如：statet = IN; 就必须用 1 来替换 IN
以下两个函数用来处理名字和替换文本
install(s, t) 函数将名字 s 和替换文本 t 记录到某个表中，其中 s 和 t 仅仅是字符串
lookup(s) 函数在表中查找 s，若找到，则返回指向该处的指针，若没找到，则返回 NULL
该算法采用的是散列查找方法 —— 将输入的名字转换为一个小的非负整数，该整数随后将作为一个指针数组的下标
数组的每个元素指向某个链表的表头，链表中的各个块用于描述具有该散列值的名字
如果没有名字散列到该值，则数组元素的值为 NULL
链表中的每个块都是一个结构，它包含一个指向名字的指针、一个指向替换文本的指针以及一个指向该链表后继块的指针
如果指向链表后继块的指针为 NULL，则表明链表结束
struct nlist {
struct nlist *next;
char *name;
char *defn;
};
相应的指针数组定义：
#define HASHSIZE 101 static struct nlist *hashtab[HASHSIZE];
散列函数 hash 在 lookup 和 install 函数中都被用到
它通过一个 for 循环进行计算
每次循环中，它将上一次循环中计算得到的结果值经过变换（即乘以 31）后得到的新值同字符串中当前字符的值相加 *s + 31 * hashval
然后将该结果值同数组长度执行取模操作，其结果即是该函数的返回值
这并不是最好的散列函数，但比较简短有效
unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != ' '; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
由于在散列计算时采用的是无符号算术运算，因此保证了散列值非负
散列过程生成了在数组 hashtab 中执行查找的起始下标
如果该字符串可以被查找到，则它一定位于该起始下标指向的链表的某个块中
具体查找过程由 lookup 函数实现
如果 lookup 函数发现表项已存在，则返回指向该表项的指针，否则返回 NULL
struct nlist *lookup(char *s)
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
if (strcmp(s, np->name) == 0)
return np;
return NULL;
}
lookup 函数中的 for 循环是遍历一个链表的标准方法：
for (ptr = head; ptr != NULL; ptr = ptr->next)
...
install 函数借助 lookup 函数判断待加入的名字是否已经存在
如果已存在，则用新的定义取而代之，否则，创建一个新表项
如无足够空间创建新表项，则 install 函数返回 NULL
struct nlist *lookup(char *);
char *strdup(char *);
struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) {
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
free((void *) np->defn);
if ((np->defn = strdup(defn)) == NULL)
return NULL;
return np;
}
参考文献：The C Programming Language
目录
