第9章模板精选文档.ppt

《第9章模板精选文档.ppt》由会员分享，可在线阅读，更多相关《第9章模板精选文档.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第9章模板本讲稿第一页，共二十四页9.1 函数模板1.问题的提出重载函数重载函数可以解决功能相同或相似的函数可以解决功能相同或相似的函数使用同一个函数名使用同一个函数名的问的问题。题。void swap(char&x,char&y)void swap(char&x,char&y)char t=x;char t=x;x=y;x=y;y=t;y=t;void swap(int&x,int&y)void swap(int&x,int&y)int t=x;int t=x;x=y;x=y;y=t;y=t;第第9 9章章 模板模板void swap(float&x,float&y)void swap(fl

2、oat&x,float&y)float t=x;float t=x;x=y;x=y;y=t;y=t;实际代码量并未减实际代码量并未减少。可使用函数模板减少。可使用函数模板减少大量代码。少大量代码。本讲稿第二页，共二十四页9.1 函数模板2.函数模板的定义templatetemplate或或类型名类型名 函数名（参数表）函数名（参数表）函数体函数体函数模板函数模板就像是一个带有就像是一个带有类型参数类型参数的函数的函数(参数参数T T即为类型即为类型)，编译程，编译程序会根据实际参数的类型确定参数的类型。序会根据实际参数的类型确定参数的类型。第第9 9章章 模板模板templatetemplat

3、e类型名类型名 函数名（参数表）函数名（参数表）函数体函数体 本讲稿第三页，共二十四页例9.19.1定义用于变量交换的函数模板定义用于变量交换的函数模板#include#include template template void swap(T&x,T&y)void swap(T&x,T&y)T temp=x;T temp=x;x=y;x=y;y=temp;y=temp;void main(void)void main(void)char a=A,b=B;char a=A,b=B;int c=123,d=456;int c=123,d=456;double x=12.3,y=45.6;doub

4、le x=12.3,y=45.6;swap(a,b);swap(a,b);swap(c,d);swap(c,d);swap(x,y);swap(x,y);cout a ,b endl;cout a ,b endl;cout c ,d endl;cout c ,d endl;cout x ,y endl;cout x ,y endl;第第9 9章章 模板模板程序运行结果为：程序运行结果为：B,AB,A456,123456,12345.6,12.345.6,12.3T本身是一个类型参数，在调用函数本身是一个类型参数，在调用函数swap（）时，编译程序会根据实际参数的（）时，编译程序会根据实际参数的

5、类型确定类型确定T的类型。的类型。本讲稿第四页，共二十四页例例9.29.2插入排序函数模板，使用插入排序函数模板可以为不同数据类插入排序函数模板，使用插入排序函数模板可以为不同数据类型的数组排序，如整型、字符型、实型等等，为了使程序具有通用性，型的数组排序，如整型、字符型、实型等等，为了使程序具有通用性，设计函数模板设计函数模板InsertionSortInsertionSort（）。插插入入排排序序的的基基本本思思想想：每每一一步步将将一一个个待待排排序序的的元元素素按按其其关关键键字字值值的的大大小小插插入入到到已已排排序序列的合适位置，直到待排序元素全部插入完为止。序序列的合适位置，直到

