如同函数模板一样，使用类模板可以为类定义一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值能取任意类型。类模板是对一批仅仅成员数据类型不同的类的抽象，编程人员只要为这一批类所组成的整个类家族创建一个类模板，给出一套程序代码，就可以用来生成多种具体的类，这类被称为是类模板的实例，从而提高编程的效率。

定义类模板的一般形式是：

与函数模板类似，template为声明类模板所用的关键字，class或typename为声明类型的关键字。T1，T2是函数模板的类型参数，实际上是一个虚拟的类型名。这些类型名在使用类创建对象前并未指定为具体的类型。

定义如下一个单链表的类模板：

template< class T>

class Link List

{

//类声明体

};

链表是线性表的链式存储结构，是用一组任意的存储单元来存放线性表中的数据元素。在链式存储中，每个存储结点不仅存储有数据元素本身的信息，而且还存储有元素之间逻辑关系的信息，即前驱结点包含有后继结点的地址信息，这称为指针域，这样可以通过前驱结点的指针域方便地找到后继结点的位置，提高数据查找速度。一般地，每个结点有一个或多个这样的指针域。若一个结点中的某个指针域不需要任何结点，则仅将它的值设置为空，用常量NULL表示。由于后继结点的地址信息存储在其前驱结点中，因此在线性表的链式存储结构中，逻辑上相邻的数据元素其物理存储地址则不必相邻。

图8-1　单链表的结点结构

1.单链表的概念

在单链表中，每个结点包含两个域：数据域和指针域。数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址，如图8-1所示。

由于线性表中第一个结点没有前驱，所以应设一个头指针L 指向第一个结点。由于线性表中的最后一个结点没有直接后继，因此，单链表最后一个结点的指针域应设置为“空”（NULL），如图8-2所示。一个单链表由头指针唯一确定。

图8-2　单链表的结点结构

单链表存储结构如下：

2.单链表的基本操作

与线性表的顺序存储结构不同的是，在线性表的单链表存储结构中，数据元素之间的存储位置关系都是不固定的。然而，每个元素的存储位置信息都包含在其直接前驱结点中。例如，如果指针p存储的是第i个结点的地址，则p－ >next存储的就是第i＋1个结点的地址信息。由此，在单链表中，很多操作都是借助于指针的移动实现的。(www.daowen.com)

（1）取元素操作。单链表的取第i个结点算法思想：让指针p从单链表的第一个结点开始，沿着链表移动，直到表尾或到达第i个结点。

（2）插入元素操作。插入元素操作是将数据域为e的结点插入到单链表L的第i个结点之前的位置上，即插入到ai-1和ai 之间。由于单链表中相邻的数据元素之间其存储位置并不要求相邻，因此，单链表的插入元素操作不需要移动数据元素，只需要修改相邻元素的指针连接即可。

插入操作的思想：设指针s指向新生成数据域为e的结点，在插入新数据元素前，首先要找到待插入位置的前驱结点ai-1，并用指针p指向该结点；然后把新结点的指针域next指向结点ai；最后设置新结点为结点ai-1的后继结点，如图8-3所示。则上述单链表插入元素操作中指针修改用语句描述为：

s－ >next＝p－ >next;

p－ >next＝s;

图8-3　单链表中在第i个结点前插入数据域为e的新结点

（3）删除元素操作。单链表删除元素的操作与插入元素操作类似，仅仅调整指针的指向关系就能把待删除的结点从单链表中移除。首先查找待删除结点的前驱结点ai-1，并用p指向该结点；然后把前驱结点的next指针域指向待删除结点的直接后继；最后，由于结点的存储空间都是用动态内存分配得到，因此，把一个结点从单链表中移除后还要回收待删除结点的存储空间，如图8-4所示。

图8-4　从单链表中删除第i个数据元素

（4）计算单链表长度操作。单链表中没有单独记录线性表长度的数据量，因此需要通过计算来获得单链表的长度。计算单链表的长度只需从头到尾扫描单链表。设变量n用来记录单链表的长度，每扫描过一个结点，n的值累加1，直至到达单链表的尾。

用类模板定义单链表Link List的代码如下：

单链表Link List节点的数据元素类型在Link List类首部和成员函数定义中统一表示为T。在类模板内部以外的成员函数定义均以下列代码开头：

template<class T>

因此，成员函数的定义与普通成员函数的定义类似，只是Link List节点数据元素的类型总是用类型参数T 表示。在类的外部，Link List类名就变为Link List< T> 。

需要说明的是Link List类模板及其成员函数的定义都放在同一个文件Link List.h中，这与一般类定义时把类声明放在头文件中，成员函数定义部分作为实现放在cpp文件中是不同的。