hash+1.txt

哈希表设计..针对某个集体中的30个人名设计一个哈希表,使得平均查找长度为2.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#include 

#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) != NULL;r++) //方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
			s0=*(f+r)+s0;
  
		NameList[i].k=s0;
	} 
}

/*-----------------------建立哈希表---------------------------------*/
void CreateHashList()    
{
	for (int i=0; i<NAME_NO; 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下能看到所有的数据）
	getchar();
	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");
	getchar();
	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");
	getchar();
	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 <NAME_NO;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=getchar();
		if (ch1='1')  
			Display();   
		else if (ch1='2') 
			FindList();
		else if (ch1='3') 
			return;
		else 
		{ 
			printf("\n请输入正确的选择!"); 
			goto err; 
		}
	}
}