C++语言程序设计进阶 (5).pdf

《C++语言程序设计进阶 (5).pdf》由会员分享，可在线阅读，更多相关《C++语言程序设计进阶 (5).pdf（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第九章 模板与群体数据 本章主要内容 函数模板与类模板 线性群体 群体数据的组织 函数模板 思考：如果重载的函数，其解决问题的逻辑是一致的、函数体语句相同，只是处理的数据类型不同，那么写多个相同的函数体，是重复劳动，而且还可能因为代码的冗余造成不一致性。解决：使用模板 例：求绝对值函数的模板 函数模板定义语法 语法形式：template 函数定义 模板参数表的内容 类型参数：class（或typename）标识符 常量参数：类型说明符 标识符 模板参数：template class 标识符 例 9-1 函数模板的示例/9_1.cpp#include using namespace std;t

2、emplate /定义函数模板 void outputArray(const T*array,int count)for(int i=0;i count;i+)cout arrayi ;cout endl;int main()const int A_COUNT=8,B_COUNT=8,C_COUNT=20;int a A_COUNT=1,2,3,4,5,6,7,8;double bB_COUNT=1.1,2.2,3.3,4.4,5.5,6.6,7.7,8.8;char cC_COUNT=Welcome!;cout a array contains:endl;outputArray(a,A_CO

3、UNT);cout b array contains:endl;outputArray(b,B_COUNT);cout c array contains:endl;outputArray(c,C_COUNT);return 0;运行结果如下：a array contains:1 2 3 4 5 6 7 8 如果数组元素是类的对象，需要该对象所属类重载了流插入运算符“”b array contains:1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 c array contains:W e l c o m e!注意 一个函数模板并非自动可以处理所有类型的数据 只有能够进行函数模板

4、中运算的类型，可以作为类型实参 自定义的类，需要重载模板中的运算符，才能作为类型实参 类模板 类模板的作用 使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类模板的声明 类模板：template class 类名 类成员声明;如果需要在类模板以外定义其成员函数，则要采用以下的形式：template 类型名 类名:函数名（参数表）例 9-2 类模板示例#include#include using namespace std;struct Student int id;/学号 float gpa

5、;/平均分;template class Store/类模板：实现对任意类型数据进行存取 private:T item;/item用于存放任意类型的数据 bool haveValue;/haveValue标记item是否已被存入内容 public:Store();T&getElem();/提取数据函数 void putElem(const T&x);/存入数据函数;template Store:Store():haveValue(false)template T&Store:getElem()/如试图提取未初始化的数据，则终止程序 if(!haveValue)cout No item pres

6、ent!endl;exit(1);/使程序完全退出，返回到操作系统。return item;/返回item中存放的数据 template void Store:putElem(const T&x)/将haveValue 置为true，表示item中已存入数值 haveValue=true;item=x;/将x值存入item int main()Store s1,s2;s1.putElem(3);s2.putElem(-7);cout s1.getElem()s2.getElem()endl;class Store private:int item;bool haveValue;public:S

7、tore();int&getElem();void putElem(const int&x);Student g=1000,23;Store s3;s3.putElem(g);cout The student id is s3.getElem().id endl;Store d;cout Retrieving object D.;cout d.getElem()endl /d未初始化，执行函数D.getElement()时导致程序终止 return 0;线性群体的概念 群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一

8、个元素、第二个元素等。非线性群体不用位置顺序来标识元素。线性群体中的元素次序与其逻辑位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。数组类模板 静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修改。动态数组由一系列位置连续的，任意数量相同类型的元素组成。优点：其元素个数可在程序运行时改变。vector就是用类模板实现的动态数组。例 9-3 动态数组类模板程序#ifndef ARRAY_H#define ARRAY_H 第一个元素 第二个元素 第三个元素最后

9、一个元素class Store private:Student item;bool haveValue;public:Store();Student&getElem();void putElem(const Student&x);#include template /数组类模板定义 class Array private:T*list;/用于存放动态分配的数组内存首地址 int size;/数组大小（元素个数）public:Array(int sz=50);/构造函数 Array(const Array&a);/复制构造函数 Array();/析构函数 Array&operator=(cons

10、t Array&rhs);/重载=“T&operator (int i);/重载”const T&operator (int i)const;/重载”常函数 operator T*();/重载到T*类型的转换 operator const T*()const;int getSize()const;/取数组的大小 void resize(int sz);/修改数组的大小;为什么有的函数返回引用 如果一个函数的返回值是一个对象的值，就是右值，不能成为左值。如果返回值为引用。由于引用是对象的别名，通过引用可以改变对象的值，因此是左值。template Array:Array(int sz)/构造函数

