实现哈希表构造和查找算法

男娘i 2021-12-08 22:23 318阅读 0赞

## 实现哈希表构造和查找算法 ##

实现哈希表构造和查找算法

使用的是除留余数法构造哈希函数，这里我用了两种方法解决冲突：

1.  一次探测再散列；
2.  二次探测再散列解决冲突。

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    
    #define NULLKEY -1
    typedef struct{
    	int key;
    }KeyType;
    typedef struct{
    	KeyType *elem;//表示生成的空间的首地址
    	int count;	//哈希表元素个数 
    	int sizeindex;	//哈希表长度 
    }HashTable;
    
    int Hash(HashTable *H,int k){
    	return (k%H->sizeindex);
    }
    
    int Hash2(int i,int t){
    	int a=0,b=0;
    	if(i%2==0)
    		t=t+pow(++a,2);
    	else
    		t=t-pow(++b,2);
    	return t;
    }
    
    void CreateHash(HashTable *H){
    	int i,j,key,p,t,c=0;
    	printf("输入哈希表的元素个数及长度:\n");
    	scanf("%d%d",&H->count,&H->sizeindex);
    	
        H->elem=(KeyType *)malloc(H->sizeindex * sizeof(KeyType)); //申请内存
        for(i=0;i<H->sizeindex;i++)
    		H->elem[i].key=NULLKEY;
    
    	printf("输入元素:\n");
    	for(j=0;j<H->count;j++){
    		scanf("%d",&key);
    		p=Hash(H,key);
    		if(H->elem[p].key==NULLKEY)
    			H->elem[p].key=key;
    		else{
    			while(H->elem[p].key!=NULLKEY){
    				t=p+1;
    				p=Hash(H,t);
    			}
    			H->elem[p].key=key;
    		}
    	}
    }
    
    int SearchHash(HashTable H,int key){
    	int p,t;
    	p=Hash(&H,key);
    	while(H.elem[p].key!=NULLKEY&&H.elem[p].key!=key){
    		t=p+1;
    		p=Hash(&H,t);
    	}
    	if(H.elem[p].key==key)
    		return p;
    	else
    		return -1;
    }
    
    void print(HashTable H){
    	int i=0;
    	for(i=0;i<H.sizeindex;i++){
    		printf("%d ",H.elem[i].key);
    	}
    }
    
    int main(){
    	HashTable H;
    	int key,i;
    	CreateHash(&H);
    	printf("\n输出哈希表:\n");
    	print(H);
    	printf("\n输入要查找的key:\n");
    	scanf("%d",&key);
    	i=SearchHash(H,key);
    	if(i==-1)
    		printf("没有找到!");
    	else
    		printf("%d在哈希表中的位置是%d",key,i);
    	return 0;
    }