poj2503字典树的应用

*题目链接

Babelfish

字典树介绍

字典树是一种树形结构，也叫单词搜索树、Trie树，优点是可以利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串的比较。

特点

- 根节点不包含任何字母，二除它以外的每个结点仅包含一个字母；
- 从跟结点到某个结点，路径上经过的字母一次连接起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个词，都是该字母树某个结点所对应的单词；
- 每个结点的所有儿子包含的字母各不相同。字典树的插入、删除、查找都非常简单，用一个重循环即可，即第i次循环找到前i个字母所对应的子树，然后进行相应操作。

字典树的静态与动态实现（模板）

静态数组实现（费空间）

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1000;
const int branch=26;
struct tree_node{
    int count;
    bool end;
    tree_node *next[branch];
}root,node[maxn];
int p;//静态建树的特点，记录用了几个tree_node，则下一个结点是node[p]
/*插入*/
void insert(char *word)
{
    tree_node *location=&root;//起初指向根节点，再一层层向下找
    while(*word){
        if(location->next[*word-'a']==NULL){
            node[p].count=0;//初始化新节点
            node[p].end=false;
            memset(node[p],0,sizeof(node[p]));
            location->next[*word-'a']=&node[p++];
        }
        location=location->next[*word-'a'];
        location->count++;
        word++;
    }
    location->end=true;
}
/*查找*/
bool search(cahr *word)
{
    tree_node *location=&root;
    while(*word&&location){
        location=location->next[*word-'a'];
        word++;
    }
    return (location!=NULL&&location->end);
}

动态建树（费时间）

struct tree_node{
    boot end;
    tree_node *next[branch];//指向各子树的指针，下标0-25代表26个字符
    tree_node(){
        end=false;
        memset(next,NULL,sizeof(next));
    }
}root;
/*插入*/
void insert(char *word)
{
    tree_node *location=&root;//向以root为根节点的树中插入word
    while(*word){
        if(location->next[*word-'a']==NULL){
            tree_node *tmp=new tree_node();
            location->next[*word-'a']=tmp;
        }
        location=location->next[*word-'a'];
        word++;
    }
    location->end=true;
}
/*查找*/
bool search(char *word)
{
    tree_node *location=&root;
    while(*word&&location){
        location=location->next[*word-'a'];
        word++;
    }
    return (location!=NULL&&location->end);
}

题目描述(Description)

给定一些字符串以及它在一种外星语言中的对应解释，现在有若干外星语言中的串，要求把它们翻译成英语。

分析(Analysis)

直接用字典树存外星语，维护一个长度为11的字符数组，用来存对应的英语。

代码(Code)

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=2600010;
const int branchNum=26;
struct tree_node{
    char dia[11];
    tree_node *next[branchNum];
}root,node[maxn];
int p=0;
void insert(char *word,char *dia)
{
    tree_node *location=&root;
    while(*word)
    {
        if(location->next[*word-'a']==NULL){
            memset(node[p].next,NULL,sizeof(node[p].next));
            location->next[*word-'a']=&node[p++];
        }
        location=location->next[*word-'a'];
        word++;
    }
    strcpy(location->dia,dia);
}
void search(char *word)
{
    tree_node *location=&root;
    while(*word&&location)
    {
        location=location->next[*word-'a'];
        word++;
    }
    if(location!=NULL&&location->dia!=0)
        printf("%s\n",location->dia);
    else
        printf("eh\n");
}
int main()
{
    char word[11],dia[11],c;
    while(1)
    {
        scanf("%s%s",word,dia);
        insert(dia,word);
        getchar();
        c=getchar();
        if(c=='\n')
            break;
        ungetc(c,stdin);
    }
    while(scanf("%s",dia)!=EOF)
    {
        search(dia);
    }
    return 0;
}