trie-c.cpp

1． Trie树作为一种索引树

#include "stdafx.h"
#include <stdio.h>
//#include <iostream>
#include <string.h>
//using namespace std;
const int num_chars = 26;
int trie_search(const char* word, char* entry ) ;
int insert(const char* word, const char* entry);
int remove(const char* word);
	struct Trie_node
	{
		char* data;
		Trie_node* branch[num_chars];
		Trie_node()
		{
			data = NULL;
			for (int i=0; i<num_chars; ++i) 
				branch[i] = NULL;
		};
	};

	Trie_node* root=NULL;;

int trie_search(const char* word, char* entry ) 
{
	int position = 0;
	char char_code;
	Trie_node *location = root;
	while( location!=NULL && *word!=0 ) 
	{
		if (*word>='A' && *word<='Z') 
			char_code = *word-'A';
		else if (*word>='a' && *word<='z') 
			char_code = *word-'a';
		else return 0;
		location = location->branch[char_code];
		position++;
		word++;
	}
	if ( location != NULL && location->data != NULL ) 
	{
		strcpy(entry,location->data);
		return 1;
	}
	else return 0;
}
int insert(const char* word, const char* entry) 
{
	int result = 1, position = 0;
	if ( root == NULL ) root = new Trie_node;
	char char_code;
	Trie_node *location = root;
	while( location!=NULL && *word!=0 )
	{
		if (*word>='A' && *word<='Z') 
			char_code = *word-'A';
		else if (*word>='a' && *word<='z') 
			char_code = *word-'a';
		else return 0;
		if( location->branch[char_code] == NULL ) 
			location->branch[char_code] = new Trie_node;
		location = location->branch[char_code];
		position++;
		word++;
	}
	if (location->data != NULL)
		result = 0;
	else {
		location->data = new char[strlen(entry)+1];
		strcpy(location->data, entry);
	}
	return result;
}

int remove(const char* word)
{
	int result = 1;
	char char_code;
	Trie_node *location = root;

	while( location!=NULL && *word!=0) {
		if (*word>='A' && *word<='Z')
			char_code = *word-'A';
		else if (*word>='a' && *word<='z')
			char_code = *word-'a';
		else
			return 0;

		location = location->branch[char_code];
		word++;
	}
	if (location&&location->data) {
		delete location->data;
		location->data = NULL;
	} else {
		result = 0;
	}
	return result;
}


int main()
{
	char entry[100];

	insert("aa", "空对空");  
	insert("abacus","算盘");
	insert("abalone","鲍鱼");   
	insert("abandon","放弃, 遗弃");
	insert("abandoned","被抛弃的"); 
	insert("abashed","不安的");
	insert("abate","减轻");   
	insert("baby", "婴孩");

	puts("字典初始化，插入了:");
	puts("aa, its meaning:空对空");  
	puts("abacus,its meaning:算盘");
	puts("abalone,its meaning:鲍鱼");   
	puts("abandon,its meaning:放弃, 遗弃");
	puts("abandoned,its meaning:被抛弃的"); 
	puts("abashed,its meaning:不安的");
	puts("abate,its meaning:减轻");   
	puts("baby, its meaning:婴孩");
	printf("***********************************\n");
	printf("********  1:Insert  ***************\n");
	printf("********  2:Delete  ***************\n");
	printf("********  3:Taverse ***************\n");
	printf("***********************************\n");
	char c2[10]; 
	char input[50];
	char output[50];
	while(1)
	{
		printf("please input a number  1:Insert; 2:Delete;3:Taverse! ");
		gets(c2);
		if(strcmp(c2,"1")==0)
		{

			puts("请输入要插入的单词:");
			gets(input);
			puts("请输入插入单词的意思:");
			gets(output);
			if(insert(input,output))
				puts("插入成功!");
			else
				puts("Already exist!插入失败");
		}
		if(strcmp(c2,"2")==0)
		{			         
			puts("请输入要删除的单词:");
			gets(input);
			if(remove(input))
				puts("It was found,删除成功");
			else
				puts("It does not exist at all!删除失败");

		}
		else if(strcmp(c2,"3")==0)
		{
			puts("请输入要查询的单词:");
			gets(input);
			if (trie_search(input, entry))
				printf("It was found. its meaning is:%s.查询成功\n",entry);
			else
				puts("It does not exist at all!查询失败");
		}
	}

}