c - 反转双向链表问题

Question

我正在尝试反转双向链表，但没有成功。反转后，列表似乎是空的。

这是我的实现:

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct Item Item;
typedef struct DLL DLL;

struct Item {
    int value;
    Item* next;
    Item* prev;
};

struct DLL {
    Item* head;
    Item* tail;
    int size;
    void(*add)(DLL*, int);
    void(*addToTail)(DLL*, int);
};

void add(DLL* list, int val) {
    Item* new_item = (Item*) malloc(sizeof(Item));
    if (new_item == NULL) {
        exit(-1);
    }
    new_item->value = val;
    new_item->next = list->head->next;
    list->head->next = new_item;
    new_item->prev = list->head;
    list->size++;
}

void addToTail(DLL* list, int val) {
    Item* new_item = (Item*) malloc(sizeof(Item));
    if (new_item == NULL) {
        exit(-1);
    }
    new_item->value = val;
    new_item->prev = list->tail->prev;
    list->tail->prev = new_item;
    new_item->next = list->tail;
    list->size++;
}

Item* find(DLL* list, int val) {
    Item* iter = list->head->next;
    while (iter != list->tail) {
        if (iter->value == val) {
            return iter;
        }
        iter = iter->next;
    }
    return NULL;
}

void reverse(DLL* list) {
    Item* current = list->head;
    Item* temp = NULL;
    while (current != NULL) {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;
        current = current->prev;
    }

    temp = list->head;
    list->head = list->tail;
    list->tail = temp;
}

void printList(DLL* list) {
    Item* iter = list->head->next;
    while (iter != list->tail) {
        printf("%d\n", iter->value);
        iter = iter->next;
    }
}

DLL* initDLL() {
    DLL* list = (DLL*) malloc(sizeof(DLL));
    if (list == NULL) {
        exit(-1);
    }

    // Creating head & tail
    list->head = (Item*) malloc(sizeof(Item));
    list->tail = (Item*) malloc(sizeof(Item));
    if (list->head == NULL || list->tail == NULL) {
        free(list);
        exit(-1);
    }

    // Initializing head & tail values just for testing
    list->head->value = 100;
    list->tail->value = 200;

    list->head->prev = NULL;
    list->head->next = list->tail;
    list->tail->prev = list->head;
    list->tail->next = NULL;

    list->size = 0;
    list->add = add;
    list->addToTail = addToTail;

    return list;
}

int main() {
    DLL* my_list = initDLL();
    my_list->add(my_list, 1);
    my_list->add(my_list, 2);
    my_list->add(my_list, 3);

    printList(my_list);
    // Outputs:
    // 3
    // 2
    // 1

    reverse(my_list);

    printList(my_list);
    // Prints nothing since list->head->next == list->tail
}

我以为

3
2
1
1
2
3

但只得到

3
2
1

第一个 printList() 按预期工作，但第二个没有输出。

调查问题我发现在反转列表后，由于某种原因 list->head->next 指向 list->tail，甚至尽管列表中有 3 个元素。

我在网上搜索了示例，但偶然发现了不使用 DLL 结构(例如我的)的实现，而只使用了 Node 结构。

Answer 1

在你的add函数中，你需要在设置new_item->next = list->head-之后将new_item->next->prev设置为new_item >下一步;

void add(DLL* list, int val) {
    Item* new_item = malloc(sizeof *new_item);
    if (new_item == NULL) {
        exit(EXIT_FAILURE);
    }
    new_item->value = val;
    new_item->next = list->head->next;
    new_item->next->prev = new_item;   // <--- This is missing in your code 
    list->head->next = new_item;
    new_item->prev = list->head;
    list->size++;
}

类似的问题存在于您的 addToTail() 中。您需要将 new_item->prev->next 设置为 new_item。