第六章 模板与数据结构

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

第六章模板与数据结构

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 数组的长度。

…… 此处隐藏5325字 ……

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 成功