【文档说明】C语言程序设计PPT第九章群体类和群体数据的组织.ppt，共(76)页，329.512 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-2207.html

以下为本文档部分文字说明：

第九章群体类和群体数据的组织C++语言程序设计C++语言程序设计2本章主要内容⚫模板⚫群体类⚫群体数据的组织C++语言程序设计3第一部分：模板⚫函数模板⚫类模板C++语言程序设计4函数模板⚫函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函

数体设计。⚫声明方法：template<typename标识符>函数声明函数模板C++语言程序设计5求绝对值函数的模板#include<iostream.h>template<typenameT>Tabs(Tx){returnx<0?-x:

x;}intmain(){intn=-5;doubled=-5.5;cout<<abs(n)<<endl;cout<<abs(d)<<endl;}函数模板运行结果：55.5C++语言程序设计6求绝对值函数

的模板分析⚫编译器从调用abs()时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。⚫当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函

数：intabs(intx){returnx<0?-x:x;}函数模板C++语言程序设计7类模板的作用使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类模板C++语言程序设

计8类模板的声明⚫类模板：template<模板参数表>class类名{类成员声明}⚫如果需要在类模板以外定义其成员函数，则要采用以下的形式：template<模板参数表>类型名类名<T>::函数名（参数表）类模板C++语言程序设计9例9-2类模板应用举例#include<

iostream.h>#include<cstdlib.h>//结构体StudentstructStudent{intid;//学号floatgpa;//平均分};类模板template<classT>//类模板：实现对任意类型数据进行存取classStore{private:Titem;/

/用于存放任意类型的数据inthaveValue;//用于标记item是否已被存入内容public:Store(void);//默认形式（无形参）的构造函数GetElem(void);//提取数据函数voidPutElem(Tx);//存

入数据函数};//默认形式构造函数的实现template<classT>Store<T>::Store(void):haveValue(0){}10template<classT>//提取数据函数的实现TStore<T>::GetElem(void){//如果试图提取未初始化的

数据，则终止程序if(haveValue==0){cout<<"Noitempresent!"<<endl;exit(1);}returnitem;//返回item中存放的数据}template<classT>//存

入数据函数的实现voidStore<T>::PutElem(Tx){//将haveValue置为TRUE，表示item中已存入数值haveValue++;item=x;//将x值存入item}11intmain()

{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()时出错}12C++语言程序设计13第二部分：群体数据⚫线性群体–线性群体的概念–直接访问群体--数组类–顺序访问群体--链表类–栈类–队列类C++语言程序设计14群体的概念群体是指由多个数

据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。C++语言程序设计15线性群体的概念线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同

方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。…第一个元素第二个元素第三个元素最后一个元素C++语言程序设计16数组⚫静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。–缺点：大小在编译时就已经确定，在运行时无法修改。⚫动态数

组由一系列位置连续的，任意数量相同类型的元素组成。–优点：其元素个数可在程序运行时改变。⚫动态数组类模板：例9-3（9_3.h）直接访问的线性群体#ifndefARRAY_CLASS#defineARRAY_CLASS#include<iostream.h>#includ

e<cstdlib.h>#ifndefNULLconstintNULL=0;#endif//NULLenumErrorType{invalidArraySize,memoryAllocationError,indexOutOfRange};char*

errorMsg[]={"Invalidarraysize","Memoryallocationerror","Invalidindex:"};动态数组类模板程序17template<classT>classArray{private:T*a

list;intsize;voidError(ErrorTypeerror,intbadIndex=0)const;public:Array(intsz=50);Array(constArray<T>&A);~Array(void);Ar

ray<T>&operator=(constArray<T>&rhs);T&operator[](inti);operatorT*(void)const;intListSize(void)const;voidRes

ize(intsz);};18C++语言程序设计19数组类模板的构造函数//构造函数template<classT>Array<T>::Array(intsz){if(sz<=0)//sz为数组大小（元素个数），若小于0则输出错误信息Error(invalidArraySiz

e);size=sz;//将元素个数赋值给变量sizealist=newT[size];//动态分配size个T类型的元素空间if(alist==NULL)//如果分配内存不成功，输出错误信息Error(memoryAllocationError);}直接访问的线

