6.6表查找

翻译的书就一点不好,有时候根本不知道说的是什么.理解不了.

我现在感觉看代码比看中文更容易懂.

nlist结构的成员有链表的下一级地址,定义的名字和替换文本.

首先定义了一个结构指针数组hashtab.有HASHSIZE个元素,每个元素都是一个指向nlist结构的指针.(这里的每个元素都相当于一个链表)

直接看hash(哈希)散列函数.
首先定义的hash函数是无符号类型的.保证了数值为非负.
运算过程也很简单.就是根据输入的字符串字符的数值(根据ASCII码表)进行运算.公式就是那个简单的算数运算,最后对这个值取余.因为它需要在这个表内查找,所以不能超过这个表(上面写的指针表).

然后是lookup函数
函数的参数是一个字符串,目的就是查找这个字符串.返回值是指向nlist结构的指针.
(这里的查找函数需要说一下前面的hash函数,因为hash函数是通过输入的字符串经过公式得到的一个值作为hashtab数组的下标.所以输入的字符如果是相同的或者凑巧碰到一起的就会是在一个下标里,输入的字符与表内有相同的一定会在一个下标内.所以只在同一个下标中的链表中找就可以.)
np得到需要查找链表的起始地址(hashtab是数组,hash函数返回下标,然后将这个下标的地址复制给np).
终止条件是np查到最后.
每执行一次循环体np指向链表的下一级.
循环体就是比较函数了.

然后install函数
首先处理未找到的情况.
给np分配空间.
如果空间不够,返回NULL.
然后处理正常情况.将定义的名字用hash函数处理得到hashtab数组的下标.
这个链表是从下往上链接的.最开始的块是最下面的,这里将当前最上面这个块链接到新建立这个块.(最开始我也不知道这种情况,我也是查了一下才明白.)
然后把结构指针数组的元素换成新建立的这个块.
找到相同的话将之前定义的替换文本释放.
然后将新读入的这个defn替换文本放入np->defn这个结构成员中.