无法将元素压入链表头部

问题描述 投票：0回答：3

我正在尝试在 C 中实现链表，但我遇到了输出错误的问题。第一个元素似乎没有被推到列表的头部。

我期待程序中的以下输出：

1
1

实际产量：

0
0

你知道代码有什么问题吗？谢谢

问题代码：

main.c

#include <stdio.h>
#include "linked_list.h"

int main(void) {
    struct ll_node *node = ll_new();
    ll_push_front(node, 1);
    printf("%d\n", ll_size(node)); // should print 1, actual output: 0
    printf("%d\n", ll_pop_back(node)); // should print 1, actual output: 0
    ll_destroy(node);
    return 0;
}

链接列表.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#include <stdbool.h>

struct ll_node {
    int data;
    struct ll_node *prev;
    struct ll_node *next;
};

struct ll_node *ll_new();
void ll_destroy(struct ll_node *node);
void ll_push_back(struct ll_node *node, int data);
void ll_push_front(struct ll_node *node, int data);
int ll_pop_back(struct ll_node *node);
int ll_pop_front(struct ll_node *node);
int ll_delete_at(struct ll_node *node, int index);
bool ll_contains(struct ll_node *node, int data);
int ll_find(struct ll_node *node, int data);
int ll_size(struct ll_node *node);

#endif //LINKED_LIST_H

链接列表.c

#include "linked_list.h"
#include <stdio.h>
#include <stdlib.h>

struct ll_node *ll_new() {
    struct ll_node* node = (struct ll_node *) malloc(sizeof(struct ll_node *));
    if (!node) {
        fprintf(stderr, "Error: cannot allocate struct ll_node *node at ll_new");
        exit(1);
    }
    node->prev = NULL;
    node->next = NULL;
    return node;
}

void ll_destroy(struct ll_node *node) {
    while (node->next != NULL) {
        struct ll_node *elem = node;
        node = node->next;
        free(elem);
    }
}

void ll_push_back(struct ll_node *node, int data) {
    while (node->next != NULL) {
        node = node->next;
    }
    struct ll_node *current = (struct ll_node *) malloc(sizeof(struct node *));
    current->data = data;
    current->next = NULL;
    current->prev = node;
    node->next = current;
}

void ll_push_front(struct ll_node *node, int data) {
    struct ll_node *current = (struct ll_node *) malloc(sizeof(struct node *));
    current->data = data;
    current->next = node;
    current->prev = NULL;
    node->prev = current;
}

int ll_pop_back(struct ll_node *node) {
    struct ll_node *current = node;
    while (current->next != NULL) {
        current = current->next;
    }
    int old_data = current->data;
    free(current);
    return old_data;
}

int ll_pop_front(struct ll_node *node) {
    // TODO: implement this
}

int ll_delete_at(struct ll_node *node, int index) {
    // TODO: implement this
}

bool ll_contains(struct ll_node *node, int data) {
    while (node->next != NULL) {
        if (node->data != data) {
            return false;
        }
        node = node->next;
    }
    return true;
}

int ll_find(struct ll_node *node, int data) {
    // TODO: implement this
}

int ll_size(struct ll_node *node) {
    int size = 0;
    while (node->next != NULL) {
        ++size;
        node = node->next;
    }
    return size;
}
c algorithm linked-list doubly-linked-list
3个回答
0
投票

当你把一些东西推到列表的前面时，你不需要返回一个指向新列表的指针吗？

当然应该将此代码更改为

return
指向
current
的指针。

void ll_push_front(struct ll_node *node, int data) {
    struct ll_node *current = (struct ll_node *) malloc(sizeof(struct node *));
    current->data = data;
    current->next = node;
    current->prev = NULL;
    node->prev = current;
}

然后在调用函数中，我认为您应该读取该结果并将其存储为新列表？

0
投票
  1. struct ll_node *node = ll_new();
    分配一个新节点（我们称它为根），显然，然后你将一个新节点推到前面（我们称它为节点（1）：
root->next = NULL
root->prev = node(1)
node(1)->next = root
node(1)->prev = NULL

在

main()
中
node *
仍然指向root，而且确实，它的
next
指针为NULL，所以
ll_size()
返回0。你可能想返回新的根节点并在
main()
中这样做：

node = ll_push_front(node, 1);
  1. 更喜欢使用变量而不是类型进行分配，并且不要强制转换
    void *
    指针：
 struct ll_node *current = malloc(sizeof *current);

这也修复了分配指针大小但需要对象大小的缺陷。

  1. 你有一个 

    ll_new()
    功能，但是 
    ll_push_front()
    和 
    ll_push_back()
    再次实现了同样的事情。您应该重构后两者以使用
    ll_new()
    .

  2. 使用 

    struct ll_node
    来表示链表的节点和整个链表并不一定是错误的。例如，根节点具有未初始化的
    data
    。一旦你修复了上面的 1，那么你可以这样做：

struct ll_node *root = ll_push_front(NULL, 1);

您将修改 

ll_push_front()
以处理 
node
参数是 
NULL
.

0
投票

对于函数中的初学者 

ll_new
为列表的节点分配了错误的内存。

struct ll_node* node = (struct ll_node *) malloc(sizeof(struct ll_node *));

相反，您需要写任一个

struct ll_node* node = (struct ll_node *) malloc(sizeof(struct ll_node ));

或

struct ll_node* node = (struct ll_node *) malloc(sizeof( *node ));

该函数没有太大意义，因为它没有初始化创建节点的数据成员

data
。

函数中也存在分配内存同样的问题

ll_push_front

struct ll_node *current = (struct ll_node *) malloc(sizeof(struct node *));

再次你需要写任一个

struct ll_node *current = (struct ll_node *) malloc(sizeof(struct node ));

或

struct ll_node *current = (struct ll_node *) malloc(sizeof( *current ));

实际上，在代码中的任何地方，您都在调用 

malloc
时使用了不正确的表达式。

此外，该函数不会更改指向列表头节点的指针。

它只是将它的数据成员

prev
设置为新创建的节点

因此，函数 

ll_size
将始终返回 
0
，因为在 main 中声明的指针 
next
指向的节点的数据成员 
node
等于 
NULL

int ll_size(struct ll_node *node) {
    int size = 0;
    while (node->next != NULL) {
        ++size;
        node = node->next;
    }
    return size;
}

如果空指针被传递给函数，函数

ll_push_back
可以调用未定义的行为，因为函数中的这个while循环

while (node->next != NULL) {
    node = node->next;
}

函数

ll_pop_back
再次不检查是否传递了空指针

while (current->next != NULL) {
    current = current->next;
}

此外，如果列表仅包含一个节点，则该函数不会更改传递的指针。节点将被删除，指向被删除节点的指针将保持不变。

您的代码包含很多错误。你需要重写它。从 main

中的这个声明开始 
struct ll_node *head = NULL;

并尝试首先编写将一个节点添加到空列表的函数

ll_push_front
。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.