模板与数据结构.ppt

《模板与数据结构.ppt》由会员分享，可在线阅读，更多相关《模板与数据结构.ppt（58页珍藏版）》请在优知文库上搜索。

1、第第6章章 模板与数据结构模板与数据结构模板的引入：模板的引入：6.1 模板模板增强代码的通用性，使之不受数据类型的限制。增强代码的通用性，使之不受数据类型的限制。模板的实现：模板的实现：将数据类型作为参数。将数据类型作为参数。模板模板(template)(template)函数模板函数模板(function )(function )类模板类模板(class )(class ) 功能：创建一个通用功能的函数，支持多种功能：创建一个通用功能的函数，支持多种不同形参，简化重载函数的函数体设计。不同形参，简化重载函数的函数体设计。6.1.1 函数模板及其应用函数模板及其应用函数模板定义函数模板定义：

2、templatetemplate 返回类型返回类型 函数名函数名( (形式参数表形式参数表) ) ； 例例. .找出三个数中的最大数，通过函数模板来实现。找出三个数中的最大数，通过函数模板来实现。#include #include using namespace std;using namespace std;templatetemplate T / /模板声明，其中模板声明，其中T T为类型参数为类型参数T T max( max(T T a, a,T T b, b,T T c) c) / /定义一个通用函数，用定义一个通用函数，用T T作虚拟的类型名作虚拟的类型名 if if(ba) a=b

3、;(ba) a=b; if if(ca) a=c;(ca) a=c; returnreturn a; a; intint main( ) main( ) int int i1=185, i2=-76, i3=567, i; i1=185, i2=-76, i3=567, i; double double d1=56.8, d2=90.2, d3=-314.7, d; d1=56.8, d2=90.2, d3=-314.7, d; longlong g1=6785, g2=-91245, g3=6734, g; g1=6785, g2=-91245, g3=6734, g; / /调用模板函数，

4、此时调用模板函数，此时T T被被intint取代，也可缺省取代，也可缺省 i=max i=max(i1,i2,i3); (i1,i2,i3); / /调用模板函数，此时调用模板函数，此时T T被被doubledouble取代取代 d=maxd=max(d1,d2,d3); (d1,d2,d3); / /调用模板函数，此时调用模板函数，此时T T被被longlong取代取代 g=maxg=max(g1,g2,g3); (g1,g2,g3); cout“i_max=“iendl; cout“i_max=“iendl; cout“f_max=“dendl; cout“f_max=“dendl; co

5、ut“g_max=“gendl; cout“g_max=“gy)?x:y; (xy)?x:y; intint min( ) min( ) returnreturn (xy)?x:y; (xy)?x:y; privateprivate: : intint x,y; x,y; ;6.1.2 类模板与线性表类模板与线性表若要比较两个浮若要比较两个浮点数大小呢？点数大小呢？类模板定义：类模板定义：templatetemplate classclass 类模板名类模板名 . . / /类体类体; ;类模板名类模板名 对象名对象名1 1，对象名，对象名n; n; / /可带参可带参数数templatete

6、mplate 返回类型返回类型 类模板名类模板名 :成员函数名成员函数名 ( (形参表形参表) ) / /成员函数体成员函数体 在类模板外定义成员函数，应采用以下形式：在类模板外定义成员函数，应采用以下形式：使用模板建立对象：使用模板建立对象： 用类模板实现：用类模板实现：templatetemplate / /虚拟类型虚拟类型numtypenumtypeclassclass Compare Compare / /类模板名为类模板名为CompareCompare publicpublic: : Compare( Compare(numtypenumtype a, a,numtypenumtyp

7、e b) b) x=a; y=b; x=a; y=b; numtypenumtype max( ) max( ) returnreturn (xy) ? x : y; (xy) ? x : y; numtypenumtype min( ) min( ) returnreturn (xy) ? x : y; (xy) ? x : y; privateprivate: : numtype numtype x,y; x,y; ;#include#include / /类模板应用举例类模板应用举例#include#include usingusing namespacenamespace std; s

8、td;classclass Student Student / /定义结构体类型定义结构体类型StudentStudent public: public:intint id; id; / /学号学号floatfloat gpa; gpa; / /平均分平均分 Student(Student(intint i=0, i=0,floatfloat g=0):id(i), gpa(g) g=0):id(i), gpa(g) ; ;templateclasstemplate / /类模板，实现对任意类型数据进行存取类模板，实现对任意类型数据进行存取classclass Store Store T T

