单向链表 ---- C++使用类模板实现

单向链表 —- C++使用类模板实现

关于类模板的一些知识

与函数模板不同之处是，编译器不能为类模板推断模板参数类型。
当编译器从我们的 Demo 模板实例化出一个类时，它会重写 Demo 模板，将模板参数T的每个实例替换为给定的模板参数。
一个类模板的每个实例化都形成一个独立的类

类模板的成员函数
- 我们既可以在类模板内部，也可以在类模板外部为其定义成员函数，且定义在类模板内的成员隐式为内联函数。
- 定义在类模板之外的成员函数就必须以关键字 template 开始，后接类模板参数列表。
当我们在类外定义一个成员时，必须说明成员属于哪个类。而且从一个模板生成的类的名字中必须包含其模板实参。

template <typename T>
    ret-type Demo<T>:: member-name(...)

当我们使用一个类模板类型时必须提供模板实参，但这一规则有一个例外。在类模板自己的作用域中，我们可以直接使用模板名而不提供实参。

示例代码：

template<tyname T>
class Demo
{
public:
    Demo(T data);
private:
   T m_data;
};

template <typename T>
Demo<T>::Demo(T data):m_data(data){ }

为何使用类模板实现

使用类模板写单向链表可以实现在一个链表中存储一种任何类型的数据，包括自定义数据。使得代码的复用性很高。

对于存储自定义类型的数据时，对于相应的操作符要进行重载

单向链表类模板实现代码

#include <iostream>
#include <string>

using namespace std;

//链表节点
template<typename T>
struct ListNode
{
    T data;
    ListNode<T> *next;
};

//单向链表 -- 采用类模板
//单链表操作类模板
template <typename T>
class LinkList
{
public:
    LinkList();
    LinkList(T elem);
    LinkList(int n, T elem);
    ~LinkList();
    void ClearList() const;
    bool Empty() const;
    int Length() const;
    T GetElem(int n) const;
    int LocateElem(T elem) const;
    bool Insert(int n, T elem);
    bool Delete(int n);
    void Displasy();
    void Remove(T elem);
private:
    ListNode<T> *m_head;
};

template <typename T>
LinkList<T>::LinkList() 
{
    //创建头节点
    m_head = new ListNode<T>;
    if (nullptr == m_head)
    {
        cout << "动态申请头节点内存失败" << endl;
        return;
    }

    m_head->next = nullptr;
}

template <typename T>
LinkList<T>::LinkList(T elem) :LinkList()
{
    Insert(1, elem);
}

template <typename T>
LinkList<T>::LinkList(int n, T elem) :LinkList()
{
    for (int i = 0; i < n; ++i)
    {
        Insert(i, elem);
    }
}

template <typename T>
LinkList<T>::~LinkList()
{
    ClearList();    //置为空白
    delete m_head;  //释放头节点
}

template <typename T>
void LinkList<T>::ClearList() const     //常成员函数 不改变对象的值
{
    ListNode<T> *temp, *p = m_head->next;

    while (p != nullptr)        //删除头节点以后的所有节点
    {
        temp = p->next;
        delete p;           //要释放动态内存
        p = temp;
    }

    m_head->next = nullptr;
}

template <typename T>
bool LinkList<T>::Empty() const
{
    //如果头节点的下一个节点为空，则该链表为空
    return nullptr == m_head->next;
}

template <typename T>
int LinkList<T>::Length() const
{
    int count = 0;
    ListNode<T> *ptemp = m_head->next;

    while (ptemp != nullptr)
    {
        count++;
        ptemp = ptemp->next;
    }

    return count;
}

template <typename T>
T LinkList<T>::GetElem(int n) const
{
    ListNode<T> *ptemp = m_head->next;

    if (n <= Length())
    {
        for (int i = 1; i < n; ++i)
        {
            ptemp = ptemp->next;
        }
    }
    else
    {
        cout << "out of ranger" << endl;
        return false;
    }

    return ptemp->data;
}

