信息学实验室作业（六）

更新: 2025/3/15 字数: 0 字时长: 0 分钟

一、实验目的

本次实验聚焦双向链表的实际应用，旨在通过编程实现双向链表的创建、元素添加、遍历以及特定元素删除等功能，深入理解双向链表的数据结构和操作逻辑，提升对数据结构运用和编程实践的能力。

二、实验内容

创建一个双向链表用于存储任意实数，实现链表元素的查看、新元素的添加以及删除链表中所有负数元素的功能。

三、实现思路

定义双向链表节点：设计一个结构体，包含存储实数的数据域、指向前一个节点的指针和指向后一个节点的指针，以此构建双向链表的基本单元。
初始化双向链表：创建一个空的双向链表，为后续添加节点提供基础。
添加新元素：编写添加函数，在链表尾部添加新元素。通过遍历找到链表尾节点，调整指针将新节点接入链表。
查看链表元素：编写遍历函数，从链表头节点出发，利用节点的后向指针依次访问每个节点，输出节点中的数据，从而实现查看链表所有元素的功能。
删除负数元素：遍历双向链表，逐个检查节点数据。若数据为负数，调整该节点前后节点的指针，使其脱离链表，然后释放该节点的内存空间，防止内存泄漏。

四、代码实现

cpp

#include <iostream>

// 定义双向链表节点结构体
struct Node {
    double data;
    Node* prev;
    Node* next;
    Node(double value) : data(value), prev(nullptr), next(nullptr) {}
};

// 在链表尾部添加新元素
void addElement(Node*& head, double value) {
    Node* newNode = new Node(value);
    if (!head) {
        head = newNode;
        return;
    }
    Node* current = head;
    while (current->next) {
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
}

// 遍历链表并输出元素
void displayList(Node* head) {
    Node* current = head;
    while (current) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

// 删除链表中的负数元素
void deleteNegativeNodes(Node*& head) {
    Node* current = head;
    while (current) {
        if (current->data < 0) {
            if (current->prev) {
                current->prev->next = current->next;
            } else {
                head = current->next;
            }
            if (current->next) {
                current->next->prev = current->prev;
            }
            Node* temp = current;
            current = current->next;
            delete temp;
        } else {
            current = current->next;
        }
    }
}

// 释放链表内存
void freeList(Node* head) {
    Node* current = head;
    while (current) {
        Node* temp = current;
        current = current->next;
        delete temp;
    }
}

cpp

int main() {
    Node* head = nullptr;

    // 添加测试数据
    addElement(head, 1.2);
    addElement(head, -3.5);
    addElement(head, 2.8);
    addElement(head, -4.1);
    addElement(head, 5.0);

    std::cout << "原始链表: ";
    displayList(head);

    // 删除负数元素
    deleteNegativeNodes(head);

    std::cout << "删除负数元素后的链表: ";
    displayList(head);

    // 释放链表内存
    freeList(head);

    return 0;
}

五、代码解释

Node结构体：定义了双向链表节点的结构，包含数据成员data，以及用于连接前后节点的指针prev和next。
addElement函数：负责在链表尾部添加新元素。首先创建新节点，若链表为空，直接将新节点设为头节点；否则，通过循环找到尾节点，将新节点连接到尾节点之后，并调整指针关系。
displayList函数：实现链表的遍历和输出功能。从链表头开始，通过next指针逐个访问节点，输出每个节点的数据。
deleteNegativeNodes函数：遍历链表，检查每个节点的数据。当发现负数时，分情况处理：若不是头节点，调整前驱节点的next指针和后继节点的prev指针；若是头节点，则更新头指针。最后释放被删除节点的内存。
freeList函数：在程序结束时，用于释放链表中所有节点占用的内存，避免内存泄漏。
main函数：创建双向链表，添加测试数据，先输出原始链表，再调用删除负数元素的函数，输出处理后的链表，最后释放链表内存。

六、编译与运行

将代码保存为.cpp文件，例如doubly_linked_list_experiment.cpp。
使用g++编译器进行编译，在命令行输入g++ doubly_linked_list_experiment.cpp -o doubly_linked_list_experiment。
编译成功后，在命令行输入./doubly_linked_list_experiment运行程序，观察输出结果。

七、实验总结

通过本次实验，成功掌握了双向链表的基本操作，包括节点添加、遍历和特定元素删除。在实验过程中，深刻体会到双向链表结构中指针操作的复杂性和重要性，遇到了指针指向混乱、内存泄漏等问题，通过反复调试和查阅资料得以解决，这极大地提升了编程和调试能力。后续可以进一步拓展双向链表的功能，如实现更复杂的元素查找、插入和删除操作，或者将双向链表应用于实际问题的解决，以加深对数据结构的理解和应用能力。

信息学实验室作业（六） ​

一、实验目的 ​

二、实验内容 ​

三、实现思路 ​

四、代码实现 ​

五、代码解释 ​

六、编译与运行 ​

七、实验总结 ​