列出双向链表项 C

Question

我是 C.I 的新手，我正在尝试创建一个双向链表，其中数据字段是一个结构。但是当我输出元素时，只有结构的第一个字段被正确显示。

struct n
{
    int a;
    int b;

};

typedef struct _Node {
    struct n *value;
    struct _Node *next;
    struct _Node *prev;
} Node;


typedef struct _DblLinkedList {
    size_t size;
    Node *head;
    Node *tail;
} DblLinkedList;


DblLinkedList* createDblLinkedList() {
    DblLinkedList *tmp = (DblLinkedList*) malloc(sizeof(DblLinkedList));
    tmp->size = 0;
    tmp->head = tmp->tail = NULL;
    return tmp;
}

void pushBack(DblLinkedList *list, struct n *value) {
    Node *tmp = (Node*) malloc(sizeof(Node));
    if (tmp == NULL) {
        exit(3);
    }
    tmp->value = value;
    tmp->next = NULL;
    tmp->prev = list->tail;
    if (list->tail) {
        list->tail->next = tmp;
    }
    list->tail = tmp;

    if (list->head == NULL) {
        list->head = tmp;
    }
    list->size++;
}
void printInt(struct n *value) {
    printf("%d, %d", value->a, value->b);
}
void printDblLinkedList(DblLinkedList *list, void (*fun)(struct n*)) {
    Node *tmp = list->head;
    while (tmp) {
        fun(tmp->value);
        tmp = tmp->next;
        printf("\n");
    }
}

所以，我有几个问题。我是否正确声明了节点值字段？我是否正确地将节点插入到列表的末尾？我是否正确地输出了双向链表项？我的错误在哪里以及如何解决？

Answer 1

Did I declare the node value field correctly?

这取决于你的意图。在存储指向 struct n 的指针方面：是的。

Am I inserting the node at the end of the list correctly?

是的。

Am I doing the output of doubly linked list items correctly?

是的。

And where is my mistake and how to fix it?

从我的角度来看，代码是有效的，但可能会产生误导的是 pushBack 的运行方式。 pushBack 按原样获取 struct n 指针并将其存储在 Node 中。您没有 post pushBack 调用者代码，但如果调用者假设 struct n 被复制，当前的实现可能会导致问题。

为了说明这一点，请考虑以下内容：

  struct n value;
  value.a = 1;
  value.b = 2;
  pushBack(list, &value);
  value.a = 3;
  value.b = 4;
  pushBack(list, &value);

通过重用值，两个链表节点将有效地包含相同的值。此外，插入的 struct n 指针必须在列表的整个生命周期内保持有效。因此，插入堆栈分配的值（稍后将通过离开其作用域来释放）或过早释放动态分配的值可能会导致不正确的值。只要调用者知道，这不一定是问题。

通常有 3 种方式处理内存所有权：

数据结构拥有值（就像它拥有节点一样）并负责释放它们
数据结构复制值并负责释放它们
调用者拥有值并负责释放它们

对于链表，策略 #3 有很多优点，因为可以从现有值创建链表，而无需任何复制或所有权转移，这肯定需要更改现有代码。这基本上就是您的代码目前正在做的事情。

列出双向链表项 C

listing doubly linked list items C

c

struct

linked-list

doubly-linked-list