c“加”“加”9群体类和群体数据的组织

AB第九章群体类和群体数据的组织C++语言程序设计2本章主要内容模板群体类群体数据的组织3第一部分—模板函数模板类模板4函数模板函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。声明方法：templatetypename标识符函数声明函数模板5求绝对值函数的模板#includeiostreamusingnamespacestd;templatetypenameTTabs(Tx){returnx0?-x:x;}intmain(){intn=-5;doubled=-5.5;coutabs(n)endl;coutabs(d)endl;}函数模板运行结果：55.56求绝对值函数的模板分析编译器从调用abs()时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：intabs(intx){returnx0?-x:x;}函数模板7类模板的作用使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类模板8类模板的声明类模板：template模板参数表class类名{类成员声明}如果需要在类模板以外定义其成员函数，则要采用以下的形式：template模板参数表类型名类名T::函数名（参数表）类模板9例9-2类模板应用举例#includeiostream#includecstdlibusingnamespacestd;//结构体StudentstructStudent{intid;//学号floatgpa;//平均分};类模板templateclassT//类模板：实现对任意类型数据进行存取classStore{private:Titem;//用于存放任意类型的数据inthaveValue;//用于标记item是否已被存入内容public:Store(void);//默认形式（无形参）的构造函数TGetElem(void);//提取数据函数voidPutElem(Tx);//存入数据函数};//默认形式构造函数的实现templateclassTStoreT::Store(void):haveValue(0){}10templateclassT//提取数据函数的实现TStoreT::GetElem(void){//如果试图提取未初始化的数据，则终止程序if(haveValue==0){coutNoitempresent!endl;exit(1);}returnitem;//返回item中存放的数据}templateclassT//存入数据函数的实现voidStoreT::PutElem(Tx){haveValue++;//将haveValue置为TRUE，表示item中已存入数值item=x;//将x值存入item}11intmain(){Studentg={1000,23};StoreintS1,S2;StoreStudentS3;StoredoubleD;S1.PutElem(3);S2.PutElem(-7);coutS1.GetElem()S2.GetElem()endl;S3.PutElem(g);coutThestudentidisS3.GetElem().idendl;coutRetrievingobjectD;coutD.GetElem()endl;//输出对象D的数据成员//由于D未经初始化,在执行函数D.GetElement()时出错}1213第二部分—群体数据线性群体–线性群体的概念–直接访问群体--数组类–顺序访问群体--链表类–栈类–队列类14群体的概念群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。15线性群体的概念线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。…第一个元素第二个元素第三个元素最后一个元素16数组静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。–缺点：大小在编译时就已经确定，在运行时无法修改。动态数组由一系列位置连续的，任意数量相同类型的元素组成。–优点：其元素个数可在程序运行时改变。动态数组类模板：例9-3（9_3.h）直接访问的线性群体#ifndefARRAY_CLASS#defineARRAY_CLASSusingnamespacestd;#includeiostream#includecstdlib#ifndefNULLconstintNULL=0;#endif//NULLenumErrorType{invalidArraySize,memoryAllocationError,indexOutOfRange};char*errorMsg[]={Invalidarraysize,Memoryallocationerror,Invalidindex:};动态数组类模板程序17templateclassTclassArray{private:T*alist;intsize;voidError(ErrorTypeerror,intbadIndex=0)const;public:Array(intsz=50);Array(constArrayT&A);~Array(void);ArrayT&operator=(constArrayT&rhs);T&operator[](inti);operatorT*(void)const;intListSize(void)const;voidResize(intsz);};1819数组类模板的构造函数//构造函数templateclassTArrayT::Array(intsz){if(sz=0)//sz为数组大小（元素个数），若小于0，则输出错误信息Error(invalidArraySize);size=sz;//将元素个数赋值给变量sizealist=newT[size];//动态分配size个T类型的元素空间if(alist==NULL)//如果分配内存不成功，输出错误信息Error(memoryAllocationError);}直接访问的线性群体20数组类的拷贝构造函数templateclassTArrayT::Array(constArrayT&X){intn=X.size;size=n;alist=newT[n];if(alist==NULL)Error(memoryAllocationError);T*srcptr=X.alist;//X.alist是对象X的数组首地址T*destptr=alist;//alist是本对象中的数组首地址while(n--)//逐个复制数组元素*destptr++=*srcptr++;}直接访问的线性群体21浅拷贝alistsizeAA的数组元素占用的内存拷贝前alistsizeAA的数组元素占用的内存拷贝后alistsizeBintmain(){ArrayintA(10);......ArrayintB(A);......}templateclassTArrayT::Array(constArrayT&X){size=X.size;alist=X.alist;}22深拷贝alistsizeAA的数组元素占用的内存拷贝前alistsizeAA的数组元素占用的内存拷贝后alistsizeBB的数组元素占用的内存23数组类的重载=运算符函数templateclassTArrayT&ArrayT::operator=(constArrayT&rhs){intn=rhs.size;if(size!=n){delete[]alist;alist=newT[n];if(alist==NULL)Error(memoryAllocationError);size=n;}T*destptr=alist;T*srcptr=rhs.alist;while(n--)*destptr++=*srcptr++;return*this;}直接访问的线性群体24数组类的重载下标操作符函数templateclassTT&ArrayT::operator[](intn){//检查下标是否越界if(n0||nsize-1)Error(indexOutOfRange,n);//返回下标为n的数组元素returnalist[n];}直接访问的线性群体25为什么有的函数返回引用如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成为左值。如果返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变对象的值。直接访问的线性群体26重载指针转换操作符templateclassTArrayT::operatorT*(void)const{//返回当前对象中私有数组的首地址returnalist;}直接访问的线性群体27指针转换运算符的作用#includeiostreamusingnamespacestd;intmain(){inta[10];voidread(int*p,intn);read(a,10);}voidread(int*p,intn){for(inti=0;in;i++)cinp[i];}intmain(){Arrayinta(10);voidread(int*p,n);read(a,10);}voidread(int*p,intn){for(inti=0;in;i++)cinp[i];}直接访问的线性群体28Array类的应用例9-4求范围2~N中的质数，N在程序运行时由键盘输入。直接访问的线性群体#includeiostream#includeiomanip#include9_3.husingnamespacestd;intmain(){ArrayintA(10);intn;intprimecount=0,i,j;coutEnteravalue=2asupperlimitforprimenumbers:;cinn;A[primecount++]=2;//2是一个质数for(i=3;in;i++){if(primecount==A.ListSize())A.Resize(primecount+10);if(i%2==0)continue;j=3;while(j=i/2&&i%j!=0)j+=2;if(ji/2)A[primecount++]=i;}for(i=0;iprimecount;i++){coutsetw(5)A[i];if((i+1)%10==0)coutendl;}coutendl;}2930链表链表是一种动态数据结构，可以用来表示顺序访问的线性群体。链表是由系列结点组成的，结点可以在运行时动态生成。每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。顺序访问的线性群体31单链表data1data2data3datanNULL…headrear顺序访问的线性群体32单链表的结点类模板templateclassTclassNode{private:NodeT*next;public:Tdata;Node(constT&item,NodeT*ptr