#define HASH_LEN 50                     //哈希表的长度         
#define M 47                            
#define NAME_NO 30                     //人名的个数        

typedef struct NAME       
{
 char *py;   //名字的拼音
 int k;      //拼音所对应的整数
}NAME;
NAME NameList[HASH_LEN];                 

typedef struct  hterm    //哈希表
{
 char *py;  //名字的拼音
 int k;     //拼音所对应的整数
 int si;    //查找长度
}HASH;
HASH HashList[HASH_LEN];                            

/*-----------------------姓名（结构体数组）初始化---------------------------------*/
void InitNameList()               
{
 NameList[0].py="chenghongxiu";
 NameList[1].py="yuanhao";
 NameList[2].py="yangyang";
 NameList[3].py="zhanghen";
 NameList[4].py="chenghongxiu";
 NameList[5].py="xiaokai";
 NameList[6].py="liupeng";
 NameList[7].py="shenyonghai";
 NameList[8].py="chengdaoquan";
 NameList[9].py="ludaoqing";
 NameList[10].py="gongyunxiang";
 NameList[11].py="sunzhenxing";
 NameList[12].py="sunrongfei";
 NameList[13].py="sunminglong";
 NameList[14].py="zhanghao";
 NameList[15].py="tianmiao";
 NameList[16].py="yaojianzhong";
 NameList[17].py="yaojianqing";
 NameList[18].py="yaojianhua";
 NameList[19].py="yaohaifeng";
 NameList[20].py="chengyanhao";
 NameList[21].py="yaoqiufeng";
 NameList[22].py="qianpengcheng";
 NameList[23].py="yaohaifeng";
 NameList[24].py="bianyan";
 NameList[25].py="linglei";
 NameList[26].py="fuzhonghui";
 NameList[27].py="huanhaiyan";
 NameList[28].py="liudianqin";
 NameList[29].py="wangbinnian";
 
 char *f;
 int r,s0;
 
 for (int 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()    
{
 for (int i=0; i<HASH_LEN;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  FindList()     
{ 
 printf("\n\n请输入姓名的拼音:   ");    //输入姓名
 char name[20]={0}; 
 scanf("%s",name); 
 
 int s0=0;
 for (int r=0;r<20;r++)    //求出姓名的拼音所对应的整数(关键字)
  s0+=name[r]; 
 
 int sum=1;
 int adr=s0 % M;  //使用哈希函数
 int 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()         
{
   printf("\n\n地址\t关键字\t\t搜索长度\tH(key)\t\t拼音 \n"); //显示的格式

 for(int i=0; i<15; 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");
 }

 printf("按任意键继续显示...\n");  //由于数据比较多，所以分屏显示（以便在Win9x／DOS下能看到所有的数据）
 getch();
 for( i=15; i<30; 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");
 }

 printf("按任意键继续显示...\n");
 getch();
 for( i=30; i<40; 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");
 }

 printf("按任意键继续显示...\n");
 getch();
 for( i=40; 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");
 }
 
 float average=0;
 for (i=0;i<HASH_LEN;i++)
  average+=HashList[i].si; 
 average/=NAME_NO;
 printf("\n\n平均查找长度：ASL(%d)=%f \n\n",NAME_NO,average); 
}

/*--------------------------------主函数----------------------------*/
void main()
{
/*  ::SetConsoleTitle("哈希表操作");       //Windows API函数,设置控制台窗口的标题
 HANDLE hCon = ::GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备的句柄
 ::SetConsoleTextAttribute(hCon, 10|0);   //设置文本颜色
*/
 printf("\n------------------------哈希表的建立和查找----------------------");
 InitNameList();                                
 CreateHashList ();                        
 
 while(1)
 {
  printf("\n\n");
  printf("    1. 显示哈希表\n"); 
  printf("    2. 查找\n"); 
  printf("    3. 退出\n");
  
err:  
  char ch1=getch();
  if (ch1=='1')  
   Display();   
  else if (ch1=='2') 
   FindList();
  else if (ch1=='3') 
   return;
  else
  {
   printf("\n请输入正确的选择!");
   goto err;
  }
 }
}