c - 为链表数组分配内存

Question

大家好，我是链表的新手，但我很确定我知道它们是如何工作的，从理论上讲，我想我可能有语法误解或内存管理错误。

编辑:我的主要目的是制作一个由数组索引的列表集合，每个数组元素都是一个头(或根)节点。我在动态分配此结构数组时遇到问题。

我正在做的是:

typedef struct item_list{
int item_name;
int item_supplier;
int item_price;
struct item_list *next
}node; 

int i;
node ** shop_1 = (node **)malloc(shop_items_elements * sizeof(node)); 

for (i=0;i<=shop_items_elements;i++)
{
    shop_1[i]->next=NULL;
}

当我尝试为元素 i 处的 next 赋予 NULL 值时出现段错误。

Answer 1

问题是您正试图为 20000 个项目分配内存作为一个连续的 block 。这意味着您实际上还没有理解链表。

我认为您将随机访问数组功能与纯链表混合在一起，纯链表不允许在不遍历列表的情况下访问单个项目。

---

链表通常有一个 head 和 tail 节点，当列表中没有元素时，它们最初为 NULL:

node* head = NULL;
node* tail = NULL;

添加新节点时，您首先使用大小为单个节点结构的 malloc 分配它:

node* the_new_node = (node*)malloc(sizeof(node));

初始化结构成员，特别是将每个新节点的next设置为NULL。然后使用此 append_node() 函数将节点追加到链表中:

void append_node(node** head, node** tail, node* the_new_node)
{
  if(*tail == NULL)
  { // list was empty
    *head = *tail = the_new_node;
  }
  else
  {
    (*tail)->next = the_new_node; // link previous tail node with new one
    *tail = the_new_node; // set the tail pointer to the new node
  }

请注意更新 head 和 tail 指针所需的指针。为您要添加的任何给定 n 调用这样的函数:

append_node(&head, &tail, n);

对每个新节点重复此操作。

封装链表的更好方法是将头指针和尾指针放入另一个结构中

typedef struct linked_list
{
  node* head;
  node* tail;
} list;

并使用它的一个实例作为 append_node() 的第一个参数(我将留给你作为练习；)

当使用这样的链表时，不可能在不到 O(n) 的时间内方便地访问第 N 个节点，因为您必须遵循所有 next 指针从 head 节点开始，直到到达第 N 节点。

---

编辑:如果您希望能够为商店商品编制索引并从每个元素构建一个链表，我建议采用以下解决方案:

node** shop_1 = (node**)malloc(shop_items_elements * sizeof(node*));
int i;
for(i = 0; i < shop_items_elements; ++i)
{
  node* n = (node*)malloc(sizeof(node));
  n->next = NULL;
  shop_1[i] = n;
}

您首先分配一个指向 node 指针的指针数组，当然这些指针必须单独分配。看一下这张图以供引用:

实际的节点实例可能大于指针的大小(与图中绘制的不同)，这就是为什么您在 block 中分配 N * sizeof(node*) 而不是 的原因N * sizeof(node).