# 数据结构与算法分析-开放定址散列表的实现

```#include<stdio.h>
#include"fatal.h"
typedef char* ElementType;

typedef unsigned int Index;
typedef Index Position;
struct HashTbl;
typedef struct HashTbl *HashTable;

HashTable InitializeTable(int TableSize);
void DestroyTable(HashTable H);
Position Find(ElementType key,HashTable H);
void Insert(ElementType key,HashTable H);
ElementType Retrieve(Position P,HashTable H);
HashTable Rehash(HashTable H);

enum KindOfEntry {Legitimate,Empty,Deleted};

struct HashEntry
{
ElementType Element;
enum KindOfEntry Info;
};

typedef struct HashEntry Cell;

struct HashTbl
{
int TableSize;
Cell *TheCells;
};

int MinTableSize=23;

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=TableSize;
H->TheCells=malloc(sizeof(Cell)*H->TableSize);
if(H->TheCells==NULL)
FatalError("Out of space !!");
for(i=0;i<H->TableSize;i++)
H->TheCells[i].Info=Empty;
return H;
}

int Hash(ElementType key,int TableSize)
{
unsigned int HashVal=0;
while(*key!='\0')
{
HashVal=(HashVal<<5)+*key++;
}
HashVal=HashVal%TableSize;
return HashVal;
}

Position Find(ElementType key,HashTable H)
{
Position CurrentPos;
int CollisionNum;
CollisionNum=0;
CurrentPos=Hash(key,H->TableSize);
while(H->TheCells[CurrentPos].Info!=Empty&&H->TheCells[CurrentPos].Element!=key)
{
CurrentPos+=2*++CollisionNum-1;
if(CurrentPos>=H->TableSize)
CurrentPos-=H->TableSize;
}
return CurrentPos;
}

void Insert(ElementType key,HashTable H)
{
Position Pos;
Pos=Find(key,H);
if(H->TheCells[Pos].Info!=Legitimate)
{
H->TheCells[Pos].Info=Legitimate;
H->TheCells[Pos].Element=key;
}
}

ElementType Retrieve(Position P,HashTable H)
{
if(H->TheCells[P].Info!=Empty)
return H->TheCells[P].Element;
else
return NULL;
}

HashTable rehash(HashTable H)
{
int i,OldSize;
Cell* OldCells;
OldCells=H->TheCells;
OldSize=H->TableSize;

H=InitializeTable(2*OldSize);
for(i=0;i<OldSize;i++)
if(OldCells[i].Info==Legitimate)
Insert(OldCells[i].Element,H);
free(OldCells);
return H;
}```

原文作者：Jessica程序猿
原文地址: https://www.cnblogs.com/wuchanming/p/3808715.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。