性群体C++语言程序设计20数组类的拷贝构造函数template<classT>Array<T>::Array(constArray<T>&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++;}直接访问的线性群体C++语言程序设计21浅拷贝alistsizeAA的数组元素占用的内存拷贝前alistsizeAA的数组元素占用的

内存拷贝后alistsizeBintmain(){Array<int>A(10);......Array<int>B(A);......}template<classT>Array<T>::Array(constArra

y<T>&X){size=X.size;alist=X.alist;}C++语言程序设计22深拷贝alistsizeAA的数组元素占用的内存拷贝前alistsizeAA的数组元素占用的内存拷贝后alistsizeBB的数组元素占用的内存C++语言程序设计23数组类的重载"="

运算符函数template<classT>Array<T>&Array<T>::operator=(constArray<T>&rhs){intn=rhs.size;if(size!=n){delete[]alist;alist=newT[n];if(alist==NULL)Error(m

emoryAllocationError);size=n;}T*destptr=alist;T*srcptr=rhs.alist;while(n--)*destptr++=*srcptr++;return*this;}直接访问的线性群体C++语言程序设计24数组类的重载下标操作符函数

template<classT>T&Array<T>::operator[](intn){//检查下标是否越界if(n<0||n>size-1)Error(indexOutOfRange,n);//返回下标为n的数组元素returnalist[n];}直接访问的线性群体C++语言程序设计2

5为什么有的函数返回引用⚫如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成为左值。⚫如果返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变对象的值。直接访问的线性群体C++语言程序设计26重载指针转换操作

符template<classT>Array<T>::operatorT*(void)const{//返回当前对象中私有数组的首地址returnalist;}直接访问的线性群体C++语言程序设计27指针转换运算符的作用#include<iostream.h>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,n);read(a,10);}voi

dread(int*p,intn){for(inti=0;i<n;i++)cin>>p[i];}直接访问的线性群体C++语言程序设计28Array类的应用⚫例9-4求范围2~N中的质数，N在程序运行时

由键盘输入。直接访问的线性群体#include<iostream.h>#include<iomanip.h>#include"9_3.h"intmain(){Array<int>A(10);intn;intprimecount=0,i,j;cout<<"Enteravalue>=2asup

perlimitforprimenumbers:";cin>>n;A[primecount++]=2;//2是一个质数for(i=3;i<n;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(j>i/2)A[primecount++]=i;}for(i=0;i<primecount;i++){cout<<setw(

5)<<A[i];if((i+1)%10==0)cout<<endl;}cout<<endl;}29C++语言程序设计30链表⚫链表是一种动态数据结构，可以用来表示顺序访问的线性群体。⚫链表是由系列结点组成的，结点可以在运行时动态生成。⚫每一个结点包括数据域和指向链表中下一个结点的

指针（即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。顺序访问的线性群体C++语言程序设计31单链表data1data2data3datanNULL…headrear顺序访问的线性群体C++语言程序设计32单

链表的结点类模板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;};顺序访问的线性群体C++语言程序设计33在结点之后插入一个结点data1data2…pdata…template<classT>void

