实验十三.cpp

针对某个集体（比如你所在的班级）中的“人名”设计 一个哈希表

#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="shaoxingchi";
NameList[1].py="chenshijie";
NameList[2].py="chenxi";
NameList[3].py="chencheng";
NameList[4].py="tangjianwei";
NameList[5].py="hujinjun";
NameList[6].py="guoyifeng";
NameList[7].py="yuanzhencheng";
NameList[8].py="xihuineng";
NameList[9].py="maozhenzhong";
NameList[10].py="fanyuming";
NameList[11].py="zhangcheng";
NameList[12].py="zhangyang";
NameList[13].py="zhangjianfeng";
NameList[14].py="ruanxiqi";
NameList[15].py="zhanglinjun";
NameList[16].py="yanghui";
NameList[17].py="ruigongliang";
NameList[18].py="wangyazhou";
NameList[19].py="wangjun";
NameList[20].py="wangzhenyu";
NameList[21].py="wangxincheng";
NameList[22].py="tianzhihua";
NameList[23].py="liumengjun";
NameList[24].py="shichunhui";
NameList[25].py="mouhongyu";
NameList[26].py="xvguoqi";
NameList[27].py="zhuqing";
NameList[28].py="yaoyuqing";
NameList[29].py="yufengqi";

	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; 
		}
	}
}