9、item; item; / /存放任意类型数据存放任意类型数据intint Valued; Valued; / /标记标记itemitem是否已被存入内容是否已被存入内容 publicpublic: : Store(); Store(); / /默认形式的构造函数默认形式的构造函数T T GetElem(); GetElem(); / /提取数据函数提取数据函数voidvoid PutElem( PutElem(T T x); x); / /存入数据函数存入数据函数; ;templatetemplate StoreStore:Store( ):Valued(0) :Store( ):Value

10、d(0) templatetemplate T T Store Store:GetElem():GetElem() if if(Valued=0)(Valued=0) coutNo item present!endl; coutNo item present!endl; exitexit(1); (1); / /使程序完全退出，返回操作系统使程序完全退出，返回操作系统 returnreturn item; item; / /返回返回itemitem中存放的数据中存放的数据 templatetemplate voidvoid Store:PutElem( Store:PutElem(T T x)

11、x) Valued+; Valued+; / /将此置为将此置为tureture，表示，表示itemitem中已存入数值中已存入数值 item=x; item=x; / /将将x x值存入值存入itemitem voidvoid main() main() Student g(1000,23); Student g(1000,23); / /声明声明StudentStudent类型结构体变量，赋以初值类型结构体变量，赋以初值 StoreStore S1,S2; S1,S2; / /声明两个声明两个StoreStore类对象类对象 StoreStore S3; S3;/ /声明声明StoreSt

12、ore类对象类对象S3S3 StoreStore D; D;/ /声明声明StoreStore类对象类对象D D S1.PutElem(3); S1.PutElem(3); / /向对象向对象S1S1中存入数据中存入数据( (初始化对象初始化对象S1)S1) S2.PutElem(-7); S2.PutElem(-7); / /向对象向对象S2S2中存入数据中存入数据( (初始化对象初始化对象S2)S2) coutcoutS1.GetElem() S2.GetElem()endl; S1.GetElem() S2.GetElem()endl; /S1/S1和和S2S2的数据成员的数据成员 S3

13、.PutElem(g); S3.PutElem(g); / /向对象向对象S3S3中存入数据中存入数据 coutS3.GetElem().idendl; coutS3.GetElem().idendl; / /输出对象输出对象S3S3的数据成员的数据成员 cout“Retrieving object Dn”;cout“Retrieving object Dn”; coutD.GetElem()endl; coutD.GetElem()endl; / /输出对象输出对象D D的数据成员的数据成员 / /由于由于D D未初始化，在执行函数未初始化，在执行函数D.GetElem()D.GetElem

14、()过程中导致程序终止过程中导致程序终止 return return 0;0; 线性表线性表静态数组：静态数组：由编译器编译时分配内存，数组的长由编译器编译时分配内存，数组的长度不可改变。度不可改变。防止的溢出：防止的溢出：一般采用一般采用“大开小用大开小用”的方法，且的方法，且应在添加新数据时判断表是否满。应在添加新数据时判断表是否满。1 13 33 34 410109 96 65 58 87 72 21 16 62 21 19 92 27 711118 85 51 112121 10 013131 12 23 34 4 i i图图a a下标下标1 13 33 34 410109 96 65

15、 58 87 72 21 12 21 19 97 711118 85 51 112121 10 01313图图b b下标下标图图6.1 6.1 从表中删除一个数据从表中删除一个数据直接前驱直接前驱直接后继直接后继图图6.2 6.2 向表中插入一个数据向表中插入一个数据141431313 34 410109 96 65 58 87 7242416162 218189 927277 711118 85 51 1121211110 013135 54 43 32 2i i图图a a下标下标1 1272731313 34 410109 96 65 58 87 7242416162 218189 97

16、711115 511111 18 812121414x x0 01313图图b b下标下标【例例6.36.3】顺序表类模板顺序表类模板templatetemplate sizeclassclass seqlist seqlist T slistsize; T slistsize; / /存放顺序表的数组存放顺序表的数组 intint Maxsize; Maxsize; / /最大可容纳项数最大可容纳项数 intint last; last; / /已存表项的最后位置已存表项的最后位置publicpublic: : seqlist() last=-1; Maxsize=size; seqlist() last=-1; Maxsize=size; / /初始化为空表初始化为空表 intint Length() Length() constconst return return last+1; last+1; / /计算表长度计算表长度 intint Find(T & x) Find(T & x)constconst; ; / / 寻找寻找x x在表中位置在表中位置（下标）（下标） bool