C++类模板与线性表
<上一节
下一节>
参数化程序设计——通用的代码就必须不受数据类型的限制，可以把数据类型改为一个设计参数。这种类型的程序设计称为参数化(parameterize) 程序设计。
这种设计由模板(template)完成。包括函数模板(function template)和类模板(class template)。本节主要讲解类模板及线性表，函数模板请点击这里：C++函数模板及应用
template<模板参数表> class 类名{
……//类声明体，成员数据和成员函数的声明或定义，语法同普通类。
};//再次指出分号不可少
例如：
template< typename T,int i>class array
{
T vector[i];
int size;
public: array()； ~array(){ };
... ...
};
尖括号中的模板参数有两种：
在类内定义成员函数的语法和普通类一致。在类模板外定义类的成员函数，语法如下：
template<模板参数表> 返回类型 类名<模板参数表>::成员函数名1(形参表)
{ ……; /*成员函数1定义体*/ }
例如：
template<typename T,int i>array<T,i>::array( ) {size=i;}
//构造函数无返回类型
注意：在类模板外定义成员函数必须是函数模板。标准C++要求这样的成员函数只有在被调用（或取地址）时才被实例化。成员函数模板定义中，指定成员函数所在类域的类型名后跟的<模板参数名表>中成员，与类模板的<模板参数表>中的类型参数名相同，但不加 typename 或class。
类名<类模板实在参数表> 对象名;
例如：
template< typename T,int i>class array{……}；
array < float, 6 > test1; // OK
array <char,items++> test2; //Error,second parameter must be constant.
◆ 2、A class template is first specialized and then instantiated by the compiler. The compiler does not instantiate the class template until a reference to a member of this template class is made.
The syntax for explicit specialization of class templates is：（For example）
template<class T> class X {...};
//Explicit specialization of X with 'int'
template< > class X<int> { };
The following form of old syntax is also supported:
//Explicit specialization of X with 'char'
class X< char> { }
对顺序表的典型操作包括：计算表长度，寻找变量或对象x（其类型与表元素相同）在表中的位置（下标值），判断x是否在表中，删除x，将x插入列表中第i个位置，寻找x的后继，寻找x的前驱，判断表是否空，判断表是否满（表满不能再插入数据，否则会溢出，产生不可预知的错误），取第i个元素的值。
上述操作与数组封装起来可以定义一个类，考虑到数组元素的类型可以各不相同，所以定义为类模板。
静态数组：由编译器编译时分配内存的数组称为静态数组，数组的长度是不可改变的。
如果定义了30个元素的数组，后来需要40个元素，是不可能续上10个的，必然产生溢出。因系统不检查数组边界，进而产生不可预知的运行时错误，所以一般采用“大开小用”的方法，即数组定义的较大，而实用较小。为防止不可避免的溢出，应在添加新数据时判断表是否满。
当需要在顺序表中删除一个元素时，必须把它后面的元素的数据全部顺序前移一个位置，否则表中前驱后继关系被破坏。图6.1表中有11个数据。删去第i个元素的数据，就是把第i+1个元素拷入第i个元素，把第i+2个元素拷入第i+1个元素,依此类推，直到最后一个元素（下标为10），现在表长度为10。
（演示删除过程）
当需要在顺序表的指定位置i 插入一个数据x时，必须为它腾出这个位置，把从该位置开始向后的所有元素数据，后移一个位置，最后才插入。后移时从最后一个元素开始，参见图6.2。现在长度为12，这样的移动也是不可少的，否则新插入的数据x会冲掉原来的数据，或先移的数据冲掉未移的数据。
（演示插入过程）
【例6.3】顺序表类模板。（查看源码）
函数模板请点击这里：C++函数模板及应用
这种设计由模板(template)完成。包括函数模板(function template)和类模板(class template)。本节主要讲解类模板及线性表，函数模板请点击这里：C++函数模板及应用
类模板定义
类模板定义的定义如下：template<模板参数表> class 类名{
……//类声明体，成员数据和成员函数的声明或定义，语法同普通类。
};//再次指出分号不可少
例如：
template< typename T,int i>class array
{
T vector[i];
int size;
public: array()； ~array(){ };
... ...
};
尖括号中的模板参数有两种：
- 模板类型参数：与函数模板相同。
- 模板非类型参数：由普通的参数声明构成，表示一些潜在的常量，使用模板时企图修改这种参数的值，是不行的！例如数组类模板，可以有一个表示数组长度的非类型参数。
在类内定义成员函数的语法和普通类一致。在类模板外定义类的成员函数，语法如下：
template<模板参数表> 返回类型 类名<模板参数表>::成员函数名1(形参表)
{ ……; /*成员函数1定义体*/ }
例如：
template<typename T,int i>array<T,i>::array( ) {size=i;}
//构造函数无返回类型
注意：在类模板外定义成员函数必须是函数模板。标准C++要求这样的成员函数只有在被调用（或取地址）时才被实例化。成员函数模板定义中，指定成员函数所在类域的类型名后跟的<模板参数名表>中成员，与类模板的<模板参数表>中的类型参数名相同，但不加 typename 或class。
类模板注意事项
◆ 1、从通用类模板定义中生成类的过程称为模板实例化（template instantiation），格式为：类名<类模板实在参数表> 对象名;
例如：
template< typename T,int i>class array{……}；
array < float, 6 > test1; // OK
array <char,items++> test2; //Error,second parameter must be constant.
◆ 2、A class template is first specialized and then instantiated by the compiler. The compiler does not instantiate the class template until a reference to a member of this template class is made.
The syntax for explicit specialization of class templates is：（For example）
template<class T> class X {...};
//Explicit specialization of X with 'int'
template< > class X<int> { };
The following form of old syntax is also supported:
//Explicit specialization of X with 'char'
class X< char> { }
线性表
线性表是数据结构中的概念。数组中除第一个元素外，其他元素有且仅有一个直接前驱，第一个元素没有前驱；除最后一个元素外，其他元素有且仅有一个直接后继，最后一个元素无后继。这样的特性称为线性关系。所议称数组元素在一个线性表中。线性表实际包括顺序表（数组）和链表。对顺序表的典型操作包括：计算表长度，寻找变量或对象x（其类型与表元素相同）在表中的位置（下标值），判断x是否在表中，删除x，将x插入列表中第i个位置，寻找x的后继，寻找x的前驱，判断表是否空，判断表是否满（表满不能再插入数据，否则会溢出，产生不可预知的错误），取第i个元素的值。
上述操作与数组封装起来可以定义一个类，考虑到数组元素的类型可以各不相同，所以定义为类模板。
静态数组：由编译器编译时分配内存的数组称为静态数组，数组的长度是不可改变的。
如果定义了30个元素的数组，后来需要40个元素，是不可能续上10个的，必然产生溢出。因系统不检查数组边界，进而产生不可预知的运行时错误，所以一般采用“大开小用”的方法，即数组定义的较大，而实用较小。为防止不可避免的溢出，应在添加新数据时判断表是否满。
当需要在顺序表中删除一个元素时，必须把它后面的元素的数据全部顺序前移一个位置，否则表中前驱后继关系被破坏。图6.1表中有11个数据。删去第i个元素的数据，就是把第i+1个元素拷入第i个元素，把第i+2个元素拷入第i+1个元素,依此类推，直到最后一个元素（下标为10），现在表长度为10。
（演示删除过程）
当需要在顺序表的指定位置i 插入一个数据x时，必须为它腾出这个位置，把从该位置开始向后的所有元素数据，后移一个位置，最后才插入。后移时从最后一个元素开始，参见图6.2。现在长度为12，这样的移动也是不可少的，否则新插入的数据x会冲掉原来的数据，或先移的数据冲掉未移的数据。
（演示插入过程）
【例6.3】顺序表类模板。（查看源码）
函数模板请点击这里：C++函数模板及应用
<上一节
下一节>
