分离链表法散列ADT

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

数据结构定义如下：

 struct ListNode;

 typedef struct ListNode *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);

 struct ListNode{

     ElementType Element;

     Position Next;

 };

 typedef Position List;

 struct HashTbl{

     int TableSize;

     List *TheLists;

 };

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

 HashTable InitializeTable(int TableSize){

     HashTable H;

     int i;

     if(TableSize < MinTableSize){

         printf("Table size too small\n");

         return NULL;

     }

     H = malloc(sizeof(struct HashTbl));

     H->TableSize = TableSize;

     H->TheLists = malloc(H->TableSize * sizeof(List));

     for(i=; i<H->TableSize; i++){

         H->TheLists[i] = malloc(sizeof(struct ListNode));

         H->TheLists[i]->Next = NULL;

     }

     return H;

 }

Find的实现代码如下：

 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;

 }

Insert的实现代码如下：

 void Insert(ElementType Key, HashTable H){

     Position Pos, NewCell;

     List L;

     Pos = Find(Key, H);

     if(Pos != NULL){

         NewCell = malloc(sizeof(struct ListNode));

         L = H->TheLists[Hash(Key, H->TableSize)];

         NewCell->Element = Key;

         NewCell->Next = L->Next;

         L->Next = NewCell;

     }

 }

Delete的实现代码如下：

 void Delete(ElementType Key, HashTable H){

     Position P;

     List L;

     L = H->TheLists[Hash(Key, H->TableSize)];

     while(L->Next!=NULL && L->Next->Element!=Key)

         L = L->Next;

     if(L->Next == NULL)

         printf("Key not in the hashtable\n");

     else{

         P = L->Next;

         L->Next = P->Next;

         free(P);

     }

 }

巴特西

分离链表法散列ADT

最新文章

热门文章