6、待排序元素全部插入完为止。第第9 9章章 模板模板本讲稿第五页，共二十四页例9.2（续一）（续一）template template void InsertionSort(T A,int n)void InsertionSort(T A,int n)int i,j;int i,j;T temp;T temp;for(i=1;i n;i+)for(i=1;i 0&temp 0&temp=Aj-1temp=Aj-1结束循环时，结束循环时，结束循环时，结束循环时，j j便是应插入的位置便是应插入的位置便是应插入的位置便是应插入的位置 /当遇到当遇到当遇到当遇到j=0j=0结束循环时，则结束循环时，则

7、结束循环时，则结束循环时，则0 0是应插入的位置。是应插入的位置。是应插入的位置。是应插入的位置。Aj=Aj-1;Aj=Aj-1;/将元素逐个后移，以便找到插入位置时可立即插入。将元素逐个后移，以便找到插入位置时可立即插入。将元素逐个后移，以便找到插入位置时可立即插入。将元素逐个后移，以便找到插入位置时可立即插入。j-;j-;Aj=temp;Aj=temp;第第9 9章章 模板模板本讲稿第六页，共二十四页例例9.29.2（续二）（续二）#include#include void main()void main()int a10=2,4,1,8,7,9,0,3,5,6;int a10=2,4,1

8、,8,7,9,0,3,5,6;double b10=12.1,24.2,15.5,81.7,2.7,5.9,40.3,33.3,25.6,4.6;double b10=12.1,24.2,15.5,81.7,2.7,5.9,40.3,33.3,25.6,4.6;InsertionSort(a,10);InsertionSort(a,10);InsertionSort(b,10);InsertionSort(b,10);cout a0 a1 a2 a3 ;cout a0 a1 a2 a3 ;cout a4 a5 a6 a7 ;cout a4 a5 a6 a7 ;cout a8 a9 endl;c

9、out a8 a9 endl;cout b0 b1 b2 b3 ;cout b0 b1 b2 b3 ;cout b4 b5 b6 b7 ;cout b4 b5 b6 b7 ;cout b8 b9 endl;cout b8 b9 endl;第第9 9章章 模板模板程序运行结果为：程序运行结果为：012345678901234567892.74.65.912.115.524.225.633.340.381.72.74.65.912.115.524.225.633.340.381.7本讲稿第七页，共二十四页例例9.3使用函数模板产生的二意性使用函数模板产生的二意性#include#include t

10、emplate template T max(T a,T b)T max(T a,T b)return ab?a:b;return ab?a:b;void main(void)void main(void)int a=max(10.5,20);int a=max(10.5,20);double b=max(10,20.6);double b=max(10,20.6);cout a endl;cout a endl;cout b endl;cout b endl;第第9 9章章 模板模板产生二意性，系统不能确定将其中的一个产生二意性，系统不能确定将其中的一个参数由整数转化为实数，还是应该将另一参

11、数由整数转化为实数，还是应该将另一个参数由实数转化为整数个参数由实数转化为整数。可使用强制类型转换解决：可使用强制类型转换解决：int a=max(int)10.5,20);double b=max(double )10,20.6);返 回本讲稿第八页，共二十四页9.2 模板函数的覆盖下列函数模板：下列函数模板：templatetemplateTmax(Ta,Tb)Tmax(Ta,Tb)retumab?a:b;retumab?a:b;对于简单的数据类型，如对于简单的数据类型，如整型、实型、字符型整型、实型、字符型数据，这个模板能够正数据，这个模板能够正常工作。对于常工作。对于字符串字符串，用上

12、述模板就会，用上述模板就会出现问题出现问题，因为对于字符串，不能，因为对于字符串，不能使用运算符使用运算符“”，要为其编写独立的，要为其编写独立的maxmax（）函数。（）函数。我们将函数模板生成的函数称为我们将函数模板生成的函数称为模板函数模板函数。如果某一函数的函数原型与。如果某一函数的函数原型与函数模板生成的函数（模板函数）原型一致，称该函数为模板函数的函数模板生成的函数（模板函数）原型一致，称该函数为模板函数的覆盖函覆盖函数数。第第9 9章章 模板模板本讲稿第九页，共二十四页例9.49.4模板函数的覆盖#include#include#include#include template

13、template T max(T a,T b)T max(T a,T b)return ab?a:b;return ab?a:b;char*max(char*x,char*y)char*max(char*x,char*y)return strcmp(x,y)0?x:y;return strcmp(x,y)0?x:y;void main(void)void main(void)char*p=ABCD,*q=EFGH;char*p=ABCD,*q=EFGH;p=max(p,q);p=max(p,q);int a=max(10,20);int a=max(10,20);float b=max(10.

14、5,20.6);float b=max(10.5,20.6);cout p endl;cout p endl;cout a endl;cout a endl;cout b endl;cout b endl;第第9 9章章 模板模板程序运行结果为：程序运行结果为：EFGHEFGH202020.620.6本讲稿第十页，共二十四页9.2 模板函数的覆盖在进行函数调用时，编译程序采用如下策略确定调用哪个函数：在进行函数调用时，编译程序采用如下策略确定调用哪个函数：（1 1）首先寻找一个实参与形参完全匹配的）首先寻找一个实参与形参完全匹配的覆盖函数覆盖函数，如果找到，则调，如果找到，则调用该函数用该函数