Node<T>::InsertAfter(Node<T>*p){//p节点指针域指向当前节点的后继节点p->next=next;next=p;//当前节点的指针域指向p}顺序访问的线性群体C++语言程序设计34删除结点之后的结点顺序访问的线性群体data1

data2data3……Node<T>*Node<T>::DeleteAfter(void){Node<T>*tempPtr=next;if(next==NULL)returnNULL;next=tempPtr->next;returntempPtr;}

tempPtrC++语言程序设计35链表的基本操作⚫生成结点⚫插入结点⚫查找结点⚫删除结点⚫遍历链表⚫清空链表顺序访问的线性群体C++语言程序设计36链表类模板(例9-6)顺序访问的线性群体//9_6.h#ifndefLINKEDLIST_CLASS#defineLI

NKEDLIST_CLASS#include<iostream.h>#include<cstdlib.h>#ifndefNULLconstintNULL=0;#endif//NULL#include"9_5.h"template<class

T>classLinkedList{private:Node<T>*front,*rear;Node<T>*prevPtr,*currPtr;intsize;intposition;Node<T>*GetNode(constT&ite

m,Node<T>*ptrNext=NULL);voidFreeNode(Node<T>*p);voidCopyList(constLinkedList<T>&L);public:LinkedList(void);LinkedList(constLinke

dList<T>&L);~LinkedList(void);LinkedList<T>&operator=(constLinkedList<T>&L);intListSize(void)const;intListEmp

ty(void)const;voidReset(intpos=0);voidNext(void);intEndOfList(void)const;intCurrentPosition(void)const;voidInsertFront(const

T&item);voidInsertRear(constT&item);voidInsertAt(constT&item);voidInsertAfter(constT&item);TDeleteFront(void);voidDeleteAt(void);T&Data(void);voidCl

earList(void);};#endif//LINKEDLIST_CLASSC++语言程序设计37链表类应用举例(例9-7)顺序访问的线性群体#include<iostream.h>#include"9_6.h"#include"9_6.cpp"intmain(){LinkedList<

int>Link;inti,key,item;for(i=0;i<10;i++){cin>>item;Link.InsertFront(item);}cout<<"List:";Link.Reset();while(!Link.EndOfList()){cout<<

Link.Data()<<"";Link.Next();}cout<<endl;cout<<"请输入一个需要删除的整数:";cin>>key;Link.Reset();while(!Link.EndOfList()){if(Link.Data()==key)Lin

k.DeleteAt();Link.Next();}cout<<"List:";Link.Reset();while(!Link.EndOfList()){cout<<Link.Data()<<"";Link.Next();

}cout<<endl;}C++语言程序设计38特殊的线性群体——栈栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。an┆a2a1入栈出栈栈顶栈底特殊的线性群体——栈C++语言程序设计39栈的应用举例——函数

调用特殊的线性群体——栈main{}调fun(参数)结束fun(参数)返回①②⑤⑦⑧参数当前现场返回地址③⑥入栈当前现场返回地址出栈参数④出栈当前现场返回地址C++语言程序设计40栈的应用举例——表达式处理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)特殊的线性群体——栈C++语言程序设计41栈的基本状态⚫栈空–栈中没有元素⚫栈满–栈中元素个数达到上限⚫一般状态–栈中有元素，但未达到栈

满状态特殊的线性群体——栈栈顶┆an┆a1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态（栈空）maxn10栈顶amax┆an┆a1a0入栈出栈数组下标maxn10栈满状态42C++语言程

序设计43栈的基本操作⚫初始化⚫入栈⚫出栈⚫清空栈⚫访问栈顶元素⚫检测栈的状态（满、空）特殊的线性群体——栈C++语言程序设计44栈类模板(例9-8)特殊的线性群体——栈//9-8.h#ifndefSTACK_CLASS#defineSTACK_C

LASS#include<iostream.h>#include<cstdlib.h>constintMaxStackSize=50;template<classT>classStack{private:Tstacklist[M

axStackSize];inttop;public:Stack(void);voidPush(constT&item);TPop(void);voidClearStack(void);TPeek(void)const;intStackEmpty(void)co

nst;intStackFull(void)const;};//类的实现略C++语言程序设计45栈的应用⚫例9.9一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白

符分隔。例如，若要计算"3+5"则输入"35+"。乘方运算符用"^"表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入"c"。当键入"q"时程序结束。⚫9-9.h9-9.cpp特殊的线性群体——栈//9_9.h#includ

e<iostream.h>#include<cmath.h>#include<cstdlib.h>#include<cstring.h>enumBoolean{False,True};#include"9_8.h"classCalculator{private:Stack<int>S;voidE

nter(intnum);BooleanGetTwoOperands(int&opnd1,int&opnd2);voidCompute(charop);public:voidRun(void);voidClea

