c-用bucket实现链表

Question

我有一个链表，它在每个节点中存储一个文本字符串，每个节点都可以指向下一个节点(基本上就是链表的作用)。

我正在尝试制作另一个链表，其中每个节点都有一个给定大小(bucket)的字符串数组，比如说20。

因此，每个节点存储一个字符串数组[20]和到下一个节点的链接(bucket链表)。

在链表中存储(添加新项目)时，它应该不断填充当前节点的数组或存储桶，直到其满为止，当其满时，它应将数组或存储盒拆分为两个相同大小的存储桶(20)，每个存储桶中有10个项目。

通过这种方式，所有节点都将具有半空的存储桶——在任何给定时间，只有第一个存储桶可以是半空或超过半空。再次开始将新字符串填充到正确的bucket(半空bucket中的一个)中，直到其填充完毕，然后重复该过程。

我在想，如果在任何地方都有这样的数据结构的实现，请给我指一下。这样我就可以看一看，更好地理解它。

Answer 1

好的，您有两个链表。存储桶列表和节点列表：

bucket -> bucket -> bucket -> NULL
|         |         |
node      node      node
|         |         |
node      node      node
|         |         |
node      node      node
|         |         |
node      NULL      NULL
|
NULL

插入始终位于第一个铲斗。如果溢出，内容将被拆分，后半部分将转移到第一个存储桶之后插入的新存储桶中。

除了节点(nd)和bucket(bt)之外，下面的代码还使用bucket列表(bl)作为所有操作的前端：

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
typedef struct Bucketlist Bucketlist;
typedef struct Bucket Bucket;
typedef struct Node Node;
/*
*      The node holds the actual data, here an int
*/
struct Node {
int data;
Node *next;
};
Node *nd_new(int x)
{
Node *nd = malloc(sizeof(*nd));
nd->data = x;
nd->next = NULL;
return nd;
}
void nd_delete(Node *nd)
{
while (nd) {
Node *nx = nd->next;
free(nd);
nd = nx;
}
}

/*
*      The bucket holds the nodes as a linked list. It has a tail
*      for easy inserting and keeps a count of its elements. Buckets
*      are also organised in a linked list via the next pointer.
*/
struct Bucket {
Node *head;
Node *tail;
Bucket *next;
int count;
};
Bucket *bt_new()
{
Bucket *bt = malloc(sizeof(*bt));
bt->head = NULL;
bt->tail = NULL;
bt->next = NULL;
bt->count = 0;
return bt;
}
void bt_delete(Bucket *bt)
{
while (bt) {
Bucket *nx = bt->next;
nd_delete(bt->head);
free(bt);
bt = nx;
}
}
void bt_split(Bucket *bt)
{
Bucket *nx = bt_new();
Node *nd = bt->head;
int n = bt->count / 2;
nx->next = bt->next;
bt->next = nx;
nx->count = bt->count - n;
bt->count = n;
while (--n) nd = nd->next;
nx->head = nd->next;
nx->tail = bt->tail;
nd->next = NULL;
bt->tail = nd;
}
void bt_add(Bucket *bt, int x)
{
Node *nd = nd_new(x);
if (bt->count >= 20) bt_split(bt);
if (bt->head == NULL) {
bt->head = bt->tail = nd;
} else {
bt->tail->next = nd;
bt->tail = nd;
}
bt->count++;
}
void bt_print(Bucket *bt)
{
Node *nd = bt->head;
printf("%d items [", bt->count);
while (nd) {
if (nd != bt->head) printf(", ");
printf("%d", nd->data);
nd = nd->next;
}
printf("]n");
}

/*
*      The bucket list is just a front end to the linked list of
*      buckets. It is the interface that the cleient code uses.
*/
struct Bucketlist {
Bucket *head;
};
void bl_add(Bucketlist *bl, int x)
{
if (bl->head == NULL) bl->head = bt_new();
bt_add(bl->head, x);
}
void bl_delete(Bucketlist *bl)
{
bt_delete(bl->head);
}
void bl_print(Bucketlist *bl)
{
Bucket *bt = bl->head;
while (bt) {
bt_print(bt);
bt = bt->next;
}
}

int main()
{
Bucketlist bl = {NULL};
int i;
srand(time(NULL));
i = 36 + (rand() & 63);
while (i--) bl_add(&bl, rand() & 1023);
bl_print(&bl);
bl_delete(&bl);
return 0;
}

我在这里使用了整数作为数据，但修改这个字符串列表应该很容易。