3.3 在C中构造数据结构

现在开始考虑C语言中的实现。首先是定义一些常数：

这个声明定义了前缀中词的个数(NPREF)，散列表数组的大小(NHASH)，生成词数的上界(MAXGEN)。如果NPREF是个编译时的常数而不是运行时的变量，程序里的存储管理将会更简单些。数组的规模设得相当大，因为我们预计程序可能处理很大的输入文件，或许是整本书。选择NHASH=4093，这样，即使输入里有10 000个不同前缀(词对)，平均链长仍然会很短，大约两个到三个前缀。数组越大，链的期望长度越短，查询进行得也越快。实际上，这个程序还仍然是个摆设，因此其性能并不那么关键。另一方面，如果选用的数组太小，程序将无法在合理时间里处理完可能的输入。而如果它太大，又可能无法放进计算机的存储器中。

前缀可以用词的数组的方式存储。散列表的元素用State(状态)数据类型表示，它是前缀与Suffix(后缀)链表的关联：

现在看一看图示，整个数据结构将具有下面的样子：

我们需要一个作用于前缀的散列函数，前缀的形式是字符串数组，显然不难对第2章的字符串散列函数做一点修改，使之可用于字符串的数组。下面的函数对数组里所有字符串的拼接做散列：

再加上对检索函数的简单修改，散列表的实现就完成了：

注意，lookup在建立新状态时并不做输入字符串的拷贝。它只是向sp->pref[]里存入一个指针。这实际上要求调用lookup的程序必须保证这些数据不会被覆盖。例如，如果字符串原来存放在I/O缓冲区里，那么在调用lookup前必须先做一个拷贝。否则后面的输入就会把散列表指针所指的数据覆盖掉。对于跨越某个界面的共享资源，常常需要确定它的拥有者到底是谁。在下一章里有对这个问题的详尽讨论。

作为下一步，我们需要在读入文件的同时构造散列表：

对sprintf的调用有些奇怪，这完全是为了避免fscanf的一个非常烦人的问题，而从其他方面看，使用fscanf都是很合适的。如果以%s作为格式符调用fscanf，那就是要求把文件里的下一个由空白界定的词读入缓冲区。但是，假如在这种情况下没有长度限制，特别长的词就可能导致输入缓冲区溢出，从而酿成大祸。假设缓冲区的长度为100个字节(这远远超出正常文本中可能出现的词的长度)，我们可以用%99s(留一个字节给串的结束符‘\0’)，这是告诉fscanf读到99个字符就结束。这样做有可能把过长的词分成段，虽然是不幸的，但却是安全的。我们可以声明：

但是这里又出现了由一个带随意性的决定(缓冲区大小)导出的两个常数，并要求维护它们之间的关系。这个问题可以一下子解决：只要利用sprintf动态地建立格式串，也就是上面程序里采用的方式。

函数build有两个参数，一个是prefix数组，用于保存前面的NPREF个输入词；另一个是个FILE指针。函数把prefix和读入词的一个拷贝送给add，该函数在散列表里加入一个新项，并更新前缀数组：

对memmove的调用是在数组里做删除的一个惯用法。该操作把前缀数组里从1到NPREF-1的元素向下搬，移到从0到NPREF-2的位置。这也就删去了第一个前缀词，并为新来的一个在后面腾出了位置。

函数addsuffix把一个新后缀加进去：

这里的状态更新操作分由两个函数实现：add完成给有关前缀加入一个后缀的一般性工作，addsuffix做的是由特定实现方式决定的动作，把一个词具体地加进后缀链表里。函数add由build调用，而addsuffix只在add内部使用，因为这里牵涉到的是一个实现细节，这个细节今后也可能会变化。所以，虽然该操作只在这一个地方用，最好也将它建立为一个独立的函数。