将数组节点添加到链表

Question

我必须构建一个链表，每个节点都是一个 16 字节的数组。使用适用于单个 uint8_t 值的代码，我稍微修改它以接受 16 个字节。但是，每当我打印列表时，所有节点都是最后添加的节点。我做错了什么？

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>

struct array_deck
{
    uint8_t *val;
    struct array_deck *next;
};

struct array_deck *head = NULL;
struct array_deck *curr = NULL;

int sizeOfSet;

struct array_deck *create_list(uint8_t *val)
{
    struct array_deck *ptr = (struct array_deck*)malloc(sizeof(struct array_deck));

    if(NULL == ptr)
        return NULL;

    ptr->val = val;
    ptr->next = NULL;

    head = curr = ptr;
    return ptr;
}

void print_list(void)
{
    struct array_deck *ptr = head;

    while(ptr != NULL)
    {
        printf("\n");
        printf("actually added = ");
        for (int i = 0; i < 16; i++) {
            uint8_t blah = ptr->val[i];
            printf("[%2i] ",blah);
        }
        ptr = ptr->next;
    }

        printf("\n");
    return;
}

struct array_deck *add_to_list(uint8_t *data, bool add_to_end)
{
    printf("array to be added = ");
    for (int i = 0; i < 16; i++) {
        printf("[%2X] ",data[i]);
    }

    if(NULL == head)
        return (create_list(data));

    struct array_deck *ptr = (struct array_deck*)malloc(sizeof(struct array_deck));
    if(NULL == ptr)
        return NULL;

    ptr->val = data;
    ptr->next = NULL;

    if(add_to_end)
    {
        curr->next = ptr;
        curr = ptr;
    }
    else
    {
        ptr->next = head;
        head = ptr;
    }

    return ptr;
}

int main(void)
{
    printf ("# of arrays  >> ");
    scanf ("%d", &sizeOfSet);

    uint8_t data[16];

    for(int i = 1; i<=sizeOfSet; i++){
        for (int j = 0; j < 16; j++) {
            data[j] = i;
        }
        printf("\n");
        add_to_list(data,true);
    }

    print_list();

    return 0;
}

示例运行构建具有 3 个节点的链表：

# of arrays  >> 3

array to be added = [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] 
array to be added = [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] [ 2] 
array to be added = [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] 
actually added = [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] 
actually added = [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] 
actually added = [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] [ 3] 
Program ended with exit code: 0

Answer 1

您的所有 array_deck -> val 都指向 相同的内存地址 - 指向 main 中的局部变量 data。您要覆盖它 N 次，这就是它打印最后插入的值的原因。

要解决问题，您应该 将 data 数组复制 到新数组中，并将新分配的数组地址分配给 ptr->val。

struct array_deck *add_to_list(uint8_t *data, bool add_to_end)
{
    ...

    struct array_deck *ptr = (struct array_deck*)malloc(sizeof(struct array_deck));
    if(NULL == ptr)
        return NULL;

    ptr->val = malloc(16*sizeof(uint8_t));
    memcpy(ptr->val, data, 16*sizeof(uint8_t));
    ptr->next = NULL;

    ...
}

P.S。删除 create_list 函数并在 add_to_list.

中执行分配给 head 的所有逻辑会很好

Answer 2

在create_list和add_to_list中，节点数据没有被正确复制。显示的代码只是存储一个指向传入数据的指针，而不是复制数据。所以结果是所有节点最终都指向 main 中定义的相同 data，因此在打印出来时会产生相同的值。

有多种方法可以解决此问题。有些比其他的更优雅，但都需要复制数据。

最简单的方法是假定固定大小的数据并为数据声明具有静态内存的节点结构。像这样：

#define DATA_BYTES 16
struct array_deck
{
    uint8_t val[DATA_BYTES];
    struct array_deck *next;
};

然后用数据副本替换列表函数中的指针赋值。例如：

memcpy(ptr->val, val, sizeof(ptr->val));

一个更 flexible/elegant 的解决方案是在节点本身中显式存储数据的大小，这样您就可以拥有可变大小的数据。然后使用动态内存分配（malloc 和朋友）为节点 val.

获取内存

将数组节点添加到链表

Adding array nodes to linked list

c

arrays

linked-list