模板：总结 计划 汇报 设计 纯word可编辑

1、第十一章 模版本章概要： 模板概念是对类属概念的继承与开展。利用模板机制可以显著减少冗余信息，能大幅度地节约程序代码，进一步提高面向对象程序的可重用性和可维护性。本章主要讲述，类属概念与模板概念，函数模板与模板函数，类模板与模板类，模板机制应用实例等内容。 本章快速索引11.1 从类属到模板11.2 函数模板与模板函数11.3 类模板与模板类11.4 模板应用实例11.5 小结11.1 从类属到模板 ALGOL68语言最先引入类属(genericity)的概念，最主要的类属形式是类型参数化，即用一个或多个类型去参数化一个软件元素的能力。 根本思想：在实际工作中人们经常用到这样一些程序模块，从它

2、们的逻辑功能(或实现算法)看，彼此是相同的，所不同的主要是处理对象(数据)的类型。如果提供具有相同逻辑功能的程序正文(保存共性)，然后把数据类型作为参数传递(指出不同特性)，那么可节约大量程序代码，这就是类属机制的思想，又称为参数化模板。 11.1 从类属到模板 类属又可分为无约束类属机制和约束类属机制，所谓无约束类属机制是指对作为类属参数的数据类型没有任何特殊要求，而约束类属机制那么意味着对类属参数有明确要求，只有在类属实参满足一定条件时才有意义。 无约束类属的例子void swap(T &x,T &y)T temp;temp = x;x = y;/只要是同类型就可以赋值y = temp;

3、11.1 从类属到模板 约束类属的例子T minimum(T x，T y)if(x=y) return x;/结构变量的比较运算与整型变量的比较 /运算就有很大差异 else return x; 并不是任何数据类型都可以作为这个函数的类属实参，只有满足一定条件(即定义了“=操作)的数据类型，才能作为这个函数的类属实参。 C+语言使用模板来实现类属机制。图11.1用直观形象的形式说明了模板、类、对象、函数之间的关系。 11.1 从类属到模板 图11.1 模板、类、对象和函数的关系11.2 函数模板与模板函数 11.2.1 概念 有多少种需要求最大值的数据类型，就需要定义多少个重载版本。这些版本的

4、代码都相同，只是参数类型和函数返回值类型不同。解决这个问题的最正确方法是使用模板。如果使用模板，那么数据类型本身就是一个参数，max函数的模板定义如下： template / 模板声明T max(T x,T y) / 模板定义体return(xy)?x:y; 用关键字template说明，现在正在声明一个模板，数据类型参数T由模板参数给出，它既可以取系统的预定义类型，也可以取用户自定义的类类型。 11.2.1 概念 函数模板不是一个完全的函数，它代表了一类函数，必须把它的模板参数T实例化之后，才能完成具体函数的功能。 把T实例化的参数称为模板实参，同模板实参实例化的函数称为模板函数。例如，用以

5、下函数main来调用前面定义的函数模板如下： main()int i=18，j=-57；Myclass a b;int x = max(i,j); / 模板实参为整型模板函数模板的函数Myclass m = max(a,b);/ 模板实参为Myclass类的对象11.2.1 概念 这里生成了两个模板函数：max(i,j)用模板实参int把类型参数T实例化，max(a,b)用类类型Myclass把T实例化。 总之，一个函数模板是对一类函数的抽象，它以任意类型T为参数(称为模板参数)。由一个函数模板经把T实例化而产生的函数称为模板函数，它是函数模板的具体实例。函数模板与模板函数之间的关系，类似类与

6、对象之间的关系。 11.2.2 重载 函数模板有一个特点，虽然模板参数T可以实例化成各种类型，但是采用模板参数T的每个参数必须实例化成完全相同的类型。模板类型不具有隐式的类型转换。 解决问题的方法是，允许函数模板参与重载，即允许用普通函数重载一个同名的函数模板。有以下两种重载方式。 11.2.2 重载 与函数模板共享函数体 通过借用函数模板的函数体来定义重载函数模板的非模板函数。 重新定义函数体 在定义重载函数模板的非模板函数时，给出这个重载函数的函数体。 11.3 类模板与模板类 使用类模板(也称为类属类或类生成类)机制，用户可以为类定义一种模式，使得类中的某些数据成员、某些成员函数的参数和

7、某些成员函数的返回值，可以是任意类型的。 类模板不再代表一个具体的、实际的类，而是代表一类类。11.3.1 定义类模板 定义类模板，包含两方面内容： 1. 定义类定义类模板中的类的格式如下：template / 模板声明class Name / 类的定义； 向量类模板定义如下：#include stdafx.h#include iostream.htemplateclass VectorT *data;int size;public:Vector(int i) data=new Ti; Vector() delete data; T &operator(int i) return datai;

