分离链表法散列ADT

分离链表法解决冲突的散列表ADT实现

数据结构定义如下：

 1 struct ListNode;
 2 typedef struct ListNode *Position;
 3 struct HashTbl;
 4 typedef struct HashTbl *HashTable;
 5 
 6 HashTable InitializeTable(int TableSize);
 7 void DestroyTable(HashTable H);
 8 Position Find(ElementType Key, HashTable H);
 9 void Insert(ElementType Key, HashTable H);
10 
11 struct ListNode{
12     ElementType Element;
13     Position Next;
14 };
15 
16 typedef Position List;
17 
18 struct HashTbl{
19     int TableSize;
20     List *TheLists;
21 };

初始化散列表实现代码如下：

 1 HashTable InitializeTable(int TableSize){
 2     HashTable H;
 3     int i;
 4 
 5     if(TableSize < MinTableSize){
 6         printf("Table size too small
");
 7         return NULL;
 8     }
 9     H = malloc(sizeof(struct HashTbl));
10     H->TableSize = TableSize;
11     H->TheLists = malloc(H->TableSize * sizeof(List));
12     for(i=0; i<H->TableSize; i++){
13         H->TheLists[i] = malloc(sizeof(struct ListNode));
14         H->TheLists[i]->Next = NULL;
15     }
16     return H;    
17 }

Find的实现代码如下：

1 Position Find(ElementType Key, HashTable H){
2     Position P;
3     List L;
4     L = H->TheLists[Hash(Key, H->TableSize)];
5     P = L->Next;
6     while(P!=NULL && P->Element!=Key)
7         P = P->Next;
8     return P;
9 }

Insert的实现代码如下：

 1 void Insert(ElementType Key, HashTable H){
 2     Position Pos, NewCell;
 3     List L;
 4 
 5     Pos = Find(Key, H);
 6     if(Pos != NULL){
 7         NewCell = malloc(sizeof(struct ListNode));
 8         L = H->TheLists[Hash(Key, H->TableSize)];
 9         NewCell->Element = Key;
10         NewCell->Next = L->Next;
11         L->Next = NewCell;
12     }
13 }

Delete的实现代码如下：

 1 void Delete(ElementType Key, HashTable H){
 2     Position P;
 3     List L;
 4 
 5     L = H->TheLists[Hash(Key, H->TableSize)];
 6     while(L->Next!=NULL && L->Next->Element!=Key)
 7         L = L->Next;
 8     
 9     if(L->Next == NULL)
10         printf("Key not in the hashtable
");
11     else{
12         P = L->Next;
13         L->Next = P->Next;
14         free(P);
15     }
16 }