哈希表的运用(C++实现)

哈希表的应用(C++实现)

代码：

// MyHashTable.cpp : 定义控制台应用程序的入口点。
////设计哈希表实现电话号码查询系统
//说明：一是从文件old.txt中读取的数据自己在程序运行前建立，
//      二是由系统随机生成数据，在程序运行由随机数产生器生成，并且将产生的记录保存到 new.txt文件。

//存在的问题：使用随机产生的文件，在显示时出现乱码


#include "stdafx.h"
#include<fstream>//文件流
#include<iostream>
#include <string>
using namespace std;

const int D[] = {3,5,8,11,13,14,19,21};//预定再随机数
const int HASH_MAXSIZE = 50;//哈希表长度

//记录信息类型
class DataInfo
{
public:
	DataInfo();//默认构造函数
	friend ostream& operator<<(ostream& out, const DataInfo& dataInfo); //重载输出操作符
	//friend class HashTable;

//private:
	string name;//姓名
	string phone;//电话号码
	string address;//地址	
	char sign;//冲突的标志位，'1'表示冲突，'0'表示无冲突
};

DataInfo::DataInfo():name(""), phone(""), address(""), sign('0')
{

}

ostream& operator<<(ostream& out, const DataInfo& dataInfo) //重载输出操作符
{
	cout << "姓名：" << dataInfo.name << "   电话：" << dataInfo.phone 
		 << "    地址：" << dataInfo.address << endl;
	return out;
}

//存放记录的哈希表类型
class HashTable
{
public:
	HashTable();//默认构造函数
	~HashTable();//析构函数
	int Random(int key, int i);// 伪随机数探测再散列法处理冲突
	void Hashname(DataInfo *dataInfo);//以名字为关键字建立哈希表	
	int Rehash(int key, string str);// 再哈希法处理冲突   注意处理冲突还有链地址法等
	void Hashphone(DataInfo *dataInfo);//以电话为关键字建立哈希表		
	void Hash(char *fname, int n);// 建立哈希表
	//fname 是数据储存的文件的名称，用于输入数据，n是用户选择的查找方式	
	
	int Findname(string name);// 根据姓名查找哈希表中的记录对应的关键码
	int Findphone(string phone);// 根据电话查找哈希表中的记录对应的关键码
	void Outhash(int key);// 输出哈希表中关键字码对应的一条记录
	void Outfile(string name, int key);// 在没有找到时输出未找到的记录
	void Rafile();// 随机生成文件，并将文件保存在 new.txt文档中
	void WriteToOldTxt();//在运行前先写入数据	

//private:
        DataInfo *value[HASH_MAXSIZE];
	int length;//哈希表长度
};

HashTable::HashTable():length(0)//默认构造函数
{
	//memset(value, NULL, HASH_MAXSIZE*sizeof(DataInfo*));
	for (int i=0; i<HASH_MAXSIZE; i++)
	{
		value[i] = new DataInfo();
	}
}

HashTable::~HashTable()//析构函数
{
	delete[] *value;
}

void HashTable::WriteToOldTxt()
{
	ofstream openfile("old.txt");
	if (openfile.fail())
	{
		cout << "文件打开错误！" << endl;
		exit(1);
	}

	string oldname;
        string oldphone;
	string oldaddress;

	for (int i=0; i<30; i++)
	{
		cout << "请输入第" << i+1 << "条记录:" << endl;		
		cin >> oldname ;
		cin >> oldphone;
		cin >> oldaddress;
		openfile << oldname << "  " << oldphone << "  " << oldaddress << "," << endl;
	}
	openfile.close();
}


int HashTable::Random(int key, int i)// 伪随机数探测再散列法处理冲突
{//key是冲突时的哈希表关键码，i是冲突的次数，N是哈希表长度
	//成功处理冲突返回新的关键码，未进行冲突处理则返回-1
	int h;
	if(value[key]->sign == '1')//有冲突
	{
		h = (key + D[i]) % HASH_MAXSIZE;
		return h;
	}
	return -1;
}

void HashTable::Hashname(DataInfo *dataInfo)//以名字为关键字建立哈希表
{//利用除留取余法建立以名字为关键字建立的哈希函数，在发生冲突时调用Random函数处理冲突
	int i = 0;	
	int key = 0;

        for (int t=0; dataInfo->name[t]!='\0'; t++)   
	{		
		key = key + dataInfo->name[t];
	}
	key = key % 42;
	while(value[key]->sign == '1')//有冲突
	{
		key = Random(key, i++);//处理冲突
	}
	if(key == -1) exit(1);//无冲突
	length++;//当前数据个数加
	value[key]->name = dataInfo->name;
	value[key]->address = dataInfo->address;
	value[key]->phone = dataInfo->phone;
	value[key]->sign = '1';//表示该位置有值
	//cout << value[key]->name << "  " << value[key]->phone << "  "  << value[key]->address << endl;
}

