R向单词查找树(TrieST) -- C++实现


实现代码

// Component.h
#ifndef TIREAST_H
#define TIREAST_H

#include "Component.h"
#define TABLE_SIZE 128

namespace jay{

	class TireST
	{
	public:
		class Node
		{
		private:
			shared_ptr<shared_ptr<Node>> next;
			bool iswordEnd; 
		public:
			Node(const int& R = TABLE_SIZE):next(shared_ptr<shared_ptr<Node>>(new shared_ptr<Node>[TABLE_SIZE], 
				default_delete<shared_ptr<Node>[]>())), iswordEnd(false)
			{
				shared_ptr<Node> *tmp = next.get();
				for (int i = 0; i < R; ++i)
					next.get()[i] = nullptr;
					
			}

			void put( string s,const int& pos)
			{
				if (s[pos] <0)
				{
					return ;
				}
				if (pos == (s.length() - 1))
				{
					// 如果该字符不是某单词的结束字符
					if (next.get()[s[pos]] == nullptr)
						next.get()[s[pos]] = shared_ptr<Node>(new Node);
					// 标记单词结束
					next.get()[s[pos]]->iswordEnd = true;
					return;
				}

				// 如果 list[s[pos] 上没有字符,则添加字符
				if (next.get()[s[pos]] == nullptr)
					next.get()[s[pos]] = shared_ptr<Node>(new Node);

				// 遍历处理剩下的字符
				next.get()[s[pos]]->put(s, pos + 1);
			}

			bool find(const string& s, const int& pos)
			{   
				// 不支持查找中文
				if (s[pos] <0)
				{
					return false;
				}
				if (next.get()[s[pos]] == nullptr)
				{
					return false;
				}
				// 没有找到
				if (pos >= s.length())
					return false;
				// 找到了
				if (pos == (s.length() - 1) && next.get()[s[pos]]->iswordEnd == true)
					return true;

				// 递归查找
				else
					return next.get()[s[pos]]->find(s, pos + 1);
			}

			shared_ptr<Node> get(string& s, const int& pos)
			{   
				// 不支持查找中文
				if (s[pos] <0)
				{
					return nullptr;
				}
				if (next.get()[s[pos]] == nullptr)
				{
					return nullptr;
				}
				// 没有找到
				if (pos >= s.length())
				{
					return nullptr;
				}

				// 找到了
				if (pos == (s.length() - 1))
					return next.get()[s[pos]];
				// 递归查找
				else
					return next.get()[s[pos]]->get(s, pos + 1);
			}

		};
	private:
		shared_ptr<Node> root;
	public:
		TireST():root(new Node)
		{

		}
		void put( string s)
		{
			root->put(s, 0);
		}
		bool find(const string& s)
		{
			return root->find(s, 0);
		}
	};

};

#endif

测试代码

//main.cpp
#include "Component.h"
#include "TireST.h"
using namespace jay;

int main(int argc, char* argv[])
{
	TireST t1;
	t1.put("mzk");
	t1.put("mka");
	t1.put("mds");
	t1.put("qlk");
	t1.put("11313");
	t1.put("4abc");
	t1.put("5abc");
	t1.put("6abc");
	t1.put("7abc");


	cout << "mka is Contain? " << t1.find("mka") <<endl;
	cout << "1abc is Contain? " << t1.find("1abc") <<endl;
	cout << "5abc is Contain? " << t1.find("5abc") <<endl;
	cout << "hexx is Contain? " << t1.find("hexx") <<endl;
	cout << "y is Contain? " << t1.find("y") <<endl;
	cout << "qlk is Contain? " << t1.find("qlk") <<endl;


}

运行结果

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。