今晚在公众号上看到一条题：
看到题目第一时间想到树，而且是多叉树。为什么呢？
首先说说为何不选择顺序表，我们来试想想，如果500万个单词放在顺序表上，不加索引而且乱序，那么搜索一个关键词为开头的单词的时间按最差算要500万次比较，简直疯狂。但是如果先按首字母a~z排序一次，并记住每个首字母的第一个单词在表格第几个位置，效率又要好些，如果第二个字母再排序一些再做索引，又好些。可是这样插入单词的效率就太低了，所以顺序表无论如何并不是一个好的选择。
然后我们换个想法，我们可以先把单词按照字母为单位分割，然后第1个字母在树的第一层搜索，若不存在该字母则添加该字母为本层的兄弟节点，存在该字母就选择第2个字母，跳到下一层的首节点，再逐个搜索，若不存在该字母则添加该字母为本层的兄弟节点，存在该字母就选择第3个字母，跳到下一层的首节点，再逐个搜索……，如此类推，直到搜索或添加最后一个字母时，把该节点标记为“单词最后字母”，即完成添加一个单词的任务。然后每个单词均进行一次这个行为，就完成了单词树，不仅不需要存储单词中同样的部分，而且在搜索时，最差情况仅 =（该语言字母数 * 单词长度），例如搜索一个10个字母构成的英文单词，最差只需要搜索26*10=260次，无论增加多少个单词也只需要这么多次，效率比搜索一个乱序表高好几个数量级了，也使得单词表的排序变得十分简单。
具体C语言实现代码如下：
字母单元定义：
typedef struct vocalUnit VocalUnit;
struct vocalUnit {
char isWord; //如果深搜的时候发现是单词的时候根据这个标记进行显示
char c; //同一层的邻居字母
struct vocalUnit *nextLayerHead; //以本节点开始的下一层的首节点
struct vocalUnit *nextBrother; //保存的字母
};
全部实现代码：
#include "stdio.h"
#include "stdlib.h"
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
/**************ChenJieZhu created at 20181030 18:00***********************/
typedef struct vocalUnit VocalUnit;
struct vocalUnit {
char isWord; //如果深搜的时候发现是单词的时候根据这个标记进行显示
char c; //同一层的邻居字母
struct vocalUnit *nextLayerHead; //以本节点开始的下一层的首节点
struct vocalUnit *nextBrother; //保存的字母
};
/**初始化节点**/
void initDictTrees(VocalUnit* unit) {
unit->isWord = 0;
unit->nextBrother = NULL;
unit->nextLayerHead = NULL;
unit->c = NULL;
}
/**添加单词到多叉树**/
void addWord(VocalUnit* vHead, char* word){
int len = strlen(word);
int i;
VocalUnit* cursor = vHead;
for(i = 0; i < len; i++) {
char c = word[i];
char nextBrotherisEmpty = 0;
while(cursor != NULL) {
if(cursor->c == NULL) { //如果结点内容为空，即为以下情况之一：1、该字母与该层所有兄弟都对比过之后发现不存在，需要在本层添加 2、在该分支中该字母到此层未出现过，需要保存
VocalUnit* newLayerHead = (VocalUnit*) malloc(sizeof(VocalUnit));
initDictTrees(newLayerHead);
cursor->c = c;
if(i == len - 1) {
cursor->isWord = 1;
} else { //创建下一层为新字母保存做准备
cursor->nextLayerHead = newLayerHead;
cursor = cursor->nextLayerHead;
}
break;
} else {
if(cursor->c == c) {
if(i == len - 1) { //如果最后一个字母与该层已存在的其中一个字母一样，标记为到此为一个单词
cursor->isWord = 1;
}
else if(cursor->nextLayerHead == NULL) { //如果需要遍历下一层，可是不存在下一层，就新建一层
VocalUnit* newLayerHead = (VocalUnit*) malloc(sizeof(VocalUnit));
initDictTrees(newLayerHead);
cursor->nextLayerHead = newLayerHead;
}
cursor = cursor->nextLayerHead; //预备遍历下一个字母，对应就是多叉树的下一层
break;
} else { //如果该字母与该层当前兄弟不一致，移动到下一个兄弟进行比较
if(cursor->nextBrother == NULL) { //如果没有下一个兄弟就创建下一个兄弟
VocalUnit* nextBrother = (VocalUnit*) malloc(sizeof(VocalUnit));
initDictTrees(nextBrother);
cursor->nextBrother = nextBrother;
}
cursor = cursor->nextBrother;
}
}
}
}
}
int layer = 0;
char content[100];
/**读取树中所有的单词**/
void readVolcalProc(VocalUnit* cursor){
if(cursor != NULL) {
layer++;
//printf("layer:%d:%c\n", layer, cursor->c);
content[layer - 1] = cursor->c;
if(cursor->isWord) {
printf("word:%s\n", content);
}
readVolcalProc(cursor->nextLayerHead);
content[layer - 1] = 0;
layer--;
readVolcalProc(cursor->nextBrother);
}
}
void readVolcal(VocalUnit* cursor) {
layer = 0;
memset(content, 0, 100);
readVolcalProc(cursor);
}
/**搜索某开头的所有内容**/
void searchProc(VocalUnit* cursor, char* key, int keyLen) {
while(cursor != NULL) {
if(key[layer] != cursor->c) {
cursor = cursor->nextBrother;
} else {
content[layer++] = cursor->c;
if(layer == keyLen && cursor->isWord) { //如果被搜索词发现本身也是一个单词，也显示一下
if(cursor->isWord) {
printf("word:%s\n", content);
}
}
cursor = cursor->nextLayerHead;
if(layer == keyLen) {
break;
}
}
}
readVolcalProc(cursor);
}
/**搜索某关键字开头的条目**/
void search(VocalUnit* cursor, char* key, int keyLen) {
layer = 0;
memset(content, 0, 100);
searchProc(cursor, key, keyLen);
}
int main(){
int in = open("dict.txt", O_RDONLY,S_IRUSR);
int i = 0;
char p;
char input[100];
int flag;
//init///
VocalUnit *vHead = (VocalUnit*) malloc(sizeof(VocalUnit));
char *str = malloc(100);
memset(str, 0, 100);
initDictTrees(vHead);
while((flag = read(in, &p, 1)) > 0) {
if(p == '\n') {
addWord(vHead, str);
memset(str, 0, 100);
i = 0;
}
else{
str[i] = p;
i++;
}
}
/**someTest:**/
addWord(vHead, "a");
addWord(vHead, "apple");
addWord(vHead, "app");
addWord(vHead, "banana");
addWord(vHead, "ash");
addWord(vHead, "123456789");
printf("Loading finished.\n");
//readVolcal(vHead);
do{
printf("\nplease input what you want to search:");
scanf("%s", input);
search(vHead, input, strlen(input));
} while(strcmp(input, "!") > 0);
return 0;
}
具体运行效果：