8、 ; 可见类中函数模板是指函数中的参数类型数据成员data的类型T是可变的11.3.1 定义类模板 11.3.1 定义类模板 在类定义体外定义成员函数 在类定义体外定义成员函数时，如果该成员函数中有模板参数，那么需先进行模板声明，而且用类模板名，而不是用类名来限定函数名，即在函数名前的类名后缀上“。例如：templateVector:Vector(int n)data = new T(n);size = n;11.3.2 使用类模板 使用类模板时首先把它实例化成一个具体的类(即模板类)，把类模板实例化为模板类的格式如下： 类名然后再说明模板类的对象并使用这些对象完成所需要的功能。 如，向量类模

9、板的主函数：#include stdafx.h#include iostream.h void main()Vector x(7);for(int i=0;i7;i+)xi=10*i;for(int j=0;j7;j+)coutxj“ ;cout“n;此程序的输出为：0 10 20 30 40 50 60类模板的派生 既可以从类模板派生出类模板，也可以派生出普通类(非模板类)。 从类模板派生出类模板从类模板派生出新的类模板的格式如下例所示：templateclass Base / 省略具体内容;templateclass Derived : public Base; 11.3.3 类模板的派生

10、 从类模板派生出普通类从类模板派生出非模板类的格式如下例所示：templateclass Base ;class Derived : public Base; 首先，作为新派生出来的非模板类的父类，必须是类模板实例化后生成的模板类，例如，Base;其次，在派生类定义之前不需要模板声明语句template。 11.4 模板应用实例 11.4.1 用类模板实现类属链表 链表是程序设计中经常使用的数据结构，可以把它抽象成链表类。 首先定义一个结构模板，以表示类属链表的节点，结构模板实质上就是类模板，只是不包含成员函数；然后定义链表类模板。结构模板和类模板使用同样的模板参数T。 11.4.1 用类模板

11、实现类属链表 这个类属链表的根本功能是，在表头插入一个节点，删除一个指定内容的节点，判断给定的数据内容是否在链表内，以及打印链表内容等。考虑到将来从链表类模板派生出的类模板或非模板类的插入功能可能和链表插入功能有差异，我们把实现插入功能的成员函数声明为虚函数。该类的类图如图11.2所示： 下面给出链表类模板的定义及使用这个类模板的一个主函数：.#include stdafx.h#include iostream.htemplate / 模板声明struct Node / 定义结构模板T val;Node *next;template/ 模板声明class ListNode *head; / 定

12、义类模板int size;public:List()head = 0;size = 0;virtual bool insert(T val);bool deletes(T val);bool contains(T val);void print();List(); 11.4.1 用类模板实现类属链表template/ 模板声明List : List()/ 定义函数模板Node *temp;for(Node *p = head;p;)temp = p;p = p - next;delete temp;template/ 模板声明bool List : insert(T x)/ 定义函数模板Nod

13、e *nodes = new Node;if(nodes)nodes - val = x;nodes - next = head;head = nodes;size +;return true;return false; 11.4.1 用类模板实现类属链表template/ 模板声明bool List : deletes(T x)/ 定义函数模板Node *temp;if(head - val = x)temp = head - next;delete head;size - ;head = temp;return true;for(Node *p = temp = head;p;temp =

14、 p, p = p - next)if(p - val = x)temp - next = p - next;delete p;size -;return true;return false;template/ 模板声明bool List : contains(T x)/ 定义函数模板for(Node *p = head;p;p = p - next)if(p - val = x)return true;return false;11.4.1 用类模板实现类属链表template/ 模板声明void List : print()/ 定义函数模板for(Node *p = head;p;p =

15、p - next)cout val ;cout n;void main()/ 主函数List intlist;/ 说明整型链表对象intlist.insert(-11);intlist.insert(35);intlist.insert(48);intlist.insert(57);intlist.insert(79);intlist.deletes(48);intlist.print();List floatlist;/ 说明浮点型链表对象floatlist.insert(3.1416);floatlist.insert(29.78);floatlist.print();List charl

16、ist;/ 说明字符串型链表对象charlist.insert(programming);charlist.insert(object_oriented);charlist.insert(C +);charlist.print();11.4.1 用类模板实现类属链表程序输出如下：79 57 35 -1129.78 3.1416C +object_oriented programming需求链表的根本功能在表头插入节点内容是：T 类型的数据和一个指向节点类型的指针，其中 T是模板参数打印链表输出链表的节点数判断给定的数据内容是否在链表内删除一个指定内容的节点删除整个链表释放内存分析与设计根据需求

