C++语言程序设计第九章

1第一部分：模板函数模板类模板第第2页页/共共76页页第1页/共76页2函数模板函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。声明方法：template 函数声明 函 数 模 板第第3页页/共共76页页第2页/共76页3求绝对值函数的模板#includeusing namespace std;templateT abs(T x)return x0?-x:x;int main()int n=-5;double d=-5.5;coutabs(n)endl;coutabs(d)endl;函 数 模 板运行结果：运行结果：55.5第第4页页/共共76页页第3页/共76页4求绝对值函数的模板分析编译器从调用abs()时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：int abs(int x)return x0?-x:x;函 数 模 板第第5页页/共共76页页第4页/共76页5类模板的作用使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类 模 板第第6页页/共共76页页第5页/共76页6类模板的声明类模板：template class 类名类成员声明如果需要在类模板以外定义其成员函数，则要采用以下的形式：template 类型名 类名:函数名（参数表）类 模 板第第7页页/共共76页页第6页/共76页7例9-2 类模板应用举例#include#include using namespace std;/结构体Studentstruct Student int id;/学号 float gpa;/平均分;类 模 板第第8页页/共共76页页第7页/共76页template /类模板：实现对任意类型数据进行存取class Store private:T item;/用于存放任意类型的数据 int haveValue;/用于标记item是否已被存入内容 public:Store(void);/默认形式（无形参）的构造函数 GetElem(void);/提取数据函数 void PutElem(T x);/存入数据函数;/默认形式构造函数的实现template Store:Store(void):haveValue(0)8第第9页页/共共76页页第8页/共76页template /提取数据函数的实现T Store:GetElem(void)/如果试图提取未初始化的数据，则终止程序 if(haveValue=0)cout No item present!endl;exit(1);return item;/返回item中存放的数据 template /存入数据函数的实现 void Store:PutElem(T x)/将haveValue 置为 TRUE，表示item中已存入数值 haveValue+;item=x;/将x值存入item9第第10页页/共共76页页第9页/共76页int main()Student g=1000,23;Store S1,S2;Store S3;Store D;S1.PutElem(3);S2.PutElem(-7);cout S1.GetElem()S2.GetElem()endl;S3.PutElem(g);cout The student id is S3.GetElem().idendl;cout Retrieving object D ;cout D.GetElem()endl;/输出对象D的数据成员 /由于D未经初始化,在执行函数D.GetElement()时出错10第第11页页/共共76页页第10页/共76页11第二部分：群体数据线性群体线性群体的概念直接访问群体-数组类顺序访问群体-链表类栈类队列类第第12页页/共共76页页第11页/共76页12群体的概念群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。第第13页页/共共76页页第12页/共76页13线性群体的概念线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。第一个元素第二个元素第三个元素最后一个元素第第14页页/共共76页页第13页/共76页14数组静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修改。动态数组由一系列位置连续的，任意数量相同类型的元素组成。优点：其元素个数可在程序运行时改变。动态数组类模板：例9-3（9_3.h）直接访问的线性群体第第15页页/共共76页页第14页/共76页#ifndef ARRAY_CLASS#define ARRAY_CLASSusing namespace std;#include#include#ifndef NULLconst int NULL=0;#endif /NULLenum ErrorType invalidArraySize,memoryAllocationError,indexOutOfRange;char*errorMsg=Invalid array size,Memory allocation error,Invalid index:;动态数组类模板程序15第第16页页/共共76页页第15页/共76页template class Array private:T*alist;int size;void Error(ErrorType error,int badIndex=0)const;public:Array(int sz=50);Array(const Array&A);Array(void);Array&operator=(const Array&rhs);T&operator(int i);operator T*(void)const;int ListSize(void)const;void Resize(int sz);16第第17页页/共共76页页第16页/共76页17数组类模板的构造函数/构造函数template Array:Array(int sz)if(sz=0)/sz为数组大小（元素个数），若小于0则输出错误信息 Error(invalidArraySize);size=sz;/将元素个数赋值给变量size alist=new Tsize;/动态分配size个T类型的元素空间 if(alist=NULL)/如果分配内存不成功，输出错误信息 Error(memoryAllocationError);直接访问的线性群体第第18页页/共共76页页第17页/共76页18数组类的拷贝构造函数template Array:Array(const Array&X)int n=X.size;size=n;alist=new Tn;if(alist=NULL)Error(memoryAllocationError);T*srcptr=X.alist;/X.alist是对象X的数组首地址 T*destptr=alist;/alist是本对象中的数组首地址 while(n-)/逐个复制数组元素 *destptr+=*srcptr+;直接访问的线性群体第第19页页/共共76页页第18页/共76页19浅拷贝 alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBint main()int main()Array A(10);Array A(10);.Array B(A);Array B(A);.template template Array:Array(Array:Array(const Array&X)const Array&X)size=X.size;size=X.size;alist=X.alist;alist=X.alist;第第20页页/共共76页页第19页/共76页20深拷贝 alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBB的数组元素占用的内存第第21页页/共共76页页第20页/共76页21数组类的重载=运算符函数template Array&Array:operator=(const Array&rhs)int n=rhs.size;if(size!=n)delete alist;alist=new Tn;if(alist=NULL)Error(memoryAllocationError);size=n;T*destptr=alist;T*srcptr=rhs.alist;while(n-)*destptr+=*srcptr+;return*this;直接访问的线性群体第第22页页/共共76页页第21页/共76页22数组类的重载下标操作符函数template T&Array:operator(int n)/检查下标是否越界 if(n size-1)Error(indexOutOfRange,n);/返回下标为n的数组元素 return alistn;直接访问的线性群体第第23页页/共共76页页第22页/共76页23为什么有的函数返回引用如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成为左值。如果返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变对象的值。直接访问的线性群体第第24页页/共共76页页第23页/共76页24重载指针转换操作符template Array:operator T*(void)const /返回当前对象中私有数组的首地址 return alist;直接访问的线性群体第第25页页/共共76页页第24页/共76页25指针转换运算符的作用#include using namespace std;int main()int a10;void read(int*p,int n);read(a,10);void read(int*p,int n)for(int i=0;ipi;int main()Array a(10);void read(int*p,n);read(a,10);void read(int*p,int n)for(int i=0;ipi;直接访问的线性群体第第26页页/共共76页页第25页/共76页26Array类的应用例9-4求范围2N中的质数，N在程序运行时由键盘输入。直接访问的线性群体第第27页页/共共76页页第26页/共76页#include#include#include 9_3.husing namespace std;int main()Array A(10);int n;int primecount=0,i,j;cout=2 as upper limit for prime numbers:;cin n;Aprimecount+=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)Aprimecount+=i;for(i=0;i primecount;i+)cout setw(5)Ai;if(i+1)%10=0)cout endl;cout endl;27第第28页页/共共76页页第27页/共76页28链表链表是一种动态数据结构，可以用来表示顺序访问的线性群体。链表是由系列结点组成的，结点可以在运行时动态生成。每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。顺序访问的线性群体第第29页页/共共76页页第28页/共76页29单链表 data1 data1 data2 data2 data3 data3 datan NULL datan NULLheadheadrearrear顺序访问的线性群体第第30页页/共共76页页第29页/共76页30单链表的结点类模板template class Node private:Node*next;public:T data;Node(const T&item,Node*ptrnext=NULL);void InsertAfter(Node*p);Node*DeleteAfter(void);Node*NextNode(void)const;顺序访问的线性群体第第31页页/共共76页页第30页/共76页31在结点之后插入一个结点 data1 data2 p datatemplate template void Node:void Node:InsertAfterInsertAfter(Node*p)(Node*p)/p /p节点指针域指向当前节点的后继节点节点指针域指向当前节点的后继节点 p-next=next;p-next=next;next=p;/next=p;/当前节点的指针域指向当前节点的指针域指向p p 顺序访问的线性群体第第32页页/共共76页页第31页/共76页32 删除结点之后的结点顺序访问的线性群体 data1 data2 data3Node*Node:DeleteAfter(void)Node*Node:DeleteAfter(void)Node*tempPtr=next;Node*tempPtr=next;if(next=NULL)if(next=NULL)return NULL;return NULL;next=tempPtr-next;next=tempPtr-next;return tempPtr;return tempPtr;tempPtr第第33页页/共共76页页第32页/共76页33链表的基本操作生成结点插入结点查找结点删除结点遍历链表清空链表顺序访问的线性群体第第34页页/共共76页页第33页/共76页34链表类模板(例9-6)顺序访问的线性群体/9_6.h#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include#include using namespace std;#ifndef NULLconst int NULL=0;#endif /NULL#include 9_5.htemplate class LinkedListprivate:Node*front,*rear;Node*prevPtr,*currPtr;int size;int position;Node*GetNode(const T&item,Node*ptrNext=NULL);void FreeNode(Node*p);void CopyList(const LinkedList&L);public:LinkedList(void);LinkedList(const LinkedList&L);LinkedList(void);LinkedList&operator=(const LinkedList&L);int ListSize(void)const;int ListEmpty(void)const;void Reset(int pos=0);void Next(void);int EndOfList(void)const;int CurrentPosition(void)const;void InsertFront(const T&item);void InsertRear(const T&item);void InsertAt(const T&item);void InsertAfter(const T&item);T DeleteFront(void);void DeleteAt(void);T&Data(void);void ClearList(void);#endif /LINKEDLIST_CLASS第第35页页/共共76页页第34页/共76页35链表类应用举例(例9-7)从键盘输入10个整数，用这些整数作为结点数据，生成一个链表，按顺序输出链表中结点的数值。然后从键盘输入一个待查找整数，在链表中查找该整数，如找到则删除该整数所在的结点（如果出现多次，全部删除），然后输出删除结点以后的链表。在程序结束前清空链表。顺序访问的线性群体第第36页页/共共76页页第35页/共76页36链表类应用举例(例9-7)顺序访问的线性群体#include#include 9_6.h#include 9_6.cppusing namespace std;int main()LinkedList Link;int i,key,item;for(i=0;i item;Link.InsertFront(item);cout List:;Link.Reset();while(!Link.EndOfList()coutLink.Data();Link.Next();cout endl;cout key;Link.Reset();while(!Link.EndOfList()if(Link.Data()=key)Link.DeleteAt();Link.Next();cout List:;Link.Reset();while(!Link.EndOfList()cout Link.Data();Link.Next();cout endl;第第37页页/共共76页页第36页/共76页37特殊的线性群体栈栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。ana2a1入栈出栈栈顶栈底特殊的线性群体栈第第38页页/共共76页页第37页/共76页38栈的应用举例函数调用特殊的线性群体栈main调fun(参数)结束fun(参数)返回参数当前现场返回地址入栈当前现场返回地址出栈参数出栈当前现场 返回地址第第39页页/共共76页页第38页/共76页39栈的应用举例表达式处理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)特殊的线性群体栈第第40页页/共共76页页第39页/共76页40栈的基本状态栈空栈中没有元素栈满栈中元素个数达到上限一般状态栈中有元素，但未达到栈满状态特殊的线性群体栈第第41页页/共共76页页第40页/共76页栈顶ana1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态（栈空）maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满状态41第第42页页/共共76页页第41页/共76页42栈的基本操作初始化入栈出栈清空栈访问栈顶元素检测栈的状态（满、空）特殊的线性群体栈第第43页页/共共76页页第42页/共76页43栈类模板(例9-8)特殊的线性群体栈/9-8.h#ifndef STACK_CLASS#define STACK_CLASS#include#include using namespace std;const int MaxStackSize=50;template class Stackprivate:T stacklistMaxStackSize;int top;public:Stack(void);void Push(const T&item);T Pop(void);void ClearStack(void);T Peek(void)const;int StackEmpty(void)const;int StackFull(void)const;/类的实现略第第44页页/共共76页页第43页/共76页44栈的应用例9.9 一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算3+5则输入3 5 +。乘方运算符用表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入c。当键入q时程序结束。9-9.h 9-9.cpp特殊的线性群体栈第第45页页/共共76页页第44页/共76页/9_9.h#include#include#include#include using namespace std;enum Boolean False,True;#include 9_8.h class Calculator private:Stack S;void Enter(int num);Boolean GetTwoOperands(int&opnd1,int&opnd2);void Compute(char op);public:void Run(void);void Clear(void);45第第46页页/共共76页页第45页/共76页void Calculator:Enter(int num)S.Push(num);Boolean Calculator:GetTwoOperands(int&opnd1,int&opnd2)if(S.StackEmpty()cerr Missing operand!endl;return False;opnd1=S.Pop();if(S.StackEmpty()cerr Missing operand!endl;return False;opnd2=S.Pop();return True;46第第47页页/共共76页页第46页/共76页void Calculator:Compute(char op)Boolean result;int operand1,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)cerrDivide by 0!endl;S.ClearStack();else S.Push(operand2/operand1);break;case:S.Push(pow(operand2,operand1);break;cout=S.Peek()c,*c!=q)switch(*c)case c:S.ClearStack();break;case-:if(strlen(c)1)Enter(atoi(c);else Compute(*c);break;case+:case*:case/:case:Compute(*c);break;default:Enter(atoi(c);break;void Calculator:Clear(void)S.ClearStack();48第第49页页/共共76页页第48页/共76页/9_9.cpp#include 9-9.hint main()Calculator CALC;CALC.Run();49第第50页页/共共76页页第49页/共76页50特殊的线性群体队列队列是只能向一端添加元素，从另一端删除元素的线性群体a1 a2an-1 an队头队尾入队出队a0第第51页页/共共76页页第50页/共76页51队列的基本状态队空队列中没有元素队满队列中元素个数达到上限一般状态队列中有元素，但未达到队满状态特殊的线性群体队列第第52页页/共共76页页第51页/共76页a0 a1an-1 an队头队尾入队出队数组下标 0 1 n-1 n max(一般状态)队头队尾入队出队数组下标 0 1 n-1 n max(队空状态)a0 a1 an-1 an amax队头队尾入队出队数组下标 0 1 n-1 n max(队满状态)元素移动方向元素移动方向52第第53页页/共共76页页第52页/共76页53循环队列在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。特殊的线性群体队列第第54页页/共共76页页第53页/共76页1234m-1m-2m-30amam+1am+2a3队头队尾a4am-2am-3am-1队满状态 元素个数=m1234m-1m-2m-30队尾队头队空状态 元素个数=0队尾1234m-1m-2m-30a0a1a2a3队头一般状态54第第55页页/共共76页页第54页/共76页55例9-10 队列类模板特殊的线性群体队列#ifndef QUEUE_CLASS#define QUEUE_CLASS#include#include using namespace std;const int MaxQSize=50;template class Queue private:int front,rear,count;T qlistMaxQSize;public:Queue(void);void QInsert(const T&item);T QDelete(void);void ClearQueue(void);T QFront(void)const;int QLength(void)const;int QEmpty(void)const;int QFull(void)const;/成员函数的实现略第第56页页/共共76页页第55页/共76页56第三部分：群体数据的组织插入排序选择排序交换排序顺序查找折半查找第第57页页/共共76页页第56页/共76页57排序（sorting）排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。在排序过程中需要完成两种基本操作：比较两个数的大小调整元素在序列中的位置群体数据的组织第第58页页/共共76页页第57页/共76页58内部排序与外部排序内部排序：待排序的数据元素存放在计算机内存中进行的排序过程。外部排序：待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。群体数据的组织第第59页页/共共76页页第58页/共76页59内部排序方法插入排序选择排序交换排序群体数据的组织第第60页页/共共76页页第59页/共76页60插入排序的基本思想每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。初始状态：5 4 10 20 12 3插入操作：1 4 4 5 10 20 12 32 10 4 5 10 20 12 33 20 4 5 10 20 12 34 12 4 5 10 12 20 35 3 3 4 5 10 12 20第第61页页/共共76页页第60页/共76页61直接插入排序在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序算法，这里我们只介绍最简单的直接插入排序算法。例9-11 直接插入排序函数模板（9_11.h）群体数据的组织第第62页页/共共76页页第61页/共76页template void InsertionSort(T A,int n)int i,j;T temp;for(i=1;i 0&temp Aj-1)Aj=Aj-1;j-;Aj=temp;直接插入排序函数模板（9_11.h）62第第63页页/共共76页页第62页/共76页63选择排序的基本思想每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。5 4 10 20 12 3初始状态：3 4 10 20 12 53 4 10 20 12 5第 i 次选择后，将选出的那个记录与第 i 个记录做交换。3 4 5 20 12 10.第第64页页/共共76页页第63页/共76页64直接选择排序在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是通过顺序比较找出待排序序列中的最小元素，称为直接选择排序。例9-12 直接选择排序函数模板（9-12.h）群体数据的组织第第65页页/共共76页页第64页/共76页template void Swap(T&x,T&y)T temp;temp=x;x=y;y=temp;template void SelectionSort(T A,int n)int smallIndex;int i,j;for(i=0;i n-1;i+)smallIndex=i;for(j=i+1;j n;j+)if(Aj AsmallIndex)smallIndex=j;Swap(Ai,AsmallIndex);直接选择排序函数模板（9-12.h）65第第66页页/共共76页页第65页/共76页66交换排序的基本思想两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。群体数据的组织第第67页页/共共76页页第66页/共76页67最简单的交换排序方法 起泡排序对具有n个元素的序列按升序进行起泡排序的步骤：首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，依次类推，直到第n-1和第n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第n个位置。对前n-1个元素进行第二趟起泡排序，将其中最大元素交换到第n-1个位置。如此继续，直到某一趟排序未发生任何交换时，排序完毕。对n个元素的序列，起泡排序最多需要进行n-1趟。群体数据的组织第第68页页/共共76页页第67页/共76页68起泡排序举例对整数序列 8 5 2 4 3 按升序排序8524352438243582345823458初始状态第一趟结果第二趟结果第三趟结果第四趟结果小的逐渐上升每趟沉下一个最大的群体数据的组织第第69页页/共共76页页第68页/共76页69例9-13 起泡排序函数模板template void Swap(T&x,T&y)T temp;temp=x;x=y;y=temp;template void BubbleSort(T A,int n)int i,j;int lastExchangeIndex;i=n-1;while(i 0)lastExchangeIndex=0;for(j=0;j i;j+)if(Aj+1 Aj)Swap(Aj,Aj+1);lastExchangeIndex=j;i=lastExchangeIndex;群体数据的组织第第70页页/共共76页页第69页/共76页70顺序查找其基本思想从序列的首元素开始，逐个元素与待查找的关键字进行比较，直到找到相等的。若整个序列中没有与待查找关键字相等的元素，就是查找不成功。顺序查找函数模板例9-14群体数据的组织第第71页页/共共76页页第70页/共76页template int SeqSearch(T list,int n,T key)for(int i=0;i n;i+)if(listi=key)return i;return-1;顺序查找函数模板71第第72页页/共共76页页第71页/共76页72折半查找的基本思想对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。群体数据的组织第第73页页/共共76页页第72页/共76页73折半查找举例用折半查找法，在下列序列中查找值为21的元素：L=1513192137566475808892H=11M=INT(L+H)/2)=6513192137L=1H=M-1=5M=INT(L+H)/2)=3M2137HL=M+1=4LM=INT(L+H)/2)=4M第第74页页/共共76页页第73页/共76页74例9-15 折半查找函数模板template int BinSearch(T list,int n,T key)int mid,low,high;T midvalue;low=0;high=n-1;while(low=high)mid=(low+high)/2;midvalue=listmid;if(key=midvalue)return mid;else if(key midvalue)high=mid-1;else low=mid+1;return-1;群体数据的组织第第75页页/共共76页页第74页/共76页75小结与复习建议主要内容模板、群体类和群体数据的组织达到的目标理解模板的作用，学会简单的应用。以群体类以及查找、排序算法为综合例题，对前面章节的内容进行全面复习；掌握一些常用的数据结构和算法，能够解决一些略复杂的问题，也为下一章学习C+标准模板库打下基础。实验任务实验九第第76页页/共共76页页第75页/共76页76感谢您的观赏！第76页/共76页