entrie.cpp

Trie数据结构

#include <iostream>
#include <queue> 
#include <vector>
#include <fstream>
#include <string>
using namespace std;
class trieNode
{
private:
	char key;
	int value;
	//string value;
	trieNode *next;
	trieNode *child;

public:
	friend class trie;
	trieNode():key('\0'),value(-1),next(NULL),child(NULL){} 
	trieNode(char key,int value,trieNode *next,trieNode *child);
	void setValue(int value){this->value = value;}
};
trieNode::trieNode(char key,int value,trieNode *next,trieNode *child){
	this->key = key;
	this->value = value;
	this->next = next;
	this->child = child;
}


class trie{
private:
	trieNode head;
public:
	trie():head('\0',-1,NULL,NULL){}
	void addItem(const char *str,int value);	
	bool findItem(const char *str);
	void delItem(const char *str);
	trieNode *getTrieTreeRoot()
	{
		return &head;
	}
	void printTrie();
	void printNode(trieNode *first);
	int findPre(const char *str);
};
void trie::addItem(const char *str,int value){
	const char *p;
	trieNode *root;
	trieNode *t;
	trieNode *pre;
	trieNode *node;

	if(str == NULL){
		return ; 
	}
	root = &head;

	for(p = str;;p++){
		pre = NULL;
		for(t = root->child;t != NULL;t = t->next)
		{
			if(t->key == *p)
			{
				break;
			}
			pre = t;
		}
		if(t == NULL)
		{
			node = new trieNode(*p,-1,NULL,NULL);    
			if(node == NULL){
				return ;
			}
			if(pre == NULL){
				root->child = node;
			}
			else{
				pre->next = node;
			}
			root = node;
		}
		else
		{
			root = t;
		}
		if(*p == '\0'){
			node->setValue(value);
			break;
		}
	}
}
void trie::delItem(const char *str)
{
	if(str == NULL || !findItem(str)) return;
	trieNode *root;
	trieNode *t;
	const char *p;
	int nSz = (int)strlen(str), i, pos = -1;
	vector<int> countVec;
	root = &head;
	p = str;
	for(i = 0; i < nSz; i++)
	{
		for(t = root->child; t != NULL; t = t->next)
		{
			if(t->key == p[i])
			{
				break;
			}
		}
		if(t->child->next == NULL)
		{
			countVec.push_back(0);
		}
		else
		{
			countVec.push_back(1);
		}
		root = t;
	}
	for(i = (int)countVec.size() - 1; i >= 0; i--)
	{
		if(countVec[i] == 1)
		{
			pos = i;
			break;
		}
	}
	root = &head;
	p = str;
	for(i = 0; i <= pos; i++)
	{
		for(t = root->child; t != NULL; t = t->next)
		{
			if(t->key == *p)
			{
				break;
			}
		}
		root = t;
		p++;
	}

	if(*p == '\0')
	{
		if(root->child->key == '\0')
		{
			trieNode *tmp = root->child;
			root->child = tmp->next;
			delete tmp;
		}
		else
		{
			trieNode *tmp = root->child;
			while(tmp->next->key != '\0') tmp = tmp->next;
			root = tmp;
			tmp = tmp->next;
			root->next = tmp->next;
			delete tmp;
		}
		return;		
	}
	else 
	{
		if(root->child->key == *p)
		{
			trieNode *tmp = root->child;
			root->child = tmp->next;
			while(tmp != NULL)
			{
				root = tmp;
				tmp = root->child;
				delete root;
			}
		}
		else
		{
			trieNode *tmp = root->child;
			while(tmp->next->key != *p) tmp = tmp->next;
			root = tmp;
			tmp = tmp->next;
			root->next = tmp->next;
			while(tmp != NULL)
			{
				root = tmp;
				tmp = root->child;
				delete root;
			}			
		}
	}	

}
bool trie::findItem(const char *str)
{
	trieNode *root;
	trieNode *t;
	root = &head;
	const char *inStr = str;
	while(true)
	{
		for(t = root->child; t != NULL; t = t->next)
		{
			if(t->key == *inStr)
			{
				break;
			}
		}
		if(t != NULL)
		{
			root = t;
		}	
		else 
		{
			return false;
		}
		if(*inStr == '\0')
		{
			return true;
			break;
		}
		inStr++;
	}
}
void trie::printTrie(){
	queue<trieNode *> triequ[2];
	trieNode *p;
	trieNode *root;
	int i = 0;
	triequ[i].push(&head);
	while(!triequ[i].empty())
	{
		while(!triequ[i].empty())
		{
			root = triequ[i].front();
			triequ[i].pop();
			if(root == NULL)
			{
				cout << endl;
				continue;
			}
			for(p = root->child;p != NULL;p = p->next)
			{
				triequ[1 - i].push(p);
				cout << p->key << "(" << p->value << "," << root->key << ")\t";
			}
		}
		cout << endl;
		i = 1 - i;
	}
}
int trie::findPre(const char *str){
	int count = 0;
	const char *p;
	trieNode *root;
	trieNode *t = NULL;
	queue<trieNode *> triequ;

	if(str == NULL || *str == '\0'){
		return count; 
	}
	root = &head;

	for(p = str;*p != '\0';p++)
	{
		for(t = root->child;t != NULL;t = t->next)
		{
			if(t->key == *p){
				break;
			}
		}
		if(t == NULL){
			return count;
		}
		root = t;
	}
	triequ.push(t);
	while(!triequ.empty())
	{
		root = triequ.front();
		triequ.pop();
		for(t = root->child;t != NULL;t = t->next)
		{
			triequ.push(t);
			if(t->key == '\0')
			{
				count++;
			}
		}
	}
	return count;
}

int main()
{

	return 0;
}