17、我们可以把节点说明为结构类型：template /说明T是模板参数struct NodeT a;Node* next;head: 链表的头，找到了头就找到了整个链表根据需求我们给出链表类模版的定义：template class ListNode * head; int size;public:List() head = 0; size = 0; bool insert(T x)；void print()；int Get_size() return size; bool contains( T x)；bool deletes(T x)；List();分析与设计功能1：在表头插入一个节点算法分析：

18、 链表中一个节点都没有时，head=0,表示链表是空的。我们首先要在内存中产生一个节点用 new 来产生一个Node 类型的内存空间，并获得这个空间的地址 current。即 Node* current = new Node ;此节点作为链表的第一个节点，也是链表的头节点，也是链表的尾节点最后一个，此时，我们可以认为这个链表只有一个节点。 通常我们把最后的一个节点的next设为0，即 next = 0 或 next = head;head的初始值为0；另外，这时头指针head 的值不再是初始值0，而应该是当前节点的首地址， 即 head = current ; 当有下一个节点产生时，必然要产生

19、一个新的current，先给这个新的节点赋值， current-a = x; 新节点中的next值，必须指向原来链表的头，即：current-next = head; 否那么，就不能和原来的链表链接。这样一来，链表的头，就应该是刚生成的这个节点，头指针head，应该重新设为这个新节点的首地址，即 head = current ; 总之，head 永远指向链表的头，打印链表、遍历链表、删除链表等操作都是从链表达的头开始的。 bool insert(T x)Node *current = new Node;if(current) /判断内存节点是否创立成功current-a = x; /节点中存放

20、的数据current-next = head; /节点中用来指向下一个节点的指针head = current; /注意给head 赋值的顺序size+;return true;elsereturn false;功能2：打印链表 打印链表是从链表的头开始的，即从head开始用来链接链表的指针next的值，每个都是有效值，唯有最后一个节点的next 值是0 打印链表的实现代码void print()for(Node* node = head; node ; node = node-next )couta endl;注意：Node* node = head;/循环变量赋初值。执行一次，指向链表头 n

21、ode;/循环结束的条件。判断是否为0，即最后一个节点node = node-next /改变循环变量的值。将 node中的next赋给node 将此循环形式，作为遍历链表的一般循环形式 ，今后遇到遍历链表的操作都可以套用此形式的循环。功能3：输出链表的节点数 通常函数原形采用int Get_size() 形式应为在对节点的操作中，随时统计了节点数，所以，直接 return size即可以了，否那么，还要遍历整个链表统计其节点个数： int Get_size()return size; 功能4：判断给定的数据内容是否在链表内 首先应该考虑，此项操作必须遍历整个链表才能知道，链表中是否包含要查找

22、的数据内容一般循环形式如前所述：for(Node * node = head ; node ;node = node-next ) 判断给定的数据内容是否在链表内代码bool contains( T x)for(Node * node = head ; node; node = node-next )if(node-a = x) return true;else false;功能5：删除一个指定内容的节点 要删除一个指定内容的节点，有两种情况：一种是第一个节点以外的节点；另一种情况是第一个节点采用的循环形式还是：Node* temp;for(Node * node = temp=head ;n

23、ode;temp=node,node = node-next )具体实现如下：bool deletes(T x)Node* temp;for(Node * node = temp=head ;node;temp=node,node = node-next ) if(node-a = x) if(node=head)/头节点单独处理head = node-next ;delete node;size-;return true; else /其他节点，统一处理temp-next = node-next ; /假设是头节点那么 temp=node,所以 /有节点单独处理delete node;siz

24、e-; return true; return false;功能5：删除一个指定内容的节点 功能6：释放链表 首先要获得链表的头指针，从头节点开始删除，在删除头节点以前，先要保存头节点中next的值，因为它将是删除后的头节点的指针，只有保存好以后，才能删除，这个头节点，依次进行直到最后一个节点。释放链表的代码List()for(Node* current = head; current; ) /注意这种形式/current = current-next )head = current-next ;/指向下一个节点cout“*x = currentendl;/观察删除了几个delete curr

25、ent;/删除当前节点，非0那么删除current = head; /指向下一个节点，准备删除注意： 假设current = 0，那么delete current； delete current都可以。因为，它不指向一个有效内存空间但int x = 5；current = &x;那么delete current；delete current;不可以，属连续释放一个内存空间。11.4.2 派生出集合类模板和集合类 集合与链表的唯一差异是，集合中没有相同的元素，因此，在进行插入操作时要先判断集合中是否已存在要插入的元素，仅当集合中原来没有这个元素时才真正做插入操作。 11.4.2 派生出集合类模板和集合类派生出集合类模板template/模板声明class Set : public List/ 定义集合类模板public:boolean insert(T val); ; te