面向对象程序设计（C++）：第九章 数组类与群体数据的组织

第九章群体类和群体数据的组织本章主要内容模板群体类群体数据的组织第一部分—模板函数模板类模板9.1函数模板1、函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。2、声明方法：template<typename

标识符>函数声明案例：求绝对值函数的模板#include<iostream>usingnamespacestd;template<typenameT>Tabs(Tx){returnx<0?-x:x;}intmain(){intn=-5;doubled=-5.5;cout<<abs(n)<<endl;cout<<abs(d)<<endl;}运行结果：55.5案例：求绝对值函数的模板分析（1）编译器从调用abs()时实参的类型，推导出函数模板的参数类型。例如，对于调用表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。（2）当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：

intabs(intx)

{returnx<0?-x:x;}1、类模板的作用使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的形式参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。9.2类模板2、类模板的声明类模板语法格式：template<classT>class类名{类成员声明}

9.2类模板2、类模板的声明如果需要在类模板以外定义其成员函数，则要采用以下的形式：template<class

模板参数表>类型名类名<T>::函数名（参数表）{}9.2类模板例9-2类模板应用举例#include<iostream>#include<cstdlib>usingnamespacestd;//结构体StudentstructStudent{intid;//学号

floatgpa;//平均分};template<classT>//类模板：实现对任意类型数据进行存取classStore{private:Titem;//成员变量类型待定

inthaveValue;//用于标记item是否已被存入内容

public:Store(void);//默认形式（无形参）的构造函数

TGetElem(void);//提取数据函数,返回值类型待定

voidPutElem(Tx);//存入数据函数，形参类型待定};//默认形式构造函数的实现template<classT>Store<T>::Store(void):haveValue(0){}11例9-2类模板应用举例template<classT>//提取数据函数的实现TStore<T>::GetElem(void){//如果试图提取未初始化的数据，则终止程序

if(haveValue==0){cout<<"Noitempresent!"<<endl;exit(1);}returnitem;//返回item中存放的数据}12例9-2类模板应用举例template<classT>//存入数据函数的实现voidStore<T>::PutElem(Tx){haveValue++;//将haveValue置为TRUE，表示item中已存入数值

item=x;//将x值存入item}13例9-2类模板应用举例intmain(){Studentg={1000,23}; Store<int>S1,S2;Store<Student>S3;Store<double>D;

S1.PutElem(3);S2.PutElem(-7);cout<<S1.GetElem()<<""<<S2.GetElem()<<endl;S3.PutElem(g);cout<<"Thestudentidis"<<S3.GetElem().id<<endl;cout<<"RetrievingobjectD"; cout<<D.GetElem()<<endl;//输出对象D的数据成员

//由于D未经初始化,在执行函数D.GetElement()时出错}14例9-2类模板应用举例模版的本质(1)函数模版从功能上来说，和函数重载的功能相似(2)与函数重载区别

函数重载在代码编写阶段需要写出多个同名的函数，而模版是在程序编译阶段才将模版转化成函数重载的形式。从而使得程序员不要编写多个重名函数，减少了程序员的代码编写量。

第二部分—群体数据9.3群体1、群体概念群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。1、线性群体的概念2、直接访问群体--数组类3、顺序访问群体--链表类4、栈类5、队列类9.3.1线性群体9.3.1线性群体1、线性群体的概念线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。…第一个元素第二个元素第三个元素最后一个元素2、数组（1）静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。（2）动态数组由一系列位置连续的，任意数量相同类型的元素组成。

动态数组类模板：例9-3（9_3.h）（3）动态数组类模板程序212、数组浅拷贝alistsizeAA的数组元素占用的内存拷贝前alistsizeAA的数组元素占用的内存拷贝后alistsizeBintmain(){Array<int>A(10);......Array<int>B(A);......}template<classT>Array<T>::Array(constArray<T>&X){size=X.size;alist=X.alist;}深拷贝alistsizeAA的数组元素占用的内存拷贝前alistsizeAA的数组元素占用的内存拷贝后alistsizeBB的数组元素占用的内存为什么有的函数返回引用（1）如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成为左值。（2）如果返回值为引用，由于引用是对象的别名，所以通过引用当然可以改变对象的值。指针转换运算符的作用#include<iostream>usingnamespacestd;intmain(){inta[10];voidread(int*p,intn);read(a,10);}voidread(int*p,intn){for(inti=0;i<n;i++)cin>>p[i];}intmain(){Array<int>a(10);voidread(int*p,intn);read(a,10);}//调用指针类型强制转换voidread(int*p,intn){for(inti=0;i<n;i++)cin>>p[i];}Array类的应用例9-4求范围2~N中的质数，N在程序运行时由键盘输入。3、链表（1）链表是一种动态数据结构，可以用来表示顺序访问的线性群体。（2）每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。单链表data1data2data3datanNULL…headrear3、链表单链表的结点类模板template<classT>classNode{private:Node<T>*next;//链表中当前结点

public:Tdata;Node(constT&item,Node<T>*ptrnext=NULL);voidInsertAfter(Node<T>*p);Node<T>*DeleteAfter(void);Node<T>*NextNode(void)const;};在结点之后插入一个结点data1data2…pdata…template<classT>voidNode<T>::InsertAfter(Node<T>*p){//p节点指针域指向当前节点的后继节点

p->next=next->next;next->next=p;//当前节点的指针域指向p}next

删除结点之后的结点data1data2data3……Node<T>*Node<T>::DeleteAfter(void){Node<T>*tempPtr=next;if(next==NULL)returnNULL;next=tempPtr->next;returntempPtr;}tempPtr（3）基本操作生成结点插入结点查找结点删除结点遍历链表清空链表3、链表（4）链表类模板(例9-6)3、链表（4）链表类应用举例(例9-7)3、链表4、特殊的线性群体——栈栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。an┆a2a1入栈出栈栈顶栈底（1）栈的基本操作初始化入栈出栈清空栈访问栈顶元素检测栈的状态（满、空）4、特殊的线性群体——栈栈的应用例9.9一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。4、特殊的线性群体——栈5、特殊的线性群体——队列队列是只能向一端添加元素，从另一端删除元素的线性群体a1a2an-1an……队头队尾入队出队a0循环队列在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。1234……m-1m-2m-30amam+1am+2a3队头队尾a4am-2am-3am-1队满状态元素个数=m1234……m-1m-2m-30队尾队头队空状态元素个数=0队尾1234……m-1m-2m-30a0a1a2a3队头一般状态41循环队列例9-10队列类模板#ifndefQUEUE_CLASS#defineQUEUE_CLASS#include<iostream>#include<cstdlib>usingnamespacestd;constintMaxQSize=50;template<classT>classQueue{private:intfront,rear,count;Tqlist[MaxQSize];public:Queue(void);voidQInsert(constT&item);TQDelete(void);voidClearQueue(void);TQFront(void)const;intQLength(void)const;intQEmpty(void)const;intQFull(void)const;};//成员函数的实现略第三部分—群体数据的组织插入排序选择排序交换排序顺序查找折半查找9.4.1排序（sorting）1、排序是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。2、排序需要完成两种基本操作：（1）比较两个数的大小（2）调整元素在序列中的位置9.4.2内部排序方法1、插入排序2、选择排序3、交换排序1、插入排序（1）思想：

每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。（2）直接插入排序例9-11直接插入排序函数模板（9_11.h）1、插入排序template<classT>voidInsertionSort(TA[],intn){inti,j;Ttemp;for(i=1;i<n;i++){j=i;temp=A[i];while(j>0&&temp<A[j-1]){A[j]=A[j-1];j--;}A[j]=