雜湊表 -- 以寬字串為 key

高等 C 語言

簡介

字串

指標與陣列

函數

結構

物件導向

記憶體

檔案

錯誤處理

巨集處理

C 與組合語言

資料結構

動態字串

動態陣列

鏈結串列

雜湊表

開發環境

Make

Cygwin

MinGW

DevC++

wxDevC++

編譯器

gcc 編譯器

TinyCC 編譯器

LCC 編譯器

應用主題

CGI 程式

GNU 程式

視窗程式

影像處理

練習題

訊息

相關網站

參考文獻

最新修改

簡體版

English

執行結果

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

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

程式碼

#include <stdio.h>
#include <assert.h>

#define NIL -1

typedef struct {
    wchar_t *str;
    int strIdx, strMax;
} WcsTable;

void wcsTableNew(WcsTable *st, wchar_t *str, int strMax) {
     st->str = str;
     st->strIdx = 0;
     st->strMax = strMax;
}

int wcsPut(WcsTable *st, wchar_t *key) {
    wcscpy(&st->str[st->strIdx], key);
    int strBegin = st->strIdx;
    st->strIdx += wcslen(key)+1;
    return strBegin;
}

typedef struct {
    int *hashTable;
    int hashMax, hashCount;
    WcsTable *strTable;
} WHashTable;

void wHashClear(int table[], int size) {
    int i;
    for (i=0; i<size; i++)
        table[i] = NIL;
}

void wHashNew(WHashTable *h, int *hashTable, int hashMax, WcsTable *strTable) {
    h->hashMax   = hashMax;
    h->hashTable = hashTable;
    h->hashCount = 0;
    wHashClear(h->hashTable, hashMax);
    h->strTable = strTable;
}

int wHash(WHashTable *h, wchar_t *key) {
  int i, hashCode=0;
  for (i=0; i<wcslen(key); i++) {
    hashCode = hashCode * 739 + key[i];
    hashCode %= h->hashMax;
  }
  return hashCode;
}

wchar_t *wHashKey(WHashTable *h, int slot) {
    int si = h->hashTable[slot];
    if (si == NIL)
        return NULL;
    else
        return &h->strTable->str[si];
}

int wHashSeek(WHashTable *h, wchar_t *key) {
  int i, slot = wHash(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 (wcscmp(wHashKey(h, i), key)==0)
        return i;
  }
}

int wHashPut(WHashTable *h, wchar_t *key) {
    int slot = wHashSeek(h, key);
    if (h->hashTable[slot] == NIL) {
        h->hashCount ++;
        assert(h->hashCount < h->hashMax);
    }
    h->hashTable[slot] = wcsPut(h->strTable, key);
    return slot;
}

#define HASH_MAX 997
#define STAB_MAX 10000

WHashTable h;
WcsTable  st;
wchar_t strTable[STAB_MAX];
int hashTable[HASH_MAX];

// TEL 相關表格 
int valueTable[HASH_MAX];

int valuePut(wchar_t *key, wchar_t *value) {
    int slot = wHashPut(&h, key);
    valueTable[slot] = wcsPut(h.strTable, value);
    return slot;
}

wchar_t *valueGet(wchar_t *key) {
    int slot = wHashSeek(&h, key);
    if (h.hashTable[slot] == NIL)
       return NULL;
    else
       return &h.strTable->str[valueTable[slot]];
}

int main() {
    wcsTableNew(&st, strTable, STAB_MAX);
    wHashNew(&h, hashTable, HASH_MAX, &st);
    wchar_t *keys[] = {L"John", L"Mary", L"George", L"Peter", NULL};
    wchar_t *tels[] = {L"313530", L"313531", L"313532", L"313533"};
    int i;
    for (i=0; keys[i]!=NULL; i++) {
        wHashPut(&h, keys[i]);
    }
    int gi = wHashSeek(&h, L"George");
    printf("gi=%d key=%ls\n", gi, wHashKey(&h, gi));
    int bi = wHashSeek(&h, L"Betty");
    printf("bi=%d hashTable[bi]=%d\n", bi, h.hashTable[bi]);
    // TEL
    wHashClear(valueTable, HASH_MAX);
    valuePut(L"John", L"313530");
    wchar_t *jtel = valueGet(L"John");
    printf("jtel=%ls\n", jtel);
}

Facebook
page revision: 6, last edited: 09 Nov 2012 04:09
Edit Rate (0) Tags Discuss (0) History Files Print Site tools + Options
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License