Реализация связанного списка с ведром?

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

.

Я использовал целые числа в качестве данных здесь, но это должно быть легко изменить этот список для строк.