hashlist.cpp

hashtable 测试可用 包含数据 数据可以自行修改

/* 2005-03-05 ---------------------------------------------------------------------
  实验内容：
	  针对某个集体（比如所在班级）中的人名设计一个哈希表，使的平均查找的长度不超过2
	  完成相应的建表和查表的程序
  实验要求：
      假设人名为姓名的汉语拼音形式，待填入哈希表的人名工有30个，取平均查找长度的上限
	  为2。哈希函数用除留余数法构造，用伪散列探测再散列法处理冲突。
  测试数据
      自定义。 
-----------------------------------------------------------------------------------*/

#include <stdio.h>
#include<conio.h>
#include<string.h>
#include<windows.h> 

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