c - C 中的双向链表 - 链已损坏，不确定在哪里

Question

已关闭。此问题需要 debugging details 。目前不接受答案。

---

编辑问题以包含 desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem 。这将有助于其他人回答问题。

已关闭 7 年前。

Improve this question

我正在尝试创建一个双向链表并打印它。

我有两个函数，一个在列表的最前面添加，一个在列表的后面添加。但它打印不正确..我觉得我搞砸了一些东西，我知道我声明下一个和上一个指针的方式有问题，但我不太明白它是什么..任何反馈都值得赞赏。谢谢。

这是我的代码

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

struct node
{
    int val;
    struct node *next;
    struct node *prev;
};

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

void initialize(struct list *l)
{
    l->head = NULL;
    l->tail = NULL;
}

void push_front(struct list *l, int value)
{
    if(l->head == NULL)
    {
        l->head = (struct node *)malloc(sizeof(struct node));
        l->head->prev = NULL;
        l->head->val = value;
        if(l->tail == NULL)
            l->head->next = l->tail;
    } else {
        struct node *temp;
        temp = (struct node *)malloc(sizeof(struct node));
        l->head->prev = temp;
        temp->next = l->head;
        temp->val = value;
        temp->prev = NULL;
        l->head = temp;
    }
}

void push_back(struct list *l, int value)
{
    if(l->tail == NULL)
    {
        l->tail = (struct node *)malloc(sizeof(struct node));
        l->tail->next = NULL;
        l->tail->val = value;
        if(l->head == NULL)
            l->tail->prev = l->head;
    } else {
        struct node *temp;
        temp = (struct node *)malloc(sizeof(struct node));
        l->tail->next = temp;
        temp->prev = l->tail;
        temp->val = value;
        temp->next = NULL;
        l->tail = temp;
    }
}

void print(struct list *l)
{
    if(l->head == NULL)
    {
        printf("%s", "List is empty..");
    } else {
        struct node *current;
        current = l->head;
        while(current != NULL)
         {
             printf("%d", current->val);
             current = current->next;
         }
    }

}

int main()
{
    struct list l;
    initialize(&l);

    push_front(&l, 6);
    push_front(&l, 7);
    push_back(&l, 10);
    push_front(&l, 8);
    push_front(&l, 9);
    push_back(&l, 11);

    print(&l);   


    return 0;
}

Answer 1

除其他问题外，您的 push_front() 代码无法确保设置 l->tail。它是:

void push_front(struct list *l, int value)
{
    if(l->head == NULL)
    {
        l->head = (struct node *)malloc(sizeof(struct node));
        l->head->prev = NULL;
        l->head->val = value;
        if(l->tail == NULL)
            l->head->next = l->tail;
    } else {
        struct node *temp;
        temp = (struct node *)malloc(sizeof(struct node));
        l->head->prev = temp;
        temp->next = l->head;
        temp->val = value;
        temp->prev = NULL;
        l->head = temp;
    }
}

它应该检查内存分配是否成功。它应该确保当 l->head 为 null 时设置 l->tail。等等

void push_front(struct list *l, int value)
{
    struct node *node = (struct node *)malloc(sizeof(*node));
    if (node == 0)
        err_error("Failed to allocate memory for a node\n"); // Does not return
    node->val = value;
    node->prev = NULL;

    if (l->head == NULL)
    {
        assert(l->tail == NULL);
        l->head = node;
        node->next = NULL;
        l->tail = node;
    }
    else
    {
        l->head->prev = node;
        node->next = l->head;
        l->head = node;
    }
}

在 push_back() 中也需要进行类似的更改:

void push_back(struct list *l, int value)
{
    struct node *node = (struct node *)malloc(sizeof(*node));
    if (node == NULL)
        err_error("Failed to allocate memory for a node\n");  // Does not return
    node->val = value;
    node->next = NULL;

    if (l->tail == NULL)
    {
        assert(l->head == NULL);
        l->head = node;
        l->tail = node;
        node->prev = NULL;
    }
    else
    {
        assert(l->tail->next == NULL);
        l->tail->next = node;
        node->prev = l->tail;
        l->tail = node;
    }
}

最好有一个 print_backwards() 和一个 print_forwards() 函数。您可以在每次操作后使用它们，以确保列表有意义。您可以添加更多断言以确保事情有意义。

修改print()和main():

void print(struct list *l)
{
    if (l->head == NULL)
        printf("%s\n", "List is empty..");
    else
    {
        struct node *current;
        current = l->head;
        while (current != NULL)
        {
            printf(" %2d", current->val);
            current = current->next;
        }
        putchar('\n');
    }
}

int main(void)
{
    struct list l;
    initialize(&l);

    printf("Push front 6: ");
    push_front(&l, 6);
    print(&l);
    printf("Push front 7: ");
    push_front(&l, 7);
    print(&l);
    printf("Push back 10: ");
    push_back(&l, 10);
    print(&l);
    printf("Push front 8: ");
    push_front(&l, 8);
    print(&l);
    printf("Push front 9: ");
    push_front(&l, 9);
    print(&l);
    printf("Push back 11: ");
    push_back(&l, 11);

    print(&l);
    return 0;
}

示例输出:

Push front 6:   6
Push front 7:   7  6
Push back 10:   7  6 10
Push front 8:   8  7  6 10
Push front 9:   9  8  7  6 10
Push back 11:   9  8  7  6 10 11

这看起来很合理。