- 註冊時間
- 2006-10-8
- 最後登錄
- 2019-6-20
- 主題
- 查看
- 積分
- 1306
- 閱讀權限
- 110
- 文章
- 1393
- 相冊
- 0
- 日誌
- 1
  
狀態︰
離線 
|
檔案：HashTable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include "Array.h"
typedef struct {
char *key;
void *data;
} Entry;
Entry* EntryNew(char *key, void *data);
int EntryCompare(Entry *e1, Entry *e2);
int hash(char *key, int range);
#define HashTable Array
HashTable* HashTableNew(int size);
void HashTableFree(HashTable *table);
void HashTablePut(HashTable *table, char *key, void *data);
void *HashTableGet(HashTable *table, char *key);
void HashTableEach(HashTable *table, FuncPtr1 f);
Array* HashTableToArray(HashTable *table);
void HashTableTest();
#endif
檔案：HashTable.c
#include "HashTable.h"
void HashTableTest() {
printf("\n=======HashTableTest()==========\n");
char *names[] = { "John", "Mary", "George", "Mickey", "Snoopy", "Bob", "Jack" };
char *ids[] = { "1", "2", "3", "4", "5", "6", "7" };
HashTable* table = HashTableNew(3);
int i;
for (i=0; i<5; i++)
HashTablePut(table, names[i], ids[i]);
// for (i=0; i<7; i++)
// printf("id=%s\n", HashTableGet(table, names[i]));
// HashTableEach(table, strPrintln);
HashTableFree(table);
}
int hash(char *key, int range) {
int i, hashCode=0;
for (i=0; i<strlen(key); i++) {
BYTE value = (BYTE) key[i];
hashCode += value;
hashCode %= range;
}
return hashCode;
}
Entry* EntryNew(char *key, void *data) {
Entry* e = ObjNew(Entry, 1);
e->key = key;
e->data = data;
return e;
}
void EntryFree(Entry *e) {
ObjFree(e);
}
int EntryCompare(Entry *e1, Entry *e2) {
return strcmp(e1->key, e2->key);
}
HashTable* HashTableNew(int size) {
Array *table = ArrayNew(size);
int i;
for (i=0; i<table->size; i++)
ArrayAdd(table, ArrayNew(1));
return table;
}
void HashTableFree(HashTable *table) {
int ti, hi;
for (ti=0; ti<table->size; ti++) {
Array *hitArray = table->item[ti];
ArrayFree(hitArray, (FuncPtr1) EntryFree);
}
ArrayFree(table, NULL);
}
Entry keyEntry;
// 尋找雜湊表中 key 所對應的元素並傳回
void *HashTableGet(HashTable *table, char *key) {
int slot = hash(key, table->size); // 取得雜湊值 (列號)
Array *hitArray = (Array*) table->item[slot]; // 取得該列
// 找出該列中是否有包含 key 的配對
keyEntry.key = key;
int keyIdx = ArrayFind(hitArray, &keyEntry, EntryCompare);
if (keyIdx >= 0) { // 若有，則傳回該配對的資料元素
Entry *e = hitArray->item[keyIdx];
return e->data;
}
return NULL; // 否則傳回 NULL
}
// 將 (key, data) 配對放入雜湊表中
void HashTablePut(HashTable *table, char *key, void *data) {
Entry *e;
int slot = hash(key, table->size); // 取得雜湊值 (列號)
Array *hitArray = (Array*) table->item[slot]; // 取得該列
keyEntry.key = key;
int keyIdx = ArrayFind(hitArray, &keyEntry, EntryCompare);
if (keyIdx >= 0) { // 若有，則傳回該配對的資料元素
e = hitArray->item[keyIdx];
e->data = data;
} else {
e= EntryNew(key, data);// 建立配對
ArrayAdd(hitArray, e); // 放入對應的列中
}
}
void HashTableEach(HashTable *table, FuncPtr1 f) {
int i, j;
for (i=0; i<table->count; i++) {
Array *hits = table->item[i];
for (j=0; j<hits->count; j++) {
Entry *e = hits->item[j];
f(e->data);
}
}
}
Array* HashTableToArray(HashTable *table) {
Array *array = ArrayNew(table->count);
int i, j;
for (i=0; i<table->count; i++) {
Array *hits = table->item[i];
for (j=0; j<hits->count; j++) {
Entry *e = hits->item[j];
ArrayAdd(array, e->data);
}
}
return array; |
|
發表於 2012-7-11 00:21:17
