心若明镜,哈希从容

实现哈希表的构造和查找算法，要求：用除留余数法构造哈希函数，分别用一次探测再散列、二次探测再散列解决冲突。

想法：有构造哈希表，查找元素，插入一个元素，如果查找到一个哈希表里面没有的元素应该插入到哈希表中。

小小希望：如果你的题目与我的完全一样！！！就不要完全照抄，对你对我都不好！！！函数功能都是完整的。。。

线性探测
H(i)=（H(key)+di）%m (di = 1 2 3 4 - - - m-1.)
从发生冲突的位置开始，依次继续向后探测，直到有空位置。
插入时：使用哈希函数找到待插入元素在哈希表中的位置，如果该位置没有元素则直接插入，如果该位置有元素但不是待插入元素则发生哈希冲突，使用线性探测找到下一个空位置，在找空位置的路上如果遇到元素与待插入元素相同则不插入（即哈希表中不允许有相同的元素），没有遇到等找到空位置就插入。

.二次探测
发生哈希冲突时，二次探测寻找下一个空位置的公式为：H(i)=（H(key)+di）%m
di = 1^2 , -1^2, 2^2 ,.-2^2, - - -(+-)k^2.(K<=m/2),其中m都是表示表长。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define max 14
#define casue 13
#define DataType int
typedef struct Hash{
	int findnum;
	DataType key;
}Hash;

void Createhash(Hash *hash,int kind)
{
	printf("How many data you want to input ? \n");
	int num,data;
	int j,count=0;
	scanf("%d",&num);
	while(num>max){
		printf("out of the hash list's max capacity !\n");
		printf("please input again !\n");
		scanf("%d",&num);
	};
	getchar();
	int p=1,q=1;
	for(int i=0;i<num;i++){
		printf("input the %d data\n",i+1);
		scanf("%d",&data);
		getchar();
		if(kind==1){//一次探测再散列
			do{
				j = (data+count)%casue;
				count++;
				if(hash[j].key == 0){
					hash[j].key=data;
					hash[j].findnum=count;
					count=0;
				}
			}while(count!=0);
		}else{//二次探测再散列解决冲突
			do{
				j=data%casue;
				if(count>0){//有冲突 
					if(count%2==1){
						j+=pow(q,2);
						q++;
					}else{
						j-=pow(p,2);
						p++;
					}
				}
				count++;
				if(j<0){
					j += max;
				}else if(j>max){
					j %= max;
				}
				else{
					if(hash[j].key == 0){
						hash[j].key=data;
						hash[j].findnum=count;
						count=0;
					}
				}
			}while(count!=0);
		}
	}	
}

void insert(Hash *hash,int data,int insert,int count){
	hash[insert].key = data;
	hash[insert].findnum = count;
}

int findkey(Hash *hash , int k,int kind)
{
	int j,i=0;
	bool find = true;
	if(kind == 1){
		do{
			j = (k+i)%casue;
			if(hash[j].key == k){
				find = false;
			}else if(hash[j].key == 0){
				find = false;////没有找到
				insert(hash,k,j,i+1);//插入
				j=-1;
			}
			i++;
			if(i>max){
				printf("hash list is full\n");
				exit(0);
			}
		}while(find);
	}else{
		int p=1,q=1,count=0;
		do{
			j=k%casue;
			//奇偶判断 
			if(count>0){//有冲突 
				if(count%2==1){
					j+=pow(q,2);
					q++;
				}else{
					j-=pow(p,2);
					p++;
				}
			}
			count++;
			if(j<0){
				j+=max;
			}else if(j>max){
					j %= max;
			}else{
				if(hash[j].key == k){
					find = false;
				}else if(hash[j].key == 0){
					find = false;//没有找到
					insert(hash,k,j,count);
					j=-1;//查找不成功 没有该元素
				}
			}
			if(count>max){
				printf("hash list is full\n");
				exit(0);
			}
		}while(find);
	}
	return j;
}

int main()
{
	Hash hash[max];
	int kind;
	printf("1.一次探测再散列 2.二次探测再散列解决冲突\n");
	scanf("%d",&kind);
	Createhash(hash,kind);
	printf("which key do you want find ?\n"); 
	scanf("%d",&k);
	getchar();
	int i = findkey(hash,k,kind);//i=-1则就是没有该元素这里的判断被我删了
	printf("address: %d data: %d findnum: %d \n",i,hash[i].key,hash[i].findnum);
	return 0;
}