本文主要是介绍ACM 字典树 Phone List Hat’s Words，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
字典树：又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。
典型应用：统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
优点：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
基本性质：
1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。
基本模板:(来自百度百科)
#define MAX 26//字符集大小
typedef struct TrieNode
{int nCount;//记录该字符出现次数struct TrieNode* next[MAX];
}TrieNode;TrieNode Memory[1000000];
int allocp=0;/*初始化*/
void InitTrieRoot(TrieNode* *pRoot)
{*pRoot=NULL;
}/*创建新结点*/
TrieNode* CreateTrieNode()
{int i;TrieNode *p;p=&Memory[allocp++];p->nCount=1;for(i=0;i<MAX;i++){p->next[i]=NULL;}return p;
}/*插入*/
void InsertTrie(TrieNode* *pRoot,char *s)
{int i,k;TrieNode*p;if(!(p=*pRoot)){p=*pRoot=CreateTrieNode();}i=0;while(s[i]){k=s[i++]-'a';//确定branchif(!p->next[k])p->next[k]=CreateTrieNode();elsep->next[k]->nCount++;p=p->next[k];}
}//查找
int SearchTrie(TrieNode* *pRoot,char *s)
{TrieNode *p;int i,k;if(!(p=*pRoot)){return0;}i=0;while(s[i]){k=s[i++]-'a';if(p->next[k]==NULL) return 0;p=p->next[k];}return p->nCount;
}
HDU 1671 Phone List
题目大意：（例题带入）有2组数据，第一组数据有3个电话号码，问是否存在一个号码是另一个的前缀，若存在则不合适，输出NO。
思路:字典树，在建树的时候直接判断了...
#include <iostream>
#define MAX 10
using namespace std;
bool flag;
typedef struct Trie_Node
{bool isphone;struct Trie_Node *next[MAX];
}Trie;
void insert(Trie *root,char *phone)
{Trie *p=root;while(*phone!='\0'){if(p->next[*phone-48]==NULL){Trie *temp=(Trie *)malloc(sizeof(Trie));temp->isphone=false;for(int i=0;i<MAX;i++)temp->next[i]=NULL;p->next[*phone-48]=temp; }if(p->isphone==true)flag=true;p=p->next[*phone-48];phone++;}p->isphone=true;for(int i=0;i<MAX;i++){if(p->next[i]!=NULL){flag=true;break;}}
}
void del(Trie *root)
{for(int i=0;i<MAX;i++){if(root->next[i]!=NULL)del(root->next[i]);}free(root);
}
int main(int argc, char *argv[])
{int t;scanf("%d",&t);while(t--){int i;int n;char phone[11];Trie *root=(Trie *)malloc(sizeof(Trie));root->isphone=false;flag=false;for(i=0;i<MAX;i++)root->next[i]=NULL;scanf("%d",&n);for(i=0;i<n;i++){scanf("%s",phone);if(flag!=true)insert(root,phone);}if(flag==true)printf("NO\n");elseprintf("YES\n");del(root); }return 0;
}
HDU 1247 Hat’s Words
题目大意：输入直到EOF结束，判断是否存在两个组合可以组成另一个字符串。
思路：先把所有字符串都存下来建树，然后从根走到每个叶子结点记下来比较。
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX=26;
typedef struct Trie_Node
{bool isWord;struct Trie_Node *next[MAX];
}Trie;
char s[50010][50];
void insert(Trie *root,char *word)
{Trie *p=root;int i=0;while(word[i]!='\0'){if(p->next[word[i]-'a']==NULL){Trie *temp=(Trie *)malloc(sizeof(Trie));for(int j=0;j<MAX;j++)temp->next[j]=NULL;temp->isWord=false;p->next[word[i]-'a']=temp;}p=p->next[word[i]-'a'];i++;}p->isWord=true;
}
bool search(Trie *root,char *word)
{Trie *p=root;for(int i=0;word[i]!='\0';i++){if(p->next[word[i]-'a']==NULL)return false;p=p->next[word[i]-'a'];}return p->isWord;
}
void del(Trie *root)
{for(int i=0;i<MAX;i++){if(root->next[i]!=NULL)del(root->next[i]);}free(root);
}
int main()
{int i,j;int cnt=0;char str[50];Trie *root=(Trie *)malloc(sizeof(Trie));for(i=0;i<MAX;i++)root->next[i]=NULL;root->isWord=false;while(scanf("%s",s[cnt])!=EOF){insert(root,s[cnt++]);}for(i=0;i<cnt;i++){int len=strlen(s[i]);for(j=1;j<len-1;j++){char temp1[50]={'\0'};char temp2[50]={'\0'};strncpy(temp1,s[i],j);strncpy(temp2,s[i]+j,len-j);if(search(root,temp1)&&search(root,temp2)){printf("%s\n",s[i]);break;}}}del(root);return 0;
}
这篇关于ACM 字典树 Phone List Hat’s Words的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
