C++语言程序设计(清华大学郑莉) (9)(精品).ppt

第九章第九章 群体类群体类和群体数据的组织和群体数据的组织清华大学清华大学 郑郑 莉莉C+语言程序设计C+语言程序设计清华大学 郑莉本章主要内容本章主要内容l模板模板l群体类群体类l群体数据的组织群体数据的组织2C+语言程序设计清华大学 郑莉第一部分：第一部分：模板模板l函数模板函数模板l类模板类模板3C+语言程序设计清华大学 郑莉函数模板函数模板l函数模板可以用来创建一个通用功能函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。步简化重载函数的函数体设计。l声明方法：声明方法：template 函数声明 函 数 模 板4C+语言程序设计清华大学 郑莉求绝对值函数的模板求绝对值函数的模板#include#include using namespace std;using namespace std;templatetemplate T T abs(abs(T T x)x)return x0?-x:x;return x0?-x:x;intint main()main()intint n=-5;n=-5;double d=-5.5;double d=-5.5;coutcoutabs(abs(n n)endlendl;coutcoutabs(abs(d d)endlendl;函 数 模 板运行结果：运行结果：55.55C+语言程序设计清华大学 郑莉求绝对值函数的模板分析求绝对值函数的模板分析l编译器从调用编译器从调用abs()时实参的类型，推时实参的类型，推导出函数模板的类型参数。例如，对导出函数模板的类型参数。例如，对于调用表达式于调用表达式abs(n)，由于实参，由于实参n为为int型，所以推导出模板中类型参数型，所以推导出模板中类型参数T为为int。l当类型参数的含义确定后，编译器将当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：以函数模板为样板，生成一个函数：int abs(int x)return x0?-x:x;函 数 模 板6C+语言程序设计清华大学 郑莉类模板的作用类模板的作用使用类模板使用户可以为类声明一使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类型的和用户自定义类型）。类 模 板7C+语言程序设计清华大学 郑莉类模板的声明类模板的声明l类模板：类模板：template class 类名类成员声明l如果需要在类模板以外定义其成员如果需要在类模板以外定义其成员函数，则要采用以下的形式：函数，则要采用以下的形式：template 类型名 类名:函数名（参数表）类 模 板8C+语言程序设计清华大学 郑莉例例9-2 类模板应用举例类模板应用举例#include#include#include#include using namespace std;using namespace std;/结构体结构体StudentStudentstructstruct Student Student intint id;/id;/学号学号 float float gpagpa;/;/平均分平均分;类 模 板9template template /类模板：实现对任意类型数据进行存取类模板：实现对任意类型数据进行存取class Storeclass Store private:private:T item;/T item;/用于存放任意类型的数据用于存放任意类型的数据 intint haveValuehaveValue;/;/用于标记用于标记itemitem是否已被存入内容是否已被存入内容 public:public:Store(voidStore(void);/);/默认形式（无形参）的构造函数默认形式（无形参）的构造函数 GetElem(voidGetElem(void);/);/提取数据函数提取数据函数 void void PutElem(TPutElem(T x);/x);/存入数据函数存入数据函数;/默认形式构造函数的实现默认形式构造函数的实现template template Store:Store(void):haveValue(0)Store:Store(void):haveValue(0)1010template /template /提取数据函数的实现提取数据函数的实现T Store:T Store:GetElem(voidGetElem(void)/如果试图提取未初始化的数据，则终止程序如果试图提取未初始化的数据，则终止程序 if(if(haveValuehaveValue=0)=0)coutcout No item present!No item present!endlendl;exit(1);exit(1);return item;/return item;/返回返回itemitem中存放的数据中存放的数据 template /template /存入数据函数的实现存入数据函数的实现 void Store:void Store:PutElem(TPutElem(T x)x)/将将haveValuehaveValue 置为置为 TRUETRUE，表示，表示itemitem中已存入数值中已存入数值 haveValuehaveValue+;+;item=x;/item=x;/将将x x值存入值存入itemitem 1111intint main()main()Student g=1000,23;Student g=1000,23;Store Store S1,S2;S1,S2;Store S3;Store S3;Store D;Store D;S1.PutElem(3);S1.PutElem(3);S2.PutElem(-7);S2.PutElem(-7);coutcout S1.GetElem()S1.GetElem()S2.GetElem()S2.GetElem()endlendl;S3.PutElem(g);S3.PutElem(g);coutcout The student id is The student id is S3.GetElem().id S3.GetElem().idendlendl;coutcout Retrieving object D ;Retrieving object D ;coutcout D.GetElemD.GetElem()()endlendl;/;/输出对象输出对象D D的数据成员的数据成员 /由于由于D D未经初始化未经初始化,在执行函数在执行函数D.GetElementD.GetElement()()时出错时出错 1212C+语言程序设计清华大学 郑莉第二部分：第二部分：群群体数据体数据l线性群体线性群体线性群体的概念直接访问群体-数组类顺序访问群体-链表类栈类队列类13C+语言程序设计清华大学 郑莉群体的概念群体的概念群体群体是指由多个数据元素组成的集是指由多个数据元素组成的集合体。群体可以分为两个大类：合体。群体可以分为两个大类：线性群线性群体体和和非线性群体非线性群体。线性群体中的元素按位置排列有序，线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元非线性群体不用位置顺序来标识元素。素。14C+语言程序设计清华大学 郑莉线性群体的概念线性群体的概念线性群体中的元素次序与其位置关线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照系是对应的。在线性群体中，又可按照访问元素的不同方法分为访问元素的不同方法分为直接访问直接访问、顺顺序访问序访问和和索引访问索引访问。在本章我们只介绍直接访问和顺序在本章我们只介绍直接访问和顺序访问。访问。第一个元素第二个元素第三个元素最后一个元素15C+语言程序设计清华大学 郑莉数组数组l静态数组是具有固定元素个数的群体，其静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。中的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修改。l动态数组由一系列位置连续的，任意数量动态数组由一系列位置连续的，任意数量相同类型的元素组成。相同类型的元素组成。优点：其元素个数可在程序运行时改变。l动态数组类模板：例动态数组类模板：例9-3（9_3.h）直接访问的线性群体16#ifndefifndef ARRAY_CLASS ARRAY_CLASS#define ARRAY_CLASS#define ARRAY_CLASSusing namespace std;using namespace std;#include#include#include#include#ifndefifndef NULL NULLconst const intint NULL=0;NULL=0;#endifendif /NULL /NULLenumenum ErrorTypeErrorType invalidArraySizeinvalidArraySize,memoryAllocationErrormemoryAllocationError,indexOutOfRangeindexOutOfRange;char*char*errorMsgerrorMsg=Invalid array size,Memory allocation error,Invalid array size,Memory allocation error,Invalid index:;Invalid index:;动态数组类模板程序1717template template class Arrayclass Array private:private:T*T*alistalist;intint size;size;void void Error(ErrorTypeError(ErrorType error,interror,int badIndexbadIndex=0)const;=0)const;public:public:ArrayArray(int(int szsz=50);=50);ArrayArray(const(const Array&A);Array&A);ArrayArray(void);(void);Array&Array&operator=operator=(const (const Array&Array&rhsrhs););T&T&operatoroperator(int(int i);i);operator operator T T*(void)const;(void)const;intint ListSizeListSize(void(void)const;)const;void void ResizeResize(int(int szsz););1818C+语言程序设计清华大学 郑莉数组类模板的构造函数数组类模板的构造函数/构造函数构造函数template template Array:Array:ArrayArray(int(int szsz)if(if(szsz=0)=0)/sz/sz为数组大小（元素个数），若小于为数组大小（元素个数），若小于0 0则输出错误信息则输出错误信息 Error(invalidArraySizeError(invalidArraySize););size=size=szsz;/将元素个数赋值给变量将元素个数赋值给变量sizesize alistalist=new=new TsizeTsize;/动态分配动态分配sizesize个个T T类型的元素空间类型的元素空间 if(if(alistalist=NULL)=NULL)/如果分配内存不成功，输出错误信息如果分配内存不成功，输出错误信息 Error(memoryAllocationErrorError(memoryAllocationError););直接访问的线性群体19C+语言程序设计清华大学 郑莉数组类的拷贝构造函数数组类的拷贝构造函数template template Array:Array:ArrayArray(const Array&X)(const Array&X)intint n=n=X.sizeX.size;size=n;size=n;alistalist=new Tn;=new Tn;if(if(alistalist=NULL)=NULL)Error(memoryAllocationErrorError(memoryAllocationError););T*T*srcptrsrcptr=X.alistX.alist;/X.alistX.alist是对象是对象X X的数组首地址的数组首地址 T*T*destptrdestptr=alistalist;/alistalist是本对象中的数组首地址是本对象中的数组首地址 while(nwhile(n-)-)/逐个复制数组元素逐个复制数组元素 *destptrdestptr+=*+=*srcptrsrcptr+;+;直接访问的线性群体20C+语言程序设计清华大学 郑莉浅拷贝浅拷贝 alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBintint main()main()Array Array A(10);A(10);.Array Array B(A);B(A);.template template Array:Array(Array:Array(const Array&X)const Array&X)size=X.size;size=X.size;alistalist=X.alistX.alist;21C+语言程序设计清华大学 郑莉深拷贝深拷贝 alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBB的数组元素占用的内存22C+语言程序设计清华大学 郑莉数组类的重载数组类的重载=运算符函数运算符函数template template Array&Array:Array&Array:operator=operator=(const Array&(const Array&rhsrhs)intint n=n=rhs.sizerhs.size;if(size!=n)if(size!=n)delete delete alistalist;alistalist=new Tn;=new Tn;if(if(alistalist=NULL)=NULL)Error(memoryAllocationErrorError(memoryAllocationError););size=n;size=n;T*T*destptrdestptr=alistalist;T*T*srcptrsrcptr=rhs.alistrhs.alist;while(n-)while(n-)*destptrdestptr+=*+=*srcptrsrcptr+;+;return*this;return*this;直接访问的线性群体23C+语言程序设计清华大学 郑莉数组类的重载下标操作符函数数组类的重载下标操作符函数template template T&Array:T&Array:operatoroperator(intint n)n)/检查下标是否越界检查下标是否越界 if(n size-1)if(n size-1)Error(indexOutOfRange,nError(indexOutOfRange,n););/返回下标为返回下标为n n的数组元素的数组元素 return return alistnalistn;直接访问的线性群体24C+语言程序设计清华大学 郑莉为什么有的函数返回引用为什么有的函数返回引用l如果一个函数的返回值是一个对象的如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成值，它就被认为是一个常量，不能成为左值。为左值。l如果返回值为引用。由于引用是对象如果返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变的别名，所以通过引用当然可以改变对象的值。对象的值。直接访问的线性群体25C+语言程序设计清华大学 郑莉重载指针转换操作符重载指针转换操作符template template Array:operator T*(void)constArray:operator T*(void)const /返回当前对象中私有数组的首地址返回当前对象中私有数组的首地址 return return alistalist;直接访问的线性群体26C+语言程序设计清华大学 郑莉指针转换运算符的作用指针转换运算符的作用#include#include using namespace std;using namespace std;intint main()main()intint a10;a10;void void read(read(intint*p*p,intint n);n);read(read(a a,10);,10);void void read(read(intint*p*p,intint n)n)for(for(intint i=0;in;i+)i=0;ipi;pi;intint main()main()ArrayArray a(10);a(10);void void read(read(intint*p*p,n);,n);read(read(a a,10);,10);void void read(read(intint*p*p,intint n)n)for(for(intint i=0;in;i+)i=0;ipi;pi;直接访问的线性群体27C+语言程序设计清华大学 郑莉Array类的应用类的应用l例例9-4求范围求范围2N中的质数，中的质数，N在程序在程序运行时由键盘输入。运行时由键盘输入。直接访问的线性群体28#include#include#include#include#include 9_3.h#include 9_3.husing namespace std;using namespace std;intint main()main()Array Array A(10);A(10);intint n;n;intint primecountprimecount=0,i,j;=0,i,j;coutcout=2 as upper limit for prime numbers:;=2 as upper limit for prime numbers:;cincin n;n;AprimecountAprimecount+=2;/2+=2;/2是一个质数是一个质数 for(ifor(i=3;i n;i+)=3;i n;i+)if(if(primecountprimecount=A.ListSizeA.ListSize()()A.Resize(primecountA.Resize(primecount+10);+10);if(i%2=0)continue;if(i%2=0)continue;j=3;j=3;while(j=i/2&i%j!=0)j+=2;while(j i/2)if(j i/2)AprimecountAprimecount+=i;+=i;for(i=0;i for(i=0;i primecountprimecount;i+);i+)coutcout setw(5)setw(5)AiAi;if(i+1)%10=0)if(i+1)%10=0)coutcout endlendl;coutcout endlendl;2929C+语言程序设计清华大学 郑莉链表链表l链表是一种动态数据结构，可以用来链表是一种动态数据结构，可以用来表示顺序访问的线性群体。表示顺序访问的线性群体。l链表是由系列链表是由系列结点结点组成的，结点可以组成的，结点可以在运行时动态生成。在运行时动态生成。l每一个结点包括每一个结点包括数据域数据域和指向链表中和指向链表中下一个结点的下一个结点的指针指针（即下一个结点的（即下一个结点的地址）。如果链表每个结点中只有一地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称个指向后继结点的指针，则该链表称为单链表。为单链表。顺序访问的线性群体30C+语言程序设计清华大学 郑莉单链表单链表 data1 data1 data2 data2 data3 data3 datandatan NULL NULLheadheadrearrear顺序访问的线性群体31C+语言程序设计清华大学 郑莉单链表的结点类模板单链表的结点类模板template template class Nodeclass Node private:private:Node*next;Node*next;public:public:T data;T data;Node(constNode(const T&item,Node*T&item,Node*ptrnextptrnext=NULL);=NULL);void void InsertAfter(NodeInsertAfter(Node*p);*p);Node*Node*DeleteAfter(voidDeleteAfter(void););Node*Node*NextNode(voidNextNode(void)const;)const;顺序访问的线性群体32C+语言程序设计清华大学 郑莉在结点之后插入一个结点在结点之后插入一个结点 data1 data2 p datatemplate template void Node:void Node:InsertAfterInsertAfter(Node(Node*p)*p)/p /p节点指针域指向当前节点的后继节点节点指针域指向当前节点的后继节点 p-next=next;p-next=next;next=p;/next=p;/当前节点的指针域指向当前节点的指针域指向p p 顺序访问的线性群体33C+语言程序设计清华大学 郑莉 删除结点之后的结点删除结点之后的结点顺序访问的线性群体 data1 data2 data3Node*Node:Node*Node:DeleteAfter(voidDeleteAfter(void)Node*Node*tempPtrtempPtr=next;=next;if(next=NULL)if(next=NULL)return NULL;return NULL;next=next=tempPtrtempPtr-next;-next;return return tempPtrtempPtr;tempPtr34C+语言程序设计清华大学 郑莉链表的基本操作链表的基本操作l生成结点生成结点l插入结点插入结点l查找结点查找结点l删除结点删除结点l遍历链表遍历链表l清空链表清空链表顺序访问的线性群体35C+语言程序设计清华大学 郑莉链表类模板链表类模板(例例9-6)顺序访问的线性群体/9_6.h/9_6.h#ifndefifndef LINKEDLIST_CLASS LINKEDLIST_CLASS#define LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include#include#include#include using namespace std;using namespace std;#ifndefifndef NULL NULLconst const intint NULL=0;NULL=0;#endifendif /NULL /NULL#include 9_5.h#include 9_5.htemplate template class class LinkedListLinkedListprivate:private:Node*front,*rear;Node*front,*rear;Node*Node*prevPtrprevPtr,*,*currPtrcurrPtr;intint size;size;intint position;position;Node*Node*GetNode(constGetNode(const T&item,T&item,Node*Node*ptrNextptrNext=NULL);=NULL);void void FreeNode(NodeFreeNode(Node*p);*p);void void CopyListCopyList(const const LinkedListLinkedList&L);&L);public:public:LinkedList(voidLinkedList(void););LinkedList(constLinkedList(const LinkedListLinkedList&L);&L);LinkedList(voidLinkedList(void););LinkedListLinkedList&operator=(&operator=(const const LinkedListLinkedList&L);&L);intint ListSize(voidListSize(void)const;)const;intint ListEmpty(voidListEmpty(void)const;)const;void void Reset(intReset(int pos=0);pos=0);void void Next(voidNext(void););intint EndOfList(voidEndOfList(void)const;)const;intint CurrentPosition(voidCurrentPosition(void)const;)const;void void InsertFront(constInsertFront(const T&item);T&item);void void InsertRear(constInsertRear(const T&item);T&item);void void InsertAt(constInsertAt(const T&item);T&item);void void InsertAfter(constInsertAfter(const T&item);T&item);T T DeleteFront(voidDeleteFront(void););void void DeleteAt(voidDeleteAt(void););T&T&Data(voidData(void););void void ClearList(voidClearList(void););#endifendif /LINKEDLIST_CLASS /LINKEDLIST_CLASS36C+语言程序设计清华大学 郑莉链表类应用举例链表类应用举例(例例9-7)l从键盘输入从键盘输入10个整数，用这些整数作个整数，用这些整数作为结点数据，生成一个链表，按顺序为结点数据，生成一个链表，按顺序输出链表中结点的数值。然后从键盘输出链表中结点的数值。然后从键盘输入一个待查找整数，在链表中查找输入一个待查找整数，在链表中查找该整数，如找到则删除该整数所在的该整数，如找到则删除该整数所在的结点（如果出现多次，全部删除），结点（如果出现多次，全部删除），然后输出删除结点以后的链表。在程然后输出删除结点以后的链表。在程序结束前清空链表。序结束前清空链表。顺序访问的线性群体37C+语言程序设计清华大学 郑莉链表类应用举例链表类应用举例(例例9-7)顺序访问的线性群体#include#include#include 9_6.h#include 9_6.h#include 9_6.cpp#include 9_6.cppusing namespace std;using namespace std;intint main()main()LinkedListLinkedList Link;Link;intint i,key,item;i,key,item;for(i=0;i 10;i+)for(i=0;i item;item;Link.InsertFront(itemLink.InsertFront(item););coutcout List:;List:;Link.ResetLink.Reset();();while(!Link.EndOfListwhile(!Link.EndOfList()()coutcoutLink.DataLink.Data();();Link.NextLink.Next();();coutcout endlendl;coutcout key;key;Link.ResetLink.Reset();();while(!while(!Link.EndOfListLink.EndOfList()()if(Link.Dataif(Link.Data()=key)()=key)Link.DeleteAtLink.DeleteAt();();Link.NextLink.Next();();coutcout List:;List:;Link.ResetLink.Reset();();while(!Link.EndOfListwhile(!Link.EndOfList()()coutcout Link.DataLink.Data();();Link.NextLink.Next();();coutcout endlendl;38C+语言程序设计清华大学 郑莉特殊的线性群体特殊的线性群体栈栈栈是只能从一端访问的线性群体，栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈可以访问的这一端称栈顶，另一端称栈底。底。ana2a1入栈出栈栈顶栈底特殊的线性群体栈39C+语言程序设计清华大学 郑莉栈的应用举例栈的应用举例函数调用函数调用特殊的线性群体栈main调fun(参数)结束fun(参数)返回参数当前现场返回地址入栈当前现场返回地址出栈参数出栈当前现场 返回地址40C+语言程序设计清华大学 郑莉栈的应用举例栈的应用举例表达式处理表达式处理ba/a/b+c*d(a)t1+a/b+c*dt1=a/b(b)dct1*+a/b+c*d(c)t3a/b+c*dt3=t1+t2(e)t2t1+a/b+c*dt2=c*d(d)特殊的线性群体栈41C+语言程序设计清华大学 郑莉栈的基本状态栈的基本状态l栈空栈空栈中没有元素l栈满栈满栈中元素个数达到上限l一般状态一般状态栈中有元素，但未达到栈满状态特殊的线性群体栈42栈顶ana1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态（栈空）maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满状态4343C+语言程序设计清华大学 郑莉栈的基本操作栈的基本操作l初始化初始化l入栈入栈l出栈出栈l清空栈清空栈l访问栈顶元素访问栈顶元素l检测栈的状态（满、空）检测栈的状态（满、空）特殊的线性群体栈44C+语言程序设计清华大学 郑莉栈类模板栈类模板(例例9-8)特殊的线性群体栈/9-8.h/9-8.h#ifndefifndef STACK_CLASS STACK_CLASS#define STACK_CLASS#define STACK_CLASS#include#include#include#include using namespace std;using namespace std;const const intint MaxStackSizeMaxStackSize=50;=50;template template class Stackclass Stackprivate:private:T T stacklistMaxStackSizestacklistMaxStackSize;intint top;top;public:public:Stack(void);Stack(void);void Push(const T&item);void Push(const T&item);T Pop(void);T Pop(void);void void ClearStack(voidClearStack(void););T Peek(void)const;T Peek(void)const;intint StackEmpty(voidStackEmpty(void)const;)const;intint StackFull(voidStackFull(void)const;)const;/类的实现略类的实现略45C+语言程序设计清华大学 郑莉栈的应用栈的应用l例例9.9 一个简单的整数计算器一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算3+5则输入3 5 +。乘方运算符用表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入c。当键入q时程序结束。l9-9.h 9-9.cpp特殊的线性群体栈46/9_9.h/9_9.h#include#include#include#include#include#include#include#include using namespace std;using namespace std;enumenum Boolean False,True;Boolean False,True;#include 9_8.h#include 9_8.h class class CalculatorCalculator private:private:Stack Stack S;S;void void Enter(intEnter(int num);num);Boolean Boolean GetTwoOperands(intGetTwoOperands(int&opnd1,&opnd1,intint&opnd2);&opnd2);void void Compute(charCompute(char op);op);public:public:void void Run(voidRun(void););void void Clear(voidClear(void););4747void void Calculator:Calculator:EnterEnter(int(int num)num)S.Push(num);S.Push(num);Boolean Boolean Calculator:Calculator:GetTwoOperandsGetTwoOperands(intint&opnd1,int&opnd2)&opnd1,int&opnd2)if(if(S.StackEmptyS.StackEmpty()()cerrcerr Missing operand!Missing operand!endlendl;return False;return False;opnd1=S.Pop();opnd1=S.Pop();if(if(S.StackEmptyS.StackEmpty()()cerrcerr Missing operand!Missing operand!endlendl;return False;return False;opnd2=S.Pop();opnd2=S.Pop();return True;return True;4848void