C中链表的链表

Question

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

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

然后应该包含上述节点的散列table如下：

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

我已经耗尽了我的小脑袋（第一次接触链表），不知道如何创建散列 table 以及如何在每个条目中输入数据。任何帮助将不胜感激。

谢谢！

Answer 1

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

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

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

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

get()或find()：对要查找的元素进行哈希运算得到外链表中的索引，然后在该索引处遍历内链表找到该元素您正在寻找
put() or insert()：对你要查找的元素进行散列，得到外链表中的索引，你会追加到内链表的尾部指数

对于哈希 table 最重要的是，您需要创建 hash() 函数。在这种情况下，由于您的数据看起来是一个 int，您的散列函数应该接受一个 int，然后将该 int 散列到外部链表中的给定位置。

由于您使用链表来表示散列 table 的外部结构，因此您肯定希望创建一个 at() 方法来遍历外部链表 (t_htentry) 和 returns 指向内部链表索引的指针（在你的例子中，一个 t_listnode 节点）。

例子:

我们想将 10、201、302 添加到我们的散列中 table。

第一步是将 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

之一

insert长得像

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
}

find 长得像

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中链表的链表

Linked list of Linked lists in C

c

hashtable

linked-list