#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#define HASHLEN 16             //哈希表的長度         
#define	P 13                         //小于20的質數
#define NUM 12                   //數據的個數        

 typedef struct    //哈希表結構
{   
	int key;      //關鍵字
	int len;     //查找長度
}	HASH;         

HASH HashList[HASHLEN];        //HASH變量                     

typedef struct LNode               //結點類型結構
{
	int data;                    
    struct LNode *next;
}LNode, List[HASHLEN];


int NumList[NUM];    //數組變量  

void InitNumList() //數組初始化          
{ 
	NumList[0]=34;
	NumList[1]=13;
	NumList[2]=25;
	NumList[3]=1;
	NumList[4]=61;
	NumList[5]=24;
	NumList[6]=86;
	NumList[7]=27;
	NumList[8]=52;
	NumList[9]=18;
	NumList[10]=10;
	NumList[11]=79;
}


void CreateHashList_1() //線性再散列法   
{	
	int i,di;                      //增量序列di
	float average=0;              //平均查找長度
	for(i=0; i<HASHLEN;i++) 
	{   
		HashList[i].key=0;     //關鍵字初始化
		HashList[i].len=0;    //查找長度初始化
	}
	for(i=0;i<NUM;i++)
	{  
		int sum=0;                  //查找長度
		int adress=(NumList[i])%P;  //用除留余數法確定地址
		int a=adress;
			if(HashList[a].key==0)     //如果不沖突
			{  
				HashList[a].key=NumList[i];
				HashList[a].len=1;
			}
			else   //沖突  
			{	
				di=1;
				do
				{   
					a=(adress+di)%HASHLEN;   //線性探測再散列法處理沖突    
					sum++; 
					di++;                   //查找次數加1    
				}
				while (HashList[a].key!=0);
					HashList[a].key=NumList[i];
					HashList[a].len=sum+1;		//查找長度賦值
			}
	}
	printf(" \n\n地址\t\t數據\t\t搜索長度\t哈希地址\n"); //顯示哈希表
		for(i=0; i<HASHLEN; i++)
		{   
			printf("%d ",i); 
			printf("\t\t%d ",HashList[i].key);
			printf("\t\t%d ",HashList[i].len);
			printf("\t\t%d ",HashList[i].key%P);
			printf("\n");
		}
		for(i=0;i<HASHLEN;i++)                         //計算平均長度
			average+=HashList[i].len; 
			average/=NUM;
			printf("\n平均查找長度ASL為：(%d)=%f \n",NUM,average); 
}





void CreateHashList_2()					//鏈地址法  
{
	int i,t;                            //c存放查找次數
	int sum=0;			
	float average;
	struct LNode *s;					//創建結點指針
	struct LNode *M[HASHLEN] ;			//指針數組存放表頭

	for(i=0; i<HASHLEN;i++)				//將各鏈表表頭元素賦空值
		M[i]=NULL;


	for(i=0;i<NUM;i++)
	{   
		int adress=(NumList[i])%P;					 //除留余數法構造哈希函數
		int a=adress;
		s=(LNode *)malloc (sizeof(LNode));				
		if(s!=NULL)								//結點空間申請成功
			s->data=NumList[i];
			s->next=M[a];
			M[a]=s;
	}
	
	for(i=0;i<NUM;i++)
	{   
		t=1;
		int adress=(NumList[i])%P;					 //除留余數法構造哈希函數
	    int a=adress;
		s=M[a];
		
		while(s->data!=NumList[i])			    //查找元素不匹配
		{
			s=s->next;                          //繼續查找
			t++;								//查找次數+1
		}
		sum=sum+t;                              //記錄下總的查找次數
	}
	average=(float)sum/NUM;
	
		
	printf("\n\n\n");
	printf("\t哈\t希\t表\n\n");
	printf("哈希地址\t\t數據\n");

	for(i=0;i<HASHLEN;i++)
	{
		s=M[i];
		printf("%5d",i);
		printf("\t\t");

		while(s!=NULL)
		{
			printf("%4d",s->data);
			s=s->next;
		}

		printf("\n");

	}

	printf("\n\n");
	printf("平均查找長度ASL為：(%d)=%f",NUM,average);

}







void main()
{	
	char ch1;
	InitNumList();                                
	do
	{	
		printf("\t\t\t請 選 擇 操 作 類 型:\n\n");
		printf("\t\t\t1. 線 性 再 散 列 法\n\t\t\t2. 鏈 地 址 法\n\t\t\t0. 退 出\n\t\t請選擇:");
		cin>>&ch1;
		switch(ch1)
		{
		case '1':CreateHashList_1();cout<<endl;break;
		case '2':CreateHashList_2();cout<<endl;break;
		case '0':exit(0); 
		default :cout<<"\t\t\t錯誤選項!\n\n";
		}
		printf("\n\n");
		cout<<"是否繼續?(y/n):";
		cin>>&ch1;
		printf("\n\n\n");
	}while(ch1!='n'); 
}