C中链接列表的链接列表

I have a project in C that I need to create a chained hash table with linked lists. Actually as I see it is a linked list with linked lists as nodes. So the data structure of each node in each entry in hash table should be:

我在C中有一个项目,我需要创建一个链接列表的链式哈希表。实际上,因为我看到它是一个链表,链表作为节点。因此,哈希表中每个条目中每个节点的数据结构应该是:

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

and then the hash table that should contain the above nodes is stated as below:

然后应该包含上述节点的哈希表如下所示:

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

I have drained my little brain (first time touching linked lists) and can't figure how to create the hash table and how to enter data in each entry. Any help would be highly appreciated.

我已经耗尽了我的小脑(第一次触摸链表),无法想出如何创建哈希表以及如何在每个条目中输入数据。任何帮助将受到高度赞赏。

Thank you!

1 个解决方案

#1

This answer assumes you're using an outer linked list and an inner linked list:

这个答案假设您正在使用外链表和内链表:

First, to make your life easier, you should make some methods for your inner linked list node:

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

insert(): Iterate to the end of the linked list and add a new node

insert():迭代到链表的末尾并添加一个新节点

find(): Iterate through the list and see if your value is what you're looking for

find():遍历列表,看看你的值是否正是你想要的

Next, you'll want to implement the relevant methods for a Hash Table:

接下来,您将要实现哈希表的相关方法:

get() or find(): hash the element you're looking for to get the index in the outer linked list, and then iterate through the inner linked list at that index to find the element you're looking for

get()或find():散列您要查找的元素以获取外部链接列表中的索引,然后遍历该索引处的内部链接列表以查找您要查找的元素

put() or insert(): hash the element you're looking for to get the index in the outer linked list, where you'll append to the end of the inner linked list at that index

put()或insert():散列您要查找的元素以获取外部链接列表中的索引,您将在该链接列表中附加到内部链接列表的末尾

Most importantly for a hash table, you'll want to create your hash() function. In this case, since your data appears to be an int, your hash function should take in an int and then hash that int to a given spot in the outer linked list.

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

Since you're using a linked list to represent the outer structure of the hash table, you will definitely want to create an at() method that iterates through the outer linked-list (t_htentry) and returns a pointer to the index of the inner linked list (in your case, a t_listnode node).

由于您使用链接列表来表示哈希表的外部结构,因此您肯定希望创建一个迭代通过外部链表(t_htentry)的at()方法并返回指向内部索引的指针链表(在您的情况下,是一个t_listnode节点)。

Example:

We want to add 10, 201, 302 into our hash table.

我们想在我们的哈希表中添加10,201,302。

First step is to pre-allocate the t_htentry* hashtable[PRIME_NUMBER] to a prime size -- i.e., let's say we start with an array of size 5 (each index in the array is denoted by [ ]). The t_listnode* head is already in each of the t_htentry*'s, (each t_htentry* is denoted by ( ), the head nodes are denoted by *, and the tail nodes are denoted by t).

第一步是将t_htentry *哈希表[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

Second step is to hash our first data point - 10.

第二步是哈希我们的第一个数据点--10。

int idx = hash(10); //-> 2

Third step is to locate idx (2) in our outer list. hashtable[idx] will give us a constant time lookup!

第三步是在我们的外部列表中找到idx(2)。 hashtable [idx]会给我们一个恒定的时间查找!

Fourth step is to now append a node with the data point 5 to that list.

第四步是现在将具有数据点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)

Fifth step, we now proceed to our next data point, 201. Let's say 201 hashes to idx = 2 as well. (From this point on, I'm omitting drawing the [(t)]'s for all indices that don't have any data in them, but note that they are still there.)

第五步,我们现在进入下一个数据点201.假设201哈希值也是idx = 2。 (从现在开始,我省略了为所有没有任何数据的索引绘制[(t)]的内容,但请注意它们仍在那里。)

idx = hash(201); //-> 2
t_listnode * spot = positionAt(hashtable, idx);
insert(spot, 201);

[(*)]  [(*)]  [(*)]  [(*)]  [(*)]
                |
                v
               (5)
                |
                v
               (2)
                |
                v
               (t)

Next step, we'll move to our last data point, 302. Let's say 302 hashes to idx = 0.

下一步,我们将移动到我们的最后一个数据点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)

where,

hash would look like one of these examples

hash看起来就像这些例子中的一个

insert looks like

插入看起来像

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 looks like

找起来像

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
}

The performance for this implementation will be O(1) amortized for find and insert. It's important that you understand why.

此实现的性能将为查找和插入分摊O(1)。了解原因非常重要。

#1