r(void);};46voidCalculator::Enter(intnum){S.Push(num);}BooleanCalculator::GetTwoOperands(int&opnd1,int&opnd2){if(S.StackEmpty()){cerr<<"Missingoperan

d!"<<endl;returnFalse;}opnd1=S.Pop();if(S.StackEmpty()){cerr<<"Missingoperand!"<<endl;returnFalse;}opnd2

=S.Pop();returnTrue;}47voidCalculator::Compute(charop){Booleanresult;intoperand1,operand2;result=GetTwoOperands(operan

d1,operand2);if(result){switch(op){case'+':S.Push(operand2+operand1);break;case'-':S.Push(operand2-operand1);break;case'*'

:S.Push(operand2*operand1);break;case'/':if(operand1==0){cerr<<"Divideby0!"<<endl;S.ClearStack();}els

eS.Push(operand2/operand1);break;case'^':S.Push(pow(operand2,operand1));break;}cout<<'='<<S.Peek()<<'';}elseS.ClearS

tack();}48voidCalculator::Run(void){charc[20];while(cin>>c,*c!='q')switch(*c){case'c':S.ClearStack();bre

ak;case'-':if(strlen(c)>1)Enter(atoi(c));elseCompute(*c);break;case'+':case'*':case'/':case'^':Compute(*c);break;default:Enter(atoi(c));

break;}}voidCalculator::Clear(void){S.ClearStack();}49//9_9.cpp#include"9-9.h"intmain(){CalculatorCALC;CALC.Run();}50C++语言程序设计51特殊的线性群体——队列队列是只

能向一端添加元素，从另一端删除元素的线性群体a1a2an-1an……队头队尾入队出队a0C++语言程序设计52队列的基本状态⚫队空–队列中没有元素⚫队满–队列中元素个数达到上限⚫一般状态–队列中有元素，但未达到队满状态特殊的线性群体——队列a0a1an-1an……队头队尾入队

出队数组下标01n-1nmax(一般状态)……队头队尾入队出队数组下标01n-1nmax(队空状态)a0a1an-1anamax……队头队尾入队出队数组下标01n-1nmax(队满状态)元素移动方向元素移动方向5

3C++语言程序设计54循环队列在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。特殊的线性群体——队列1234……m-1m-2m-30amam+1am+2a3队头队尾a4am-2am-3am-1

队满状态元素个数=m1234……m-1m-2m-30队尾队头队空状态元素个数=0队尾1234……m-1m-2m-30a0a1a2a3队头一般状态55C++语言程序设计56例9-10队列类模板特殊的线性群体——队列#ifndefQUEUE_CLASS#defi

neQUEUE_CLASS#include<iostream.h>#include<cstdlib.h>constintMaxQSize=50;template<classT>classQueue{private:intfront,rear,count;Tqlist[MaxQSize];pu

blic:Queue(void);voidQInsert(constT&item);TQDelete(void);voidClearQueue(void);TQFront(void)const;intQLength(void)const;intQEmpty

(void)const;intQFull(void)const;};//成员函数的实现略C++语言程序设计57第三部分：群体数据的组织⚫插入排序⚫选择排序⚫交换排序⚫顺序查找⚫折半查找C++语言程序设计58排序（sorting）⚫排序是计算机程序设

计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。–数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。–关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。⚫在排序过程中需要完成两种

基本操作：–比较两个数的大小–调整元素在序列中的位置群体数据的组织C++语言程序设计59内部排序与外部排序⚫内部排序：待排序的数据元素存放在计算机内存中进行的排序过程。⚫外部排序：待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需

对外存进行访问的排序过程。群体数据的组织C++语言程序设计60内部排序方法⚫插入排序⚫选择排序⚫交换排序群体数据的组织C++语言程序设计61插入排序的基本思想⚫每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元

素插入完为止。初始状态：[5]41020123插入操作：1[4][45]10201232[10][4510]201233[20][451020]1234[12][45101220]35[3][345101220]C+

