《数据结构与算法分析——C语言描述》ADT实现(NO.05) : 散列(Hash)
散列(Hash)是一种以常数复杂度实现查找功能的数据结构。它将一个关键词Key,通过某种映射(哈希函数)转化成索引值直接定位到相应位置。
实现散列有两个关键,一是哈希函数的选择,二是冲突的处理。
对于哈希函数,例程中以“Key为int型,操作为取(关于表长的)模”为例。事实上,可以直接将其换成任何一个哈希函数,不会影响实现。
对于冲突处理,有两大类处理方案,一是分离链接法,二是开放定址法。开放定址法包括线性探测法、平方探测法、双散列法等,本文给出分离链接法和平方探测法的实现。
1. 分离链接法:
// HashSep.h #include <stdio.h> #include <stdlib.h> struct ListNode; typedef struct ListNode *Position; struct HashTbl; typedef struct HashTbl *HashTable; typedef Position List; HashTable InitializeTable(int TableSize); void DestroyTable(HashTable H); Position Find(ElementType Key, HashTable H); void Insert(ElementType Key, HashTable H);
// HashSep.c #include "HashSep.h" struct ListNode { ElementType Key; Position Next; }; struct HashTbl { int TableSize; List *TheLists; }; int NextPrime(int N) { if (N % 2 == 0) N++; int i; int NotPrime = 0; for (;; N += 2) { NotPrime = 0; for (i = 3; i * i <= N; i += 2) if (N % i == 0) { NotPrime = 1; break; } if (!NotPrime) return N; } } int Hash(ElementType Key, int TableSize) { return Key * Key % 10; } HashTable InitializeTable(int TableSize) { HashTable H; int i; if ((H = (HashTable)malloc(sizeof(struct HashTbl))) == NULL) { printf("Error! Out of memory! \n"); return NULL; } H->TableSize = NextPrime(TableSize); H->TheLists = (Position *)malloc(H->TableSize * sizeof(Position)); for (i = 0; i < H->TableSize; i++) { if ((H->TheLists[i] = (List)malloc(sizeof(struct ListNode))) == NULL) { printf("Error! Out of memory! \n"); return NULL; } H->TheLists[i]->Next = NULL; } return H; } void DestroyTable(HashTable H) { int i; for (i = 0; i < H->TableSize; i++) { Position p, q; q = H->TheLists[i]; p = q->Next; while(p) { free(q); q = p; p = p->Next; } } free(H); } int Same(ElementType e1, ElementType e2) { return e1 == e2; } Position Find(ElementType Key, HashTable H) { Position p; p = H->TheLists[Hash(Key, H->TableSize)]->Next; while(p) { if(Same(p->Key, Key)) break; p = p->Next; } return p; } void Insert(ElementType Key, HashTable H) { Position p; List L; if(Find(Key, H) != NULL) return; if((p = (Position)malloc(sizeof(struct ListNode))) == NULL) { printf("Error! Out of memory! \n"); return; } p->Key = Key; L = H->TheLists[Hash(Key, H->TableSize)]; p->Next = L->Next; L->Next = p; }
2. 平方探测法
// HashQuad.h #include <stdio.h> #include <stdlib.h> typedef unsigned int Index; typedef Index Position; struct HashTbl; typedef struct HashTbl *HashTable; typedef struct HashEntry Cell; 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);
// HashQuad.c #include "HashQuad.h" enum KindOfEntry { Legitimate, Empty, Deleted }; struct HashEntry { ElementType Element; enum KindOfEntry Info; }; struct HashTbl { int TableSize; Cell *TheCells; }; int NextPrime(int N) { if (N % 2 == 0) N++; int i; int NotPrime = 0; for (;; N += 2) { NotPrime = 0; for (i = 3; i * i <= N; i += 2) if (N % i == 0) { NotPrime = 1; break; } if (!NotPrime) return N; } } Index Hash(ElementType Key, int TableSize) { return Key % TableSize; } HashTable InitializeTable(int TableSize) { HashTable H; int i; if ((H = (HashTable)malloc(sizeof(struct HashTbl))) == NULL) { printf("Error!\n"); return NULL; } H->TableSize = NextPrime(TableSize); if ((H->TheCells = (Cell *)malloc(sizeof(Cell) * H->TableSize)) == NULL) { printf("Error!\n"); return NULL; } for (i = 0; i < H->TableSize; i++) H->TheCells[i].Info = Empty; return H; } void DestroyTable(HashTable H) { free(H->TheCells); free(H); } Position Find(ElementType Key, HashTable H) { Index id = Hash(Key, H->TableSize); int i = 0; while (H->TheCells[id].Info == Legitimate && H->TheCells[id].Element != Key) { id += (++i << 1) - 1; if (id >= H->TableSize) id -= H->TableSize; } return id; } void Insert(ElementType Key, HashTable H) { Position p = Find(Key, H); if (H->TheCells[p].Info != Legitimate) { H->TheCells[p].Element = Key; H->TheCells[p].Info = Legitimate; } } ElementType Retrieve(Position P, HashTable H) { return H->TheCells[P].Element; } HashTable ReHash(HashTable H) { int i; int OldSize; Cell *OldCells; OldCells = H->TheCells; OldSize = H->TableSize; H = InitializeTable(2 * OldSize); for(i = 0; i < H->TableSize; i++) if(OldCells[i].Info == Legitimate) Insert(OldCells[i].Element, H); free(OldCells); return H; }
优质内容筛选与推荐>>