用桶實現鏈表？

Question

我有一個鏈接列表，它在每個節點中存儲1個文本字符串，每個節點可以指向下一個節點（基本上是鏈接列表的作用）。

我想再拍鏈接列表，其中每個節點都有一個給定大小（桶）的字符串數組讓說20

因此，每個節點存儲串[20]的陣列和一個鏈接下一個節點（存儲區鏈表）。

在鏈接列表中存儲（添加新項目）時，它應該繼續填充當前節點的數組或存儲桶，直到完全填滿爲止，並且應該將數組或存儲桶分成兩個相同大小的桶（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; 
} 

我使用整數作爲此數據，但應該很容易修改這個字符串列表。