c - 用桶实现链表？

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;
}

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