一字典树
字典树，又称单词查找树，Trie树，是一种树形结构，哈希表的一个变种
二.性质
根节点不包含字符，除根节点以外的每一个节点都只包含一个字符；
从根节点到某一节点，路径上经过的字符串连接起来，为该节点对应的字符串；
每个节点的所有子节点包含的字符都不相同。
三.优势： 利用字符串的公共前缀，节约存储空间和查找时间。时间复杂度O(n)
四.适用于：快速字符串插入，查找字符串，在大量字符串的查找中，体现其高效性。
查找的时间复杂度只和树的深度有关，跟表中有多少个单词无关。
树的深度与单词的长度有关：
每个节点代表字符串下的一个字母，那么单词的每一个字母独占树的一层的位置，没有单词的两个字母在同一层级，
则整个树高为（最长字符串+1）， + 1因为root 节点独占顶层
五.应用
（1）排序:
排序：使用数组创建模拟字典树：将字母序列转化成数字序列 ，标记为数组索引，那么数组索引有序，字母即有序。（参考上图，前序遍历即排序）
对树进行前序遍历 就是有序排序了。
(2)统计单词/字符串出现次数
字典树的结构体：
count即为统计的串出现的次数
(3) 查找公共前缀字符串
使用举例：
/*
字典树学习： 输入n个单词 举出一个单词出现的次数。 10 apple
ppppp
hello
hello
need
bee
bee
none
you
apple need
==1
==Program ended with exit code: 0 */
//
// main.cpp
// CPlusDemo
//
// Created by HF on 2018/5/15.
// Copyright © 2018年 HF-Liqun. All rights reserved.
// #include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std; #define MAX 26 //the total number of alphabet is 26, a...z struct DicTrie{
bool isTerminal;//是否是单词结束标志
int count; //当前字符串出现次数
struct DicTrie *next[MAX ]; //每个节点 最多 有 MAX 个孩子节点 结构体嵌套
} ; DicTrie *root = NULL; // 根节点是一个空节点 特此声明并赋值 int init() //初始化链表,有对空间要求的 可选用该方法进行初始化
{
root = new DicTrie;
root->count = 0;
for (int i = 0; i < MAX; i ++) {
root->next[i] = NULL; // 空节点
root->isTerminal = false; //
}
return 0;
} bool isFindTrie(char *targetString) //判断是否能在字典树中查到目标串
{
int len = strlen(targetString);
DicTrie *head = root;
for (int i = 0; i < len; i ++) {
int res = (int)(targetString[i] - 'a');//当前小写字母对应数字
if (head->next[res] == NULL) { //如果是空节点 则为否 结束查找
return false;
} else {//不为空 更新头指针 以便继续往下查找
head = head->next[res];
}
}
if (head->count > 0) {
return true;
}
return false;
} int findTrieCount(char *targetString) //判断是否能在字典树中查到目标串
{
int len = strlen(targetString);
DicTrie *head = root;
for (int i = 0; i < len; i ++) {
int res = (int)(targetString[i] - 'a');//当前小写字母对应数字
if (head->next[res] == NULL) { //如果是空节点 则为否 结束查找
return false;
} else {//不为空 更新头指针 以便继续往下查找
head = head->next[res];
}
}
return head->count;
} int insertTrie(char *targetString)
{
int len = strlen(targetString);
DicTrie *head = root;
for (int i = 0; i < len; i ++) {
int res = (int)(targetString[i] - 'a');//当前小写字母对应数字
if (head->next[res] == NULL) { //如果是空节点
head->next[res] = new DicTrie;//则插入新节点元素
head = head->next[res]; //更新头指针 并初始化
head->count = 0; //
for (int j = 0; j < MAX; j ++) {
head->next[j] = NULL;
head->isTerminal = false;
}
} else {
head = head->next[res];
}
}
head->count ++;//每次插入一个，响应计数都增加1
head->isTerminal = true;
return head->count;
} int deleteTrie(char *targetString)
{
int len = strlen(targetString);
DicTrie *head = root;
for (int i = 0; i < len; i ++) {
int res = (int)(targetString[i] - 'a');//当前小写字母对应数字
if (head->next[res] == NULL) { //如果是空节点 表示删除的字符串不在字典中
return 0;
} else { //继续查找
head = head->next[res];
}
}
head->count --;//每次删除一个，响应计数都-1
if (head->count <= 0) {
head->count = 0;
head->isTerminal = false;
}
return 0;
} int main(int argc, const char * argv[]) {
// insert code here...
int n;
char targetString[20]; init(); scanf("%d",&n); //n 组数据
for (int i = 0; i < n; i ++) {
scanf("%s",targetString);
//字符串插入字典树
insertTrie(targetString);//插入方法
}
scanf("%s",targetString);
printf("==%d\n",findTrieCount(targetString));//查找方法 return 0;
}
参考
1.https://blog.csdn.net/piaocoder/article/details/47836559
2.http://blog.51cto.com/570842253/1556652
3.http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f743c2923f8170798f62a585257fdd8436cd73b6d
4.https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E6%A0%91/9825209?fr=aladdin&fromid=517527&fromtitle=Trie%E6%A0%91