C++语言程序设计(清华大学郑莉)09

第九章群体类和群体数据的组织清华大学郑莉C++语言程序设计C++语言程序设计清华大学郑莉2本章主要内容模板群体类群体数据的组织深度探索C++语言程序设计清华大学郑莉3第一部分：模板函数模板类模板C++语言程序设计清华大学郑莉4函数模板函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。定义方法：template模板参数表函数定义模板参数表的内容–类型参数：class（或typename）标识符–常量参数：类型说明符标识符–模板参数：template参数表class标识符函数模板C++语言程序设计清华大学郑莉5求绝对值函数的模板#includeiostreamusingnamespacestd;templatetypenameTTabs(Tx){returnx0?-x:x;}intmain(){intn=-5;doubled=-5.5;coutabs(n)endl;coutabs(d)endl;return0;}函数模板运行结果：55.5C++语言程序设计清华大学郑莉6求绝对值函数的模板分析编译器从调用abs()时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：intabs(intx){returnx0?–x:x;}函数模板C++语言程序设计清华大学郑莉7类模板的作用使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类模板C++语言程序设计清华大学郑莉8类模板的声明类模板：template模板参数表class类名{类成员声明}如果需要在类模板以外定义其成员函数，则要采用以下的形式：template模板参数表类型名类名模板参数标识符列表::函数名（参数表）类模板C++语言程序设计清华大学郑莉9例9-2类模板应用举例#includeiostream#includecstdlibusingnamespacestd;//结构体StudentstructStudent{intid;//学号floatgpa;//平均分};类模板templateclassTclassStore{//类模板：实现对任意类型数据进行存取private:Titem;//item用于存放任意类型的数据boolhaveValue;//haveValue标记item是否已被存入内容public:Store();//缺省形式（无形参）的构造函数T&getElem();//提取数据函数voidputElem(constT&x);//存入数据函数};//以下实现各成员函数。templateclassT//缺省构造函数的实现StoreT::Store():haveValue(false){}10templateclassT//提取数据函数的实现T&StoreT::getElem(){//如试图提取未初始化的数据，则终止程序if(!haveValue){coutNoitempresent!endl;exit(1);//使程序完全退出，返回到操作系统。}returnitem;//返回item中存放的数据}templateclassT//存入数据函数的实现voidStoreT::putElem(constT&x){//将haveValue置为true，表示item中已存入数值haveValue=true;item=x;//将x值存入item}11intmain(){Storeints1,s2;//实例类模板中的类型为整型s1.putElem(3);s2.putElem(-7);couts1.getElem()s2.getElem()endl;Studentg={1000,23};StoreStudents3;s3.putElem(g);coutThestudentidiss3.getElem().idendl;Storedoubled;coutRetrievingobjectD...;coutd.getElem()endl//由于d未经初始化,在执行函数D.getElement()过程中导致程序终止return0;}12C++语言程序设计清华大学郑莉13第二部分：群体数据线性群体–线性群体的概念–直接访问群体--数组类–顺序访问群体--链表类–栈类–队列类C++语言程序设计清华大学郑莉14群体的概念群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。C++语言程序设计清华大学郑莉15线性群体的概念线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。…第一个元素第二个元素第三个元素最后一个元素C++语言程序设计清华大学郑莉16数组静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。–缺点：大小在编译时就已经确定，在运行时无法修改。动态数组由一系列位置连续的，任意数量相同类型的元素组成。–优点：其元素个数可在程序运行时改变。vector就是用类模板实现的动态数组。动态数组类模板：例9-3（Array.h）直接访问的线性群体#ifndefARRAY_H#defineARRAY_H#includecasserttemplateclassT//数组类模板定义classArray{private:T*list;//用于存放动态分配的数组内存首地址intsize;//数组大小（元素个数）public:Array(intsz=50);//构造函数Array(constArrayT&a);//拷贝构造函数~Array();//析构函数ArrayT&operator=(constArrayT&rhs);//重载=“T&operator[](inti);//重载[]”constT&operator[](inti)const;operatorT*();//重载到T*类型的转换operatorconstT*()const;intgetSize()const;//取数组的大小voidresize(intsz);//修改数组的大小};17动态数组类模板程序C++语言程序设计清华大学郑莉18数组类模板模板的构造函数//构造函数templateclassTArrayT::Array(intsz){//sz为数组大小（元素个数），应当非负assert(sz=0);//将元素个数赋值给变量sizesize=sz;//动态分配size个T类型的元素空间list=newT[size];}直接访问的线性群体C++语言程序设计清华大学郑莉19数组类模板的拷贝构造函数//拷贝构造函数templateclassTArrayT::Array(constArrayT&a){//从对象x取得数组大小，并赋值给当前对象的成员size=a.size;//为对象申请内存并进行出错检查list=newT[size];//动态分配n个T类型的元素空间//从对象X复制数组元素到本对象for(inti=0;isize;i++)list[i]=a.list[i];}直接访问的线性群体C++语言程序设计清华大学郑莉20浅拷贝listsizeaa的数组元素占用的内存拷贝前listsizeaa的数组元素占用的内存拷贝后listsizebintmain(){Arrayinta(10);......Arrayintb(a);......}templateclassTArrayT::Array(constArrayT&x){size=x.size;list=x.list;}C++语言程序设计清华大学郑莉21深拷贝listsizeaa的数组元素占用的内存拷贝前listsizeaa的数组元素占用的内存拷贝后listsizebb的数组元素占用的内存C++语言程序设计清华大学郑莉22数组类模板的重载=运算符函数//重载“=”运算符templateclassTArrayT&ArrayT::operator=(constArrayT&rhs){if(&rhs!=this){if(size!=rhs.size){delete[]list;//删除数组原有内存size=rhs.size;//设置本对象的数组大小list=newT[size];//重新分配n个元素的内存}//从对象X复制数组元素到本对象for(inti=0;isize;i++)list[i]=rhs.list[i];}return*this;//返回当前对象的引用}直接访问的线性群体C++语言程序设计清华大学郑莉23数组类模板的重载下标操作符函数templateclassTT&ArrayT::operator[](intn){assert(n=0&&nsize);//越界检查returnlist[n];//返回下标为n的数组元素}templateclassTconstT&ArrayT::operator[](intn)const{assert(n=0&&nsize);//越界检查returnlist[n];//返回下标为n的数组元素}直接访问的线性群体C++语言程序设计清华大学郑莉24为什么有的函数返回引用如果一个函数的返回值是一个对象的值，就不应成为左值。如果返回值为引用。由于引用是对象的别名，通过引用当然可以改变对象的值。直接访问的线性群体C++语言程序设计清华大学郑莉25重载指针转换操作符templateclassTArrayT::operatorT*(){returnlist;//返回私有数组的首地址}templateclassTArrayT::operatorconstT*()const{returnlist;//返回私有数组的首地址}直接访问的线性群体C++语言程序设计清华大学郑莉26指针转换运算符的作用#includeiostreamusingnamespacestd;voidread(int*p,intn){for(inti=0;in;i++)cinp[i];}intmain(){inta[10];read(a,10);return0;}#includeArray.h#includeiostreamusingnamespacestd;voidread(int*p,intn){for(inti=0;in;i++)cinp[i];}intmain(){Arrayinta(10);read(a,10);return0;}直接访问的线性群体C++语言程序设计清华大学郑莉27Array类的应用例9-4求范围2~N中的质数，N在程序运行时由键盘输入。直接访问的线性群体#includeiostream#includeiomanip#includeArray.husingnamespacestd;intmain(){Arrayinta(10);//用来存放质数的数组，初始状态有10个元素。intn,count=0;coutEnteravalue=2asupperlimitforprimenumbers:;cinn;for(inti=2;i=n;i++){boolisPrime=true;for(intj=0;jcount;j++)if(i%a[j]==0){//若i被a[j]整除，说明i不是质数isPrime=false;br