hashtable.cpp

这些程序是本人学习数据结构时编的

// Hash.cpp: implementation of the Hash class.
//
//////////////////////////////////////////////////////////////////////

#include "HashTable.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////


Hash::Hash()
{
	int i;
	for ( i= 0 ; i< 26 ;i ++)	//初始化关键码
	{
		ht[i].Key = 65 + i;		//从 'A' 到 'Z'
	}
	initialization();			//读入字典库
};

//读入字典库
void Hash::initialization()
{
	ifstream file;
	Data data;
	char ch[256];			//定义缓冲区 
	file.open ("dictionary.txt");	
	if (!file)
		exit(1);
	while (!file.eof ())	//文件没结束则继续
	{
		file.getline(ch ,999,'#');	//读入一个单词
		data.word = ch;				//赋值
		file.getline(ch ,999,'#');	//读入一个解释
		data.means = ch;			//赋值
		if (data.word.length () && data.means.length () ) 
			insert(data);			//插入单词
	};
}

//hash函数
int Hash::HashFunc(const string &x)
{
	char ch = x[0];			//取单词首字符
	if (ch >96)			
		return ch - 97;		//a ~ z 映射到 0 ~ 25 
	else return ch - 65;	//A ~ Z 映射到 0 ~ 25
}


//给出单词查找相应解释，并存储于 result 对象中用于返回
int Hash::Find(const string& x,Data& result)
{
	int j = HashFunc(x);		//计算Hash值
	list<Data> * p = &ht[j].l;	//对应bucket
	if( p->empty ())			
		return 0;				//bucket为空返回 0 
	lp = p->begin();			//游标初始于首元素
	while (lp != p->end())		//未到达链表尾部
	{
		if (lp->word == x)		//查找到
		{
			result.word = lp->word;		//赋值
			result.means = lp->means;
			return 1;
		};
		lp++;					//找下个元素
	};
	return 0;
};

//插入一个单词和解释
int Hash::Insert (const Data & x)
{
	int j = HashFunc (x.word);
	Data temp;
	if (Find(x.word ,temp) == 1)  //如果该单词已经在字典库中，
	{
		cout<<"\n该单词已存在";   //则返回
		return 0;
	};
	list<Data> *p = &ht[j].l;	  //取对应的bucket
	p->push_back(x);			  //插入
	cout<<"\n该单词已成功插入";
	return 1;
}

//插入一个单词和解释
int Hash::insert (const Data & x)
{
	int j = HashFunc (x.word);
	Data temp;
	if (Find(x.word ,temp) == 1)  //如果该单词已经在字典库中，
	{
		cout<<"\n该单词已存在";   //则返回
		return 0;
	};
	list<Data> *p = &ht[j].l;	  //取对应的bucket
	p->push_back(x);			  //插入
	return 1;
}

//给出单词删除该单词和解释
int Hash::Remove(const string &x)
{
	int j = HashFunc (x);
	list<Data> *p = &ht[j].l ;
	Data temp;
	if (Find(x,temp) == 0)			//如果单词不在字典中
	{
		cout<<"\n该单词不存在字典中";	//返回
		return 0;
	};
	p->remove(temp);				//在，则删除掉
	cout<<"\n该单词已成功删除"; 
	return 1;
}