字典树算法.cpp

字典树算法

// 字典树算法.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#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; 
	if (i>=0)
	{
		s[i] = root->date;
	}
	 

	if(root->cnt==1) 
	{ 
		s[i+1] ='\0'; 
		printf("%s\n",s); 
	} 

	for(j=0;j<26;j++) 
	{ 
		if(root->next[j]!=NULL) 
		{ 
			print(root->next[j],s,i+1); 
		} 
	} 

}
int _tmain(int argc, _TCHAR* argv[])
{
	char *str1="abcdefg";
	char *str2="abcefg";
	char *str3="bcd";
	char *str4="abcdef";
	_tire root=new struct tire[26];
	//root->date=' ';
    for(int i=0;i<26;i++)
	{
		root->next[i]=NULL;
	}

    init_tire(root,str1);
	init_tire(root,str2);
	init_tire(root,str3);
	init_tire(root,str4);

	char *s=(char *)malloc(sizeof(char)*20);
	print(root,s,-1);
	getchar();


	return 0;
}