15、（2 2）如果能通过）如果能通过函数模板生成实例函数函数模板生成实例函数，并且参数匹配，则调用该函数。，并且参数匹配，则调用该函数。（3 3）通过）通过强制类型转换强制类型转换，寻找能够与实参匹白的覆盖函数，或通过，寻找能够与实参匹白的覆盖函数，或通过函数模板生成的实例函数、如果找到则调用该函数。函数模板生成的实例函数、如果找到则调用该函数。（4 4）如果所有努力失败，则给出出错信息。）如果所有努力失败，则给出出错信息。第第9 9章章 模板模板 返 回本讲稿第十一页，共二十四页9.3 类模板1.问题的提出 class A class A int i;int i;public:public:A(

16、int a)A(int a)void set(int b)void set(int b);class B class B double i;double i;public:public:B(double a)B(double a)void set(double b)void set(double b);第第9 9章章 模板模板对应的类模板：对应的类模板：对应的类模板：对应的类模板：template template class Aclass A T i;T i;public:public:A(T a)A(T a)void set(T b)void set(T b);这两个类的方法都一样，这两个

17、类的方法都一样，只是一个数据类型是整只是一个数据类型是整型，另一个数据类型是型，另一个数据类型是实型。可以使用类模板实型。可以使用类模板简化代码简化代码类模板也称为参数化的类，类模板也称为参数化的类，用于为类型相似的类定义一用于为类型相似的类定义一种通用模式种通用模式本讲稿第十二页，共二十四页9.3 类模板2.类模板的定义 templatetemplate classclass类模板名类模板名成员声明成员声明如果需要在类模板外定义类模板的成员函数，格式如下：如果需要在类模板外定义类模板的成员函数，格式如下：templatetemplate 类型类型 类模板名类模板名:函数名（参数表）函数名（参

18、数表）函数体函数体第第9 9章章 模板模板本讲稿第十三页，共二十四页9.3 类模板2.类模板的定义（续）使用类模板建立对象的语法如下：使用类模板建立对象的语法如下：类模板类模板 对象对象1 1，对象，对象2 2，；系统会根据实参的类型，生成一个类（称为系统会根据实参的类型，生成一个类（称为模板类模板类），然后建立），然后建立该类的对象。即对模板实例化生成类，再对类实例化生成对象。该类的对象。即对模板实例化生成类，再对类实例化生成对象。第第9 9章章 模板模板本讲稿第十四页，共二十四页例9.5定义数组类的类模板，并利用成员函数对数组中的元素初始化。定义数组类的类模板，并利用成员函数对数组中的元素

19、初始化。#include#include template template class myArrayclass myArray public:public:myArray(int nSize,T Initial);myArray(int nSize,T Initial);myArray()myArray()delete m_pArray;delete m_pArray;T&operator(int nIndex)T&operator(int nIndex)/重载运算符重载运算符用于取得数组的元素用于取得数组的元素 return m_pArraynIndex;return m_pArrayn

20、Index;void Show(int nNumElems,char*pszMsg=,bool bOneLine=true);void Show(int nNumElems,char*pszMsg=,bool bOneLine=true);void Sort(int nNumElems);void Sort(int nNumElems);protected:protected:T*m_pArray;T*m_pArray;/保存数组起始地址保存数组起始地址int m_nSize;int m_nSize;/数组的长度数组的长度;第第9 9章章 模板模板本讲稿第十五页，共二十四页例9.5（续一）（续

