建立索引和查找--二叉树

这两天写了一个索引的建立与搜索过程，目前是对13M的数据进行了测试，整个过程只用了不到6s，这个数字是值得庆祝的。算是一个比较快的算法了。在此要感谢wang sir和xu sir的支持。对这两位表示由衷的感谢。

整个算法过程对文件中每个字符进行了一次遍历，对每次得到的字符进行建立二叉树（综合考虑，二叉树还是最好的一个数据结构），并且统计总共有多少个字符和每个字符出现的次数，存放在一个数组中，还对每次出现的不重复字符进行编号（一个字对于一个号，该号是从小往大排的）。这是第一步的遍历：建立二叉树。

在第一步结束后就得到了两个变量，一个存放出现次数的数组，另一个是总共有多少字符。有了出现次数，就可以计算出将来存放每个字符所用的空间大小（出现一次就申请一个int的大小共32位，这时候前24位存放所在行号，后8位存放对于行首的偏移量），有了需要空间大小就可以申请一段连续的内存，专门存放每个字符的所在位置。对这片连续内存的存放算法是：根据每个字的编号和第一步统计的数组能得到对于编号相对于首地址的偏移量，把该字的位置连续写到首地址+偏移量所指向的内存区。一个字出现多次，就按照出现的顺序依次写入。最终我们只需要对这片内存区进行查找就能得到所检索字的位置（行号和偏移号）。由于有点牵涉到公司机密问题，我只是把部分代码粘出来，以供大家批评、指正、交流、学习。有问题可以私信。。。。。

看代码：

这是程序需要的数据结构