字典树的应用单词意义查找-C语言实现

ゞ浴缸里的玫瑰 2022-08-02 09:54 119阅读 0赞

/*
    字典树应用，快速单词查找 
    */
    
    const int M = 1000000;
    char word[1000000][11];
    int wp; // 单词列表的下标 
    struct node{
    	int next[26];
    	int value;
    	bool end;
    } tree[M]; // 可用节点数组，相当于内存池 
    int pi = 1; // 代表空闲的节点位置 
    void init(){
    	memset(tree,0,sizeof(tree));
    	pi = 1; // 头节点占用0，空闲节点从1开始 
    	wp = 0;
    }
    void insert(char * keyword,int value){
    	int index,p,i; // p代表当前的节点，开始为根节点 
    	for(i=p=0;keyword[i];i++){
    		index = keyword[i] - 'a';
    		if(tree[p].next[index] == 0)
    			tree[p].next[index] = pi++;
    		p = tree[p].next[index]; 
    	}
    	tree[p].value = value;
    	tree[p].end = 1;
    }
    bool query(char * keyword, int &value){
    	int index,p,i;
    	for(i=p=0;keyword[i];i++){
    		index = keyword[i] - 'a';		
    		if(tree[p].next[index] == 0)
    			return 0;
    		p = tree[p].next[index];
    	}
    	if(tree[p].end){
    		value = tree[p].value;
    		return 1; 
    	}
    	return 0;
    }
    int main(){
    	char s1[15],s2[15],s[30];
    	int i,value;
    	while(gets(s)){
    		if(!strlen(s))
    			break;
    		for(i=0;i<strlen(s);i++){
    			if(s[i]==' ')
    				break;
    		}
    		strncpy(s1,s,i); // say speak ==> say
    		s1[i] = 0;
    		strcpy(s2,s+i+1);
    		strcpy(word[wp],s1); // 单词数组（二维） 
    		insert(s2,wp++); // 含义插入字典树，应用时根据含义找单词，用下标wp进行关联 
    	}
    	while(scanf("%s",s)!=EOF){
    		if(query(s,value))
    			cout<<word[value]<<endl;
    		else
    			cout<<"no the word"<<endl;
    		}
    }

实现根据单词快速找到对应的解释