哈希表设计.cpp

假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个

#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'); 
}