我有一个 C 语言的项目,我需要用链表创建一个链式哈希表。 实际上,正如我所见,它是一个以链表为节点的链表。 所以哈希表中每个表项中每个节点的数据结构应该是:
typedef struct node {
int value;
int counter;
struct node *next;
} t_listnode;
则应包含上述节点的哈希表如下:
typedef struct {
t_listnode *head;
t_listnode *tail;
} t_htentry;
我已经耗尽了我的小脑袋(第一次接触链表)并且不知道如何创建哈希表以及如何在每个条目中输入数据。 任何帮助将不胜感激。
谢谢!
最佳答案
此答案假定您使用的是外部链表和内部链表:
首先,为了让您的生活更轻松,您应该为您的内部链表节点
制作一些方法:
insert()
:迭代到链表末尾,添加新节点find()
:遍历列表,看看你的值是不是你要找的
接下来,您需要为哈希表实现相关方法:
get()
orfind()
:将要查找的元素散列得到外链表中的索引,然后遍历内链表在该索引处列出以找到您要查找的元素put()
或insert()
:散列您要查找的元素以获得外部链表中的索引,您将在其中附加到该索引处的内部链表的末尾
对于哈希表最重要的是,您需要创建hash()
函数。在这种情况下,由于您的数据看起来是 int
,因此您的散列函数应该接受一个 int,然后将该 int 散列到外部链表中的给定位置。
由于您使用链表来表示哈希表的外部结构,因此您肯定希望创建一个 at()
方法来遍历外部链表(t_htentry
) 并返回指向内部链表索引的指针(在您的例子中,是一个 t_listnode
节点)。
示例:
我们想将 10、201、302 添加到我们的哈希表中。
第一步是将 t_htentry* hashtable[PRIME_NUMBER]
预分配为质数大小——也就是说,假设我们从一个大小为 5 的数组开始(数组中的每个索引都表示为通过 [ ]
)。 t_listnode* head
已经在每个 t_htentry*
中,(每个 t_htentry*
由 ( )
,头节点用*
表示,尾节点用t
表示)。
0 1 2 3 4 -- indexes
[(*)] [(*)] [(*)] [(*)] [(*)] -- t_htentry*[] with t_listnode* head in each index
| | | | |
v v v v v -- pointer
(t) (t) (t) (t) (t) -- t_listnode* tail
第二步是散列我们的第一个数据点 - 10。
int idx = hash(10); //-> 2
第三步是在我们的外部列表中定位idx
(2)。 hashtable[idx]
将为我们提供一个恒定的时间查找!
第四步是现在将具有数据点 5 的节点附加到该列表。
// append value to hashtable[idx] (where "next" points to TAIL)
insert(hashtable[idx], 5);
[(*)] [(*)] [(*)] [(*)] [(*)]
| | | | |
| | v | |
| | (5) | |
| | | | |
v v v v v
(t) (t) (t) (t) (t)
第五步,我们现在继续我们的下一个数据点,201。假设 201 哈希值也为 idx = 2
。 (从现在开始,我将省略为所有没有任何数据的索引绘制 [(t)]
,但请注意它们仍然存在。)
idx = hash(201); //-> 2
t_listnode * spot = positionAt(hashtable, idx);
insert(spot, 201);
[(*)] [(*)] [(*)] [(*)] [(*)]
|
v
(5)
|
v
(2)
|
v
(t)
下一步,我们将移至最后一个数据点 302。假设 302 哈希为 idx = 0
。
idx = hash(302); //-> 0
t_listnode * spot = positionAt(hashtable, idx);
insert(spot, 302);
[(*)] [(*)] [(*)] [(*)] [(*)]
| |
v v
(302) (5)
| |
v v
(t) (2)
|
v
(t)
在哪里,
hash
看起来像 these examples 之一
插入
看起来像
void insert(t_htentry * bucket, int value) {
// copy spot to a new t_listnode* and iterate until spot->next is NULL
// (i.e., t_htentry* tmp = bucket; tmp = bucket->head->next)
// create a new node with t_listnode->value set to value
// set the current spot's next to the new node
// set the new node's next to the TAIL node
}
找到
的样子
bool find(hashtable, int value) {
// hash "value" and go to hashtable[idx] as before
// iterate through hashtable[idx]'s linked list as before using a copy
// of that t_htentry*.
// if the node that you're on has ->value == value, return true
// else continue until you're at the end of the list, and return false
}
此实现的性能将为 find
和 insert
摊销 O(1)。了解原因很重要。
关于c - C中链表的链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29683895/