[科技论文网] http://www.scipapers.com    2007-12-01  

字典树实现源代码

由字母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;
}


    来源：

声明：本文由网友推荐或作者提交，版权归原作者所有，刊登此文仅为传播知识，展示研究成果，提高文章引用率。未经原作者授权，禁止用于任何形式的商业行为。科技论文网倡导尊重知识、尊重劳动、保护原创、知识共享。由于部分论文文章来于网络，文章作者不祥，请相关的原创作者与我们联系，以便加上您的署名。