4
我試圖通過一個字段搜索結構一個記錄的數組(id
)。代碼編譯,但不起作用 代碼編譯,但不起作用。我認爲這是創建哈希表的問題。但是不能解決這個問題,我是一個有散列表的初學者,可以創建一個大小爲元素數的散列表嗎?無論如何,訪問的時間是O(1)所以我只用了很多內存嗎?錯誤的實現使用散列表搜索記錄。未找到結果?
這是我的完整代碼,在此先感謝您的每一條建議/意見。
這些都是我的ADT:
typedef struct _SPerson {
char name[20];
char surname[20];
char id[20];
char telephone[20];
} SPerson;
typedef struct SInfo {
int key;
SPerson value;
} TInfo;
struct SNode_list { /*list node*/
TInfo information; /*data->key and value*/
struct LNode *next; /*pointer to next element*/
};
typedef struct SNode_list LNode; // LNode single element of list
typedef LNode *List;
/*hash table struct*/
typedef struct _HashTable {
int bucket_number;
List *bucket;
} HashTable;
我在 SPerson Archive[20000];
裝載的20000個記錄數組在我的功能來搜索數據我這樣做:
這些是我的功能:
插入
void hashtable_insert(HashTable *ht, int key, SPerson value) {
TInfo info;
LNode *node;
unsigned h;
info.key = key;
info.value = value;
h = hash(value.id) % ht->bucket_number;
node = list_search_unordered(ht->bucket[h], info);
if (node == NULL) /*no collision*/
ht->bucket[h] = list_insert_at_index(ht->bucket[h], info);
else /*push*/
node->information = info;
}
搜索
SPerson *hashtable_search(HashTable *ht, char *key) {
unsigned h = hash(key) % ht->bucket_number;
TInfo info;
info.key = key;
LNode *node = list_search_unordered(ht->bucket[h], info);
if (node == NULL)
return NULL;
else
return &node->information.value;
}
列表搜索
LNode *list_search_unordered(List list, TInfo info) {
LNode *curr;
curr = list;
while ((curr != NULL) && !equal(info, curr->information)) {
curr = curr->next;
}
if (curr == NULL)
return NULL;
else
return curr;
}
平等
bool equal(TInfo a, TInfo b) {
return a.key == b.key;
}
創建
HashTable *hashtable_create(int buckets) {
int i;
HashTable *p = (HashTable *)malloc(sizeof(HashTable)); /*allocation*/
assert(p != NULL); /*assert verificate if allocation went ok*/
assert(buckets > 0);
p->bucket_number = buckets;
p->bucket = (List *)malloc(sizeof(List)*buckets);
assert(p->bucket != NULL);
for (i = 0; i < buckets; i++)
p->bucket[i] = NULL;
return p;
}
哈希算法
unsigned long hash(unsigned char *str) { /*djb algorithm*/
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
所以我應該用char *鍵代替int鍵嗎? – user3289840
在'hashtable_search'中,使用'unsigned h = hash(key)%ht-> bucket_number'從_key_獲得'h'值。 **但在'hashtable_insert'中,您計算'h' _differently_,**不是**使用鍵,而是使用該值代替:'h = hash(value.id)%ht-> bucket_number;'。這是@MajeedSiddiqui所說的。你應該在兩個函數中以相同的方式計算'h'。 – Castaglia