我在学校的一项练习中遇到了麻烦。
我必须使用以下结构实现一个哈希表:
struct Book {
char * title;
char * author;
int price;
struct Book * next;
}
我必须创建一个函数initTable()，它创建我的哈希表，这是一个包含1000个元素的结构体Book的表。所以我的函数是:
struct Book* initTable(){
struct Book *tab = malloc(sizeof(struct Book) * 1000);
return tab;
}
注意，该函数应该返回表的第一个元素。但是我不知道这个语法是否正确。
我的问题是:
语法正确吗
如何在表中导航?例如，如果我想转到表的单元格50，我该怎么做?
然后，如果我的哈希表中有冲突，我必须创建一个链表，我把冲突的元素放在其中。但是我的表格中的每个单元格都是一个结构，而不是这个结构的指针，所以我不明白如何链接我的元素。
哈希表用于在常量时间内按键查找集合中的条目。在实现方面，这通常由一个"隐藏"的对象指针数组(而不是对象本身)组成。然后需要一个散列函数，将键转换为数组查找索引(整数)。例如:
ValueObjectType **createHashTable(int hashSize)
{
ValueObjectType **table = malloc( sizeof(ValueObjectType *) * hashSize);
return table;
}
void hashInsert(ValueObjectType **hashTable, KeyObjectType key, ValueObjectType *value)
{
int arrayIndex = hashingFunction(key);
if ( hashTable[arrayIndex] != NULL ) traverseLinkedListAndAdd(...);
else hashTable[arrayIndex] = value;
}
ValueObjectType *lookupByKey(ValueObjectType **hashTable, KeyObjectType key)
{
int arrayIndex = hashingFunction(key);
return traverseLinkedListAndReturnObjectWithKey(...);
}
哈希函数通常包括取一个或多个关键元素(可以是任何类型)并将其转换为单个整数值，然后通过对哈希数组大小取模将其转换为数组索引。
Book结构中链表的目的是处理哈希冲突。在插入时发生哈希冲突，要么是因为给定的键已经存在于哈希中(在这种情况下，您应该用新对象替换值对象引用)，要么是因为哈希函数的非唯一性。当发生后一种情况时，链表用于存储具有不同键的多个条目，这些条目散列到相同的数组索引(通常通过遍历列表，如果看到键相等，则替换列表的元素，否则在末尾添加新对象)。
在上面的示例代码中，我有一个单独的键对象，但是为了评估键的相等性，它需要包含在对象本身中(我怀疑在您的情况下，键是标题和作者的某种组合)，或者包装在元结构中(例如包含指向键和值的指针的"KeyValue"结构，您将散列而不是ValueObjectType)。您需要提供逻辑来计算两个键的相等/不相等，以便正确处理哈希冲突情况。
我没有在这里指定散列函数、链表导航和键相等逻辑，因为这显然是你的老师想让你学习的。
你想
malloc(sizeof(struct book) * 1000)
用于在已分配数组中查找指针算术。这意味着你正在寻找一个偏离初始指针的对象。
的指针算术开始检查http://www.eskimo.com/~scs/cclass/notes/sx10b.html