《第十一章模板.ppt》由会员分享,可在线阅读,更多相关《第十一章模板.ppt(48页珍藏版)》请在三一文库上搜索。
1、第十一章 模版,11.1 从类属到模板,ALGOL68语言最先引入类属(genericity)的概念,最主 要的类属形式是类型参数化,即用一个或多个类型去参数 化一个软件元素的能力。 基本思想:提供具有相同逻辑功能的程序正文(保存共性),然后把数据类型作为参数传递(指出不同特性),则可节约大量程序代码,这就是类属机制的思想,又称为参数化模板。,11.1 从类属到模板,类属又分为无约束类属机制和约束类属机制,所谓无约束类 属机制是指对作为类属参数的数据类型没有任何特殊要求,而约束 类属机制则意味着对类属参数有明确要求,只有在类属实参满足一 定条件时才有意义。 无约束类属的例子 void swap
2、(T ,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 概念,有多少种需要求最大值的数据类型,就需要定义多
3、少个重 载版本。这些版本的代码都相同,只是参数类型和函数返回值 类型不同。解决这个问题的最佳方法是使用模板。如果使用模 板,则数据类型本身就是一个参数,max函数的模板定义如 下: template / 模板声明 T max(T x,T y) / 模板定义体 return(xy)?x:y; 用关键字template表明,现在正在声明一个模板,数据类 型参数T由模板参数给出,它既可以取系统的预定义 类型,也可以取用户自定义的类类型。,11.2.1 概念,函数模板不是一个完全的函数,它代表了一类函数,必须把它的 模板参数T实例化之后,才能完成具体函数的功能。 把T实例化的参数称为模板实参,同模板实
4、参实例化的函数称为模 板函数。例如,用下列函数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为参数(称为模板参数)。函数模板与模板函数之间的关系,类似类与对象之间的关系
5、。,11.2.2 重载,函数模板有一个特点,虽然模板参数T可以实 例化成各种类型,但是采用模板参数T的每个参数 必须实例化成完全相同的类型。模板类型不具有隐 式的类型转换。,template T max(T x,T y) return(xy)?x:y; void f(int i,char c) max(i,i) ; /正确 max(c,c); /正确 max(i,c); /错误 max(c,i); /错误 从上面的例子可以看出,当模板实参类型完全相同时才正确。虽然int和char之间的隐式类型转换在C+中很普遍,但是模板类型却不具有隐式类型转换的能力。,11.2.2 重载,解决问题的办法是,允
6、许函数模板参与重载,即允许用普通函数重载一个同名的函数模板。有以下两种重载方式。 与函数模板共享函数体 通过借用函数模板的函数体来定义重载函数模板的非模板函数。也就是说,需要定义重载函数模板的普通函数时,只需给出函数声明,无须给出 函数体,当执行这个重载版本时系统将自动调用函数模板的函数体。 注意:使用这种 重载方法时,声明重载函数时各个模板参数的实参类型必须相同。 看下面的例子:,template T max(T x,T y) return(xy)?x:y; int max(int,int); /声明max(int ,int)为重载的非模板函数 void f(int i,char c) ma
7、x(i,i) ; /调用 max(int ,int) max(c,c); /调用模板函数 max(char ,char) max(i,c); /调用 max(int ,int) max(c,i); /调用 max(int ,int) 由于普通函数参数具有隐式类型转换能力,因此调用语句max(i,c)和max(c,i),都可以正确编译。, 重新定义函数体 在定义重载函数模板的非模板函数时,给出这个重载函数的函数体。 例如:下面是一个重载函数模板max(T x,T y) 的非模板函数的定义: char* max(char* s1,char* s2) return (strcmp(s1,s2)0)?
8、s1:s2; ,11.3 类模板与模板类,使用类模板(也称为类属类或类生成类)机 制,用户可以为类定义一种模式,使得类中的 某些数据成员、某些成员函数的参数和某些成 员函数的返回值,可以是任意类型的。 类模板不再代表一个具体的类,而是代表一类类。,11.3.1 定义类模板,定义类模板中的类的格式如下: template / 模板声明 class Name / 类的定义 ;,#include using namespace std; template class Max4 T a,b,c,d; T Max(T a,T b)return(ab)?a:b; public: Max4(T,T,T,T)
9、; T Max(void); ; /在类定义体外定义成员函数 template /定义成员函数必须再次声明模板 Max4:Max4(T x1,T x2,T x3,T x4):a(x1),b(x2),c(x3),d(x4) template /定义成员函数必须再次声明模板 T Max4:Max(void) return Max(Max(a,b),Max(c,d);,求4 个数中最大值的类模板,11.3.2 使用类模板,使用类模板时首先把它实例化成一个具体的类(即模板类),把类模板实 例化为模板类的格式如下: 类名 然后再说明模板类的对象并使用这些对象完成所需要的功能。 #include usin
10、g namespace std; void main() Max4 C(W,w,a,A);/比较字符 Max4 A(25,33,14,29);/比较整数 Max4 B(1.55,2.32,5.31,-2.6);/比较双精度实型 coutC.Max()“ “A.Max()“ “B.Max()endl; ,11.3.3类模板的派生,既可以从类模板派生出类模板,也可以派生出普通类 (非模板类)。 从类模板派生出类模板 从类模板派生出新的类模板的格式如下例所示: template class Base / 省略具体内容 ; template class Derived : public Base ;,
11、#include using namespace std; template class Point T x,y; public: Point(T a,T b) x=a;y=b; void Show() cout class Line:public Point T x2,y2; public: Line(T a,T b,T c,T d):Point(a,b) x2=c;y2=d; void Show() Point:Show();coutx2“,“y2endl; ;,例:设计一个模板类point,然后公有派生一个模板类Line,void main() Point a(4.5,2.9); a.S
12、how(); Line b(3,1,6,4); b.Show(); Line c(3.2,5.7,4.1,8.4); c.Show(); ,11.3.3 类模板的派生, 从类模板派生出普通类 从类模板派生出非模板类的格式如下例所示: template class Base ; class Derived : public Base ; 首先,作为新派生出来的非模板类的父类,必须是类 模板实例化后生成的模板类,例如,Base;其次,在 派生类定义之前不需要模板声明语句template。,#include using namespace std; template class Point T x,
13、y; public: Point(T a,T b) x=a;y=b; void Show() cout /继承Point的int模板类 int x2,y2; public: Line(int a, int b, int c, int d):Point(a,b) x2=c;y2=d; void Show() Point:Show();coutx2“,“y2endl; ;,例:设计一个模板类point,然后设计一个继承Point类的Line 类,void main() Point a(4.5,2.9); /可以是double类型 a.Show(); Line b(3,1,6,4); /只能是int
14、类型 b.Show(); ,11.4 模板应用实例 11.4.1 用类模板实现类属链表,链表是程序设计中经常使用的数据结构,可 以把它抽象成链表类。 首先定义一个结构模板,以表示类属链表的 节点,结构模板实质上就是类模板,只是不包含 成员函数;然后定义链表类模板。结构模板和类 模板使用同样的模板参数T。,11.4.1 用类模板实现类属链表,这个类属链表的基本功能是,在表头插入一个节点, 删除一个指定内容的节点,判断给定的数据内容是否在链 表内,以及打印链表内容等。考虑到将来从链表类模板派 生出的类模板或非模板类的插入功能可能和链表插入功能 有差别,我们把实现插入功能的成员函数声明为虚函数。 该
15、类的类图如图11.2所示:,下面给出链表类模板的定义及使用这个类模板的一个主函数:. #include using namespace std; template / 模板声明 struct Node / 定义结构模板 T val; Node *next; ; template / 模板声明 class List Node *head; / 定义类模板 int size; public: List() head = 0; size = 0; virtual bool insert(T val); bool deletes(T val); bool contains(T val); void p
16、rint(); 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) / 定义函数模板 Node *nodes = new Node; if(nodes) nodes - val = x; nodes - next = head; head = nodes; size +; return tru
17、e; 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 = p, p = p - next) if(p - val = x) temp - next = p - next; delete p; size -; retur
18、n 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 = p - next) cout val intlist; / 说明整型链表对象 intlist.insert(-11);
19、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 charlist; / 说明字符串型链表对象 charlist.insert(“programming“); charlist.insert(“object_
20、oriented“); charlist.insert(“C +“); charlist.print(); ,11.4.1 用类模板实现类属链表,程序输出如下: 79 57 35 -11 29.78 3.1416 C +object_oriented programming,需求链表的基本功能,在表头插入节点(内容是:T 类型的数据和一个 指向节点类型的指针,其中 T是模板参数) 打印链表 输出链表的节点数 判断给定的数据内容是否在链表内 删除一个指定内容的节点 删除整个链表(释放内存),分析与设计,根据需求我们可以把节点说明为结构类型: template /说明T是模板参数 struct N
21、ode T a; Node* next; ; head: 链表的头,找到了头就找到了整个链表,根据需求我们给出链表类模版的定义: template class List Node * 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:在表头插入一个节点,算法分析: 链表中一个节点都没有时,head=0,表示
22、链表是空的。我们首先要在内 存中产生一个节点(用 new 来产生一个Node 类型的内存空间,并获得 这个空间的地址 current)。即 Node* current = new Node ;此节 点作为链表的第一个节点,也是链表的头节点,也是链表的尾节点(最后一 个),此时,我们可以认为这个链表只有一个节点。 通常我们把最后的一个节点的next设为0,即 next = 0 或 next = head; (head的初始值为0);另外,这时头指针head 的值不再是初始值0,而应 该是当前节点的首地址, 即 head = current ; 当有下一个节点产生时,必然 要产生一个新的curre
23、nt,先给这个新的节点赋值, current-a = x; 新节点 中的next值,必须指向原来链表的头,即:current-next = head; 否则,就 不能和原来的链表链接。这样一来,链表的头,就应该是刚生成的这个节 点,头指针head,应该重新设为这个新节点的首地址,即 head = current ; 总之,head 永远指向链表的头,打印链表、遍历链表、删除链表等操作 都是从链表达的头开始的。,bool insert(T x) Node *current = new Node; if(current) /判断内存节点是否创建成功 current-a = x; /节点中存放的数据
24、 current-next = head; /节点中用来指向下一个节点的指针 head = current; /注意给head 赋值的顺序 size+; return true; else return false; ,功能2:打印链表,打印链表是从链表的头开始的,即从head开 始用来链接链表的指针next的值,每个都是有效 值,唯有最后一个节点的next 值是0,打印链表的实现代码,void print() for(Node* node = head; node ; node = node-next ) couta * node = head;/循环变量赋初值。执行一次,指向链表头 nod
25、e;/循环结束的条件。判断是否为0,即最后一个节点 node = node-next /改变循环变量的值。将 node中的next赋给node 将此循环形式,作为遍历链表的一般循环形式 ,今后遇到 遍历链表的操作都可以套用此形式的循环。,功能3:输出链表的节点数,通常函数原形采用int Get_size() 形式应为在对节点的 操作中,随时统计了节点数,所以,直接 return size即可 以了,否则,还要遍历整个链表统计其节点个数: int Get_size() return size; ,功能4:判断给定的数据内容是否在链表内,首先应该考虑,此项操作必须遍历整个 链表才能知道,链表中是否
26、包含要查找的数 据内容一般循环形式如前所述: 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 * n
27、ode = temp=head ;node;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,
28、所以 /有节点单独处理 delete node; size-; return true; return false; ,功能5:删除一个指定内容的节点,功能6:释放链表,首先要获得链表的头指针,从头节点开始删除, 在删除头节点以前,先要保存头节点中next的值,因 为它将是删除后的头节点的指针,只有保存好以后, 才能删除,这个头节点,依次进行直到最后一个节 点。,释放链表的代码,List() for(Node* current = head; current; ) /注意这种形式 /current = current-next ) head = current-next ; /指向下一个节点
29、cout“*x = ”currentendl; /观察删除了几个 delete current; /删除当前节点,非0则删除 current = head; /指向下一个节点,准备删除 注意: 若current = 0,则delete current; delete current都可以。因为,它 不指向一个有效内存空间但int x = 5;current = 不可以,属连续释放一个内存空间。,11.4.2 派生集合类模板和集合类,集合与链表的唯一差别是,集合中没有相同的 元素,因此,在进行插入操作时要先判断集合中 是否已存在要插入的元素,仅当集合中原来没有 这个元素时才真正做插入操作。 下面
30、从刚才定义的链表类派生出一个集合类模板,派生出集合类模板,template /模板声明 class Set : public List / 定义集合类模板 public: boolean insert(T val); ; template / 模板声明 boolean Set : insert(T x) / 定义函数模板 if(!(List : contains(x) ,派生出集合类模板,下面给出一个使用集合类模板的示例程序: void main() Set intset; / 说明整型集合类对象 intset.insert(18); intset.insert(25); intset.ins
31、ert(36); intset.insert(25); intset.insert(59); intset.print(); ,程序输出为: 59 36 25 18,派生出整数集合类,class Set : public List public: boolean insert(int val); ; boolean Set : insert(int val) if(!(List : contains(val) ,使用这个类的方法和使用普通类的方法完全相同, 下面是一个示例程序: void main() Set intset; intset.insert(18); intset.insert(25); intset.insert(36); intset.insert(25); intset.insert(59); intset.print(); ,程序输出为: 59 36 25 18,
链接地址:https://www.31doc.com/p-2584168.html