C++ 类模板实现链表类（实参为 类 类型）的插入、删除、查找、打印操作

C++ 类模板实现链表类（实参为 类 类型）的插入、删除、查找、打印操作

由于在实际使用中，存在很多“相似”的类，如果逐个定义类的成员将会十分麻烦，于是就提出了类模板这个概念。意思就是提供一个模板，在实例化过程中才生成一个真正的类。
常见的实例化数据类型会有int, char, string等等，但是这里提供一个实参类型为类的链表类，也就是说使用一个类去实例化一个链表的模板类。

类模板的定义方式：
template < typename T>
class 类模板名
{
成员变量；
成员函数；
};

其中，typename 也可以用 class 来代替，只是容易混淆它跟类的概念(但这里的class单纯就是一个代表未知变量的名称，与一般概念的类无关)，因此使用 typename 会更容易理解；
T 是一个可以自己随意定义的形参名称，在类模板中会使用到这个还不知道是什么类型的变量，在实例化过程中才真正定义 T 到底是什么类型，可以是 int, char, string, class 等等；
也可以定义两个或两个以上的未知变量 T1，T2等等，
比如：template< typename T1, typename T2>

类模板的成员函数在类模板外定义
template < typeneme T>
返回值类型 类模板名< typeneme T>::成员函数名(参数表)
{
…
}

本文章解决的是使用 类 类型来实例化一个链表类，意味着：链表类的数据域也为类；
每一个节点为一个作曲家Composer的信息，包括姓名、死亡日期以及一些成员函数；
图例：

代码实例

1. 定义节点类型 Node.h

链表中的节点类型

#include<iostream>
#include<string>
using namespace std;template <typename T>
class Node
{
public:T data;Node<T>* next;Node(){}~Node(){}
};

2. 定义链表类 LinkedList.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和nullptr的区别，NULL既可以代表0和空指针，但是容易出现问题；
而nullptr则是专门定义出来表示空指针，因此使用nullptr会更加保险

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 emptyn";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 listn";delete p;return true;}}cout << data << " was not found in the list when attempting to removen";return false;
}

8）查找特定数据的节点
考虑原链表为空的情况，此时查找不到任何节点，返回false;

template<typename T>  //找到特定数据
bool LinkList<T>::find(const T data)  
{Node<T>* p = head;if (head == NULL){cout << "List is emptyn";return false;}while (p->next != nullptr){if (p->data == data){cout << data << " was found in the listn";return true;}p = p->next;  //要先判断当前节点的数据是否为所需查找的节点，再将p往后移//不然容易发生头节点查找不到的情况}cout << data << " was not found in the listn";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. 定义Composer类 Composer.h

注意：每个Composer是一个类，除了成员变量还有成员函数

Composer类中包含每一个作曲家的姓名和死亡日期，以及一些重载函数；
由于在实例化过程中，Composer类不能直接用一些运算符（普通的int、char、string可以），因此需要对一些运算符进行重载，以便使用；

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.实现Composer类的成员函数 Composer.cpp

1)构造函数

Composer::Composer(string cname, int cdeath)
{name = cname;death = cdeath;
}

2） 重载输出<<运算符
在输出Composer类时（<<Composer），因为在有的时候（比如打印整个链表)，需要将姓名和死亡日期一起输出；而在查找和删除过程中提示是否查找或删除成功时，则只需要输出姓名，因此这里加了一个判断，它会根据这个节点中是否有死亡日期这个信息，来决定一起输出姓名和死亡日期 还是 只输出姓名；
这里有一个小问题就是，一开始想通过 com.death 是否为NULL或者nullptr来直接判断死亡日期是否为空，但是，发现这两种方法都没有用，debug发现无论 com.death 是否为空，程序还是会觉得第一个 if 中的判断依据不成立。于是，在监视窗口中查看，当 com.death 为空时，它的内存究竟是什么，发现是一个默认生成的地址-858993460，就试着将这个信息作为判断依据，发现这样就可以正常判断了。

ostream& operator<<(ostream& out,const Composer& com)
{if (com.death != -858993460){out << "" << com.name << " - " << com.death;}else if (com.death == -858993460){out << com.name << " ";}return out;
}

3）重载==关系运算符
在判断节点是否等于该Composer类时，只需要判断这两个节点中数据域的作曲家姓名是否一样；

bool Composer::operator==(const Composer& other)
{if (this->name == other.name)return true;else{return false;}
}

tips:在写重载函数的过程中，由于在使用中，composer类的对象类型是const，因此在重载过程中，也得使用const类型

