《C++语言程序设计》第九章：群体类和群体数据的组织

第九章群体类和群体数据的组织,C+语言程序设计,2,本章主要内容,模板群体类群体数据的组织,3,第一部分模板,函数模板类模板,4,函数模板,函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。声明方法：template函数声明,函数模板,5,求绝对值函数的模板,#includeusingnamespacestd;templateTabs(Tx)returnx0?-x:x;intmain()intn=-5;doubled=-5.5;coutabs(n)endl;coutabs(d)endl;,函数模板,运行结果：55.5,6,求绝对值函数的模板分析,编译器从调用abs()时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：intabs(intx)returnx0?-x:x;,函数模板,7,类模板的作用,使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。,类模板,8,类模板的声明,类模板：templateclass类名类成员声明如果需要在类模板以外定义其成员函数，则要采用以下的形式：template类型名类名:函数名（参数表）,类模板,9,例9-2类模板应用举例,#include#includeusingnamespacestd;/结构体StudentstructStudentintid;/学号floatgpa;/平均分;,类模板,template/类模板：实现对任意类型数据进行存取classStoreprivate:Titem;/用于存放任意类型的数据inthaveValue;/用于标记item是否已被存入内容public:Store(void);/默认形式（无形参）的构造函数TGetElem(void);/提取数据函数voidPutElem(Tx);/存入数据函数;/默认形式构造函数的实现templateStore:Store(void):haveValue(0),10,template/提取数据函数的实现TStore:GetElem(void)/如果试图提取未初始化的数据，则终止程序if(haveValue=0)cout/存入数据函数的实现voidStore:PutElem(Tx)haveValue+;/将haveValue置为TRUE，表示item中已存入数值item=x;/将x值存入item,11,intmain()Studentg=1000,23;StoreS1,S2;StoreS3;StoreD;S1.PutElem(3);S2.PutElem(-7);coutS1.GetElem()S2.GetElem()endl;S3.PutElem(g);coutThestudentidisS3.GetElem().idendl;coutRetrievingobjectD;coutD.GetElem()pi;,直接访问的线性群体,28,Array类的应用,例9-4求范围2N中的质数，N在程序运行时由键盘输入。,直接访问的线性群体,#include#include#include9_3.husingnamespacestd;intmain()ArrayA(10);intn;intprimecount=0,i,j;cout=2asupperlimitforprimenumbers:;cinn;Aprimecount+=2;/2是一个质数for(i=3;ii/2)Aprimecount+=i;for(i=0;iprimecount;i+)coutsetw(5)Ai;if(i+1)%10=0)coutendl;coutnext;returntempPtr;,tempPtr,35,链表的基本操作,生成结点插入结点查找结点删除结点遍历链表清空链表,顺序访问的线性群体,36,链表类模板(例9-6),/9_6.h#ifndefLINKEDLIST_CLASS#defineLINKEDLIST_CLASS#include#includeusingnamespacestd;#ifndefNULLconstintNULL=0;#endif/NULL#include9_5.h,顺序访问的线性群体,templateclassLinkedListprivate:Node*front,*rear;Node*prevPtr,*currPtr;intsize;intposition;Node*GetNode(constT,37,public:LinkedList(void);LinkedList(constLinkedList,38,voidInsertFront(constT#endif/LINKEDLIST_CLASS,39,40,链表类应用举例(例9-7),#includeusingnamespacestd;#include9_6.h#include9_6.cppintmain()LinkedListLink;inti,key,item;for(i=0;iitem;Link.InsertFront(item);,顺序访问的线性群体,coutkey;Link.Reset();,41,while(!Link.EndOfList()if(Link.Data()=key)Link.DeleteAt();Link.Next();coutList:;Link.Reset();while(!Link.EndOfList()coutLink.Data();Link.Next();coutendl;,42,43,特殊的线性群体栈,栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。,特殊的线性群体栈,44,栈的应用举例函数调用,特殊的线性群体栈,45,栈的应用举例表达式处理,特殊的线性群体栈,46,栈的基本状态,栈空栈中没有元素栈满栈中元素个数达到上限一般状态栈中有元素，但未达到栈满状态,特殊的线性群体栈,47,48,栈的基本操作,初始化入栈出栈清空栈访问栈顶元素检测栈的状态（满、空）,特殊的线性群体栈,49,栈类模板(例9-8),特殊的线性群体栈,/9-8.h#ifndefSTACK_CLASS#defineSTACK_CLASS#include#includeusingnamespacestd;constintMaxStackSize=50;templateclassStackprivate:TstacklistMaxStackSize;inttop;,public:Stack(void);voidPush(constT/类的实现略,50,栈的应用,例9.9一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算3+5则输入35+。乘方运算符用表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入c。当键入q时程序结束。9-9.h9-9.cpp,特殊的线性群体栈,/9_9.h#include#include#include#includeusingnamespacestd;enumBooleanFalse,True;#include9_8.hclassCalculatorprivate:StackS;voidEnter(intnum);BooleanGetTwoOperands(int,51,voidCalculator:Enter(intnum)S.Push(num);BooleanCalculator:GetTwoOperands(int,52,voidCalculator:Compute(charop)Booleanresult;intoperand1,operand2;result=GetTwoOperands(operand1,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)cerrDivideby0!endl;S.ClearStack();elseS.Push(operand2/operand1);break;case:S.Push(pow(operand2,operand1);break;cout=S.Peek()c,*c!=q)switch(*c)casec:S.ClearStack();break;case-:if(strlen(c)1)Enter(atoi(c);elseCompute(*c);break;case+:case*:case/:case:Compute(*c);break;default:Enter(atoi(c);break;,54,voidCalculator:Clear(void)S.ClearStack();/9_9.cpp#include9-9.hintmain()CalculatorCALC;CALC.Run();,55,56,特殊的线性群体队列,队列是只能向一端添加元素，从另一端删除元素的线性群体,57,队列的基本状态,队空队列中没有元素队满队列中元素个数达到上限一般状态队列中有元素，但未达到队满状态,特殊的线性群体队列,元素移动方向,元素移动方向,58,59,循环队列,在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。,特殊的线性群体队列,60,61,例9-10队列类模板,特殊的线性群体队列,#ifndefQUEUE_CLASS#defineQUEUE_CLASS#include#includeusingnamespacestd;constintMaxQSize=50;templateclassQueueprivate:intfront,rear,count;TqlistMaxQSize;,public:Queue(void);voidQInsert(constT/成员函数的实现略,62,第三部分群体数据的组织,插入排序选择排序交换排序顺序查找折半查找,63,排序（sorting）,排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。在排序过程中需要完成两种基本操作：比较两个数的大小调整元素在序列中的位置,群体数据的组织,64,内部排序与外部排序,内部排序：待排序的数据元素存放在计算机内存中进行的排序过程。外部排序：待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。,群体数据的组织,65,内部排序方法,插入排序选择排序交换排序,群体数据的组织,66,插入排序的基本思想,每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。,初始状态：541020123,67,直接插入排序,在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序算法，这里我们只介绍最简单的直接插入排序算法。例9-11直接插入排序函数模板（9_11.h）,群体数据的组织,templatevoidInsertionSort(TA,intn)inti,j;Ttemp;for(i=1;i0,直接插入排序函数模板（9_11.h）,68,69,选择排序的基本思想,每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。,341020125,341020125,第i次选择后，将选出的那个记录与第i个记录做交换。,70,直接选择排序,在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是通过顺序比较找出待排序序列中的最小元素，称为直接选择排序。例9-12直接选择排序函数模板（9-12.h）,群体数据的组织,templatevoidSwap(T,直接选择排序函数模板（9-12.h）,71,72,交换排序的基本思想,两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。,群体数据的组织,73,最简单的交换排序方法起泡排序,对具有n个元素的序列按升序进行起泡排序的步骤：首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，依次类推，直到第n-1和第n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第n个位置。对前n-1个元素进行第二趟起泡排序，将其中最大元素交换到第n-1个位置。如此继续，直到某一趟排序未发生任何交换时，排序完毕。对n个元素的序列，起泡排序最多需要进行n-1趟。,群体数据的组织,74,起泡排序举例,对整数序列85243按升序排序,85243,5,2,4,3,8,2,4,3,5,8,2,3,4,5,8,2,3,4,5,8,初始状态,第一趟结果,第二趟结果,第三趟结果,第四趟结果,小的逐渐上升,每趟沉下一个最大的,群体数据的组织,75,例9-13起泡排序函数模板,templatevoidSwap(T,templatevoidBubbleSort(TA,intn)inti,j;intlastExchangeIndex;i=n-1;while(i0)lastExchangeIndex=0;for(j=0;ji;j+)if(Aj+1Aj)Swap(Aj,Aj+1);lastExcha