代码

结点类代码

//创建char类型的字典树
class Node
{
	Node* next[26];
	//链接单词下一个字母的指针
	//一个字母下面最多有26个字母链接

	int count;
	//如果大于0则代表从根节点到此节点的字母所组成的单词存在
	//从根节点到此节点的字母所组成的单词在文章中的出现频率

	Node(): count(0)
	{
		for (int i = 0; i < 26; i++)
			next[i] = nullptr;

	}
	//构造函数，将所有元素置空

	friend class TrieTree;
	//友元类 TrieTree
};

字典树存在根结点，从根结点开始，有 26 个 Node 型指针，分别代表 26 个英文字母。如果字母存在，则对应的指针指向一个动态建立的 Node 型结点

一开始构建字典树时，在 Node 中还创建了 char 型变量 letter，用来记录对应字母。但是可以用指针是否指向存在的结点来判断这个字母是不是存在

如果单词插入成功，则结尾字母对应的结点上的 int 型变量 count 从 0 为 1，表示从根结点到此结点，一路上的字母组成了某一个单词，同时 count 变量还可以作为单词存储次数的计数器

调用代码

class TrieTree
{
public:
	TrieTree(string str);
	//字典树的构造函数
	//从main函数中读取一段英文文章（全为小写）
	//从中读取单词并储存

	void Insertion(string str);
	//将str中的字符插入字典树中

	bool Query(string str);
	//在字典树中查询str是否存在以及出现频率
private:
	Node* root;
	//字典树的根节点，不包含任何字母
	//仅提供单词开头为a到z的节点的指针
};

TrieTree::TrieTree(string str)
{
	start = clock();

	this->root = new Node();

	string str2;
	char s[26];//用来暂存单词
	int length = 0;//字符串str当前的读取长度
	int len = 0;//字符数组s当前的记录长度

	//isalpha(ch(x))数组用来判断字符数组或字符串当前字符是否为字母
	//是则返回非0值，否则返回0值
	//可以判断字母，符号 . ，空格
	//应该不能判断 符号 '

	while (1)//将字符串str中的单词逐个截取并插入字典树
	{
		while (isalpha(str[length]))  //判断不为字母则终止循环
			s[len++] = str[length++];//从str中截取单词记录到s数组中
		s[len] = '\0';
		str2 = s;
		Insertion(str2);
		if (str[length] == '\0')   //判断字符串str是否读取完成
			break;
		len = 0;
		while (isalpha(str[length]) == 0)   //排空不为字母的元素
			length++;
	}
	/*
		总结：
		在单词截取这个算法中，最大的困扰就是最后一个单词截取时总是出错
		问题在于 isalph()这个函数在最后一个单词的后一位判断调用时报错
		导致不能针对报错位的后一位'\0' 进行判断--->isalpha()函数已经报错，能不能判断也无所谓了
		此问题应该时Read()函数中截取文档时出现的错误
		isalph()的具体错误不了解
		但是找到了bug的具体位置

		改进思路：
		针对Read()函数，创建string型变量记录文档
		而不是使用char型数组记录文档后再赋值给string型变量
		以上为初步想法
	*/

	stop = clock();
	tree_Duration = float((stop - start) * 1000) / CLOCKS_PER_SEC;
	cout << "字典树构建成功，构建时间为" << tree_Duration << "毫秒" << endl;
	cout << "字典树内容为:" << endl;
	cout << str;
}

void TrieTree::Insertion(string str)
{
	Node* ptr = this->root;//工作指针
	int num = 0;//记录当前字符的ascll码
	for (int len = 0; len != str.length(); len++)
	{
		if (str[len] >= 'A' && str[len] <= 'Z')
			num = str[len] - 'A';
		else
			num = str[len] - 'a';
		if (ptr->next[num] == nullptr)
			ptr->next[num] = new Node;
		//在当前字符所在的指针新建结点
		ptr = ptr->next[num];
	}
	ptr->count++;
}

bool TrieTree::Query(string str)
{
	start = clock();

	Node* ptr = root;//工作指针
	int num = 0;//记录当前字符的ascll码
	bool judge = true;
	//判断字符串str是否查询成功
	//false为失败，true为成功

	for (int len = 0; len != str.length(); len++)
	{
		if (isupper(str[len]))
			str[len] = tolower(str[len]);
		//利用<iostream>中的函数进行大写字母转换成小写字母

		//if (str[i] >= 'A' && str[i] <= 'Z')
			//str[i] += 32;
		//利用ASCLL码编写相同功能的代码

		num = str[len] - 'a';
		if (ptr->next[num] == nullptr)
		//未查询到字母对应的结点，则查询失败
		{
			judge = false;
			break;
		}
		else
			ptr = ptr->next[num];
	}
	if (ptr->count == 0) //判断此单词是否被字典树记录
		judge = false;

	stop = clock();
	tree_Duration = float((stop - start) * 1000) / CLOCKS_PER_SEC;

	if (judge)
		cout << str << "检索成功，共出现" << ptr->count << "次,检索时间为" << tree_Duration << "毫秒" << endl;
	else
		cout << str << "检索失败,检索时间为" << tree_Duration << "毫秒" << endl;
	return judge;
}

相关内容

代码

结点类代码

调用代码