4）输入作曲家的姓名
一般输入的方法应该是重载 >> 输入运算符，直接 cin>> 输入作曲家姓名，但是通过观察发现，作曲家的名字（string）之间存在空格符，通过 cin >> 输入作曲家姓名时，会自动忽略掉空格后的内容，这样子造成了很大的麻烦，在查找或者删除的过程中，由于姓名输入异常，根本实现不了这两个功能。
为此，我尝试了很多方法，比如 cin>>noskpiws>>input，但发现还是不行。上网找了相关解释，得知string类型的数据，使用 cin 方法是没有办法实现不忽略空格的，要使用 getline() 函数来获取整个字符串。于是放弃了重载输入<<运算符的方法，选择定义一个成员函数来进行姓名的获取。

void Composer::getname()
{string st;getline(cin, st);this->name = st;
}

5.Main函数实例化 main.cpp

最终实例化的效果：

使用append函数将所有作曲家的信息存到链表类中

int main()
{LinkList<Composer> composer;  //使用Composer类来实例化一个类模板composer.append(Composer("Claudio Monteverdi", 1643));composer.append(Composer("Henry Purcell", 1695));composer.append(Composer("Antonio Vivaldi", 1741));composer.append(Composer("Johann Sebastian Bach", 1750));composer.append(Composer("George Frideric Handel", 1759));composer.append(Composer("Wolfgang Amadeus Mozart", 1791));composer.append(Composer("Joseph Haydn", 1809));composer.append(Composer("Ludwig van Beethoven", 1827));composer.append(Composer("Franz Schubert", 1828));composer.append(Composer("Felix Mendelssohn", 1847));composer.append(Composer("Frederic Chopin", 1849));composer.append(Composer("Robert Schumann", 1856));composer.append(Composer("Hector Berlioz", 1869));composer.append(Composer("Richard Wagner", 1883));composer.append(Composer("Franz Liszt", 1886));composer.append(Composer("Pyotr Ilyich Tchaikovsky", 1893));composer.append(Composer("Johannes Brahms", 1897));composer.append(Composer("Giuseppe Verdi", 1901));composer.append(Composer("Antonin Dvorak", 1904));composer.append(Composer("Edvard Grieg", 1907));composer.append(Composer("Gustav Mahler", 1911));composer.append(Composer("Claude Debussy", 1918));composer.append(Composer("Camille Saint-Saens", 1921));composer.append(Composer("Giacomo Puccini", 1924));composer.append(Composer("George Gershwin", 1937));composer.append(Composer("Maurice Ravel", 1937));composer.append(Composer("Sergei Rachmaninoff", 1943));composer.append(Composer("Bela Bartok", 1945));composer.append(Composer("Arnold Schoenberg", 1951));composer.append(Composer("Sergei Prokofiev", 1953));composer.append(Composer("Igor Stravinsky", 1971));composer.append(Composer("Dmitri Shostakovich", 1975));composer.append(Composer("Leonard Bernstein", 1990));composer.append(Composer("Aaron Copland", 1990));

生成链表类之后，进行对其一些操作

	char judge;int out=1;Composer temp_composer;while (out==1){cout << "Enter 's' to search, 'r' to remove, 'd' to display, or 'e' to exit:";cin >> judge;switch (judge){case's':{cout << "Enter a composer's name to search for:";cin.ignore(INT_MAX, 'n');ame();composer.find(temp_composer);break;}case'r':cout << "Enter a composer's name to remove:";cin.ignore(INT_MAX, 'n');ame();ve(temp_composer);break;case'd':composer.printList();break;case'e':out = 0;default:break;}}return 0;
}

值得注意的是：上面提到，对于作曲家姓名的输入，不使用 cin 方法，选择使用 getline() 函数来获取，但是在一开始，getline() 一直没有办法正常调用，debug过程中，没有办法输入信息。
于是上网找了很多解释，比如在 getline() 前面添加缓冲区 fflush(stdin) ，发现不行；接着将 getline() 函数调到switch 语句外面进行简单的测试，发现可以正常使用，就想着是不是switch语句出了问题，但查了好多文章都没发现有什么突破口；然后尝试将 case’s’: 里面的内容全注释掉，只留下 geiline() 函数进行测试，发现可以正常使用，于是猜想是不是前面那句 cout 语句有什么问题，最终找到一些帖子的解释。原来，如果在 getline() 函数前面有输出的语句时，这个输出的语句最后的换行符’n’，仍然会停留在缓冲区中，直接调用 getline() 函数时，getline() 会读取这个换行符’n’，这样会导致后面的输入无效，所以才会出现输入不了的情况。
解决方法：在 getline() 函数前加一个 cin.ignore(INT_MAX, ‘n’) ，这样就会先忽略掉那个换行符’n’，再进行正常输入。

6.运行效果