C++ 类模板实现链表类（实参为 类 类型）的插入、删除、查找、打印操作
由于在实际使用中，存在很多“相似”的类，如果逐个定义类的成员将会十分麻烦，于是就提出了类模板这个概念。意思就是提供一个模板，在实例化过程中才生成一个真正的类。
常见的实例化数据类型会有int, char, 等等，但是这里提供一个实参类型为类的链表类，也就是说使用一个类去实例化一个链表的模板类。
类模板的定义方式：
< T>
class 类模板名
成员变量；
成员函数；
};
其中， 也可以用 class 来代替，只是容易混淆它跟类的概念(但这里的class单纯就是一个代表未知变量的名称，与一般概念的类无关)，因此使用 会更容易理解；
T 是一个可以自己随意定义的形参名称，在类模板中会使用到这个还不知道是什么类型的变量，在实例化过程中才真正定义 T 到底是什么类型，可以是 int, char, , class 等等；
也可以定义两个或两个以上的未知变量 T1，T2等等，
比如：< T1, T2>
类模板的成员函数在类模板外定义
< T>
返回值类型 类模板名< T>::成员函数名(参数表)
…
本文章解决的是使用 类 类型来实例化一个链表类，意味着：链表类的数据域也为类；
每一个节点为一个作曲家的信息，包括姓名、死亡日期以及一些成员函数；
图例：
代码实例 1. 定义节点类型 Node.h
链表中的节点类型
#include2. 定义链表类 .h
这个链表两个指针成员，分别指向链表的头节点和尾结点。
template<typename T>
class LinkList
{
public:LinkList(); //构造函数~LinkList(); //析构函数void printList()const; //打印列表void append(const T data); //后插一个数据void prepend(const T data);//前插一个数据 void removeFront(); //删除第一个元素void insert(const T data); //按顺序插入bool remove(const T data); //删除特定数据bool find(const T data); //找到特定数据bool isEmpty()const; //判断是否为空T getFirst()const; //获取第一个数据T getLast()const; //获取最后一个数据Node<T>* head;Node<T>* tail;
};
下面就是对这个链表类各种操作：
1）构造函数和析构函数
构造函数：将head和tail指针置空；
析构函数：将节点内容从头节点开始逐个释放。
template<typename T> //构造函数
LinkList<T>::LinkList()
{head = tail = NULL;
}template<typename T> //析构函数
LinkList<T>::~LinkList()
{Node<T>* currentNode = head;while (currentNode != NULL){Node<T>* temp = currentNode->next;delete currentNode;currentNode = temp;}
}
2）打印链表
将链表的内容逐个打印出来;
这里还会涉及到NULL和的区别，NULL既可以代表0和空指针，但是容易出现问题；
而则是专门定义出来表示空指针，因此使用会更加保险
template<typename T> //打印列表
void LinkList<T>::printList()const
{Node<T>* temp = head; while(temp!=nullptr){cout << temp->data << endl;temp = temp->next;}
}
3）使用尾插法插入一个数据
考虑到原链表为空的情况，那插入的节点就作为头节点
template<typename T> //后插一个数据
void LinkList<T>::append(const T data)
{Node<T>* temp = new Node<T>;temp->data = data;temp->next = NULL;if (head == NULL){head = tail = temp; }else{this->tail->next = temp;this->tail = temp;}
}
4）使用头插法插入一个数据
template<typename T> ///前插一个数据
void LinkList<T>::prepend(const T data)
{ Node<T>* temp = new Node<T>;temp->data = data;if (head == NULL){temp->next = NULL;head = tail = temp;}else{temp->next = this->head; this->head = temp;}
}
5）删除链表第一个节点
考虑到原链表为空的情况，这种情况删除不了，则返回false;
template<typename T> //删除第一个元素
void LinkList<T>::removeFront()
{if (head == NULL){cout << "List is empty";return;}Node<T>* temp = this->head;this->head = temp->next;free(temp);
}
6）插入一个数据，并自动插在一个按照大小顺序排列的位置上
考虑到原链表为空的情况，则插入节点作为头节点；
若插入节点比头节点小，也将该插入节点作为头节点；
一般情况下，则使用辅助指针 p 来寻找合适的插入位置，直到找到下一个节点数据比插入节点大的位置（在这个位置上的节点，应该比前面所有的节点数据都要大，比下一个节点数据小），将其插入；
template<typename T> //按顺序插入
void LinkList<T>::insert(const T data)
{Node<T>* temp = new Node<T>;Node<T>* p = this->head;temp->data = data;if (head == NULL) //若链表为空，插入节点作为头结点{temp->next = NULL;head = tail = temp;return;}else if (data < p->data) //插入节点小于头结点，则该节点作为头结点{temp->next = head;head = temp;}else{while (p->next != NULL){if (data < p->next->data) //不断后移，直到下一个节点比插入节点大break;p = p->next; }temp->next = p->next;p->next = temp; //插入节点}
}
7）删除特定数据的节点
考虑原链表为空的情况下，删除不了任何数据，返回false;
使用辅助指针 p 去寻找该特定数据的节点，指针 front 一直指向指针p 所指向的前一个节点，用于删除节点后对链表进行重新连接；
template<typename T> //删除特定数据
bool LinkList<T>::remove(const T data)
{if (head == NULL){cout << "List is empty\n";return false;}Node<T>* p = head;Node<T>* front;while (p->next != nullptr)//下一个节点不为空，表示还可以删除{front = p;p = p->next;if (p->data == data){front->next = p->next;p->next = NULL;cout << data << " was successfully removed from the list\n";delete p;return true;}}cout << data << " was not found in the list when attempting to remove\n";return false;
}
8）查找特定数据的节点
考虑原链表为空的情况，此时查找不到任何节点，返回false;
template<typename T> //找到特定数据
bool LinkList<T>::find(const T data)
{Node<T>* p = head;if (head == NULL){cout << "List is empty\n";return false;}while (p->next != nullptr){if (p->data == data){cout << data << " was found in the list\n";return true;}p = p->next; //要先判断当前节点的数据是否为所需查找的节点，再将p往后移//不然容易发生头节点查找不到的情况}cout << data << " was not found in the list\n";return false;
}
9）判断链表是否为空
template<typename T> //判断是否为空
bool LinkList<T>::isEmpty()const
{if (head == NULL){return true;}else{return false;}
}
10）获取链表头节点数据
template<typename T> //获取第一个数据
T LinkList<T>::getFirst()const
{T first_data;first_data = head->data;return first_data;
}
11）获取链表尾节点数据
template<typename T> //获取最后一个数据
T LinkList<T>::getLast()const
{T last_data;last_data = tail->data;return last_data;
}
3. 定义类 .h
注意：每个是一个类，除了成员变量还有成员函数
类中包含每一个作曲家的姓名和死亡日期，以及一些重载函数；
由于在实例化过程中，类不能直接用一些运算符（普通的int、char、可以），因此需要对一些运算符进行重载，以便使用；
class Composer
{
public:string name;int death;Composer(string cname, int cdeath);friend ostream& operator<<(ostream& out,const Composer& com);bool operator==(const Composer& other);void getname();Composer(){}~Composer(){}
};
4.实现类的成员函数 .cpp
1)构造函数
Composer::Composer(string cname, int cdeath)
{name = cname;death = cdeath;
}
2） 重载输出> 输入作曲家姓名，但是通过观察发现，作曲家的名字（）之间存在空格符，通过 cin >> 输入作曲家姓名时，会自动忽略掉空格后的内容，这样子造成了很大的麻烦，在查找或者删除的过程中，由于姓名输入异常，根本实现不了这两个功能。
为此，我尝试了很多方法，比如 cin>>>>input，但发现还是不行。上网找了相关解释，得知类型的数据，使用 cin 方法是没有办法实现不忽略空格的，要使用 () 函数来获取整个字符串。于是放弃了重载输入
