我要按以下方式实现哈希表:
struct list
{
char *string;
struct list *next;
};
struct hash_table
{
int size; /* the size of the table */
struct list **table; /* the table elements */
};
我可以不使用上面这样的结构哈希表,而是使用:
struct hash_table
{
int size; /* the size of the table */
struct list *table; /* the table elements */
};
也就是说,对于哈希表元素,我可以使用单指针而不是双指针吗?如果是,请解释元素在表中存储方式的差异?
最佳答案
那要看情况了。如果你看一下表[我],你怎么知道它是空的还是不空的?如果使用list**,那么table[i]是list*类型,因此可以很容易地根据它是否为空来判断它是否为空。如果使用list*类型,那么table[i]是一个列表,因此除非对键使用null、empty或其他值作为指示列表为空的sentinel值,否则它将不起作用。所以,是的,您可以使用list*,但是您需要添加一个额外的sentinel条件,这也可能限制您允许的密钥类型或者,您可以忽略list[i]的第一个元素,但是这是浪费。我还应该指出,使用list*而不是list**会使在表[I]前面插入元素变得更加困难;如果使用list**类型,则只需将新项的下一个指针设置为表[I]的当前值,然后将新分配项的地址分配给表[I]。如果使用类型list*,则需要在表[i]和表[i]>next之间插入项,这使得插入的逻辑不必要地复杂。
另外,我还要补充一点,您的哈希表定义有缺陷。哈希表应该将一组项映射到另一组项。列表结构只有一个值。它需要一个键和一个值。更好的散列表声明如下:
typedef struct HashTableEntry
{
char* key;
void* value;
struct HashTableEntry* next;
} HashTableEntry;
typedef struct HashTable
{
HashTableEntry** entries;
int capacity; // size of entries
int length; // number of key/value pairs currently in map
} HashTable;
关于c - 我可以在C语言的哈希表中使用单个指针吗?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/2849344/