# 分离链接散列表的实现

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

``````#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;
}
}
}``````
原文作者：梁月唯
原文地址: https://www.cnblogs.com/y3w3l/p/6365029.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。