# 算法：分离链表法散列表

hash.h

```#ifndef _HASHTABLE_H
#define _HASHTABLE_H

#define MinSize 10

struct ListNode;
struct HashNode;
typedef unsigned int Index;
typedef char *ElementType;
typedef struct ListNode *Position;
typedef struct HashNode *HashTable;

HashTable InitializeHashTable(int TableSize);
Position Find(ElementType key,HashTable H);
void Insert(ElementType key,HashTable H);
void Delete(ElementType key,HashTable H);

#endif

struct ListNode
{
ElementType key;
Position next;
};
typedef Position List;

struct HashNode
{
int TableSize;
List *TheLists;
};```

Hash.c

```#include <stdlib.h>
#include <stdio.h>
#include "Hash.h"

//获取下一个素数
static int NextPrime(int N)
{
int i;
if(N%2==0)
N++;
for(;;N+=2){
for(i=3;i*i<=N;i+=2){
if(N%i==0){
goto ContOuter;
}
}
return N;
ContOuter:;
}
return N;
}
//Hash函数
Index Hash(const char *key,int TableSize)
{
unsigned int HashVal=0;
while(*key!='\0'){
HashVal=(HashVal<<5)+*key++;
}
return HashVal%TableSize;
}
HashTable InitializeHashTable(int TableSize)
{
HashTable H;
int i;
H=(HashTable)malloc(sizeof(struct HashNode));
if(H==NULL){
printf("out 0f space");
return NULL;
}
H->TableSize=NextPrime(TableSize);
//分配链表数组空间
H->TheLists=malloc(sizeof(struct List))*H->TableSize
if(H->TheLists==NULL){
printf("out of space");
return NULL;
}
//分配链表表头空间
for(i=0;i<H->TableSize;++i){
H->TheLists[i]=malloc(sizeof(struct ListNode));
if(H->TheLists[i]==NULL){
printf("out of space");
return NULL;
}
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&&strcmp(P->key,key)!=0){
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){
printf("out of space");
return NULL;
}
L=H->TheLists[Hash(key,H->TableSize)];
NewCell->next=L->next;
NewCell->key=malloc(strlen(key))+1;
strcpy(NewCell->key,key);
NewCell->key[strlen(key)]='\0';
L->next=NewCell;
}
}
void Delete(EelmentType key,HashTable H)
{
Position Pos,Pre;
List L;
Pos=Find(key,H);
L=H->TheLists[Hash(key,H->TableSize)];
for(Pre=L;Pre!=NULL;Pre=Pre->next){
if(Pre->next==Pos){
Pre->next=Pos->next;
free(Pos->key);
free(Pos);
break;
}
}
}
void DestoryTable(HashTable H)
{
Position P,Tmp;
int i;
for(i=0;i<H->TableSize;++i){
P=H->TheLists[i];
while(P!=NULL){
Tmp=P->next;
free(P->key);
free(P);
P=Tmp;
}
}
free(H);
}```

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