int HashTable::Rehash(int key, string str)// 再哈希法处理冲突
{//再哈希时使用的是折叠法建立哈希函数	
	int h;
	int num1 = (str[0] - '0') * 1000 + (str[1] - '0') * 100 + (str[2] - '0') * 10 + (str[3] - '0');
	int num2 = (str[4] - '0') * 1000 + (str[5] - '0') * 100 + (str[6] - '0') * 10 + (str[7] - '0');
	int num3 = (str[8] - '0') * 100  + (str[9] - '0') * 10  + (str[10] - '0');
	h = num1 + num2 + num3;
	h = (h + key) % HASH_MAXSIZE;
	return h;
}

void HashTable::Hashphone(DataInfo *dataInfo)//以电话为关键字建立哈希表
{//利用除留取余法建立以电话为关键字建立的哈希函数，在发生冲突时调用Rehash函数处理冲突
	int key = 0;	
	int t;
	
	for(t=0; dataInfo->phone[t] != '\0'; t++)
	{	
		key = key + dataInfo->phone[t];
	}
	key = key % 42;
	while(value[key]->sign == '1')//有冲突
	{
		key = Rehash(key, dataInfo->phone);
	}
	length++;//当前数据个数加
	value[key]->name = dataInfo->name;
	value[key]->address = dataInfo->address;
	value[key]->phone = dataInfo->phone;   
	value[key]->sign = '1';//表示该位置有值	
}

void HashTable::Outfile(string name, int key)//在没有找到时输出未找到的记录
{
	ofstream fout;
	if((key == -1)||(value[key]->sign == '0'))//判断哈希表中没有记录
	{
		fout.open("out.txt",ios::app);//打开文件

		if(fout.fail())
		{
			cout << "文件打开失败!" << endl;
			exit(1);
		}
		fout << name << endl;//将名字写入文件,有个问题，每次写入的时候总是将原来的内容替换了
		fout.close();
	}
}

void HashTable::Outhash(int key)//输出哈希表中关键字码对应的记录
{  
	if((key==-1)||(value[key]->sign=='0'))
		cout << "没有找到这条记录！" << endl;
	else
	{		
		for(unsigned int i=0; value[key]->name[i]!='\0'; i++)
		{
			cout << value[key]->name[i];			
		}

		for(unsigned int i=0; i<10; i++)
		{
			cout << " ";
		}

		cout << value[key]->phone;

		for(int i=0; i<10; i++)
		{
			cout << " ";
		}

		cout << value[key]->address << endl;
	}
}

void HashTable::Rafile()//随机生成文件，并将文件保存在new.txt文档中
{
	ofstream fout;
	fout.open("new.txt");//打开文件，等待写入
	if(fout.fail())
	{
		cout << "文件打开失败！" << endl;
		exit(1);
	}
	for(int j=0; j<30; j++)
	{		
		string name = "";
		for(int i=0; i<20; i++)//随机生成长个字的名字
		{
			name += rand() % 26 + 'a';//名字是由个字母组成			
		}
		fout << name << "   ";//将名字写入文件

		string phone = "";
		for(int i=0; i<11; i++)//随机生成长位的电话号码
		{
			phone += rand() % 10 + '0';//电话号码是纯数字
		}
		fout << phone << "      ";//将电话号码写入文件

		string address = "";
		for(int i=0; i<29; i++)//随机生成长个字的名字
		{
			address += rand() % 26 + 'a';//地址是由个字母组成
		}
		address += ',';
		fout << address << endl;//将地址写入文件
	}
	fout.close();
}

void HashTable::Hash(char *fname, int n)//建立哈希表
//fname是数据储存的文件的名称，用于输入数据，n是用户选择的查找方式
//函数输入数据，并根据选择调用Hashname或Hashphone函数进行哈希表的建立
{
	ifstream fin;		
	int i;
	fin.open(fname);//读文件流对象
	if(fin.fail())
	{
		cout << "文件打开失败！" << endl;
		exit(1);
	}
	while(!fin.eof())//按行读入数据
	{
		DataInfo *dataInfo = new DataInfo();
		char* str = new char[100];		
		fin.getline(str, 100, '\n');//读取一行数据

		if(str[0] == '*')//判断数据结束
		{
			break;
		}

		i = 0;//记录字符串数组的下标
		//a-z:97-122     A-Z:65-90    
		//本程序的姓名和地址都使用小写字母
		while((str[i] < 97) || (str[i] > 122))//读入名字
		{
			i++;
		}

		for(; str[i]!=' '; i++)
		{			
			dataInfo->name += str[i];			
		}

		while(str[i] == ' ')
		{
			i++;
		}

		for(int j=0; str[i]!=' '; j++,i++)//读入电话号码
		{			
			dataInfo->phone += str[i];
		}

		while(str[i] == ' ')
		{
			i++;
		}

		for(int j=0; str[i]!=','; j++,i++)//读入地址
		{			
			dataInfo->address += str[i];
		}

		if(n == 1)
		{			
			Hashname(dataInfo);
		}
		else
		{			
			Hashphone(dataInfo);//以电话为关键字
		}

		delete []str;
		delete dataInfo;
	}	
	fin.close();
}

