《ACM字典树详解ppt课件.ppt》由会员分享，可在线阅读，更多相关《ACM字典树详解ppt课件.ppt（16页珍藏版）》请在三一办公上搜索。
1、ACM程序设计,杭州电子科技大学 刘春英,集训队讲座（二）,字典树（Trie）,导引问题 (HDOJ-1251),Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).,初步分析（Brute-force）,Question:如果单词表容量很大-查找效率? -低更有效率的方法：字典树,假设单词表容量为M，需要统计的前缀数量为N，单词的平均长度为L，则常规算法的时间复杂度是？,什么是字典树？,字典树：又称为Trie，是一种用于快速检索的多叉树结构。Trie把要查找的关键词看作一个字符
2、序列，并根据构成关键词字符的先后顺序构造用于检索的树结构；一棵m度的Trie树或者为空，或者由m棵m度的Trie树构成。,特别地：和二叉查找树不同，在Trie树中，每个结点上并非存储一个元素。,Trie的图示,特点：利用串的公共前缀-节约内存根结点不包含任何字母其余结点仅包含一个字母(非元素)每个结点的子节点包含字母不同,Trie的查找（最主要的操作）,(1)在trie树上进行检索总是始于根结点。(2)取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索。 (3)在(5)在某个结点处，关相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索。(4
3、) . 键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。,Trie的数据结构定义,struct dictree dictree *child26; int n; /根据需要变化; dictree *root;,查找效率分析,在trie树中查找一个关键字的时间和树中包含的结点数无关，而取决于组成关键字的字符数。（对比：二叉查找树的查找时间和树中的结点数有关O(log2n)。）如果要查找的关键字可以分解成字符序列且不是很长，利用trie树查找速度优于二叉查找树。若关键字长度最大是5，则利用trie树，利用5次比较可以从26511881376个可能的关键字中检索出指定的关键字。而利用二
4、叉查找树至少要进行log2265=23.5次比较。,示例(HDOJ-1075),What Are You Talking About 题目描述：Ignatius is so lucky that he met a Martian yesterday. But he didnt know the language the Martians use. The Martian gives him a history book of Mars and a dictionary when it leaves. Now Ignatius want to translate the history book
5、 into English. Can you help him?,样本数据(HDOJ-1075),Sample InputSTART from fiwo hello difh mars riwosf earth fnnvk like fiiwj END START difh, im fiwo riwosf. i fiiwj fnnvk! END,Sample Outputhello, im from mars.i like earth!,Input Description:All the words are in the lowercase, and each word will contai
6、n at most 10 characters, and each line will contain at most 3000 characters.,题目分析(HDOJ-1075),特点？数据量大主要任务？查找单词解决方法？字典树字典树结构（除指针）？单词信息（英文）额外提醒？字符串操作的熟练应用其他问题？NO,相关练习,HDOJ-1075What Are You Talking About HDOJ-1251统计难题 HDOJ-1298T9 HDOJ-1800 Flying to the Mars ZOJ-1109 Language of FatMouse,附:参考源码(HDOJ-125
7、1),#include stdio.h #include string.h #include stdlib.h struct dictree struct dictree *child26; int n; ; struct dictree *root; void insert (char *source) int len,i,j; struct dictree *current,*newnode; len=strlen(source); if(len=0) return; current=root; for(i=0;ichildsourcei-a!=0) current=current-chi
8、ldsourcei-a; current-n=current-n+1; else newnode=(struct dictree *)malloc(sizeof(struct dictree); for(j=0;jchildj=0; current-childsourcei-a=newnode; current=newnode; current-n=1; ,int find(char *source) int i,len; struct dictree *current; len=strlen(source); if(len=0) return 0; current=root; for(i=0
9、;ichildsourcei-a!=0) current=current-childsourcei-a; else return 0; return current-n; int main() char temp11; int i,j; root=(struct dictree *)malloc(sizeof(struct dictree); for(i=0;ichildi=0; root-n=2; while(gets(temp),strcmp(temp,)!=0) insert(temp); while(scanf(%s,temp)!=EOF) i=find(temp); printf(%dn,i); ,下一讲,Welcome to HDOJ,Thank You ,
