好字典问题627dict.cpp

设计一个算法

#include <iostream>
#include <fstream>
#include <string>
#include <stack>

using namespace std;

template<class elemType>
struct NodeType
{
	elemType info;
	int num;
	NodeType<elemType>* llink;
	NodeType<elemType>* rlink;
};

template<class elemType>
class SearchTree
{
public:
	SearchTree() { root = NULL; }
	~SearchTree() { destroy(root); }
	void search(const elemType& searchItem);
	void insert(const elemType& insertItem);
	int maxNum();

private:
	NodeType<elemType>* root;
	void destroy(NodeType<elemType>* &p);
};

template<class elemType>
void SearchTree<elemType>::search(const elemType& searchItem)
{
	NodeType<elemType>* current;
	
	if (root == NULL)
		cerr << "Cannot search an empty tree." << endl;
	else
	{
		current = root;
		
		while (current != NULL)
		{
			if (current->info == searchItem)
			{
				current->num = 0;
				break;
			}
			else if (current->info > searchItem)
				current = current->llink;
			else
				current = current->rlink;
		}
	}
}

template<class elemType>
void SearchTree<elemType>::insert(const elemType& insertItem)
{
	NodeType<elemType>* current;
	NodeType<elemType>* trailCurrent;
	NodeType<elemType>* newNode;

	if (root == NULL)
	{
		newNode = new NodeType<elemType>;
		newNode->info = insertItem;
		newNode->num = 1;
		newNode->llink = NULL;
		newNode->rlink = NULL;
		root = newNode;
	}
	else
	{
		current = root;
		
		while (current != NULL)
		{
			trailCurrent = current;
	
			if (current->info > insertItem)
				current = current->llink;
			else if (current->info < insertItem)
				current = current->rlink;
			else
				break;
		}
	
		if (current != NULL && current->info == insertItem)
			(current->num)++;
		else
		{
			newNode = new NodeType<elemType>;
			newNode->info = insertItem;
			newNode->num = 1;
			newNode->llink = NULL;
			newNode->rlink = NULL;

			if (trailCurrent->info > insertItem)
				trailCurrent->llink = newNode;
			else
				trailCurrent->rlink = newNode;
		}
	}
}

template<class elemType>
int SearchTree<elemType>::maxNum()
{
	int max = 0;
	string tmp;
	stack<NodeType<elemType>* > stack;
	NodeType<elemType>* current;
	current = root;
	
	while ((current != NULL) || (!stack.empty()))
	{
		if (current != NULL)
		{
			stack.push(current);
			current = current->llink;
		}
		else
		{
			current = stack.top();
			stack.pop();
			if (current->num > max)
				max = current->num;
			current = current->rlink;
		}
	}

	return max;
}

template<class elemType>
void SearchTree<elemType>::destroy(NodeType<elemType>* &p)
{
	if (p != NULL)
	{
		destroy(p->llink);
		destroy(p->rlink);
		delete p;
		p = NULL;
	}
}

int main()
{
	ifstream fin("input.txt");
	if (!fin.is_open())
	{
		cerr << "Cannot open the input file." << endl;
		return 1;
	}
	int n, m, i;
	SearchTree<string> stringSet;
	
	fin >> n;
	string* s1 = new string[n];
	for (i = 0; i < n; i++)
		fin >> s1[i];

	fin >> m;
	string s2;
	for (i = 0; i < m; i++)
	{
		fin >> s2;
		stringSet.insert(s2);
	}
	for (i = 0; i < n; i++)
		stringSet.search(s1[i]);

	ofstream fout("output.txt");
	fout << stringSet.maxNum() << endl;
	
	fin.close();
	fout.close();

	delete [] s1;

	return 0;
}