11、 assert(sz=0);/sz为数组大小（元素个数），应当非负 size=sz;/将元素个数赋值给变量size list=new T size;/动态分配size个T类型的元素空间 template Array:Array()/析构函数 delete list;template Array:Array(const Array&a)/复制构造函数 size=a.size;/从对象x取得数组大小，并赋值给当前对象的成员 list=new Tsize;/动态分配n个T类型的元素空间 for(int i=0;i size;i+)/从对象X复制数组元素到本对象 listi=a.listi;/重载=运

12、算符，将对象rhs赋值给本对象。实现对象之间的整体赋值 template Array&Array:operator=(const Array&rhs)if(&rhs!=this)/如果本对象中数组大小与rhs不同，则删除数组原有内存，然后重新分配 if(size!=rhs.size)delete list;/删除数组原有内存 size=rhs.size;/设置本对象的数组大小 list=new Tsize;/重新分配size个元素的内存 /从对象X复制数组元素到本对象 for(int i=0;i size;i+)listi=rhs.listi;return*this;/返回当前对象的引用 /重

13、载下标运算符，实现与普通数组一样通过下标访问元素，具有越界检查功能 template T&Array:operator(int n)assert(n=0&n size);/检查下标是否越界 return listn;/返回下标为n的数组元素 template const T&Array:operator(int n)const assert(n=0&n size);/检查下标是否越界 return listn;/返回下标为n的数组元素/重载指针转换运算符，将Array类的对象名转换为T类型的指针 template Array:operator T*()return list;/返回当前对象中私

14、有数组的首地址 指针转换运算符的作用#include using namespace std;void read(int*p,int n)for(int i=0;i pi;int main()int a10;read(a,10);return 0;#include Array.h#include using namespace std;void read(int*p,int n)for(int i=0;i pi;int main()Array a(10);read(a,10);return 0;/取当前数组的大小 template int Array:getSize()const return

15、 size;/将数组大小修改为sz template void Array:resize(int sz)assert(sz=0);/检查sz是否非负 if(sz=size)/如果指定的大小与原有大小一样，什么也不做 return;T*newList=new T sz;/申请新的数组内存 int n=(sz size)?sz:size;/将sz与size中较小的一个赋值给n /将原有数组中前n个元素复制到新数组中 for(int i=0;i n;i+)newListi=listi;delete list;/删除原数组 list=newList;/使list指向新数组 size=sz;/更新siz

16、e#endif /ARRAY_H 例 9-4 数组类应用举例 例 9-4 Array 类的应用 求范围2N中的质数，N在程序运行时由键盘输入。#include#include#include Array.h using namespace std;int main()/用来存放质数的数组，初始状态有10个元素 Array a(10);int n,count=0;cout=2 as upper limit for prime numbers:;cin n;for(int i=2;i=n;i+)/检查i是否能被比它小的质数整除 bool isPrime=true;for(int j=0;j cou

