C++ 类模板实现任意类型数据域链表：增删查改功能详解

本文将深入讲解如何使用 C++ 类模板实现任意类型数据域链表，并涵盖创建、销毁、尾插节点、删除、查找和修改等核心操作。我们将提供清晰的代码示例，并附带详细注释说明，帮助读者理解链表的构建和应用。

代码实现

#include <iostream>
using namespace std;

// 实现链表增删查改
template <class T>
class Linklist
{
    template <class T1>
    friend ostream &operator<<(ostream &out, Linklist<T1> &ra);
private:

    T m_data;
    Linklist *m_next;

public:
    Linklist(T data=0);
    ~Linklist();
    void List_add(T const &ra);
    void List_del(T &ra);
    T* List_find(T &ra);
    void List_change(T &ra, T &rb);
};

template <class T>
Linklist<T>::Linklist(T data)
{
    m_data = data;
    m_next = NULL;
}

template <class T>
Linklist<T>::~Linklist()
{
    while (m_next != NULL) {
        Linklist<T> *temp = m_next;
        m_next = m_next->m_next;
        delete temp;
    }
}

template <class T>
void Linklist<T>::List_add(T const &ra)
{
    Linklist<T> *newl = new Linklist<T>(ra);
    Linklist<T> *cur = this;
    while (cur->m_next != NULL) {
        cur = cur->m_next;
    }
    cur->m_next = newl;
}

template <class T>
void Linklist<T>::List_del(T &ra)
{
    Linklist<T> *cur = this;
    while (cur->m_next != NULL) {
        if (cur->m_next->m_data == ra) {
            Linklist<T> *temp = cur->m_next;
            cur->m_next = cur->m_next->m_next;
            delete temp;
            return;
        }
        cur = cur->m_next;
    }
}

template <class T>
T* Linklist<T>::List_find(T &ra)
{
    Linklist<T> *cur = this;
    while (cur != NULL) {
        if (cur->m_data == ra) {
            return &(cur->m_data);
        }
        cur = cur->m_next;
    }
    return NULL;
}

template <class T>
void Linklist<T>::List_change(T &ra, T &rb)
{
    Linklist<T> *cur = this;
    while (cur != NULL) {
        if (cur->m_data == ra) {
            cur->m_data = rb;
            return;
        }
        cur = cur->m_next;
    }
}

template <class T1>
ostream &operator<<(ostream &out, Linklist<T1> &ra)
{
    Linklist<T1> *cur = &ra;
    while (cur != NULL) {
        out << cur->m_data << ' ';
        cur = cur->m_next;
    }
    return out;
}

int main() {
    Linklist<int> l(1);
    l.List_add(2);
    l.List_add(3);
    l.List_add(4);
    cout << l << endl; // 输出：1 2 3 4
    
    int val = 3;
    l.List_del(val);
    cout << l << endl; // 输出：1 2 4
    
    int target = 2;
    int *result = l.List_find(target);
    if (result != NULL) {
        cout << '找到了：' << *result << endl; // 输出：找到了：2
    } else {
        cout << '未找到' << endl;
    }
    
    int oldVal = 2;
    int newVal = 5;
    l.List_change(oldVal, newVal);
    cout << l << endl; // 输出：1 5 4
    
    return 0;
}

代码解析

类模板 Linklist
- template <class T>: 定义类模板，支持任意数据类型。
- T m_data: 存储节点数据。
- Linklist *m_next: 指向下一个节点的指针。
- 构造函数 Linklist(T data): 初始化节点数据和指向下一个节点的指针。
- 析构函数 ~Linklist(): 循环遍历链表并释放每个节点的内存。
- List_add(T const &ra): 尾插操作，将新节点插入链表尾部。
- List_del(T &ra): 删除操作，删除值为 ra 的节点。
- List_find(T &ra): 查找操作，返回值为 ra 的节点的指针，若未找到则返回 NULL。
- List_change(T &ra, T &rb): 修改操作，将值为 ra 的节点的数据修改为 rb。
- friend ostream &operator<<(ostream &out, Linklist<T1> &ra): 重载输出运算符，方便输出链表内容。
主函数 main(): 测试代码，演示链表的创建、添加、删除、查找和修改操作。

总结

本文介绍了使用 C++ 类模板实现任意类型数据域链表的基本步骤，并提供了清晰的代码示例。通过学习本文，读者能够掌握如何构建链表数据结构，并运用链表进行数据操作。链表是一种重要的数据结构，在许多算法和程序中都有着广泛的应用。