说明文件.txt

来自「字典树算法 算法描述为：由字母a～z所组成的字符串的一个集合中」· 文本 代码 · 共 60 行

字典树算法
算法描述为：由字母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); 
} 
}