单链表数据结构的实现与应用：C++代码示例

一、实验目的

掌握线性表的链式存储结构的特点，理解链式存储结构表示线性表的方法。
掌握链式存储结构线性表数据元素类型定义的格式与方法。
掌握单链表建立、遍历、查找、新元素插入、及元素删除的原理与方法。
用C++语言实现单链表，并上机调试。

二、实验内容

设计C++类及相关方法，用于维护单链表。
写出建立单链表，并向单链表中输入数据的函数。
实现单链表的建立、遍历、查找、新元素插入、及元素删除，写出输入及输出的内容。
将两个有序单链表合并为一个有序单链表（扩展内容）
双链表及循环链表的实现（扩展内容）

三、实验原理及代码

链式存储结构的特点是数据元素之间通过指针相连，每个节点包含数据元素和指向下一个节点的指针，可以灵活地插入和删除节点，但访问节点需要遍历整个链表。
链式存储结构线性表数据元素类型的定义格式为：

struct Node {
    ElementType data;
    struct Node *next;
};

其中，ElementType为数据元素类型，next为指向下一个节点的指针。

单链表的建立包括创建头节点和逐个插入节点，遍历链表通过指针依次访问每个节点并输出数据元素，查找节点通过比较节点的数据元素进行，新元素插入通过创建新节点并修改指针进行，元素删除通过找到待删除节点的前一个节点，修改指针跳过待删除节点。
以下是单链表的C++实现及相关方法：

#include <iostream>

using namespace std;

typedef int ElementType;

struct Node {
    ElementType data;
    struct Node *next;
};

class LinkedList {
public:
    LinkedList();
    ~LinkedList();
    void insert(ElementType x); // 新元素插入
    bool remove(ElementType x); // 元素删除
    Node* find(ElementType x); // 查找节点
    void traverse(); // 遍历链表

private:
    Node *head;
};

LinkedList::LinkedList() {
    head = new Node;
    head->next = nullptr;
}

LinkedList::~LinkedList() {
    Node *p = head;
    while (p != nullptr) {
        Node *temp = p;
        p = p->next;
        delete temp;
    }
}

void LinkedList::insert(ElementType x) {
    Node *p = new Node;
    p->data = x;
    p->next = head->next;
    head->next = p;
}

bool LinkedList::remove(ElementType x) {
    Node *p = head;
    while (p->next != nullptr) {
        if (p->next->data == x) {
            Node *temp = p->next;
            p->next = p->next->next;
            delete temp;
            return true;
        }
        p = p->next;
    }
    return false;
}

Node* LinkedList::find(ElementType x) {
    Node *p = head->next;
    while (p != nullptr && p->data != x) {
        p = p->next;
    }
    return p;
}

void LinkedList::traverse() {
    Node *p = head->next;
    while (p != nullptr) {
        cout << p->data << ' '; // 将双引号改为单引号
        p = p->next;
    }
    cout << endl;
}

int main() {
    LinkedList list;
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.insert(4);
    list.remove(3);
    list.traverse();

    Node *node = list.find(2);
    if (node != nullptr) {
        cout << 'Found' << endl; // 将双引号改为单引号
    } else {
        cout << 'Not found' << endl; // 将双引号改为单引号
    }

    return 0;
}

将两个有序单链表合并为一个有序单链表可以通过比较两个链表的节点数据元素大小进行合并，将较小的节点插入到新链表中。
双链表和循环链表的实现类似于单链表，只是每个节点多了一个指向前一个节点的指针，双链表可以实现双向遍历，循环链表的尾节点的指针指向头节点，形成一个循环。

四、实验总结

本次实验通过实践学习了单链表数据结构的实现方法，并了解了其在实际应用中的优势。通过代码示例，掌握了单链表的基本操作，为后续学习更复杂的数据结构打下了坚实的基础。