#include <stdio.h>
#include <malloc.h>
#include <process.h>
#include <iostream.h>
 
#define NULL_KEY 0
#define OVERFLOW -3
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
#define OK 1
#define ERROR 0
#define N 10

#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))

typedef int Status;


int hashsize[]={11,19,29,37};
int m;

typedef struct 
{
	int *elem;
	int count;
	int sizeindex;
}HashTable;

void InitHashTable(HashTable *H)
{
	H->count=0;
	H->sizeindex=0;
	m=hashsize[0];
	H->elem=(int *)malloc(m*sizeof(int));
	if(!H->elem)
		exit(OVERFLOW); 
	for(int i=0;i<m;i++)
		H->elem[i]=NULL_KEY; 
}

/*void DestroyHashTable(HashTable *H)
{

	free(H->elem);//?????
	H->elem=NULL;
	H->count=0;
	H->sizeindex=0;
} */

int Hash(int k)
{
	return k%m;
}

void collision(int &p,int collision)
{
	p=(p+collision)%m;
} 


Status SearchHash(HashTable *H,int key,int &p,int &c)
{
	p=Hash(key);
	int q=p;
	while(H->elem[p]!=NULL_KEY && !EQ(key,H->elem[p]))
	{
		p=q;
		c++;
		collision(p,c);
	}
	if EQ(key,H->elem[p])
		return SUCCESS;
	else
		return UNSUCCESS;

}

void TraverseHash(HashTable *H)
{
	for(int i=0;i<m;i++)
		if(H->elem[i]!=NULL_KEY)
			cout<<"adress"<<"("<<i<<")"<<"="<<H->elem[i]<<endl;

}

//void RecreateHashTable();

Status InsertHash(HashTable *H,int k)
{
	int p;
	int c=0;
	if(SearchHash(H,k,p,c))
		return DUPLICATE;
	else if(c<hashsize[(*H).sizeindex]/2) 
	{ 
		(*H).elem[p]=k;
		++(*H).count;
		return OK;
	}
	else
		//RecreateHashTable(H); 
	return ERROR;
}

void RecreateHashTable(HashTable *H)
{
	int i,num;
	num=H->count;			//num為原哈希表中的記錄數目
	int *p=(int*)malloc(num*sizeof(int));
	int *t=p;
	printf("重建哈希表\n");
	for(i=0;i<m;i++)		//保存原有的數據到p中 
		if((H->elem[i])!=NULL_KEY) // 該單元有數據 
		{
			*p=H->elem[i];
			p++;
		}
		H->count=0;
		H->sizeindex++;			//增大存儲容量 
		m=hashsize[H->sizeindex];
		int *elem=(int*)malloc(m*sizeof(int));
		if(!elem)
			exit(OVERFLOW);		//存儲分配失敗
		for(i=0;i<m;i++)
			H->elem[i]=NULL_KEY; //未填記錄的標志(初始化)
		for(i=0;i<num;i++)		//將原有的數據按照新的表長插入到重建的哈希表中
		{
			InsertHash(H,*t);
			t++;
		}
}  

Status Find(HashTable *H,int key,int &p)
{
	int c=0;
	p=Hash(key);
	int q=p;
	while(H->elem[p]!=NULL_KEY && !EQ(key,H->elem[p]))
	{
		c++;
		p=q;
		collision(p,c);
	}
	if EQ(key,H->elem[p])
		return SUCCESS;
	else
		return UNSUCCESS;
}
int main()
{
	int r[N]={17,60,29,38,60,2,3,4,1,13};//查找表
	HashTable h;
	int i,p;
	Status j;
	int k;
	InitHashTable(&h);
	for(i=0;i<N;i++)  //插入前N-1個記錄
	{ 
		j=InsertHash(&h,r[i]);
		if(j==DUPLICATE)
			cout<<"表中已有關鍵字為"<<r[i]<<"的記錄,無法再插入記錄"<<r[i]<<endl;
		if(j==OK)
			cout<<r[i]<<"插入成功!"<<endl;
		if(j==ERROR)
		{
			cout<<r[i]<<"在插入過程中，沖突次數過大，所以重建哈希表"<<endl;
			RecreateHashTable(&h);
			j=InsertHash(&h,r[i]);
		}
	}
	cout<<"按哈希地址的順序遍歷哈希表:"<<endl;
	TraverseHash(&h);
	
	cout<<"請輸入待查找記錄的關鍵字: "<<endl;
	//while(getchar()!='a')
	//{
		cin>>k;
		j=Find(&h,k,p); //查找
		if(j==SUCCESS)
			cout<<"adress"<<p<<"is"<<h.elem[p]<<endl;
		//print(p,h.elem[p]);
		else
			cout<<"沒找到"<<endl;
	//}

	cout<<"要插入的關鍵字"<<endl;
	cin>>k;
	j=InsertHash(&h,k); //插入記錄 
	if(j==ERROR) // 重建哈希表 
	{
		RecreateHashTable(&h);
		j=InsertHash(&h,k); // 重建哈希表后重新插入記錄
		cout<<"按哈希地址的順序遍歷重建后的哈希表:"<<endl;
		TraverseHash(&h);
	}
	if(j==DUPLICATE)
		cout<<"表中已有關鍵字為<<r[i]<<的記錄,無法再插入記錄r[i]"<<endl;
	if(j==OK)
		cout<<"插入成功!"<<endl;
	TraverseHash(&h);
	//cout<<h.elem[1];
//	DestroyHashTable(&h);

	return 0;
}