6_模板与数据结构

第六章 模板与数据结构

模板是建立通用的与数据类型无关的算法 模板是建立通用的与数据类型无关的算法 的重要手段，在学习与数据结构相关的表 的重要手段，在学习与数据结构相关的表、 排序与查找的知识和算法时 的知识和算法 排序与查找的知识和算法时，要逐步熟悉 函数模板和类模板的编程方法。 函数模板和类模板的编程方法。

第六章模板与数据结构

6.1

模板

6.4 模板与类参数

6.2 排序与查找

6.5 函数指针与指针识别(选读) 函数指针与指针识别(选读)

6.3 索引查找与指针数组

6.1 模板参数化程序设计： 参数化程序设计：通用的代码就必须不受数据类型的限制，可以把数据 通用的代码就必须不受数据类型的限制 ， 可以 把数据 类型改为一个设计参数。 类型改为一个设计参数 。 这种类型的程序设计称为参数 程序设计。 化(parameterize) 程序设计。 这 种 设 计 由 模 板 (template) 完 成 。 包 括 函 数 模 板 (function template)和类模板 和类模板(class template)。 。

6.1.1 6.1.2

函数模板及应用

类模板与线性表

6.1.1 函数模板及应用函数模板用来创建一个通用函数，支持多种不同类型形参。 函数模板用来创建一个通用函数，支持多种不同类型形参。 函数模板定义： 函数模板定义： template<模板参数表 返回类型 函数名 形式参数表 模板参数表>返回类型 函数名(形式参数表 形式参数表) 模板参数表 {……;}//函数体 ； 函数体

