雜湊表 -- 以字串為 key
高等 C 語言簡介字串指標與陣列函數結構物件導向記憶體檔案錯誤處理巨集處理C 與組合語言資料結構動態字串動態陣列鏈結串列雜湊表開發環境MakeCygwinMinGWDevC++wxDevC++編譯器gcc 編譯器TinyCC 編譯器LCC 編譯器應用主題CGI 程式GNU 程式視窗程式影像處理練習題訊息相關網站參考文獻最新修改簡體版English |
執行結果
程式碼#include <stdio.h> #include <assert.h> #define NIL -1 typedef struct { char *str; int strIdx, strMax; } StrTable; void strTableNew(StrTable *st, char *str, int strMax) { st->str = str; st->strIdx = 0; st->strMax = strMax; } int strPut(StrTable *st, char *key) { strcpy(&st->str[st->strIdx], key); int strBegin = st->strIdx; st->strIdx += strlen(key)+1; return strBegin; } typedef struct { int *hashTable; int hashMax, hashCount; StrTable *strTable; } SHashTable; void sHashClear(int table[], int size) { int i; for (i=0; i<size; i++) table[i] = NIL; } void sHashNew(SHashTable *h, int *hashTable, int hashMax, StrTable *strTable) { h->hashMax = hashMax; h->hashTable = hashTable; h->hashCount = 0; sHashClear(h->hashTable, hashMax); h->strTable = strTable; } int sHash(SHashTable *h, char *key) { int i, hashCode=0; for (i=0; i<strlen(key); i++) { hashCode = hashCode * 739 + key[i]; hashCode %= h->hashMax; } return hashCode; } char *sHashKey(SHashTable *h, int slot) { int si = h->hashTable[slot]; if (si == NIL) return NULL; else return &h->strTable->str[si]; } int sHashSeek(SHashTable *h, char *key) { int i, slot = sHash(h, key); for (i=slot; ; i=(i++)%h->hashMax) { assert(i!= (slot+h->hashMax-1)%h->hashMax); if (h->hashTable[i]==NIL) return i; else if (strcmp(sHashKey(h, i), key)==0) return i; } } int sHashPut(SHashTable *h, char *key) { int slot = sHashSeek(h, key); if (h->hashTable[slot] == NIL) { h->hashCount ++; assert(h->hashCount < h->hashMax); } h->hashTable[slot] = strPut(h->strTable, key); return slot; } #define HASH_MAX 997 #define STAB_MAX 10000 SHashTable h; StrTable st; char strTable[STAB_MAX]; int hashTable[HASH_MAX]; // TEL 相關表格 int valueTable[HASH_MAX]; int valuePut(char *key, char *value) { int slot = sHashPut(&h, key); valueTable[slot] = strPut(h.strTable, value); return slot; } char *valueGet(char *key) { int slot = sHashSeek(&h, key); if (h.hashTable[slot] == NIL) return NULL; else return &h.strTable->str[valueTable[slot]]; } int main() { strTableNew(&st, strTable, STAB_MAX); sHashNew(&h, hashTable, HASH_MAX, &st); char *keys[] = {"John", "Mary", "George", "Peter", NULL}; char *tels[] = {"313530", "313531", "313532", "313533"}; int i; for (i=0; keys[i]!=NULL; i++) { sHashPut(&h, keys[i]); } int gi = sHashSeek(&h, "George"); printf("gi=%d key=%s\n", gi, sHashKey(&h, gi)); int bi = sHashSeek(&h, "Betty"); printf("bi=%d hashTable[bi]=%d\n", bi, h.hashTable[bi]); // TEL sHashClear(valueTable, HASH_MAX); valuePut("John", "313530"); char *jtel = valueGet("John"); printf("jtel=%s\n", jtel); } 參考文獻 |
page revision: 8, last edited: 09 Nov 2012 04:08
Post preview:
Close preview