21、一）templatetemplatemyArray:myArray(int nSize,T InitVal)myArray:myArray(int nSize,T InitVal)m_nSize=(nSize1)?nSize:1;m_nSize=(nSize1)?nSize:1;m_pArray=new Tm_nSize;m_pArray=new Tm_nSize;for(int i=0;im_nSize;i+)for(int i=0;im_nSize;i+)m_pArrayi=InitVal;m_pArrayi=InitVal;templatetemplatevoid myArray:Sho

22、w(int nNumElems,char*pszMsg,bool bOneLine)void myArray:Show(int nNumElems,char*pszMsg,bool bOneLine)cout pszMsgendl;cout pszMsgendl;if(bOneLine)if(bOneLine)for(int i=0;inNumElems;i+)for(int i=0;inNumElems;i+)cout m_pArrayi ;cout m_pArrayi ;cout endl;cout endl;elseelse for(int i=0;inNumElems;i+)for(i

23、nt i=0;inNumElems;i+)cout m_pArrayiendl;cout m_pArrayiendl;第第9 9章章 模板模板构造函数为构造函数为m_nSize赋值，并为数组申请存储空赋值，并为数组申请存储空间，将数组的每个元素都赋值为间，将数组的每个元素都赋值为InitVal。成员函数成员函数Show（）显示数组元素的值，（）显示数组元素的值，元素的个数由第一个参数指定，第二个元素的个数由第一个参数指定，第二个参数为输出数组元素值之前，输出的提参数为输出数组元素值之前，输出的提示信息，第三个参数确定数组元素是显示信息，第三个参数确定数组元素是显示在一行上，还是多行。示在一行上

24、，还是多行。本讲稿第十六页，共二十四页例9.5（续二）templatetemplatevoid myArray:Sort(int nNumElems)void myArray:Sort(int nNumElems)int i,j;int i,j;T temp;T temp;for(i=1;i nNumElems;i+)for(i=1;i 0&temp 0&temp m_pArrayj-1)m_pArrayj=m_pArrayj-1;m_pArrayj=m_pArrayj-1;j-;j-;m_pArrayj=temp;m_pArrayj=temp;第第9 9章章 模板模板成员函数成员函数Sort

25、（）使用插入排序法对数组元素（）使用插入排序法对数组元素排序（升序），其参数是数组中元素的个数。排序（升序），其参数是数组中元素的个数。本讲稿第十七页，共二十四页例9.5（续三）void main()void main()int nArr10=89,34,32,47,15,81,78,36,63,83;int nArr10=89,34,32,47,15,81,78,36,63,83;int cArr10=C,W,r,Y,k,J,X,Z,y,s;int cArr10=C,W,r,Y,k,J,X,Z,y,s;myArray IntegerArray(10,0);myArray IntegerArr

26、ay(10,0);myArray CharArray(10,);myArray CharArray(10,);for(int i=0;i10;i+)for(int i=0;i10;i+)IntegerArrayi=nArri;IntegerArrayi=nArri;for(i=0;i10;i+)for(i=0;i10;i+)CharArrayi=cArri;CharArrayi=cArri;IntegerArray.Show(10,Unsorted array is:);IntegerArray.Show(10,Unsorted array is:);IntegerArray.Sort(10)

27、;IntegerArray.Sort(10);IntegerArray.Show(10,Sorted array is:);IntegerArray.Show(10,Sorted array is:);cout endl;cout endl;CharArray.Show(10,Unsorted array is:);CharArray.Show(10,Unsorted array is:);CharArray.Sort(10);CharArray.Sort(10);CharArray.Show(10,Sorted array is:);CharArray.Show(10,Sorted arra

28、y is:);cout endl;cout endl;第第9 9章章 模板模板定义了两个类模板对象，分别为定义了两个类模板对象，分别为int型和型和char型，数组元素分别被初始化为型，数组元素分别被初始化为0和空和空格格程序运行结果为：程序运行结果为：Unsortedarrayis:Unsortedarrayis:8934324715817836638389343247158178366383Sortedarrayis:Sortedarrayis:1532343647637881838915323436476378818389Unsortedarrayis:Unsortedarrayis:C

