第九章群体类和群体数据的组织.

第九章群体类和群体数据的组织C++语言程序设计说明目录群体的概念群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。…第一个元素第二个元素第三个元素最后一个元素群体类直接访问群体--数组类顺序访问群体--链表类栈类队列类群体数据的组织插入排序选择排序交换排序顺序查找折半查找5本章主要内容模板群体类群体数据的组织小结与复习建议9.1模板C++最重要的特性之一就是代码重用，为了实现代码重用，代码必须具有通用性。通用代码需要不受数据类型的影响，并且可以自动适应数据类型的变化。这种程序设计类型称为参数化程序设计。模板是C++支持参数化程序设计的工具，通过它可以实现参数化多态性。所谓参数化多态性，就是将程序所处理的对象的类型参数化，使得一段程序可以用于处理多种不同类型的对象。函数模板类模板9.1.1函数模板函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。定义方法：template模板参数表函数定义templatetypenameTTabs(Tx){returnx0?-x:x;}8其中：template为模板关键字。模板参数表中的类型为参数化类型，也称可变类型，类型名为class(或typename)；模板参数表中的类型也可包含普通类型。求绝对值函数的模板#includeiostreamusingnamespacestd;templatetypenameTTabs(Tx){returnx0?-x:x;}intmain(){intn=-5;doubled=-5.5;coutabs(n)endl;coutabs(d)endl;return0;}运行结果：55.5求绝对值函数的模板分析编译器从调用abs()时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：intabs(intx){returnx0?–x:x;}函数模板的重载C++规定：函数模板可以重载。它既可以用函数模板重载，也可以用普通函数重载。之所以允许重载是因为函数模板的参数T在实例化时实参类型无隐式转换功能。下面是函数模板重载的实例：templateclassT//求两个同类型T的变量中的最大者Tmax(Tx,Ty){return(xy)?x:y;}函数模板的重载C++规定：函数模板可以重载。它既可以用函数模板重载，也可以用普通函数重载。之所以允许重载是因为函数模板的参数T在实例化时实参类型无隐式转换功能。下面是函数模板重载的实例：templateclassT//求两个同类型T的变量中的最大者Tmax(Tx,Ty){return(xy)?x:y;}templateclassT//重载max函数模板，求三个同类型T的变量中的最大者Tmax(Tx,Ty,Tz){Tt;t=(xy)?x:y;return(tz)?t:z;}在下面的函数调用中：voidfun(inti,charc,floatf){coutmax(i,i);//正确!coutmax(c,c);//正确!coutmax(i,c);//错误!采用函数模板生成的模板函数虚实结合时无隐式类型转换功能coutmax(f,i);//错误!采用函数模板生成的模板函数虚实结合时无隐式类型转换功能//…}上例代码中的max(i,c)和max(f,i)，由于模板函数在调用时其参数类型不同，所以编译器报错。欲解决上述问题，可用一普通函数重载函数模板，此时，只需声明该普通函数的接口即可。请看下述示例代码：templateclassT//函数模板的定义Tmax(Tx,Ty){return(xy)?x:y;}doublemax(double,double);//重载上述函数模板，重载时只需给出函数接口//测试函数voidmain(){intx=3,y=4;longl=5;doublea=1.1,b=3.4;coutmax(x,y)endl;//调用模板函数，模板参数类型为intcoutmax(a,b)endl;//调用模板函数，模板参数类型为doublecoutmax(l,a)endl;//调用重载的模板函数，虚实结合时类型自动进行隐式转换//…}在使用上述templateclassTTmax(Tx,Ty)函数模板时，若模板参数的类型为char*，则此时模板函数为char*max(char*x,char*y){return(xy)?(x):(y);//该语句为何语义？}该函数的作用是比较两个字符串指针，而不是比较两个指针所指向的字符串的内容，这与我们所定义的函数模板的语义相违背。因此，此时须提供一个可以替换该函数模板实例的函数，用来替换的函数称为特定的模板函数，即：char*max(char*c1,char*c2){return(strcmp(c1,c2))?(c1):(c2);}9.1.2类模板的作用使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类模板：template模板参数表class类名{类成员声明}如果需要在类模板以外定义其成员函数，则要采用以下的形式：template模板参数表类型名类名模板参数标识符列表::函数名(参数表)类模板的声明templateclassTclassStoreT&StoreT::getElem()例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){}19templateclassT//提取数据函数的实现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}intmain(){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;}9.2群体类线性群体–群体的概念–直接访问群体--数组类–顺序访问群体--链表类–栈类–队列类9.2.1群体的概念群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。线性群体的概念线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。…第一个元素第二个元素第三个元素最后一个元素9.2.2数组静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。–缺点：大小在编译时就已经确定，在运行时无法修改。动态数组由一系列位置连续的，任意数量相同类型的元素组成。–优点：其元素个数可在程序运行时改变。动态数组类模板：例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);//修改数组的大小};26数组类模板的构造函数//构造函数templateclassTArrayT::Array(intsz){//sz为数组大小（元素个数），应当非负//将元素个数赋值给变量sizesize=sz;//动态分配size个T类型的元素空间list=newT[size];}数组类模板的拷贝构造函数//拷贝构造函数templateclassTArrayT::Array(constArrayT&a){//从对象a取得数组大小，并赋值给当前对象的成员size=a.size;//为对象申请内存并进行出错检查list=newT[size];//动态分配n个T类型的元素空间//从对象X复制数组元素到本对象for(inti=0;isize;i++)list[i]=a.list[i];}浅拷贝listsizeaa的数组元素占用的内存拷贝前listsizeaa的数组元素占用的内存拷贝后listsizebintmain(){Arrayinta(10);......Arrayintb(a);......}templateclassTArrayT::Array(constArrayT&x){size=x.size;list=x.list;}templateclassTArrayT::Array(constArrayT&a){size=a.size;list=newT[size];for(inti=0;isize;i++)list[i]=a.list[i];}深拷贝listsizeaa的数组元素占用的内存拷贝前listsizeaa的数组元素占用的内存拷贝后listsizebb的数组元素占用的内存数组类模板的重载=