六、查找
1. 静态查找表
静态查找表在查找过程中不改变表中数据——不插不删，故采用顺序存储结构。它适用于数据不变动或不常变动的表。根据静态查找表中数据是否按关键字有序，又可分为顺序查找（无序）和折半查找（有序）。
实现：
//静态查找表类
template<typename D>class SqTable
{//带模板的静态查找表类
protected:
D *elem; //存储基址，0 好单元留空
int length;
public:
SqTable()
{//构造函数
elem = NULL;
length = 0;
}
~SqTable()
{//析构函数
if (elem != NULL)
delete[] elem;
}
void CreateSeqFromFile(char* FileName)
{//由数据文件构造静态查找表
ifstream fin(FileName);
fin >> length;
elem = new D[length + 1];
assert(elem != NULL);
for(int i = 1; i <= length; i++)
InputFromFile(fin, elem[i]);
fin.close();
}
void OutputToFile(char* FileName)const
{//向数据文件输出静态查找表中的所有数据元素
ofstream fout(FileName);
if (elem != NULL)
for(int i = 1; i <= length; i++)
OutputToFile(fout, elem[i]);
fout.close();
}
int SearchSeq(KeyType k)const
{//在无序的静态查找表中顺序查找主关键字等于k的数据元素，若找到返回位置，否则返回0
int i;
elem[0].key = k;
for(i = length; !EQ(k, elem[i].key); i--)
return i; //找不到时，i 为 0
}
int SearchBin(KeyType k)const
{//在有序的静态查找表中折半查找主关键字等于k的数据元素，若找到返回位置，否则返回0
int mid, low = 1, high = length;
while(low <= high)
{
mid = (low + high) / 2;
if EQ(k, elem[mid].key)
return mid;
else if LT(k, elem[mid].key) //小于
high = mid - 1;
else //大于
low = mid + 1;
}
return 0; //表中不存在返回 0
}
bool GetElem(int i, D &e)const
{//用 e 返回静态查找表中第 i 个元素的值
if (i < 1 || i > length)
return false;
e = elem[i];
return true;
}
void Traverse(void(*visit) (D*))const
{//按顺序遍历
for(int i = 1; i <= length; i++)
visit(&elem[i]);
}
};
折半查找在大数据量时很有效。利用 STL 可以对无序数据进行查找。
2. 静态树表
如果有序数据的查找概率已知且差别很大，则折半查找并不是最佳的。这种情况可采用静态树表算法：把有序的静态查找表根据被查找的概率生成一棵二叉树，使查找二叉树每个结点的左右子树的概率尽量相等，以此缩短平均查找长度。这棵二叉树称为 “次优查找树” ，可以证明它不是最优的，但是近似最优。
实现：
//结点数据结构
struct S
{
KeyType key; //关键字
int weight; //权值
int sw; //累计权值
};
//静态树表类
template<typename D>class SOSTree: public SqTable<D>
{//带模板并继承 SqTable<D> 的静态树表类
private:
void FindSW()
{//按照有序表中各数据元素的 weight 域累计权值 sw
if (length > 0)
{
elem[0].sw = 0; //置边界值
cout << endl << "sw = 0 " ;
for(int i = 1; i <= length; i++)
{
elem[i].sw = elem[i - 1].sw + elem[i].weight;
cout << setw(6) << elem[i].sw;
}
}
}
void SecondOptimal(BiTNode<D>* &p, int low, int high)
{//由有序表递归构造次优查找树 p
int j, i = low;
int dw = elem[high].sw + elem[low - 1].sw;
int min = abs(elem[high].sw - elem[low].sw);
for(j = low + 1; j <= length; ++j)
if (abs(dw - elem[j].sw - elem[j-1].sw) < min)
{
i = j;
min = abs(dw - elem[j].sw - elem[j-1].sw);
}
p = new BiTNode<D>;
assert(p != NULL);
p->data = elem[i];
if (i ==low)
p->lchild = NULL;
else
SecondOptimal(p->rchild, low, i-1);
if (i == high)
p->rchild = NULL;
else
SecondOptimal(p->lchild, i+1, high);
}
public:
BiTNode<D> t; //采用二叉链表结构的二叉树 t 作为次优查找树
void CreateSOSTree()
{//由有序表构造次优查找树 t
if (length > 0)
{
FindSW();
SecondOptimal(t.root, 1, length);
}
}
BiTNode<D>* SearchSOSTree(KeyType k)const
{//查找关键字等于 k 的元素，返回其指针，否则返回空指针
BiTNode<D>* p = t.root;
while(p != NULL)
{
if EQ(k, p->data.key)
return p;
else if LT(k, p->data.key)
p = p->lchild;
else
p = p->rchild;
}
return NULL;
}
};
3. 哈希表的插入、删除及查找
哈希表也称 “散列表” ，它是通过计算求得关键字的哈希地址的。如果哈希地址冲突小，在数据量大的情况下查找效率是很高的。
实现：
//开地址法哈希表
const int SUCCESS = 1; //成功
const int UNSUCCESS = 0; //不成功
const int DUPLICATE = -1; //副本
const int N = 4; //hashsize[] 的容量
int hashsize[N] = {11, 19, 37, 73}; //哈希表容量递增表，一个合适的素数序列
template<typename D>class HashTable;
{//带模板的开地址法哈希表类
private:
D *elem; //存储基址
int count, length;
int sizeindex; //当前容量
int *rando; //随机数数组指针
int Hash(KeyType key)
{//一个简单的哈希函数
return key % length;
}
int Hash2(KeyType key)
{//双散列探查法的第二个哈希函数
return key % (length-2);
}
void Random()
{//建立伪随机数组（用于随机探查法）
bool *ra = new bool[length]; //[0] 不用
rando = new int[length]; //[0] 不用
int i;
for(i = 1; i < length; i++) //设置 ra[i] 初值
ra[i] = false; //i 不再随机数数组的标志
// srand(time(0)); //设置随机数种子
for(i = 1; i < length; i++) //依次给 rando[i] 赋随机值
{
do
{
rando[i] = rand() % (length - 1) + 1; //给rando[i]赋值(1 ~ length-1)
if (!ra[rando[i]]) //伪随机数数组中没有此数
ra[rando[i]] = true; //赋值成功
else
rando[i] = 0; //赋值失败
}while(rando[i] == 0); //赋值失败则重新赋值
cout << "rando[" << i << "] = " << rando[i] << endl;
}
delete[] ra;
}
int d(int i, KeyType key)
{//返回第 i 次冲突的增量
switch(type)
{
case 0: return i; //线性探查法（1, 2, 3, ...）
case 1: return ((i+1) / 2) * ((i+1) / 2) * (int)pow(-1, i-1);
//二次探查法（1, -1, 4, -4, 9, -9, ...）
case 2: return i * Hash2(key); //双散列探查法
case 3: return rando[i]; //随机探查法
default: return i; //默认线性探查法
}
}
void collision(KeyType key, int &p, int i)
{//开地址法求得关键字为 key 的第 i 次冲突的地址 p
p = (Hash(key) + d(i, key)) % length; //哈希函数加增量后在求余
if (p < 0) //求余得到负数（二次探查可能会出现）
p = p + length; //保证 p 为非负数
}
void RecreateHashTable()
{//重建哈希表
int i, len = length;
D *p = elem;
sizeindex++; //增大存储容量为下一个序列数
if (sizeindex < N)
{
length = hashsize[sizeindex];
elem = new D[length];
assert(elem != NULL);
for(i = 0; i < length; i++)
elem[i].key = EMPTY; //未填数据的标志
for(i = 0; i < len; i++)
if (p[i].key != EMPTY && p[i].key != TOMB) //在原哈希表[i]有数据
InsertHash(p[i]);
delete[] p;
if (type == 3)
Random();
}
}
public:
int type; //探查法类型
HashTable()
{//构造函数，构造一个空的哈希表
count = 0; //当前数据元素个数
sizeindex = 0; //初始存储容量
length = hashsize[sizeindex]; //当前哈希表容量
elem = new D[length];
assert(elem != NULL);
for(int i = 0; i < length; i++)
elem[i].key = EMPTY;
cout << "请输入探查法类型（0：线性；1：二次；2：双散列；3：随机）：" ;
cin >> type;
if (type == 3)
Random();
else
Random = NULL;
}
~HashTable()
{//析构函数，销毁哈希表
if (elem != NULL)
delete[] elem;
if (type == 3)
delete[] rando;
}
bool SearchHash(KeyType key, int &p, int &c)
{//在开放定址哈希表中查找关键字为key的元素，以 p 指示待查元素位置，并返回SUCCESS
//否则以 p 指示插入位置，并返回UNSUCCESS，用 c 记冲突次数，供建表插入时参考
int c1, tomb = -1;
p = Hash(key);
while(elem[p].key == TOMB || elem[p].key != EMPTY && !EQ(key,elem[p].key))
{//该位置元素已被删除或该位置中填有数据，并且与待查找的关键字不相等
if (elem[p].key == TOMB && tomb == -1)
{
tomb = p;
c1 = c;
}
c++;
if (c <= hashsize[sizeindex] / 2)
collision(key, p, c);
else
break;
}
if EQ(key, elem[p].key)
return true;
else
{
if (tomb != -1)
{
p = tomb;
c = c1;
}
return false;
}
}
int InsertHash(D e)
{//查找不成功时将数据元素 e 插入到开放定址哈希表中，并返回SUCCESS；查找成功时返回
//DUPLICATE，不插入元素；若冲突次数过大，则不插入，并重建哈希表，返回UNSUCCESS
int p, c = 0;
if (SearchHash(e.key, p, c))
return DUPLICATE;
else if (c < hashsize[sizeindex] / 2)
{
elem[p] = e;
++count;
return SUCCESS;
}
else
{
cout << "按哈希地址的顺序遍历重建前的哈希表：" << endl;
TraverseHash(visit);
cout << "重建哈希表" << endl;
RecreateHashTable();
return UNSUCCESS;
}
}
bool DeleteHash(KeyType key, D &e)
{//删除关键字等于key的元素，成功返回true，并将该位置关键字设为TOMB；否则返回false
int p, c;
if (SearchHash(key, p, c))
{
e = elem[p];
elem[p].key = TOMB;
--count;
return true;
}
elem
return false;
}
D GetElem(int i)const
{//返回元素[i]的值
return elem[i];
}
void TraverseHash(void(*visit) (int, D*))const
{//按哈希地址的顺序遍历哈希表
int i;
cout << "哈希地址 0 ~ " << length - 1 << endl;
for(i = 0; i < length; i++)
if (elem[i].key != EMPTY && elem[i].key != TOMB)
visit(i, &elem[i]);
}
};
增加了哈希表的删除算法，就要考虑删除数据给插入和查找带来的影响。设置被删除结点的关键字为 TOMB ，在查找过程中找到 TOMB ，并不说明要查找的关键字不存在，还要继续往后查找，否则不能确定哈希表中不存在该关键字；在插入过程中找到 TOMB ，要记下该位置，以便最后将数据插入到此处。
4. 动态查找表
动态查找表在查找过程中可改变表中数据，即可插入或删除数据，故一般采用链式存储结构。它适用于数据经常变动的表。之前介绍的二叉排序树、平衡二叉树、伸展树及红黑树都是动态查找表。
4.1 B 树
B 树是平衡的 m 路查找树， “B” 表示平衡。
平衡二叉树的查找效率很高，但在数据量非常大，以至于内存空间不够容纳平衡二叉树所有结点的情况下，就得另辟蹊径。B 树是解决这个问题的一种很好的结构。
实现：
//B 树的 3 种模板结构
template<typename D>struct Record
{//B 树数据结构
KeyType key;
D others;
};
template<typename D>struct BTNode
{//B 树结点结构
int keynum; //关键字个数
BTNode<D> *parent;
BTNode<D> *children[m + 1];
KeyType key[m + 1]; //关键字数组，[0] 未用
Record<D> *recptr[m + 1]; //数据指针数组，[0] 未用
};
template<typename D>struct Result
{//查找结构结构
BTNode<D> *pt; //指向关键字所在的 B 树结点
int i; //i = 0 - m - 1 ，在 B 树结点中的关键字序号
bool tag; //true：查找成功；false：查找失败
};
B 树的结点结构和前面介绍过的结点结构有一个重要的区别：它不是把整个数据都存放在结点中，而是仅在结点中存放数据的关键字和数据的地址两项。而在结点查找到关键字后，再根据其地址找到数据。当数据所占的存储空间非常大时，这样做的好处是减小了结点所占用的存储空间，也减小了整个 B 树占用的存储空间。
B 树是 m 路查找树，它的每个结点最多可以有 m-1 个关键字，m 棵子树（m = 2 时即为二叉树，有一个关键字，两颗子树）。子树总比关键字的数量多 1 ,故 key[0] 和 recptr[0] 单元不用，而 children[0] 要用。[m] 单元在正常情况下是不用的，只是在结点的 keynum = m-1 ，又向该结点插入关键字时，临时占用 [m] 单元。然后就要把该结点尽量平均地分裂成两个结点。
实现：
//B 树类
template<typename D>class BTree
{//带模板的 B 树类
private:
BTNode<D> *root;
int s; //s 为分裂结点的中值，与 B 树的阶 m 有关
int MinEmpt; //存 record[] 中具有最小序号的空位置
Record<D> record[N]; //存放数据的数组
void DestroyBTree(BTNode<D>* t)
{//递归销毁 t 为根的 B 树
if (t != NULL)
{
for(int i = 0; i <= t->keynum; i++)
DestroyBTree(t->children[i]);
delete t;
t = NULL;
}
}
int Search(BTNode<D>* p, KeyType k)const
{//在 p->key[1 - keynum] 中顺序查找 i 使得 p->key[i] <= k <= p->key[i + 1]
int i = 0, j;
for(int j = 1; j <= p->keynum; j++)
if LQ(p->key[j], k)
i = j;
else
break;
retun i;
}
void MoveItim2(BTNode<D>* p, int i, BTNode<D>* q, int j)
{//将结点 q[j] 中的 key 和 recptr 2项移动到结点 p[i]
p->key[i] = q->key[j];
p->recptr[i] = q->recptr[j];
}
void MoveItim3(BTNode<D>* p, int i, BTNode<D>* q, int j)
{//将结点 q[j] 中的 3 项移动到结点 p[i]
p->key[i] = q->key[j];
p->recptr[i] = q->recptr[j];
p->children[i] = q->children[j];
}
void Copy(BTNode<D>* q, int i, Record<D>* r)
{//将数据地址 r 和关键字 r->key 分别赋给 q->recptr[i] 和 q->key[i]
q->key[i] = r->key;
q->recptr[i] = r;
}
void Insert(BTNode<D>* q, int i, Record<D>* r, BTNode<D>* ap)
{//将数据地址 r 和 r->key 分别赋给 q->recptr[i+1] 和 q->key[i+1]
//q->children[i+1] 指向结点 *ap
for(int j = q->keynum; j > i; j--) //空出 *q[i+1]
MoveItim3(q, j+1, q, j);
Copy(q, i+1, r);
q->children[i + 1] = ap;
if (ap != NULL)
ap->parent = q;
q->keynum++;
}
void split(BTNode<D>* q, BTNode<D>* &ap)
{//将结点 *q 分裂成两个结点，前一半保留在 *q ，后一半移入新生结点 *ap
ap = new BTNode<D>;
ap->children[0] = q->children[s]; //结点 *q 的后一半移入结点 *ap
if (ap->children[0] != NULL)
ap->children[0]->parent = ap;
for(int i = s+1; i <= m; i++)
{
MoveItim3(ap, i-s, q, i);
if (ap->children[i-s] != NULL)
ap->children[i-s]->parent = ap;
}
ap->keynum = m - s;
q->keynum = s - 1; //前一半保留，修改 *q 的关键字个数
}
void NewRoot(Record<D>* r, BTNode<D>* ap)
{//生成含信息（r, ap）的新的根结点，原根结点 root 和 ap 为其子树指针
BTNode<D> *p = new BTNode<D>;
p->parent = NULL;
p->keynum = 1;
Copy(p, 1, r);
p->children[0] = root;
if (root != NULL)
root->parent = p;
p->children[1] = ap;
if (ap != NULL)
ap->parent = p;
root = p;
}
void InsertBTree(Record<D>* r, BTNode<D>* q, int i)
{//在结点 *q 的 key[i] 与 key[i+1] 之间插入关键字 r->k 和地址 r
//若引起结点过大，则沿双亲链进行必要的结点分裂，使得仍是 B 树
BTNode<D> *ap = NULL;
bool finished = false;
while(q && !finished)
{
Insert(q, i, r, ap);
if (q->keynum) //关键字未超出容量
finished = true;
else //超出容量，分裂结点 *q
{
r = q->recptr[s];
split(q, ap);
q = q->parent;
if (q != NULL)
i = Search(q, r->key);
}
}
if (!finished) //是空树或根结点已分裂为结点 *q 和 *ap
NewRoot(r, ap);
}
bool Move(BTNode<D>* &p)
{//p 指向删除关键字后关键字的个数不足的结点，如果其左或右兄弟有多余的关键字，
//则移给 p ，返回 true ；否则返回 false
BTNode<D> *a, *f = p->parent;
int i, j;
for(i = 0; f->children[i] != p; i++)
if (i > 0 && f->children[i-1]->keynum > (m-1)/2)
{//情况一：有左兄弟且其有多个关键字
a = f->children[i-1];
for(j = p->keynum; j > 0; j--)
MoveItim3(p, j+1, p, j);
p->children[1] = p->children[0];
MoveItim2(p, 1, f, i);
p->keynum++;
MoveItim2(f, i, a, a->keynum);
p->children[0] = a->children[a->keynum];
if (a->children[a->keynum] != NULL)
a->children[a->keynum]->parent = p;
a->keynum--;
return true;
}
else if (i < f->keynum && f->children[i+1]->keynum > (m-1)/2)
{//情况二：有右兄弟且其关键字数目大于 (m-1)/2
a = f->children[i+1];
MoveItim2(p, p->keynum+1, f, i+1);
MoveItim2(f, i+1, a, 1);
p->children[p->keynum + 1] = a->children[0];
p->keynum++;
if (a->children[0] != NULL)
a->children[0]->parent = p;
for(int j = 1; j < a->keynum; j++)
{
MoveItim2(a, j, a, j+1);
a->children[j-1] = a->children[j];
}
a->children[a->keynum - 1] = a->children[a->keynum];
a->keynum--;
return true;
}
return false;
}
BTNode<D>* Merge(BTNode<D>* &p)
{//合并结点
BTNode<D> *b, *f = p->parent;
int i, j;
for(i = 0; f->children[i] != p; i++)
if (i > 0)
{//*p 有左邻兄弟
b = f->children[i-1];
for(j = 0; j <= p->keynum; j++)
if (p->children[j] != NULL)
p->children[j]->parent = b;
++b->keynum;
MoveItim2(b, b->keynum, f, i);
b->children[b->keynum] = p->children[0];
for(j = 1; j <= p->keynum; j++)
{
++b->keynum;
MoveItim3(b, b->keynum, p, j);
}
delete p;
for(j = i+1; j <= f->keynum; j++)
MoveItim3(f, j-1, f, j);
f->keynum--;
}
else
{//这样 b 还是 p 的左兄弟，合并到左兄弟，则是在左兄弟后面加关键字
b = p;
p = f->children[i+1];
for(j = 0; j <= p->keynum; j++)
if (p->children[j] != NULL)
p->children[j]->parent = b;
++b->keynum;
MoveItim2(b, b->keynum, f, i+1);
b->children[b->keynum] = p->children[0];
for(j = 1; j <= p->keynum; j++)
{
++b->keynum;
MoveItim3(b, b->keynum, p ,j);
}
delete p;
for(j = i+1; j < f->keynum; j++)
MoveItim3(f, j, f, j+1);
f->keynum--;
}
return b;
}
public:
BTree()
{//构造函数
root = NULL;
for(int i = 0; i < N; i++)
record[i].key = EMPTY;
MinEmpt = 0;
s = (m+1) / 2;
}
~BTree()
{//析构函数
DestroyBTree(root);
}
BTNode<D>* Root()const
{//返回 B 树根结点指针
return root;
}
void TraverseBTree(BTNode<D>* t, void(*visit) (Record<D>))const
{//按关键字顺序遍历
if (t != NULL)
for(int i = 0; i <= t->keynum; i++)
{
if (i > 0)
visit(*(t->recptr[i]));
if (t->children[i] != NULL)
TraverseBTree(t->children[i], visit);
}
}
Rusult<D> SearchBTree(KeyType k)const
{//在 B 树中查找关键字 k ，返回结果（pt, i, tag），若成功，则 tag = true
//pt 所指结点的第 i 个关键字等于 k ，否则 tag = false，等于 k 的关键字应
//插在 pt 所指结点的第 i 和第 i+1 个关键字之间
BTNode<D> *p = root, *q = NULL;
bool found = false;
int i = 0;
Result<D> r;
while(p != NULL && !found)
{
i = Search(p, k);
if (i > 0 && p->key[i] == k)
found = true;
else
{
q = p;
p = p->children[i];
}
}
if (found)
{
r.pt = p;
r.tag = true;
}
else
{
r.pt = q;
r.tag = false;
}
r.i = i;
return r;
}
bool InsertRecord(Record<D> re)
{//B 树中不存在 re.key ，且 record[] 中有空位置，将数据 re 插入到 record[] 和
//B 树中，成功返回 true，否则返回 false
Result<D> u = SearchBTree(re.key);
if (u.tag)
return false;
if (MinEmpt < N)
{
record[MinEmpt] = re;
InsertBTree(&record[MinEmpt], u.pt, u.i);
for(int k = MinEmpt+1; k < N; k++)
if (record[k].key == EMPTY)
{
MinEmpt = k;
break;
}
if (k == N)
MinEmpt = N;
return true;
}
else
return false;
}
bool DeleteBTree(Record<D> &re, KeyType k)
{//在 B 树中删除关键字为 k 的数据，用 re 返回该数据
int i, j;
BTNode<D> *p, *q;
Result<D> u = SearchBTree(k);
if (u.tag == 0)
return false;
i = u.i;
p = u.pt;
re = *(p->recptr[i]);
p->recptr[i]->key = EMPTY;
if (p->recptr[i] - record < MinEmpt)
MinEmpt = p->recptr[i] - record;
if (p->children[i-1] != NULL)
{
q = p->children[i-1];
while(q->children[q->keynum] != NULL)
q = q->children[q->keynum];
if (q->keynum > (m-1)/2)
{
MoveItim2(p, i, q, q->keynum);
p = q;
i = q->keynum;
}
else
{
q = p->children[i];
while(q->children[0] != NULL)
q = q->children[0];
MoveItim2(p, i, q, 1);
p = q;
i = 0;
}
}
for(j = i+1; j <= p->keynum; j++)
MoveItim2(p, j-1, p, j);
p->keynum--;
while(p->keynum < (m-1)/2 && (p != root))
{
if (!Move(p))
p = Merge(p);
p = p->parent;
}
if (p == root && root->keynum == 0)
{
root = root->children[0];
if (root != NULL)
root->parent = NULL;
delete p;
}
return true;
}
};
与二叉排序树和平衡二叉树一样， B 树中每个关键字是唯一的。所以在插入数据时，先要查找 B 树中是否存在该关键字。如果存在，则不能插入。新数据总是要插在最底层的非叶子结点中，这就保证了所有叶子结点都出现在同一层次。当结点的关键字由于插入超出了最大限度，就要进行分裂。一个结点分成 3 部分，中间关键字并入原来的父结点中，左右两部分分别是中间关键字的左右孩子。如果原来的父结点由于中间关键字的并入超出了最大限度，则继续分裂，直至生成新的根结点。
在 B 树删除关键字，如果在最底层的非叶子结点，则直接删除；否则，类似于二叉排序树和平衡二叉树，删除其前驱或后继关键字（它们一定在最底层的非叶子结点中），再将其前驱或后继关键字和指针复制到删除的关键字和指针处。删除关键字导致结点的关键字少于最低限度，就要进行合并。如果合并导致父结点的关键字少于最低限度，则继续合并，直至根结点中没有关键字。这时删除根结点，B 树的层数减 1 。
B 树是用于处理大数据量的查找操作。其中数据量大到不能存放在内存数组 record[] 中，要将数据存放在外存的多个文件中。甚至内存也放不下整个 B 树，内存中只能存放 B 树的一个结点。所以，B 树的每个结点都存于外存的文件中，结点中的指针内容是文件名和偏移量（数据在文件中的位置）。查找过程是首先将 B 树的根结点文件放入内存中，依据关键字进行查找。随时关闭查找过的 B 树结点，再在内存中随时打开新的 B 树结点，直至查找结束。为了提高速度，就要尽量减少打开、关闭文件的次数，并尽量增大 B 树每个结点可容纳的关键字数，从而降低 B 树的层数。
由于真正的 B 树每个结点的关键字非常多，即 keynum 很大，Search() 函数在 1 ~ keynum 中查找 i 应采用折半查找法而不是顺序查找法。
4.2 键树
键树用于关键字为字符串的情况，故键树也称为 “词典查找树” 。可以用孩子-兄弟二叉链表表示键树，称为 “双链键树” ；也可以用树的多重链表示键树，称为 “Trie 树” 。
推荐阅读：
查找算法（V）键树——双链树和Trie树
键树 B树 B+树（注意，该文中有些许错误，请注意甄别）
