散列表的算法---基于链地址的散列表的建立

#include "stdio.h"
#define NIL -1
#define M 997
typedef int KeyType;
typedef struct chain
{
    KeyType key;
    struct chain *next;
}ChainType;

int h(KeyType K)
{
    return K%M;
}

ChainType* HashSearch(ChainType *Ti,KeyType K,ChainType **end)
{
    ChainType *pre,*cur;
    pre = NULL;
    cur = Ti;
    while(cur!=NULL && cur->key!=K)
    {
        pre =cur;
        cur=cur->next;
    }

    *end=pre; //end返回未查到关键字时，链表的尾部结点的地址，因为要用于插入
    if(cur == NULL) //查找不到时，返回空值
    {
        return NULL;
    }
    else
    {
        return cur; //查找到时，返回该记录地址
    }
}

int HashInsert(ChainType *T[],KeyType K)
{
    ChainType *pre,*cur;
    int i;
    i=h(K);
    cur=HashSearch(T[i],K,&pre);
    if(cur==NULL) //未找到时，在链表尾部插入该记录
    {
        cur = (ChainType*)malloc(sizeof(ChainType));
        cur->key = K;
        cur->next=NULL;
        if(pre == NULL) //在该链表插入第一条记录
        {
            T[i]=cur;
        }
        else
        {
            pre->next=cur; //插入后续记录
        }
        return 1;
    }
    return 0; //记录存在时，返回0
}

void CreateHashTable(ChainType *T[],ChainType A[],int n)
{
    //根据A[0...n-1]中结点建立散列表T[0..m-1]
    int i;
    for(i=0;i<n;i++)
    {
        HashInsert(T,A[i]);
    }

}

用链地址解决冲突的方法是：将所有关键字为同义词的记录存储在一个线性表中，并将这些链表的表头指针放在数组中，这类似于图中的邻接表和树中孩子链表的结构。