c - C中链表的链表

Question

我有一个 C 语言的项目，我需要用链表创建一个链式哈希表。实际上，正如我所见，它是一个以链表为节点的链表。所以哈希表中每个表项中每个节点的数据结构应该是:

typedef struct node {
    int value;
    int counter;
    struct node *next;
} t_listnode;

则应包含上述节点的哈希表如下:

typedef struct {
    t_listnode *head;
    t_listnode *tail;
} t_htentry;

我已经耗尽了我的小脑袋(第一次接触链表)并且不知道如何创建哈希表以及如何在每个条目中输入数据。任何帮助将不胜感激。

谢谢!

Answer 1

此答案假定您使用的是外部链表和内部链表:

首先，为了让您的生活更轻松，您应该为您的内部链表节点制作一些方法:

• insert():迭代到链表末尾，添加新节点
• find():遍历列表，看看你的值是不是你要找的

接下来，您需要为哈希表实现相关方法:

• get() or find():将要查找的元素散列得到外链表中的索引，然后遍历内链表在该索引处列出以找到您要查找的元素
• 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)。了解原因很重要。