数据结构与算法——整型关键字的散列映射

╰半夏微凉° 2022-12-28 08:14 112阅读 0赞

题目描述  
给定一系列整型关键字和素数P，用除留余数法定义的散列函数 H(Key) = Key % P将关键字映射到长度为P的散列表中。用线性探测法解决冲突。

输入  
输入第1行首先给出两个正整数N（<=1000）和P（>=N的最小素数），分别为待插入的关键字总数、以及散列表的长度。第2行给出N个整型关键字。数字间以空格分隔。

输出  
在一行内输出每个整型关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。

样例输入  
4 5  
24 15 61 88

样例输出  
4 0 1 3

这题是一个简单的哈希表问题，本题主要需要注意的是哈希表的冲突处理。  
哈希表是可能存在冲突，比如输入两个24，这个时候第二个24就不需要再去另找空间存放了，直接输出第一个24的下标即可，或者输入25和15这两个值，所给素数为5，那么25%5和15%5的值完全相同，这就导致冲突，处理方式为另找一块空的空间存放冲突的数值。

具体代码如下：

#include<stdio.h>
    int a[1009],b[1009];
    int main(){ 
    	int n,p;
    	scanf("%d %d",&n,&p);
    	int x,i,j;
    	for(i=0;i<n;i++){ 
    		scanf("%d",&x);
    		int H=x%p;
    		int t=0;
    		for(j=0;j<p;j++){            
    				if(a[j]==x){  //这里便是判断是否存在输入两个相同数值的情况
    				printf(" %d",j);
    				t=1;
    				break;
    			}
    		}
    		if(t==0){ 
    			while(b[H]){           //寻找空余空间存放数值
    				H=(H+1)%p;
    			}
    			b[H]=1;
    		 	a[H]=x;
    		 	if(i==0){ 
    		 		printf("%d",H);
    			}else{ 
    				printf(" %d",H);
    			}	
    		}
    	}
    	
    	return 0;
    }