哈希谢海良.cpp

数据结构课程设计 哈希表的创建和实现 c语言源码 文字注解等 适合正在学习数据结构的人士参考学习

#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#define HASHLEN 16             //哈希表的长度         
#define	P 13                         //小于20的质数
#define NUM 12                   //数据的个数        

 typedef struct    //哈希表结构
{   
	int key;      //关键字
	int len;     //查找长度
}	HASH;         

HASH HashList[HASHLEN];        //HASH变量                     

typedef struct LNode               //结点类型结构
{
	int data;                    
    struct LNode *next;
}LNode, List[HASHLEN];


int NumList[NUM];    //数组变量  

void InitNumList() //数组初始化          
{ 
	NumList[0]=34;
	NumList[1]=13;
	NumList[2]=25;
	NumList[3]=1;
	NumList[4]=61;
	NumList[5]=24;
	NumList[6]=86;
	NumList[7]=27;
	NumList[8]=52;
	NumList[9]=18;
	NumList[10]=10;
	NumList[11]=79;
}


void CreateHashList_1() //线性再散列法   
{	
	int i,di;                      //增量序列di
	float average=0;              //平均查找长度
	for(i=0; i<HASHLEN;i++) 
	{   
		HashList[i].key=0;     //关键字初始化
		HashList[i].len=0;    //查找长度初始化
	}
	for(i=0;i<NUM;i++)
	{  
		int sum=0;                  //查找长度
		int adress=(NumList[i])%P;  //用除留余数法确定地址
		int a=adress;
			if(HashList[a].key==0)     //如果不冲突
			{  
				HashList[a].key=NumList[i];
				HashList[a].len=1;
			}
			else   //冲突  
			{	
				di=1;
				do
				{   
					a=(adress+di)%HASHLEN;   //线性探测再散列法处理冲突    
					sum++; 
					di++;                   //查找次数加1    
				}
				while (HashList[a].key!=0);
					HashList[a].key=NumList[i];
					HashList[a].len=sum+1;		//查找长度赋值
			}
	}
	printf(" \n\n地址\t\t数据\t\t搜索长度\t哈希地址\n"); //显示哈希表
		for(i=0; i<HASHLEN; i++)
		{   
			printf("%d ",i); 
			printf("\t\t%d ",HashList[i].key);
			printf("\t\t%d ",HashList[i].len);
			printf("\t\t%d ",HashList[i].key%P);
			printf("\n");
		}
		for(i=0;i<HASHLEN;i++)                         //计算平均长度
			average+=HashList[i].len; 
			average/=NUM;
			printf("\n平均查找长度ASL为：(%d)=%f \n",NUM,average); 
}





void CreateHashList_2()					//链地址法  
{
	int i,t;                            //c存放查找次数
	int sum=0;			
	float average;
	struct LNode *s;					//创建结点指针
	struct LNode *M[HASHLEN] ;			//指针数组存放表头

	for(i=0; i<HASHLEN;i++)				//将各链表表头元素赋空值
		M[i]=NULL;


	for(i=0;i<NUM;i++)
	{   
		int adress=(NumList[i])%P;					 //除留余数法构造哈希函数
		int a=adress;
		s=(LNode *)malloc (sizeof(LNode));				
		if(s!=NULL)								//结点空间申请成功
			s->data=NumList[i];
			s->next=M[a];
			M[a]=s;
	}
	
	for(i=0;i<NUM;i++)
	{   
		t=1;
		int adress=(NumList[i])%P;					 //除留余数法构造哈希函数
	    int a=adress;
		s=M[a];
		
		while(s->data!=NumList[i])			    //查找元素不匹配
		{
			s=s->next;                          //继续查找
			t++;								//查找次数+1
		}
		sum=sum+t;                              //记录下总的查找次数
	}
	average=(float)sum/NUM;
	
		
	printf("\n\n\n");
	printf("\t哈\t希\t表\n\n");
	printf("哈希地址\t\t数据\n");

	for(i=0;i<HASHLEN;i++)
	{
		s=M[i];
		printf("%5d",i);
		printf("\t\t");

		while(s!=NULL)
		{
			printf("%4d",s->data);
			s=s->next;
		}

		printf("\n");

	}

	printf("\n\n");
	printf("平均查找长度ASL为：(%d)=%f",NUM,average);

}







void main()
{	
	char ch1;
	InitNumList();                                
	do
	{	
		printf("\t\t\t请 选 择 操 作 类 型:\n\n");
		printf("\t\t\t1. 线 性 再 散 列 法\n\t\t\t2. 链 地 址 法\n\t\t\t0. 退 出\n\t\t请选择:");
		cin>>&ch1;
		switch(ch1)
		{
		case '1':CreateHashList_1();cout<<endl;break;
		case '2':CreateHashList_2();cout<<endl;break;
		case '0':exit(0); 
		default :cout<<"\t\t\t错误选项!\n\n";
		}
		printf("\n\n");
		cout<<"是否继续?(y/n):";
		cin>>&ch1;
		printf("\n\n\n");
	}while(ch1!='n'); 
}