29、WrYkJXZysCWrYkJXZysSortedarrayis:Sortedarrayis:CJWXYZkrsyCJWXYZkrsy本讲稿第十八页，共二十四页例例9.6使用缺省参数定义数组的类模板使用缺省参数定义数组的类模板#include#include template template class Arrayclass Array T*data;T*data;int size;int size;public:public:Array(int);Array(int);Array();Array();T&operator(int);T&operator(int);第第9 9章章 模板模板t

30、emplate template Array:Array(int n)Array:Array(int n)data=new Tsize=n;data=new Tsize=n;template template Array:Array()Array:Array()delete data;delete data;template template T&Array:operator(int i)T&Array:operator(int i)return datai;return datai;注意：函数模板不能定义缺省参数，而类模板却可以定义缺省参数。本讲稿第十九页，共二十四页例例9.6（续）（续）v

31、oidmain(void)voidmain(void)inti;inti;ArrayL1(10);ArrayL1(10);/等价于等价于ArrayL1(10)ArrayL1(10)ArrayL2(20);ArrayL2(20);for(i=0;i10;i+)for(i=0;i10;i+)L1i=i;L1i=i;for(i=0;i20;i+)for(i=0;i20;i+)L2i=A+i;L2i=A+i;for(i=0;i10;i+)for(i=0;i10;i+)coutL1i;coutL1i;coutendl;coutendl;for(i=0;i20;i+)for(i=0;i20;i+)cout

32、L2i;coutL2i;coutendl;coutendl;第第9 9章章 模板模板程序运行结果为：程序运行结果为：01234567890123456789ABCDEFGHIJKLMNOPQRSTABCDEFGHIJKLMNOPQRST本讲稿第二十页，共二十四页例9.79.7折半查找函数模板折半查找函数模板第第9 9章章 模板模板基本思想：对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。比如在如下数组中查找值为48的元素：本讲稿第二十一页，共二十四页例9.7（续一）tem

33、plate template int BinSearch(T list,int n,T key)int BinSearch(T list,int n,T key)int mid,low,high;int mid,low,high;T midvalue;T midvalue;low=0;low=0;high=n-1;high=n-1;while(low=high)while(low=high)/low=high/low=high表示整个数组尚未查找完表示整个数组尚未查找完 mid=(low+high)/2;mid=(low+high)/2;/求中间元素的下标求中间元素的下标midvalue=li

34、stmid;midvalue=listmid;/取出中间元素的值取出中间元素的值if(key=midvalue)if(key=midvalue)return mid;return mid;/若找到若找到,返回下标返回下标else if(key midvalue)else if(key midvalue)high=mid-1;high=mid-1;/若若keymidvaluekeymidvalue将查找范围缩小到数组的前一半将查找范围缩小到数组的前一半elseelselow=mid+1;low=mid+1;/否则将查找范围缩小到数组的后一半否则将查找范围缩小到数组的后一半 return-1;re

35、turn-1;/没有找到返回没有找到返回-1-1 第第9 9章章 模板模板本讲稿第二十二页，共二十四页例9.79.7（续二）（续二）#include#includetemplatetemplateintBinSearch(Tlist,intn,Tkey);intBinSearch(Tlist,intn,Tkey);voidmain()voidmain()inta10=2,3,7,12,16,35,67,68,90,98;inta10=2,3,7,12,16,35,67,68,90,98;charc11=abcdhijklm;charc11=abcdhijklm;charc1=f;charc1=

36、f;inti=BinSearch(a,10,35);inti=BinSearch(a,10,35);intj=BinSearch(a,10,36);intj=BinSearch(a,10,36);intk=BinSearch(c,10,f);intk=BinSearch(c,10,f);intl=BinSearch(c,10,k);intl=BinSearch(c,10,k);couti,j,k,lendl;couti,j,k,lendl;第第9 9章章 模板模板程序运行结果为：程序运行结果为：5,-1,-1,75,-1,-1,7 返 回本讲稿第二十三页，共二十四页谢谢！本讲稿第二十四页，共二十四页