C语言实现双链表逆置算法 (VS2022)

本文将介绍使用C语言编写算法，实现双链表节点逆置功能。代码示例可在VS 2022中编译运行，并附带详细解释和示例。

代码实现

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

// 双链表节点结构
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

// 创建一个新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败！");
        exit(1);
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 将双链表逆置
void reverseList(struct Node** head) {
    struct Node* current = *head;
    struct Node* temp = NULL;
    
    // 交换每个节点的prev和next指针
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev; // 继续处理下一个节点
    }
    
    // 更新头节点
    if (temp != NULL) {
        *head = temp->prev;
    }
}

// 打印双链表
void printList(struct Node* head) {
    struct Node* current = head;
    printf('双链表: ');
    while (current != NULL) {
        printf('%d ', current->data);
        current = current->next;
    }
    printf('
');
}

int main() {
    // 创建示例双链表
    struct Node* head = createNode(1);
    struct Node* node2 = createNode(2);
    struct Node* node3 = createNode(3);
    struct Node* node4 = createNode(4);
    struct Node* node5 = createNode(5);
    
    // 构建双链表
    head->next = node2;
    node2->prev = head;
    node2->next = node3;
    node3->prev = node2;
    node3->next = node4;
    node4->prev = node3;
    node4->next = node5;
    node5->prev = node4;
    
    printf('逆置前：\n');
    printList(head);
    
    // 逆置双链表
    reverseList(&head);
    
    printf('逆置后：\n');
    printList(head);
    
    return 0;
}

代码解释

双链表节点结构

struct Node 定义了双链表节点的结构，包含三个成员：
- data: 节点存储的数据
- prev: 指向该节点的前一个节点
- next: 指向该节点的下一个节点
创建新节点

createNode 函数用于创建一个新的节点，并初始化其数据、前驱指针和后继指针。
逆置双链表

reverseList 函数用于逆置双链表。算法的核心思想是：
- 遍历双链表，从头节点开始，依次交换每个节点的前驱指针和后继指针。
- 更新头节点指针，指向逆置后的链表的头节点。
打印双链表

printList 函数用于打印双链表，以便观察逆置前后的效果。

编译运行

将上述代码复制到VS 2022中的C文件中，并进行编译运行。程序将输出逆置前后的双链表，展示逆置算法的效果。

总结

本文介绍了使用C语言实现双链表逆置算法的方法，并提供了完整的代码示例。通过代码解释和运行结果，可以帮助读者理解双链表逆置的实现原理和操作步骤。