雜湊表 -- 以字串為 key

高等 C 語言

簡介

字串

指標與陣列

函數

結構

物件導向

記憶體

檔案

錯誤處理

巨集處理

C 與組合語言

資料結構

動態字串

動態陣列

鏈結串列

雜湊表

開發環境

Make

Cygwin

MinGW

DevC++

wxDevC++

編譯器

gcc 編譯器

TinyCC 編譯器

LCC 編譯器

應用主題

CGI 程式

GNU 程式

視窗程式

影像處理

練習題

訊息

相關網站

參考文獻

最新修改

簡體版

English

執行結果

G:\c\hash>gcc strhash.c -o strhash

G:\c\hash>strhash
gi=747 key=George
bi=633 hashTable[bi]=-1
jtel=313530

程式碼

#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);
}

參考文獻

  1. http://uthash.sourceforge.net/userguide.html

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License