C - 尝试创建一个 LinkedList 指针数组

Question

我试图在 C 中创建一个 HashTable，其中每个“桶”都是一个指向 LinkedList 的指针。也就是说，我需要创建一个 LinkedList 指针数组。

截至目前，SomeHashTable->Buckets[i] 正在返回一个非指针 LinkedList。我一直在到处寻找答案，但我找不到任何东西。也许我忽略了什么？我在下面给出了我当前的代码。

HashTable.h

#include "LinkedList.h"

typedef struct HashTable
{
  LinkedList* Buckets[1009];
} HashTable;

//Creates new hashtable
HashTable* HashTable_new();

//Hashes and adds a new entry
void HashTable_add(HashTable* Table, int data);

HashTable.c

#include "HashTable.h"
HashTable* HashTable_new()
{
  HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
  newTable->Buckets = malloc(1009 * sizeof(LinkedList*));

  //Create linked lists
  for (int i = 0; i < 1009; i++)
  {
    newTable->Buckets[i] = LinkedList_new();
  }

  return newTable;
}

void HashTable_add(HashTable* Table, int data)
{
  int index = data % 1009;

  //Get bucket to hash to
  LinkedList* BucketHead = (Table->Buckets[index]);
  //Hash it iiinnnn real good
  LinkedList_add_at_end(BucketHead, data);
}

供引用的链表结构:

typedef struct LinkedListNode {
    int data;
    struct LinkedListNode *next;
    struct LinkedListNode *prev;
} LinkedListNode;

typedef struct LinkedList {
    struct LinkedListNode *first;
    struct LinkedListNode *last;
} LinkedList;

Answer 1

正如 H.S. 的评论所提到的，不需要动态和静态分配 Buckets 数组。

这一行:

newTable->Buckets = malloc(1009 * sizeof(LinkedList*));

正在覆盖指向静态分配数组的指针，这可能不是您想要的。为了可伸缩性，我会放弃静态数组并坚持使用 malloc()。这样您就可以使用 HashTable_new() 的参数来指定 buckets 数组的大小，如下所示:

HashTable* HashTable_new(int nBuckets)
{
  HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
  newTable->Buckets = malloc(nBuckets * sizeof(LinkedList*)); 
  newTable->nBuckets = nBuckets;

  //Create linked lists
  for (int i = 0; i < nBuckets; i++)
  {
    newTable->Buckets[i] = LinkedList_new();
  }

  return newTable;
}

请注意，newTable->Buckets 被分配为指向链表 (LinkedList**) 的指针。您需要跟踪 Buckets[] 的大小，因此将变量添加到结构中，如下所示:

typedef struct HashTable
{
  int nBuckets;
  LinkedList **Buckets;
} HashTable;

只要 LinkedList_new() 的返回类型是 LinkedList* 就可以了，完成后不要忘记 free() 。