<模板参数表 (template parameter list)尖括号中不能 模板参数表>( 模板参数表 ) 为空，参数可以有多个，用逗号分开。 为空，参数可以有多个，用逗号分开。模板参数主要是模板 类型参数。 类型参数模板类型参数(template type parameter)代表一种类型，由关键 代表一种类型， 模板类型参数 代表一种类型 字 class 或 typename(建议用 (建议用typename ) 后加一个标识符构 在这里两个关键字的意义相同， 成，在这里两个关键字的意义相同，它们表示后面的参数名代表 一个潜在的内置或用户定义的类型。 一个潜在的内置或用户定义的类型。

6.1.1 函数模板及应用【例6.1】用函数模板求数组元素中最大值 】 template <typename Groap> Groap max(const Groap *r_array,int size){ int i; Groap max_val=r_array[0]; for (i=1;i<size; ++i) if(r_array[i]>max_val) max_val=r_array[i]; return max_val; } 类型参数Groap在程序运行中会被各种内置(基本)类型 在程序运行中会被各种内置(基本) 类型参数 在程序运行中会被各种内置 或用户定义类型所置换。 或用户定义类型所置换。 模板参数表的使用与函数形式参数表的使用相同，都是位 模板参数表的使用与函数形式参数表的

使用相同，都是位 置对应。 置对应。类型和值的置换过程称为模板实例化 (template instantiation)。 形参 数组的长度。 。 形参size 表示 r_array 数组的长度。

6.1.1 函数模板及应用模板实参推演： 模板实参推演：函数模板根据一组实际类型或( 函数模板根据一组实际类型或(和)值构造出独立的函数的 过程通常是隐式发生的，称为模板实参推演 模板实参推演(template 过程通常是隐式发生的，称为模板实参推演 argument deduction)。 。 下面完成【 下面完成【例6.1】 】int ia[5]={10,7,14,3,25}; double da[6]={10.2,7.1,14.5,3.2,25.6,16.8}; string sa[5]={"上海 北京 沈阳 广州 武汉 上海","北京 沈阳","广州 武汉"}; 上海 北京","沈阳 广州","武汉 int main() { int i=max(ia,5);cout <<"整数最大值为："<<i<<endl; 整数最大值为： 整数最大值为 double d=max(da,6);cout <<"实数最大值为："<<d<<endl; 实数最大值为： 实数最大值为 string s=max(sa,5);cout <<"字典排序最大为："<<s<<endl; 字典排序最大为： 字典排序最大为 return 0; }

6.1.1 函数模板及应用模板实参推演过程： 模板实参推演过程：第一次调用时，Groap被int取代。第二次调用， 第一次调用时，Groap被int取代。第二次调用，Groap 取代 double取代 第三次Groap 被string取代。为了判断用作 取代。 取代。 被double取代。第三次 取代 模板实参的实际类型， 模板实参的实际类型，编译器需检查函数调用中提供的函 数实参的类型。 的类型为int 数组，id的类型为 的类型为double 数实参的类型。ia 的类型为int 数组，id的类型为double 数组。都被用来决定每个实例的模板参数。 数组。都被用来决定每个实例的模板参数。该过程称为模 板实参推演。 板实参推演。 当然也可以显式指定( ),如 当然也可以显式指定(explicitly specify),如： ), i=max<int>(ia,5); d=max<double>(da,6); 这样可读性更好。 这样可读性更好。这里数组名是作为指向数组首元素的指 针进行传递，数组长度是由size参数进行传递的。 参数进行传递的。 针进行传递，数组长度是由 参数进行传递的

6.1.1 函数模板及应用函数模板与模板函数： 函数模板与模板函数：函数中， 函数模板(functron 在main()函数中，由调用函数模板 函数中 由调用函数模板 template) 而生成的函数，称为模板函数 而生成的函数，称为模板函数 (template function)。这两个概念须分清楚。 。这两个概念须分清楚。

【例6.2】矩阵运算：矩阵转置与矩阵相乘函 】矩阵运算： 数模板。下标作为参数传递。解决例5.5程序 数模板。下标作为参数传递。解决例 程序 的通用性问题。 的通用性问题。

6.1.1 函数模板及应用函数模板的声明： 函数模板的

声明：请注意：与函数声明不同，函数模板的声明必须含变量名。 请注意：与函数声明不同，函数模板的声明必须含变量名。因 为两者编译过程不一样，函数模板必须先转换为模板函数。 为两者编译过程不一样，函数模板必须先转换为模板函数。 template <typename T1,typename T2> void inverse(T1 *mat1, T2 *mat2,int a,int b); template <typename T1,typename T2> void multi(T1 *mat1,T2 *mat2,T2 *result,int a, int b,int c); template <typename T> void output(T *mat,char*s,int a,int b); 注意： 属同一类型， 注意：mat2和result属同一类型，均为由具有相同元素数量 和 属同一类型 的一维数组所组成的二维数组。本例为mat[3][4]和 的一维数组所组成的二维数组。本例为 和 result[6][4]。记住数组最高维是不检查边界的。 。记住数组最高维是不检查边界的。

6.1.2 类模板与线性表类模板定义： 类模板定义：template<模板参数表 class 类名 模板参数表> 类名{ 模板参数表 …… //类定义体 类定义体 }; //再次指出分号不可少 再次指出分号不可少 template<模板参数表 返回类型 类名 模板参数名表>:: 模板参数表> 类名< 模板参数表 成员函数名1(形参表 形参表) 成员函数名 形参表 { ……;//成员函数定义体 ； 成员函数定义体 } …… template<模板参数表 返回类型 类名 模板参数名表>:: 模板参数表> 类名< 模板参数表 成员函数名n(形参表 形参表) 成员函数名 形参表 { ……;//成员函数 定义体 成员函数n定义体 ； 成员函数 } 模板参数有两种：模板类型参数和模板非类型参数。 模板参数有两种：模板类型参数和模板非类型参数。

6.1.2 类模板与线性表模板非类型参数： 模板非类型参数：模板非类型参数由一个普通的参数声明构成。 模板非类型参数由一个普通的参数声明构成。表示该参数 名代表了一个潜在的常量 潜在的常量， 名代表了一个潜在的常量，企图修改这种参数的值是一个错 如数组类模板，可以有一个数组长度的非类型参数： 误。如数组类模板，可以有一个数组长度的非类型参数： template< typename T,int i>class array{ T vector[i]; int size; public: array():size(i){} //等效 等效array(){size=i;}参见 参见4.4.3节 等效 参见 节 ... ... };

6.1.2 类模板与线性表注意： 注意：在类外定义的类模板中的成员函数必须是函数模板。 在类外定义的类模板中的成员函数必须是函数模板。 这样的成员函数只有在被调用(或取地址) 这样的成员函数只有在被调用(或取地址)时才被 实例化。成员函数模板定义中， 实例化。成员函数模板定义中，指定成员函数所在 类域的类型名后跟的<模板参数名表 中成员， 模板参数名表>中成员 类域的类型名后跟

的 模板参数名表 中成员，与 类模板的<模板参数表 中的类型参数名相同， 模板参数表>中的类型参数名相同 类模板的 模板参数表 中的类型参数名相同，但 不加 typename 或class。 。 与包含对象成员的构造函数类似， 模板参数名表 与包含对象成员的构造函数类似，<模板参数名表 >实际是一个模板实例化的类型实参表，所以不加 实际是一个模板实例化的类型实参表， 实际是一个模板实例化的类型实参表 typename 或class。 。

6.1.2 类模板与线性表模板实例化： 模板实例化：从通用的类模板定义中生成类的过程称为模板实例化 (template instantiation),其格式为： ) 其格式为： 类名<类模板实在参数表 类模板实在参数表> 类名 类模板实在参数表通常与定义对象同时完成： 通常与定义对象同时完成：

类名<类模板实在参数表 对象名； 类名 类模板实在参数表> 对象名； 类模板实在参数表 例如：标准串类模板basic_string,它提供了复制、查找等典 例如：标准串类模板 ，它提供了复制、 型串操作。它包含在头文件<string>中。文件中包括有： 型串操作。它包含在头文件 中 文件中包括有： typedef basic_string<char> string; //typedef是类型定义关键字，见5.6.1节 是类型定义关键字， 是类型定义关键字 节 标准串类模板basic_string实例化为上一章讨论的字符串类 标准串类模板 实例化为上一章讨论的字符串类 string。因为字符串中的字符可以是 。因为字符串中的字符可以是ASCII码，也可以是中文 码 汉字编码，还可以是unicode编码，所以使用类模板是合理的。 编码， 汉字编码，还可以是 编码 所以使用类模板是合理的。

6.1.2 类模板与线性表线性表： 线性表：线性表是数据结构中的概念。数组中除第一个元素外， 线性表是数据结构中的概念。数组中除第一个元素外， 是数据结构中的概念 除第一个元素外 其他元素有且仅有一个直接前驱，第一个元素没有前驱； 其他元素有且仅有一个直接前驱，第一个元素没有前驱；除 最后一个元素外，其他元素有且仅有一个直接后继， 最后一个元素外，其他元素有且仅有一个直接后继，最后一 个元素无后继。这样的特性称为线性关系。所议称数组元素 个元素无后继。这样的特性称为线性关系。 线性关系 在一个线性表中。线性表实际包括顺序表(数组)和链表。 在一个线性表中。线性表实际包括顺序表(数组) 链表。 顺序表 对顺序表的典型操作包括：计算表长度，寻找变量或 对顺序表的典型操作包括：计算表长度， 典型操作包括 对象x(其类型与表元素相同)在表中的位置(下标值), 对象 (其类型与表元素相同)

在表中的位置(下标值), 判断x是否在表中 删除x, 是否在表中， 插入列表中第i个位置 判断 是否在表中，删除 ，将x插入列表中第 个位置，寻 插入列表中第 个位置， 的后继， 的前驱， 找x的后继，寻找 的前驱，判断表是否空，判断表是否满 的后继 寻找x的前驱 判断表是否空， 表满不能再插入数据，否则会溢出， (表满不能再插入数据，否则会溢出，产生不可预知的错 误),取第 个元素的值。 ),取第i个元素的值。 取第 个元素的值 这些操作与数组封装在一起可以定义一个类， 这些操作与数组封装在一起可以定义一个类，考虑到 类模板。 数组元素的类型可以各不相同，所以定义为类模板 数组元素的类型可以各不相同，所以定义为类模板。

6.1.2 类模板与线性表静态数组： 静态数组：由编译器编译时分配内存的数组称为静态数 由编译器编译时分配内存的数组称为静态数 数组的长度是不可改变的。 组，数组的长度是不可改变的。 如果定义了30个元素的数组，后来需要40 30个元素的数组 40个 如果定义了30个元素的数组，后来需要40个 元素，是不可能续上10个的，必然产生溢出。 10个的 元素，是不可能续上10个的，必然产生溢出。因 系统不检查数组边界， 系统不检查数组边界，进而产生不可预知的运行 时错误，所以一般采用“大开小用”的方法， 时错误，所以一般采用“大开小用”的方法，即 数组定义的较大，而实用较小。 数组定义的较大，而实用较小。 为防止不可避免的溢出， 为防止不可避免的溢出，应在添加新数据时 判断表是否满。 判断表是否满。

6.1.2 类模板与线性表删除顺序表元素： 删除顺序表元素：当需要在顺序表中删除一个元素时 当需要在顺序表中删除一个元素时，必须把它后面的元素的数据 删除一个元素 全部顺序前移一个位置，否则表中前驱后继关系被破坏。 全部顺序前移一个位置，否则表中前驱后继关系被破坏。图6.1表 表 中有11个数据 删去第i个元素的数据 就是把第i+1个元素拷入 个数据。 个元素的数据， 中有 个数据。删去第 个元素的数据，就是把第 个元素拷入 个元素拷入第 个元素,依此类推 第i个元素，把第 个元素拷入第 个元素 依此类推，直到最后 个元素，把第i+2个元素拷入第i+1个元素 依此类推， 一个元素(下标为10),现在表长度为10。 ),现在表长度为 一个元素(下标为 ),现在表长度为 。下标 0 31 1 24 2 16 3 18 4 9 图a i 下标 0 31 1 24 2 16 3 18 图b 4 9 5 7 6 14 1 7 11 2 8 5 3 9 8 4 10 11 12 13 5 7 6 27 7 14 8 11 9 5 10 8 11 12 13

