用bucket实现链表？

Question

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

我正在尝试创建另一个链表，其中每个节点都有一个给定大小（桶）的字符串数组，比如说 20。

因此每个节点存储一个字符串数组[20]和到下一个节点的链接（桶链表）。

在链表中存储（添加新项目）时，它应该继续填充当前节点的数组或存储桶，直到其满，当其满时，它应该将数组或存储桶分成2个相同大小（20）的存储桶，并在其中包含10个项目每个桶。

这样，所有节点都将拥有半空的桶，在任何给定时间，只有第一个桶可以是半空或超过半空。再次开始将新字符串填充到正确的桶（半空桶之一）中，直到填满并重复该过程。

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

Answer 1

好的，你有两个链表。桶列表和节点列表：

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

插入总是到第一个存储桶。如果溢出，内容将被拆分，并将后半部分传输到插入到第一个存储桶之后的新存储桶中。

除了节点（nd）和水桶（bt），下面的代码使用了一个存储桶列表（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;
}

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