Trie

本文在GNU自由文档许可证之条款下提供
Trie,又称单词查找树,是一种树形结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间。

性质

Trie,又称单词查找树,是一种树形结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间。

它有3个基本性质：

1、根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2、从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3、每个节点的所有子节点包含的字符都不相同。

这是一个Trie结构的例子：

在这个Trie结构中，保存了t、to、te、tea、ten、i、in、inn这8个字符串，仅占用8个字节（不包括指针占用的空间）。

ADTs

#include <stdio.h>
#include <malloc.h>
typedef struct tire
{
   struct tire *next[26];
   char date;
   int cnt;
}*_tire;
void init_tire(_tire root, char *string)
{
    _tire s;
    s=root;
 
    while(*string!='\0')
    {
       if(s->next[*string - 'a']==NULL)
       {
          s->next[*string - 'a'] = (_tire)malloc(sizeof(struct tire));
          (s->next[*string - 'a'])->date = *string;
          s = s->next[*string - 'a'];
          for(int i=0;i<26;i++)
          {
              s->next[i] = NULL;
          }
       }
       else
       {
          s = s->next[*string - 'a'];
       }
       string++;
    }
    s->cnt=1;
}
void print(_tire root, char *s, int i)
{
    int j;
    s[i] = root->date;
 
    if(root->cnt==1)
    {
        s[i+1] = 0;
        puts(s);
    }
 
    for(j=0;j<26;j++)
    {
        if(root->next[j]!=NULL)
        {
           print(root->next[j],s,i+1);
        }
    }
 
}
int main()
{
    _tire root;
    int m,i;
    char s[265];
 
    root = (_tire)malloc(sizeof(struct tire));
    puts("输入字符串个数：");
    for(i=0;i<26;i++)
    {
       root->next[i]=NULL;
    }
    scanf("%d",&m);
    getchar();
    while(m--)
    {
       gets(s);
       init_tire(root,s);
    }
    puts("\n依字典排序后：");
    for(i=0;i<26;i++)
    {
       if(root->next[i] != NULL)
       {
          print(root->next[i],s,0);
       }
    }
    return 0;
}

联系题目

USACO prefix