图6.1 从表中删除一个数据

6.1.2 类模板与线性表添加顺序表元素： 添加

顺序表元素：当需要在顺序表的指定位置i 插入一个数据x时，必须为它腾出 当需要在顺序表的指定位置 插入一个数据 时 这个位置，把从该位置开始向后的所有元素数据， 这个位置，把从该位置开始向后的所有元素数据，后移一个位 最后才插入。后移时从最后一个元素开始，参见图6.2。 置，最后才插入。后移时从最后一个元素开始，参见图 。 现在长度为12,这样的移动也是不可少的， 现在长度为 ，这样的移动也是不可少的，否则新插入的数据 x会冲掉原来的数据，或先移的数据冲掉未移的数据。 会冲掉原来的数据， 会冲掉原来的数据 或先移的数据冲掉未移的数据。下标 0 31 1 24 2 16 3 18 图a 下标 0 31 1 24 2 16 3 18 4 9 图b 5 7 4 9 5 7 6 27 7 14 8 11 9 5 10 8 11 12 13

i 6 x

5 7 27

4 8 14

3 9 11

2 10 5

1 11 8 12 13

图6.2 向表中插入一个 数据

【例6.3】顺序表类模板 6.3】template <typename T,int size>class seqlist{ T slist[size]; //存放顺序表的数组 存放顺序表的数组 int Maxsize; //最大可容纳项数 最大可容纳项数 int last; //已存表项的最后位置 已存表项的最后位置 public: seqlist(){last=-1;Maxsize=size;} //初始化为空表 初始化为空表 int Length() const{return last+1;} //计算表长度 计算表长度 int Find(T & x)const; // 寻找 在表中位置(下标) 寻找x在表中位置 下标) 在表中位置( bool IsIn(T & x); //判断 是否在表中 判断x是否在表中 判断 bool Insert(T & x,int i); //x插入到列表中第i个位置处(下标) 插入到列表中第 个位置处(下标) 插入到列表中第 个位置处 bool Remove(T & x); //删除 删除x 删除 int Next(T & x); //寻找 的后继位置 寻找x的后继 寻找 的后继位置 int Prior(T & x); //寻找 的前驱位置 寻找x的前驱 寻找 的前驱位置 bool IsEmpty(){return last==-1;} //判断表是否空 判断表是否空 bool IsFull(){return last==Maxsize -1;} //判断表是否满 判断表是否满 T Get(int i){return i<0||i>last?NULL:slist[i];} //取第 个元素之值 取第i个元素之值 取第 T& operator[](int i); }; //重载下标运算符 重载下标运算符[] 重载下标运算符 检验主程序

6.2 排序与查找排序(sorting): 是最重要的计算应用之一。 ): 是最重要的计算应用之一。例如查字典，字典中的词条是按序存放的， 例如查字典，字典中的词条是按序存放的，我们 才能按字母顺序找到要查的字。 才能按字母顺序找到要查的字。又如图书馆的藏 书也是按书的编号有序排列的。 书也是按书的编号有序排列的。在计算机上数据 库里的资料也是有序排列的。 库里的资料也是有序排列的。

