双向链表逆向——打印出垃圾数据

Question

我对这部分代码有疑问。我的目标是反转双向链表。当我尝试打印出反向列表时收到垃圾值。

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

typedef struct list{
    Node* head;
    Node* tail;
}List;

void pushFront(List* l, Node* node){
    if(l->head == NULL){
        l->head = node;
        l->tail = node;
        l->tail->next = NULL;
    }else{
        l->head->prev = node;
        node->next = l->head;
        l->head = node;
    }
}
void printList(List* list){

    Node *ptr = list->head;
    while(ptr != NULL){
        printf("%i ",ptr->val);
        ptr = ptr->next;
    }
    puts("");
    free(ptr);
}

void reverse(List* lista){

    Node* ptr = lista->head;
    Node* temp = NULL;
    while(ptr != NULL){
        temp = ptr->prev;
        ptr->prev = ptr->next;
        ptr->next = temp;
        ptr = ptr->prev;
    }

    if(temp != NULL)
        lista->head = temp->prev;
    free(ptr);
    free(temp);
}

我收到的输出：

Original list: 1 2 3 4 5 6 7

Reversed list: 1 8532616 3 4 5 6 7 8528368 2002618240

Answer 1

我猜你在同一个列表上使用了你的函数 printList 两次（一次在反转列表之前，一次在反转列表之后），这会导致未定义的行为，因为你在 printList 期间释放你的列表，然后尝试访问和使用这些相同的内存位置 -> 未完成时不要释放你的东西：

void printList(List* list){

    Node *ptr = list->head;
    while(ptr != NULL){
        printf("%i ",ptr->val);
        ptr = ptr->next;
    }
    puts("");
    // free(ptr); --> Remove this line
}

Answer 2

为什么要释放 printList() 和 reverse() 中的节点？在 C 中，您应该只释放以前分配的变量，例如 malloc()。当你在 C 函数中声明变量时，它会自动分配到堆栈或其他内存区域（甚至在 CPU 寄存器中）。它们也会在您的函数结束时自动释放。如果您动态分配节点，然后在 "reverse" 函数中释放它们，我希望在读取释放的节点时看到垃圾。我试图删除 "free" 调用并且代码运行良好。 https://ideone.com/CN1MaC

#include <stdio.h>

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

typedef struct list{
    Node* head;
    Node* tail;
}List;

void pushFront(List* l, Node* node){
    if(l->head == NULL){
        l->head = node;
        l->tail = node;
        l->tail->next = NULL;
    }else{
        l->head->prev = node;
        node->next = l->head;
        l->head = node;
    }
}
void printList(List* list){

    Node *ptr = list->head;
    while(ptr != NULL){
        printf("%i ",ptr->val);
        ptr = ptr->next;
    }
    puts("");
}

void reverse(List* lista){

    Node* ptr = lista->head;
    Node* temp = NULL;
    while(ptr != NULL){
        temp = ptr->prev;
        ptr->prev = ptr->next;
        ptr->next = temp;
        ptr = ptr->prev;
    }

    if(temp != NULL)
        lista->head = temp->prev;
}

int main(void) {
    List list = { NULL, NULL };
    Node nodeArr[7];
    int i;

    for( i = 0; i < 7; i++ )
    {
        nodeArr[i].val = 7 - i;
        nodeArr[i].prev = NULL;
        nodeArr[i].next = NULL;
        pushFront(&list, &nodeArr[i]);
    }

    printList(&list);
    reverse(&list);
    printList(&list);

    // your code goes here
    return 0;
}

输出：

1 2 3 4 5 6 7 
7 6 5 4 3 2 1

双向链表逆向——打印出垃圾数据

Doubly linked list reversing - printing out garbage data

c

reverse

struct

data-structures

doubly-linked-list