#include <stdio.h> typedef int ElementType; typedef struct ListNode *Position; struct ListNode { ElementType Element; Position Next; }; typedef struct HashTbl *HashTable; struct HashTbl { int TableSize; Position *TheLists; // 指针数组 }; HashTable InitializeTable(int TableSize) { HashTable ht; int i; ht = malloc(sizeof(struct HashTbl)); if (ht == NULL) return -1; ht->TableSize = TableSize; ht->TheLists = calloc(TableSize, sizeof(Position)); if (ht->TheLists == NULL) return -1; return ht; } // 散列函数 int Hash(ElementType Key, int TableSize) { return Key % TableSize; } Position Find(HashTable H, ElementType Key) { Position p; p = H->TheLists[Hash(Key, H->TableSize)]; while (p != NULL && p->Element != Key) // 这里只能对数值型key进行比较 p = p->Next; return p; } // 键值不允许重复 void Insert(HashTable H, ElementType Key) { Position *p; // 如果不使用这个双重指针,那么需要计算多次散列函数 Position tmp; if (Find(H, Key) == NULL) // 元素不存在 { // 插入链表头部 p = &(H->TheLists[Hash(Key, H->TableSize)]); tmp = malloc(sizeof(struct ListNode)); tmp->Element = Key; tmp->Next = *p; *p = tmp; } } int main(void) { HashTable table; Position p; table = InitializeTable(100); Insert(table, 21); Insert(table, 24); Insert(table, 43); Insert(table, 35); p = Find(table, 43); if (p != NULL) printf("Find it!\n"); else printf("Not found!\n"); return 0; }
#include <stdio.h> typedef int ElementType; typedef int Position; enum KindOfEntry { Legitimate, Empty, Deleted }; struct HashEntry { ElementType Element; enum KindOfEntry Info; }; typedef struct HashTbl *HashTable; struct HashTbl { int TableSize; struct HashEntry *array; }; HashTable InitializeTable(int TableSize) { HashTable H; int i; H = malloc(sizeof(struct HashTbl)); if (H == NULL) return -1; H->TableSize = TableSize; H->array = malloc(TableSize * sizeof(struct HashEntry)); if (H->array == NULL) return -1; for (i = 0; i < TableSize; i++) H->array[i].Info = Empty; return H; } Position Hash(ElementType Key, int TableSize) { return Key % TableSize; } Position Find(HashTable H, ElementType Key) { Position p; int num = 0; p = Hash(Key, H->TableSize); while (H->array[p].Info != Empty && H->array[p].Element != Key) { p += ++num * 2 -1; // 平方操作可以优化 if (p >= H->TableSize) p -= H->TableSize; // 绕回去 } return p; // 返回找到的索引或一个正确的插入位置 } void Insert(HashTable H, ElementType Key) { Position p; p = Find(H, Key); if (H->array[p].Info != Legitimate) // 如果找到的位置未被占用,则插入 { H->array[p].Element = Key; H->array[p].Info = Legitimate; } } void Delete(HashTable H, ElementType Key) // 删除操作采用慵懒删除 { Position p; p = Find(H, Key); if (H->array[p].Info == Legitimate) H->array[p].Info = Deleted; } int main(void) { HashTable table; Position p; table = InitializeTable(20); Insert(table, 3); Insert(table, 1); Insert(table, 23); Insert(table, 34); Insert(table, 8); p = Find(table, 34); if (table->array[p].Info == Legitimate) printf("%d", table->array[p].Element); return 0; }
原文:http://blog.csdn.net/nestler/article/details/25912829