+语言程序设计62直接插入排序⚫在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序算法，这里我们只介绍最简单的直接插入排序算法。⚫例9-11直接插入排序函数模板（9_11.h）群体数据的组织template<classT>void

InsertionSort(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]=temp;}}直接插入排序函数模板（9_11.h）63C

++语言程序设计64选择排序的基本思想每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。[541020123]初始状态：3[41020125]34[1020125]第i次选择后，将选出的

那个记录与第i个记录做交换。345[201210]......C++语言程序设计65直接选择排序⚫在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是通过顺序比较找出待排序序列中的最小元素，称为直接选择排序。⚫例9-12直接选择排序

函数模板（9-12.h）群体数据的组织template<classT>voidSwap(T&x,T&y){Ttemp;temp=x;x=y;y=temp;}template<classT>voidSelectionSort

(TA[],intn){intsmallIndex;inti,j;for(i=0;i<n-1;i++){smallIndex=i;for(j=i+1;j<n;j++)if(A[j]<A[smallIndex])smallIndex=j;Swap(A[i

],A[smallIndex]);}}直接选择排序函数模板（9-12.h）66C++语言程序设计67交换排序的基本思想两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。群体数据的组织C++

语言程序设计68最简单的交换排序方法——起泡排序对具有n个元素的序列按升序进行起泡排序的步骤：–首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，依次类推，直到第n-1和第n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第

n个位置。–对前n-1个元素进行第二趟起泡排序，将其中最大元素交换到第n-1个位置。–如此继续，直到某一趟排序未发生任何交换时，排序完毕。对n个元素的序列，起泡排序最多需要进行n-1趟。群体数据的组织C++语言程序设计69起泡排序举例对整数序列85243按升序排

序8524352438243582345823458初始状态第一趟结果第二趟结果第三趟结果第四趟结果小的逐渐上升每趟沉下一个最大的群体数据的组织C++语言程序设计70例9-13起泡排序函数模板template<classT>voidSwap(T&x,T&y){Ttemp;te

mp=x;x=y;y=temp;}template<classT>voidBubbleSort(TA[],intn){inti,j;intlastExchangeIndex;i=n-1;while(i>0){lastExchangeI

ndex=0;for(j=0;j<i;j++)if(A[j+1]<A[j]){Swap(A[j],A[j+1]);lastExchangeIndex=j;}i=lastExchangeIndex;}}群体数据的组织C++语言程序设计71顺序查找⚫其基本思想–从序列的首元

素开始，逐个元素与待查找的关键字进行比较，直到找到相等的。若整个序列中没有与待查找关键字相等的元素，就是查找不成功。⚫顺序查找函数模板–例9-14群体数据的组织template<classT>intSeqSearch(Tlist[],intn,Tkey){for(inti=0;

i<n;i++)if(list[i]==key)returni;return-1;}顺序查找函数模板72C++语言程序设计73折半查找的基本思想对于已按关键字排序的序列，经过一次比较，可将序列分割成两部

分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。群体数据的组织C++语言程序设计74折半查找举例用折半查找法，在下列序列中查找值为21的元素：L=151

3192137566475808892H=11M=INT((L+H)/2)=6513192137L=1H=M-1=5M=INT((L+H)/2)=3M2137HL=M+1=4LM=INT((L+H)/2)=4MC++语言程序设计75例9-15折半查找函数模板templat

e<classT>intBinSearch(Tlist[],intn,Tkey){intmid,low,high;Tmidvalue;low=0;high=n-1;while(low<=high){mid=(low+high)/2;midvalue=list[mid];if(key==midv

alue)returnmid;elseif(key<midvalue)high=mid-1;elselow=mid+1;}return-1;}群体数据的组织C++语言程序设计76小结与复习建议⚫主要内容–模板、群体类和群体数据的组织⚫达到的目标–理解模板的作用，学

会简单的应用。–以群体类以及查找、排序算法为综合例题，对前面章节的内容进行全面复习；–掌握一些常用的数据结构和算法，能够解决一些略复杂的问题，也为下一章学习C++标准模板库打下基础。