字典树实现源代码

作者：来源：http://blog.csdn.net/zxg623 发表时间：2007-07-31 浏览次数：字号：大 中 小

由字母a～z所组成的字符串的一个集合中，各个字符的长度之和为n。设计一个O(n)时间的算法，将这个集合中所有字符串依字典进行排序。注意，这里可能存在非常长的字符串。

#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;
}