17、nt;j+)/若i被aj整除，说明i不是质数 if(i%aj=0)isPrime=false;break;if(isPrime)if(count=a.getSize()a.resize(count*2);acount+=i;for(int i=0;i count;i+)cout setw(8)ai;cout endl;return 0;链表的概念与结点类模板 顺序访问的线性群体链表类 链表是一种动态数据结构，可以用来表示顺序访问的线性群体。链表是由系列结点组成的，结点可以在运行时动态生成。每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。如果链表每个结点中只有一个指向后继

18、结点的指针，则该链表称为单链表。单链表 单链表的结点类模板 template class Node private:Node*next;public:T data;Node(const T&item,Node*next=0);void insertAfter(Node*p);Node*deleteAfter();Node*nextNode()const;在结点之后插入一个结点 template void Node:insertAfter(Node*p)/p 节点指针域指向当前节点的后继节点 p-next=next;next=p;/当前节点的指针域指向 p 删除结点之后的结点 Node*Node

19、:deleteAfter(void)Node*tempPtr=next;if(next=0)return 0;next=tempPtr-next;return tempPtr;例 9-5 结点类模扳/Node.h#ifndef NODE_H#define NODE_H/类模板的定义 template class Node private:Node*next;/指向后继结点的指针 public:T data;/数据域 Node(const T&data,Node*next=0);/构造函数 void insertAfter(Node*p);/在本结点之后插入一个同类结点p Node*delete

20、After();/删除本结点的后继结点，并返回其地址 Node*nextNode();/获取后继结点的地址 const Node*nextNode()const;/获取后继结点的地址;/类的实现部分 /构造函数，初始化数据和指针成员 template Node:Node(const T&data,Node*next=0):data(data),next(next)/返回后继结点的指针 template Node*Node:nextNode()return next;/返回后继结点的指针 template const Node*Node:nextNode()const return next;/

21、在当前结点之后插入一个结点p template void Node:insertAfter(Node*p)p-next=next;/p结点指针域指向当前结点的后继结点 next=p;/当前结点的指针域指向p /删除当前结点的后继结点，并返回其地址 template Node*Node:deleteAfter()Node*tempPtr=next;/将欲删除的结点地址存储到tempPtr中 if(next=0)/如果当前结点没有后继结点，则返回空指针 return 0;next=tempPtr-next;/使当前结点的指针域指向tempPtr的后继结点 return tempPtr;/返回被删除

22、的结点的地址#endif/NODE_H 链表的基本操作 生成链表 插入结点 查找结点 删除结点 遍历链表 清空链表 例 9-6 链表类模板/LinkedList.h#ifndef LINKEDLIST_H#define LINKEDLIST_H#include Node.h template class LinkedList private:/数据成员：Node*front,*rear;/表头和表尾指针 Node*prevPtr,*currPtr;/记录表当前遍历位置的指针，由插入和删除操作更新 int size;/表中的元素个数 int position;/当前元素在表中的位置序号。由函数r

23、eset使用 /函数成员：/生成新结点，数据域为item，指针域为ptrNext Node*newNode(const T&item,Node*ptrNext=NULL);/释放结点 void freeNode(Node*p);/将链表L 拷贝到当前表（假设当前表为空）。/被拷贝构造函数、operator=调用 void copy(const LinkedList&L);public:LinkedList();/构造函数 LinkedList(const LinkedList&L);/拷贝构造函数 LinkedList();/析构函数 LinkedList&operator=(const Li

24、nkedList&L);/重载赋值运算符 int getSize()const;/返回链表中元素个数 bool isEmpty()const;/链表是否为空 void reset(int pos=0);/初始化游标的位置 void next();/使游标移动到下一个结点 bool endOfList()const;/游标是否到了链尾 int currentPosition()const;/返回游标当前的位置 void insertFront(const T&item);/在表头插入结点 void insertRear(const T&item);/在表尾添加结点 void insertAt(c

25、onst T&item);/在当前结点之前插入结点 void insertAfter(const T&item);/在当前结点之后插入结点 T deleteFront();/删除头结点 void deleteCurrent();/删除当前结点 T&data();/返回对当前结点成员数据的引用 const T&data()const;/返回对当前结点成员数据的常引用 /清空链表：释放所有结点的内存空间。被析构函数、operator=调用 void clear();template /生成新结点 Node*LinkedList:newNode(const T&item,Node*ptrNext)N

26、ode*p;p=new Node(item,ptrNext);if(p=NULL)cout Memory allocation failure!n;exit(1);return p;template void LinkedList:freeNode(Node*p)/释放结点 delete p;template void LinkedList:copy(const LinkedList&L)/链表复制函数 Node*p=L.front;/P用来遍历L int pos;while(p!=NULL)/将L中的每一个元素插入到当前链表最后 insertRear(p-data);p=p-nextNode

27、();if(position=-1)/如果链表空,返回 return;/在新链表中重新设置prevPtr和currPtr prevPtr=NULL;currPtr=front;for(pos=0;pos!=position;pos+)prevPtr=currPtr;currPtr=currPtr-nextNode();template /构造一个新链表，将有关指针设置为空，size为0，position为-1 LinkedList:LinkedList():front(NULL),rear(NULL),prevPtr(NULL),currPtr(NULL),size(0),position(-

28、1)template LinkedList:LinkedList(const LinkedList&L)/拷贝构造函数 front=rear=NULL;prevPtr=currPtr=NULL;size=0;position=-1;copy(L);template LinkedList:LinkedList()/析构函数 clear();template LinkedList&LinkedList:operator=(const LinkedList&L)/重载=if(this=&L)/不能将链表赋值给它自身 return*this;clear();copy(L);return*this;te

29、mplate int LinkedList:getSize()const/返回链表大小的函数 return size;template bool LinkedList:isEmpty()const/判断链表为空否 return size=0;template void LinkedList:reset(int pos)/将链表当前位置设置为pos int startPos;if(front=NULL)/如果链表为空，返回 return;if(pos size-1)/如果指定位置不合法，中止程序 cerr Reset:Invalid list position:pos nextNode();pr

30、evPtr=front;startPos=1;for(position=startPos;position!=pos;position+)prevPtr=currPtr;currPtr=currPtr-nextNode();template void LinkedList:next()/将prevPtr和currPtr向前移动一个结点 if(currPtr!=NULL)prevPtr=currPtr;currPtr=currPtr-nextNode();position+;template bool LinkedList:endOfList()const/判断是否已达表尾 return cur

31、rPtr=NULL;template int LinkedList:currentPosition()const /返回当前结点的位置 return position;template void LinkedList:insertFront(const T&item)/将item插入在表头 if(front!=NULL)/如果链表不空则调用Reset reset();insertAt(item);/在表头插入 template void LinkedList:insertRear(const T&item)/在表尾插入结点 Node*nNode;prevPtr=rear;nNode=newNo

32、de(item);/创建新结点 if(rear=NULL)/如果表空则插入在表头 front=rear=nNode;else rear-insertAfter(nNode);rear=nNode;currPtr=rear;position=size;size+;template void LinkedList:insertAt(const T&item)/将item插入在链表当前位置 Node*nNode;if(prevPtr=NULL)/插入在链表头，包括将结点插入到空表中 nNode=newNode(item,front);front=nNode;else/插入到链表之中.将结点置于pre

33、vPtr之后 nNode=newNode(item);prevPtr-insertAfter(nNode);if(prevPtr=rear)/正在向空表中插入，或者是插入到非空表的表尾 rear=nNode;/更新rear position=size;/更新position currPtr=nNode;/更新currPtr size+;/使size增值 template void LinkedList:insertAfter(const T&item)/将item 插入到链表当前位置之后 Node*p;p=newNode(item);if(front=NULL)/向空表中插入 front=cu

34、rrPtr=rear=p;position=0;else/插入到最后一个结点之后 if(currPtr=NULL)currPtr=prevPtr;currPtr-insertAfter(p);if(currPtr=rear)rear=p;position=size;else position+;prevPtr=currPtr;currPtr=p;size+;/使链表长度增值 template T LinkedList:deleteFront()/删除表头结点 T item;reset();if(front=NULL)cerr Invalid deletion!data;deleteCurren

35、t();return item;template void LinkedList:deleteCurrent()/删除链表当前位置的结点 Node*p;if(currPtr=NULL)/如果表空或达到表尾则出错 cerr Invalid deletion!nextNode();/将其从链表中分离 else/分离prevPtr之后的一个内部结点，保存其地址 p=prevPtr-deleteAfter();if(p=rear)/如果表尾结点被删除 rear=prevPtr;/新的表尾是prevPtr position-;/position自减 currPtr=p-nextNode();/使curr

36、Ptr越过被删除的结点 freeNode(p);/释放结点，并 size-;/使链表长度自减 template T&LinkedList:data()/返回一个当前结点数值的引用 if(size=0|currPtr=NULL)/如果链表为空或已经完成遍历则出错 cerr Data:invalid reference!data;template void LinkedList:clear()/清空链表 Node*currPosition,*nextPosition;currPosition=front;while(currPosition!=NULL)nextPosition=currPosit

37、ion-nextNode();/取得下一结点的地址 freeNode(currPosition);/删除当前结点 currPosition=nextPosition;/当前指针移动到下一结点 front=rear=NULL;prevPtr=currPtr=NULL;size=0;position=-1;#endif /LINKEDLIST_H 例 9-7 链表类应用举例 从键盘输入10个整数，用这些整数值作为结点数据，生成一个链表，按顺序输出链表中结点的数值。然后从键盘输入一个待查找整数，在链表中查找该整数，若找到则删除该整数所在的结点（如果出现多次，全部删除），然后输出删除结点以后的链表。在

38、程序结束之前清空链表。/9_7.cpp#include#include LinkedList.h using namespace std;int main()LinkedList list;for(int i=0;i item;list.insertFront(item);cout List:;list.reset();while(!list.endOfList()cout list.data();list.next();cout endl;int key;cout key;list.reset();while(!list.endOfList()if(list.data()=key)list.

39、deleteCurrent();list.next();cout List:;list.reset();while(!list.endOfList()cout list.data();list.next cout endl;return 0;栈类 栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。栈是一种后进先出的数据结构。栈示意图 栈的应用举例表达式处理 栈的基本状态 栈空 栈满 一般状态 栈空 栈中没有元素（以数组容纳的栈为例）栈满 栈中元素个数达到上限（以数组容纳的栈为例）一般状态 栈中有元素，但未达到栈满状态（以数组容纳的栈为例）栈的基本操作 初始化 入栈 出栈 清空

40、栈 访问栈顶元素 检测栈的状态（满、空）例 9-8 栈类模板/Stack.h#ifndef STACK_H#define STACK_H#include template class Stack private:T listSIZE;int top;public:Stack();void push(const T&item);T pop();void clear();const T&peek()const;bool isEmpty()const;bool isFull()const;/模板的实现 template Stack:Stack():top(-1)template void Stack

41、:push(const T&item)assert(!isFull();list+top=item;template T Stack:pop()assert(!isEmpty();return listtop-;template const T&Stack:peek()const assert(!isEmpty();return listtop;/返回栈顶元素 template bool Stack:isEmpty()const return top=-1;template bool Stack:isFull()const return top=SIZE-1;template void Sta

42、ck:clear()top=-1;#endif/STACK_H 例 9-9 栈的应用 例 9-9 一个简单的整数计算器 实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算3+5则输入3 5 +。乘方运算符用表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入c。当键入q时程序结束。/Calculator.h#ifndef CALCULATOR_H#define CALCULATOR_H#include Stack.h/包含栈类模板定义文件 class Calculator /计算器类 priv

43、ate:Stack s;/操作数栈 void enter(double num);/将操作数num压入栈 /连续将两个操作数弹出栈，放在opnd1和opnd2中 bool getTwoOperands(double&opnd1,double&opnd2);void compute(char op);/执行由操作符op指定的运算 public:void run();/运行计算器程序 void clear();/清空操作数栈;#endif/CALCULATOR_H /Calculator.cpp#include Calculator.h#include#include#include using

44、namespace std;/工具函数，用于将字符串转换为实数 inline double stringToDouble(const string&str)istringstream stream(str);/字符串输入流 double result;stream result;return result;void Calculator:enter(double num)/将操作数num压入栈 s.push(num);bool Calculator:getTwoOperands(double&opnd1,double&opnd2)if(s.isEmpty()/检查栈是否空 cerr Missi

45、ng operand!endl;return false;opnd1=s.pop();/将右操作数弹出栈 if(s.isEmpty()/检查栈是否空 cerr Missing operand!endl;return false;opnd2=s.pop();/将左操作数弹出栈 return true;void Calculator:compute(char op)/执行运算 double operand1,operand2;bool result=getTwoOperands(operand1,operand2);if(result)/如果成功，执行运算并将运算结果压入栈 switch(op)c

46、ase+:s.push(operand2+operand1);break;case-:s.push(operand2-operand1);break;case*:s.push(operand2*operand1);break;case/:if(operand1=0)/检查除数是否为0 cerr Divided by 0!endl;s.clear();/除数为0时清空栈 else s.push(operand2/operand1);break;case:s.push(pow(operand2,operand1);break;default:cerr Unrecognized operator!e

47、ndl;break;cout =s.peek()str,str!=q)switch(str0)case c:s.clear();break;case-:/遇-需判断是减号还是负号 if(str.size()1)enter(stringToDouble(str);else compute(str0);break;case+:/遇到其它操作符时 case*:case/:case:compute(str0);break;default:/若读入的是操作数，转换为整型后压入栈 enter(stringToDouble(str);break;void Calculator:clear()/清空操作数栈

48、s.clear();/9_9.cpp#include Calculator.h int main()Calculator c;c.run();return 0;队列类模板 队列是只能向一端添加元素，从另一端删除元素的线性群体 队列的基本状态 队空 队满 一般状态 队空 队列中没有元素（以数组容纳的队列为例）队满 队列中元素个数达到上限（以数组容纳的队列为例）一般状态 队列中有元素，但未达到队满状态（以数组容纳的队列为例）循环队列 在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。例 9-10 队列类模板/Queue.h#ifndef QUE

49、UE_H#define QUEUE_H#include /类模板的定义 template class Queue private:int front,rear,count;/队头指针、队尾指针、元素个数 T listSIZE;/队列元素数组 public:Queue();/构造函数，初始化队头指针、队尾指针、元素个数 void insert(const T&item);/新元素入队 T remove();/元素出队 void clear();/清空队列 const T&getFront()const;/访问队首元素 /测试队列状态 int getLength()const;/求队列长度 boo

50、l isEmpty()const;/判断队列空否 bool isFull()const;/判断队列满否 ;/构造函数，初始化队头指针、队尾指针、元素个数 template Queue:Queue():front(0),rear(0),count(0)template void Queue:insert(const T&item)/向队尾插入元素 assert(count!=SIZE);count+;/元素个数增1 listrear=item;/向队尾插入元素 rear=(rear+1)%SIZE;/队尾指针增1，用取余运算实现循环队列 template T Queue:remove()asse