查找(search): 当然也是最常见的运算，就 ): 当然也是最常见的运算，是在数据集合中寻找满足条件

的数据对象，找到 是在数据集合中寻找满足条件的数据对象， 后进一步给出对象的具体信息， 后进一步给出对象的具体信息，在数据库技术中 称为检索(retrieval)。 称为检索( )。 检索

6.2.1 常用查找方法

6.2.2 常用的排序法

6.2.1 常用查找方法顺序查找： 顺序查找：从第一个元素开始，顺序查找直到找到或查到最后一个元素为止。 从第一个元素开始，顺序查找直到找到或查到最后一个元素为止。 关键字( 查找是按关键字 查找是按关键字(key word)进行。可以唯一地把资料区分出 )进行。 来的数据被称为主关键字 如学生的资料(结构体变量 主关键字。 结构体变量): 来的数据被称为主关键字。如学生的资料 结构体变量 struct student{ int id ; //学号 学号 char name[20]; // 姓名 char sex; // 性别 int age; // 年龄 char address[60]; //家庭地址 家庭地址 float eng, phy,math , electron;//英语 物理 数学和电子学成绩 英语,物理 英语 物理,数学和电子学成绩 };

学号可作为主关键字。 学号可作为主关键字。 主关键字 如果关键字小的排在前面，我们称为升序排列， 如果关键字小的排在前面，我们称为升序排列，反之为降序排 这时可以采用对半查找 对半查找( 列。这时可以采用对半查找(binary search)。 )

6.2.1 常用查找方法对半查找: 对半查找首先安排两个指针low和high指向首尾两元素，取mid= (low+ 和 指向首尾两元素， 首先安排两个指针 指向首尾两元素 high)/2,如mid指向元素是所查找的，则结束。如果该元素关键字 指向元素是所查找的， , 指向元素是所查找的 则结束。 大了，则取low=mid +1, high不变，继续查找；如果该元素关键 不变， 大了，则取 ， 不变 继续查找； 字小了， 不变， 字小了，则取 high=mid-1,low不变，继续查找。如果查到 ， 不变 继续查找。 low>high仍未找到，则失败，停止。 仍未找到， 仍未找到 则失败，停止。23 查找 2 low 5 7 8 9 11 13 17 19 mid 20 low 20 21 23 21 23 26 mid 29 31 37 39 high 20 21 23 26 29 31 37 39 high

low mid high

图6.3 查找成功例

23 low mid high 成功

本文来源：https://www.bwwdw.com/article/o5oe.html