template <typename T>
int LinkList<T>::LocateElem(T data) const
{
    size_t location = 0;
    ListNode<T> *ptemp = m_head->next;

    while (ptemp != nullptr)
    {
        ++location;
        if (ptemp->data == data)            //注意 该类型必须支持 == 操作符，如果不支持需要进行运算符重载
        {
            return location;
        }

        ptemp = ptemp->next;
    }

    return 0;       //返回0表示未找到
}

template <typename T>
bool LinkList<T>::Insert(int n, T elem)
{
    ListNode<T> *ptemp = m_head;

    if (n-1 <= Length())
    {
        for (int i = 0; i < n - 1; ++i)
        {
            ptemp = ptemp->next;
        }

        //先生成一个新的节点
        ListNode<T> *newnode = new ListNode < T >;
        if (nullptr == newnode)
        {
            cout << "申请空间失败" << endl;
            return false;
        }

        newnode->data = elem;       //如果数据类型不是基本数据类型，即不支持 = 操作符，需要重载 = 操作符
        newnode->next = ptemp->next;
        ptemp->next = newnode;

        return true;
    }
    else
    {
        cout << "out of range" << endl;
        return false;
    }
}

template <typename T>
bool LinkList<T>::Delete(int n)
{
    ListNode<T> *ptemp = m_head;

    if (n <= Length())
    {
        for (int i = 0; i < n - 1; ++i)
        {
            ptemp = ptemp->next;
        }

        ListNode<T> *t = ptemp->next;       //指向待删除的节点

        ptemp->next = ptemp->next->next;        //将待删除节点的上一节点指向待删除节点的下一节点
        delete t;       //释放删除节点的内存

        return true;
    }
    else
    {
        cout << "out of range" << endl;
        return false;
    }
}

template <typename T>
void LinkList<T>::Displasy()
{
    ListNode<T> *ptemp = m_head->next;

    while (ptemp != nullptr)
    {
        cout << ptemp->data << endl;
        ptemp = ptemp->next;
    }
}

template <typename T>
void LinkList<T>::Remove(T elem)
{
    ListNode<T> *ptemp = m_head;

    while (ptemp->next != nullptr)
    {
        if (ptemp->next->data == elem)          //找到与要删除的节点相同
        {
            ListNode<T> *t = ptemp->next;       //指向待删除的节点
            ptemp->next = ptemp->next->next;        //将待删除节点的上一节点指向待删除节点的下一节点
            delete t;       //释放删除节点的内存
        }
        else        //这里需要注意一下：如果删除了那么它的下一节点是新的节点需要重现判断，所以不需要移动
        {
            ptemp = ptemp->next;
        }

    }
}

struct Data
{
    int id;
    string name;
};
//由于使用的是结构体，所以对于一些运算符需要进行重载
ostream &operator << (ostream &os, const Data &data)
{
    os << data.id << "  " << data.name;
    return os;
}

bool operator==(const Data &data1, const Data &data2)
{
    //按照ID进行比较
    return data1.id == data2.id;
}

测试程序：(对于基本的一些数据类型)

int main()
{
    LinkList<int> List1(10, 1);
    List1.Displasy();

    LinkList<string> List2;
    List2.Insert(0, "aaa");
    List2.Insert(1, "bbb");
    List2.Insert(2, "ccc");
    List2.Insert(2, "ccc");
    List2.Insert(5, "eee"); //超出范围的插入
    List2.Displasy();
    List2.Delete(1);        //删除指定位置的节点
    List2.Displasy();
    List2.Remove("ccc");    //删除所有拥有该数据的节点
    List2.Displasy();

    system("pause");
    return 0;
}

运行结果：

当存入的链表的数据为自定义时

//自定义数据
struct Data
{
    int id;
    string name;
};

//由于使用的是自定义数据，所以对于一些运算符需要进行重载
ostream &operator << (ostream &os, const Data &data)
{
    os << data.id << "  " << data.name;
    return os;
}

bool operator==(const Data &data1, const Data &data2)
{
    //按照ID进行比较
    return data1.id == data2.id;
}

测试程序：

int main()
{
    LinkList<Data> List1(10, {1, "zjy"});
    List1.Insert(1, { 2, "yyy" });
    List1.Displasy();

    List1.Remove({ 1, "hhh" });
    List1.Displasy();

    system("pause");
    return 0;
}

运行结果：