#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#define HASH_LENGTH    50           //哈希表的長度         
#define M 47                        //隨機數        
typedef struct      
{   char py[19];    //名字的拼音
    int k;       //拼音所對應的整數
}NAME;
NAME NameList[HASH_LENGTH];    //全局變量NAME       
typedef struct    //哈希表
{   char *py;   //名字的拼音
    int k;      //拼音所對應的整數
    int si;     //查找長度
}HASH;
HASH HashList[HASH_LENGTH];        //全局變量HASH                     
void InitNameList(int NAME_NO) //姓名（結構體數組）初始化           
{   char *f;int count=1;
    int r,s0,i;
	for(i=0;i<NAME_NO;i++)
	{
		printf("輸入第%d個人名：",count);count++;
		scanf("%s",&NameList[i].py);
	} 
    for(i=0;i<NAME_NO;i++)
	{   s0=0;
        f=NameList[i].py;
        for(r=0;*(f+r)!='\0';r++) 
			//將字符串的各個字符所對應的ASCII碼相加，所得的整數做為哈希表的關鍵字
            s0=*(f+r)+s0;
        NameList[i].k=s0;
	} 
}
void CreateHashList(int LENGTH,int NAME_NO ) //建立哈希表   
{	int i;
    for(i=0; i<LENGTH;i++) 
	{   HashList[i].py="";
        HashList[i].k=0;
        HashList[i].si=0;
	}
    for(i=0;i<NAME_NO ;i++)
	{   int sum=0;
        int adr=(NameList[i].k)%M;  //哈希函數，用除留余數法構造
        int d=adr;
        if(HashList[adr].si==0)     //如果不沖突
		{  HashList[adr].k=NameList[i].k;
           HashList[adr].py=NameList[i].py;
           HashList[adr].si=1;
	   }
       else   //沖突  
	   { do
		  {   d=(d+NameList[i].k%10+1)%M;   //偽隨機探測再散列法處理沖突    
              sum=sum+1;                    //查找次數加1    
		  }while (HashList[d].k!=0);
         HashList[d].k=NameList[i].k;
         HashList[d].py=NameList[i].py;
         HashList[d].si=sum+1;
	   }
	}
}
void  SearchList() //查找    
{
	char name[19]={0}; 
    int s0=0,r,sum=1,adr,d;
    printf("請輸入姓名的拼音:");     
    scanf("%s",name); 
    for(r=0;r<19;r++)   //求出姓名的拼音所對應的整數(關鍵字)
        s0+=name[r]; 
    adr=s0%M;   //使用哈希函數
    d=adr;
    if(HashList[adr].k==s0)          //分3種情況進行判斷
       printf("\n姓名:%s   關鍵字:%d   查找長度為: 1",HashList[d].py,s0); 
    else if (HashList[adr].k==0) 
         printf("無此記錄!");
    else
	{   int g=0;
        do
		{   d=(d+s0%10+1)%M;       //偽隨機探測再散列法處理沖突                     
            sum=sum+1;
            if(HashList[d].k==0)
			{  printf("無此記錄! ");  
               g=1;     
			}
            if(HashList[d].k==s0)
			{  printf("\n姓名:%s   關鍵字:%d   查找長度為:%d",HashList[d].py,s0,sum); 
               g=1;  
			}
		}while(g==0);   
	}  
}
void   Display(int NAME_NO ) // 顯示哈希表       
{	int i;
    float average=0;
    printf("\n地址\t關鍵字\t\t搜索長度\tH(key)\t 姓名\n"); //顯示的格式
    for(i=0; i<50; i++)
	{   printf("%d ",i); 
        printf("\t%d ",HashList[i].k);
        printf("\t\t%d ",HashList[i].si);
        printf("\t\t%d ",HashList[i].k%M);
        printf("\t %s ",HashList[i].py);
        printf("\n");
	}
    for(i=0;i<HASH_LENGTH;i++)
        average+=HashList[i].si; 
    average/=NAME_NO;
    printf("\n平均查找長度：ASL(%d)=%f \n",NAME_NO,average); 
}
void main()
{
	char ch1;
	int NAME_NO;
    printf("要輸入的人名個數（不超過30個）：");
	scanf("%d",&NAME_NO);
	InitNameList( NAME_NO);
    CreateHashList(HASH_LENGTH,NAME_NO ); 
	do
	{   printf("--------------------------哈希表設計--------------------------\n");
	    printf("1. 顯示哈希表\n2. 查找\n0. 退出\n請選擇：");
		cin>>&ch1;
		switch(ch1)
		{
		case '1':Display(NAME_NO); cout<<endl;break;
	    case '2':SearchList();cout<<endl;break;
		case '0':exit(0);
		}
		cout<<"Go on ?(y/n):";
		cin>>&ch1;
	}while(ch1!='n'); 
}