有关散列表的算法---基于开放定址法的散列表的建立

    建表时首先要将表中各结点的关键字清空，使其地址为开放的。然后调用调入算法将给定的关键字序列依次插入表中。

    插入算法首先调用查找算法。若在表中找到待插入的关键字或表已满，则插入失败。若在表中找到一个开放地址，则将待插入的结点插入其中，即插入成功。

代码：

 

#include "stdio.h"
#define NIL -1 //空结点标记
#define M 997  //表长度，一般表长度为素数
typedef int KeyType;
typedef struct node  //散列表结点类型
{
    KeyType key;
}HashType;

//用除余法求K的散列地址的函数h
int h(KeyType K)
{
    return K%M;  }

//求增量序列的函数，它依赖于解决冲突的方法
int Increment(int i)  //用线性探查法求第i个增量di
{
    return i;  //若用二次探查法，则返回i*i
}

//求在散列表T[0...M-1]中第i次探查的散列地址hi，0<=i<=M-1
int Hash(KeyType k,int i)
{
    return (h(k)+Increment(i))%M;
}

int HashSearch(HashType T[],KeyType K,int *pos)
{
    int i=0; //记录探查次数
    do
    {
        *pos=Hash(K,i);
        if(T[*pos].key == K) return 1;  //查找成功返回1
        if(T[*pos].key == NIL) return 0;  //找到一个空地址即开放地址返回0
    }while(++i<M); //最多做M次探查
    return -1; //表满未找到返回-1
}

//将新结点newnode插入散列表中
void HashInsert(HashType T[],HashType newnode)
{
    int pos,sign;
    sign=HashSearch(T,newnode.key,&pos);
    if(!sign)
        T[pos]=newnode;   //找到一个开放地址即插入
    else
    {
        if(sign>0)
            printf("重复的关键字!");
        else
        {
            printf("表满错误，终止程序执行!");
            exit(0);
        }

    }
}

void CreateHashTable(HashType T[],HashType A[],int n)
{
    int i;
    if(n>M)   //用开放地址法处理冲突时，装填因子a须不大于1，一般为0.6-0.9
    {
        printf("装填因子a须不大于1");
        exit(0);
    }
    for(i=0;i<M;i++)
    {
        T[i].key=NIL;   //将各关键字清空，使地址i为开放地址
        for(i=0;i<n;i++)
        {
            HashInsert(T,A[i]);
        }
    }
}