欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

分离链接散列表的实现

程序员文章站 2024-03-22 08:44:52
...

分离链接散列表的类型声明

#ifndef _HashSep_H

struct ListNode;
typedef struct ListNode *Position;
struct HashTbl;
typedef struct HashTbl *HashTable;

HashTable InitilizeTable(int TableSize);
void DestroyTable(HashTable H);
Position Find(ElementType Key,HashTable H);
void Insert(ElementType Key,HashTable H);
ElementType Retrieve(Position P);

#endif

struct ListNode
{
    ElementType Element;
    Position Next;
};
struct HashTbl
{
    int TableSize;
    List *TheLists;
};

分离链接散列表的初始化

HashTable InitializeTable(int TableSize)
{
    HashTable H;
    int i;
    
    if(TableSize < MinTableSize)
    {
        Error("Table size too small");
        return NULL;
    }
    H = malloc(sizeof(struct HashTbl));
    if(H == NULL)
        FatalError("Out of space!!!");
    H->TableSize = NextPrime(TableSize);
    H->TheLists = malloc(sizeof(Lisr)*H->TableSize);
    if(H->TheLists == NULL)
        FatalError("Out of space!!!");
    for(i = 0;i < H->TableSize; i++)
    {
        H->TheLists[i] = malloc(sizeof(struct ListNode));
        if(H->TheLists[i] == NULL)
            FatalError("Out of space!!!");
        else
            H->TheLists[i]->Next = NULL;
    }
    return H;
}

分离链接散列表的查找程序

Position Find(ElementType Key,HashTable H)
{
    Position P;
    List L;
    L = H->TheLists[Hash(Key,H->TableSize)];
    P = L->Next;
    while(P != NULL && P->Element != Key)
        P = P->Next;
    return P;
}

分离链接散列表的插入程序

void Insert(ElementType Key,HashTable H)
{
    Position Pos,NewCell;
    List L;
    Pos = Find(Key,H);
    if(Pos == NULL)
    {
        NewCell = malloc(sizeof(struct ListNode));
        if(NewCell == NULL)
            FatalError("Out of space!!!");
        else
        {
            L = H->TheLists[Hash(Key,H->TableSize)];
            NewCell->Next = L->Next;
            NewCell->Element = Key;
            L->Next = NewCell;
        }
    }
}