int HashTable::Findname(string name)//根据姓名查找哈希表中的记录对应的关键码
{
	int i = 0;
	int j = 1;
	int t;
	int key = 0;
	
	for(key=0, t=0; name[t] != '\0'; t++)
	{
		key = key + name[t];
	}
	key = key % 42;
	while((value[key]->sign == '1') && (value[key]->name != name))
	{  
		key = Random(key, i++);
		j++;
		if(j >= length) return -1;
	}
	return key;
}

int HashTable::Findphone(string phone)//根据电话查找哈希表中的记录对应的关键码
{  
	int key = 0;
	int t;
	
	for(t=0; phone[t] != '\0' ; t++)
        {
                key = key + phone[t];
        }
	key = key % 42;
	int j = 1;
	while((value[key]->sign == '1') && (value[key]->phone != phone))
	{
		key = Rehash(key, phone);
		j++;
		if(j >= length) 
                {
                    return -1;
                }
        }
	return key;
}

void main()
{
	//WriteToOldTxt();	
	int k;
	int ch;	
	char *Fname;
	HashTable *ht = new HashTable;
	while(1)
	{
		system("cls");//cls命令清除屏幕上所有的文字
		cout << "欢迎使用本系统！" << endl << endl;
		cout << "请选择数据" << endl;
		cout << "1.使用已有数据文件" << endl;
		cout << "2.随机生成数据文件" << endl;
		cout << "0.结束" << endl;
		cout << "输入相应序号选择功能：";
		cin >> k;
		switch(k)
		{
		case 0:
			return;
		case 1:
			Fname = "old.txt";//从数据文件old.txt(自己现行建好)中读入各项记录
			break;
		case 2:
			ht->Rafile();
			Fname = "new.txt";//由系统随机产生各记录，并且把记录保存到new.txt文件中
			break;
		default:
			cout << "输入序号有误，退出程序。" << endl;	
			return;
		}

		do
		{
			system("cls");
			cout << " 请选择查找方式" << endl;
			cout << "1.通过姓名查找" << endl;
			cout << "2.通过电话查找" << endl;
			cout << "输入相应序号选择功能：";
			cin >> ch;
			if((ch != 1) && (ch != 2))
				cout << "输入序号有误！" << endl;
		}while((ch != 1) && (ch != 2));

		ht->Hash(Fname, ch);
		while(ch == 1)
		{
			int choice;
			cout << endl << "请选择功能" << endl;
			cout << "1.输入姓名查找数据" << endl;
			cout << "2.显示哈希表" << endl;
			cout << "0.退出"<<endl;
			cout << "输入相应序号选择功能：";
			cin >> choice;
			switch(choice)
			{
			case 1:	
				{//注意此处应该加上大括号
					int key1;					
					string name;					
					cout << "请输入姓名：";
					cin >> name;					
					key1 = ht->Findname(name);
					ht->Outfile(name, key1);
					ht->Outhash(key1);	
				}
				break;

			case 2:	
				{
					for(int i=0; i<HASH_MAXSIZE; i++)
					{
						if(ht->value[i]->sign!='0')
						{
							ht->Outhash(i); 
						}
					}	
				}							
				break;


			default:
				cout << endl << "您的输入有误！" << endl;				
			}

			if(choice == 0) 
			{
				return;
			}
		}

		while(ch == 2)
		{
			int choice;
			cout << endl << "请选择功能" << endl;
			cout << "1.输入电话查找数据" << endl;
			cout << "2.显示哈希表"<<endl;
			cout << "0.退出"<<endl;
			cout << "输入相应序号选择功能：";
			cin >> choice;
			switch(choice)
			{
			case 1:	
				{
					int key2;					
					string phone;					
					cout << "请输入11位的电话号码：";
					
					do
					{
						cin >> phone;						
						if(phone.length() != 11)					
						{
							cout << "电话号码应为11位！\n请重新输入：";
						}
							
					}while(phone.length() != 11);
					
					key2 = ht->Findphone(phone);
					ht->Outfile(phone, key2);
					ht->Outhash(key2);
				}
				break;

			case 2:	
				{
					for(int i=0; i<HASH_MAXSIZE; i++)
					{
						if(ht->value[i]->sign != '0') 
						{
							ht->Outhash(i); 
						}
					}
				}				
				break;

			default:
                 cout << endl << "您的输入有误！" << endl;				 
			}

			if(choice == 0) 
			{
				return;
			}
		}

		while((ch != 1) && (ch != 2))
		{
			cout << "您的输入有误！请输入相应需要选择功能：";
		}
	}
	system("pause");	
}