10-4.c

数据结构的经典实现算法

#include "stdio.h"
#define NIL -1 //空结点标记依赖于关键字类型,本节假定关键字均为非负整数
#define M 997 //表长度依赖于应用,但一般应根据。确定m为一素数
typedef int KeyType;
typedef struct node{ //哈希表结点类型
	KeyType key;
   //其他数据域
}NodeType;
int h(KeyType K){ //用除余法求K的哈希地址
    return K%M;
}
int Increment(int i){//用线性探查法求第i个增量di
    return i; //若用二次探查法,则返回i*i
}
int Hash(KeyType k,int i)
{ //求在哈希表T[0..m-1]中第i次探查的哈希地址hi,0≤i≤m-1
  //下面的h是哈希函数。Increment是求增量序列的函数,它依赖于解决冲突的方法 
	return(h(k)+Increment(i))%M; //Increment(i)相当于是di
}
int HashSearch(NodeType T[],KeyType K,int *pos)
{ //在哈希表T[0..m-1]中查找K,成功时返回1。失败有两种情况：找到一个开放
//址时返回0,表满未找到时返回-1。 *pos记录找到K或找到空结点时表中的位置
    int i=0;//记录探查次数
    do{
		*pos=Hash(K,i);//求探查地址hi
		if(T[*pos].key==K) return 1;//查找成功返回
		if(T[*pos].key==NIL) return 0;//查找到空结点返回
    }while(++i<M); //最多做m次探查
    return -1;//表满且未找到时,查找失败
} //HashSearch

void main()
{
	NodeType T[M];
	KeyType K=10;
	int pos;
	int result=HashSearch(T,K,&pos);
}