哈希表的建立和查找

建立哈希表的相关函数，用线性探查和二次探查解决冲突

#include 
#include 
#include 
#include 
#define N 1000   //表长
using namespace std;
void InsertHash（char str[]）;//创建hash表
bool SearchHash（char str[]）;//查找hash表
struct HashTable
{
	char elem[20];//记录字符串
	int count;//当前字符串字符个数
}myHashTable[N];
int chongtucishu1=0;
int chongtucishu2=0;
int g=31;//底数

void InsertHash（char str[]）{//创建hash表

	int value=int（str[0]）;
	int num=strlen（str）;

	for（int i=1;i		value=（value*g+int（str[i]））%10000;
	}

	int k=value%N;//记录字符串插入的位置
	//for（int i=k;i	//	int flag=i%N;
	//	if（myHashTable[flag].count==0）{
	//		myHashTable[flag].count=num;
	//		strcat（myHashTable[flag].elemstr）;
	//		return ;
	//	}
	//	chongtucishu1++;
	//}
	for（int j=1;;j++）{//二次探查
		int flag1=k+j*j;
		int flag2=k-j*j;
		if（flag1>=N）
			flag1%=N;
		while（flag2<0）{
			flag2+=N;
		}
		if（myHashTable[flag1].count==0）{
			myHashTable[flag1].count=num;
			strcat_s（myHashTable[flag1].elemstr）;
			return ;
		}
		if（myHashTable[flag2].count==0）{
			myHashTable[flag2].count=num;
			strcat_s（myHashTable[flag2].elemstr）;
			return ;
		}
		chongtucishu2++;
	}
}
bool SearchHash（char str[]）{
	int value=int（str[0]）;
	int num=strlen（str）;
	for（int i=1;i		value=（value*g+int（str[i]））%10000;
	}
	int k=value%N;//记录字符串最开始查找的位置
	//for（int i=k;i	//	int flag=i%N;
	//	int biaozhi=1;
	//	for（int j=0;j	//		if（str[j]!=myHashTable[flag].elem[j+1]）
	//			biaozhi=0;
	//	}
	//	if（biaozhi&&myHashTable[flag].count!=0）{
	//		return true;
	//	}
	//	if（myHashTable[flag].count==0）{
	//		return false;
	//	}
	//}
	for（int j=1;;j++）{//二次探查
		int flag1=k+j*j;
		int flag2=k-j*j;
		if（flag1>=N）
			flag1%=N;
		while（flag2<0）{
			flag2+=N;
		}
		int biaozhi_1=1;
		int biaozhi_2=1;
		int biaozhi=1;
		for（int j=0;j			if（str[j]!=myHashTable[flag1].elem[j+1]）
				biaozhi_1=0;
		}
		for（int j=0;j			if（str[j]!=myHashTable[flag2].elem[j+1]）
				biaozhi_2=0;
		}
		biaozhi=biaozhi_1+biaozhi_2;
		if（myHashTable[flag1].count!=0&&biaozhi）{
			return true;
		}
		if（myHashTable[flag2].count!=0&&biaozhi）{
			return true;
		}
		if（myHashTable[flag1].count==0&&myHashTable[flag2].count==0）{
			return false;
		}
	}
	return false;
}
void main（）{
	ifstream inFile（“data.txt“）;//打开字符串文件
	//初始化hash表
	for（int i=0;i		myHashTable[i].count=0;
		strcat_s（myHashTable[i].elem“ “）;
	}
	char str[20];
	while（!inFile.eof（））{	
		inFile.getline（str20‘\n‘）;
		InsertHash（str）;
	}

	/*cout<<“线性探查冲突次数:“<	cout<<“二次探查冲突次数:“<	char SearchStr[20]={‘\0‘};
	char select=‘0‘;
	do{
		cout<<“0:exit   1:InputWord“<		cin>>select;
		switch（select）{
		case ‘0‘:
			break;
		case ‘1‘:
			{
				cout<<“输入待查找单词:“;
				cin>>SearchStr;
				bool flag=SearchHash（SearchStr）;
				if（flag）{
					cout<<“查找成功“<

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2015-05-29 21:39  HashFunction\
     文件        3874  2015-05-27 22:43  HashFunction\data.txt
     目录           0  2015-05-29 21:38  HashFunction\Debug\
     文件         444  2015-05-29 21:38  HashFunction\Debug\cl.command.1.tlog
     文件       12434  2015-05-29 21:38  HashFunction\Debug\CL.read.1.tlog
     文件         222  2015-05-29 21:38  HashFunction\Debug\CL.write.1.tlog
     文件      272223  2015-05-29 21:38  HashFunction\Debug\Hash.obj
     文件       99840  2015-05-29 21:38  HashFunction\Debug\HashFunction.exe
     文件      910492  2015-05-29 21:38  HashFunction\Debug\HashFunction.ilk
     文件          59  2015-05-29 21:38  HashFunction\Debug\HashFunction.lastbuildstate
     文件        1278  2015-05-29 21:38  HashFunction\Debug\HashFunction.log
     文件     1043456  2015-05-29 21:38  HashFunction\Debug\HashFunction.pdb
     文件           2  2015-05-29 21:38  HashFunction\Debug\link-cvtres.read.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link-cvtres.write.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link-rc.read.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link-rc.write.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link.4024-cvtres.read.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link.4024-cvtres.write.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link.4024-rc.read.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link.4024-rc.write.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link.4024.read.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link.4024.write.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link.5560-cvtres.read.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link.5560-cvtres.write.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link.5560-rc.read.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link.5560-rc.write.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link.5560.read.1.tlog
     文件           2  2015-05-29 21:38  HashFunction\Debug\link.5560.write.1.tlog
     文件        1010  2015-05-29 21:38  HashFunction\Debug\link.command.1.tlog
     文件        2404  2015-05-29 21:38  HashFunction\Debug\link.read.1.tlog
     文件         356  2015-05-29 21:38  HashFunction\Debug\link.write.1.tlog
............此处省略10个文件信息