第九章群体类和群体数据的组织

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

2、线性群体中，又可按照访问元素的不同方法分为元素的不同方法分为直接访问直接访问、顺序访问顺序访问和和索引访问索引访问。第一个元素第二个元素第三个元素最后一个元素群体类群体类 直接访问群体直接访问群体-数组类数组类 顺序访问群体顺序访问群体-链表类链表类 栈类栈类 队列类队列类群群体数据的组织体数据的组织插入排序插入排序 选择排序选择排序 交换排序交换排序顺序查找顺序查找 折半查找折半查找5本章主要内容本章主要内容l模板模板l群体类群体类l群体数据的组织群体数据的组织l小结与复习建议小结与复习建议9.1 模板模板lC+C+最重要的特性之一就是代码重用，为了实现代码重最重要的特性之一就是代码重用，为

3、了实现代码重用，代码必须具有通用性。用，代码必须具有通用性。 通用代码需要不受数据类型的影响，并且可以自通用代码需要不受数据类型的影响，并且可以自动适应数据类型的变化。这种程序设计类型称为参数动适应数据类型的变化。这种程序设计类型称为参数化程序设计。化程序设计。l模板是模板是C+C+支持参数化程序设计的工具，通过它可以实支持参数化程序设计的工具，通过它可以实现参数化多态性。现参数化多态性。 所谓参数化多态性，就是将程序所处理的对象的类所谓参数化多态性，就是将程序所处理的对象的类型参数化，使得一段程序可以用于处理多种不同类型型参数化，使得一段程序可以用于处理多种不同类型的对象。的对象。函数模板函

4、数模板类模板类模板9.1.1 函数模板函数模板l函数模板可以用来创建一个通用功能的函函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重数，以支持多种不同形参，进一步简化重载函数的函数体设计。载函数的函数体设计。l定义方法：定义方法：template 函数定义函数定义 templatetemplate T T abs(abs(T T x) x) return x 0? -x : x; return x 0? -x : x; 8其中：其中： template为模板关键字。为模板关键字。 模板参数表中的类型为参数化类型，也称可变类型模板参数表中的类型为参数化类型，也称可变类型，

5、类型名为，类型名为class (或或typename)；模板参数表中的类模板参数表中的类型也可包含普通类型。型也可包含普通类型。求绝对值函数的模板求绝对值函数的模板#include #include using namespace std;using namespace std;templatetemplate T T abs(abs(T T x) x) return x 0? -x : x;return x 0? -x : x; intint main() main() intint n = -5; n = -5;double d = -5.5;double d = -5.5;coutcou

6、t abs(abs(n n) ) endlendl; ;coutcout abs(abs(d d) ) endlendl; ;return 0;return 0; 运行结果：运行结果：5 55.55.5求绝对值函数的模板分析求绝对值函数的模板分析l编译器从调用编译器从调用abs()时实参的类型，推导出时实参的类型，推导出函数模板的类型参数。例如，对于调用表函数模板的类型参数。例如，对于调用表达式达式abs(n)，由于实参，由于实参n为为int型，所以推型，所以推导出模板中类型参数导出模板中类型参数T为为int。l当类型参数的含义确定后，编译器将以函当类型参数的含义确定后，编译器将以函数模板为样

7、板，生成一个函数：数模板为样板，生成一个函数：int abs(int x) return x 0 ? x : x;函数模板的重载函数模板的重载C+规定：函数模板可以重载。它既可以用函规定：函数模板可以重载。它既可以用函数模板重载，也可以用普通函数重载。数模板重载，也可以用普通函数重载。之所以允许之所以允许重载是因为函数模板的参数重载是因为函数模板的参数T T在实例化时实参类型在实例化时实参类型无隐式转换功能。无隐式转换功能。下面是函数模板重载的实例：下面是函数模板重载的实例： template /求两个同类型求两个同类型T的变量中的最大者的变量中的最大者 T max(T x, T y) ret

8、urn(xy)?x:y;template /重载 max 函数模板，求三个同类型 T 的变量中的最大者 T max(T x, T y, T z) T t; t=(xy)?x:y; return(tz)?t:z; 在下面的函数调用中： void fun(int i, char c, float f) coutmax(i,i); /正确! coutmax(c,c); /正确! coutmax(i,c); /错误! 采用函数模板生成的模板函数虚实结合时无隐式类型转换功能 coutmax(f,i); /错误! 采用函数模板生成的模板函数虚实结合时无隐式类型转换功能 / 上例代码中的上例代码中的max(

9、i,c)和和max(f,i)，由于模板函数在调用时，由于模板函数在调用时其参数类型不同，所以编译器报错。其参数类型不同，所以编译器报错。欲解决上述问题，可用一普通函数重载函数模板，欲解决上述问题，可用一普通函数重载函数模板，此时，此时，只需声明该普通函数的接口即可。请看下述示例代码：只需声明该普通函数的接口即可。请看下述示例代码：template /函数模板的定义函数模板的定义 T max(T x, T y) return(xy)?x:y; double max(double, double);/重载上述函数模重载上述函数模板，重载时只需给出函数接口板，重载时只需给出函数接口/测试函数 voi

10、d main() int x=3,y=4; long l=5; double a=1.1, b=3.4; coutmax(x,y)endl; /调用模板函数，模板参数类型为 int coutmax(a,b)endl; /调用模板函数，模板参数类型为 double coutmax(l,a)endl; /调用重载的模板函数，虚实结合时类型自动进行隐式转换 / 在使用上述 template T max(T x, T y)函数模板时， 若模板参数的类型为char*，则此时模板函数为 char* max(char* x, char* y) return(xy)?(x):(y); /该语句为何语义？ 该函

11、数的作用是比较两个字符串指针，而不是比较两个指该函数的作用是比较两个字符串指针，而不是比较两个指针所指向的字符串的内容，这与我们所定义的函数模板的语义针所指向的字符串的内容，这与我们所定义的函数模板的语义相违背。相违背。 因此，此时须提供一个可以替换该函数模板实例的函数，因此，此时须提供一个可以替换该函数模板实例的函数，用来替换的函数称为特定的模板函数，即：用来替换的函数称为特定的模板函数，即：char* max(char* c1, char* c2) return (strcmp(c1,c2)?(c1):(c2); 9.1.2 类模板的作用类模板的作用 使用类模板使用户可以为类声明一种模使用

12、类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类意类型（包括基本类型的和用户自定义类型）。型）。l类模板：类模板：template template class class 类名类名 类成员声明类成员声明 l如果需要在类模板以外定义其成员函数，则要如果需要在类模板以外定义其成员函数，则要采用以下的形式：采用以下的形式：template template 类型名类型名 类名类名 :函数名函数名( (参数表参数表) )类模板的声明

13、类模板的声明template class StoreT& Store:getElem()例例9-2 类模板应用举例类模板应用举例#include #include #include #include using namespace std;using namespace std;/ / 结构体结构体StudentStudentstructstruct Student Student intint id; / id; /学号学号 float float gpagpa; /; /平均分平均分; ; template class Store /class Store /类模板：实现对任意类型

14、数据进行存取类模板：实现对任意类型数据进行存取private:private:T item; / item / item用于存放任意类型的数据用于存放任意类型的数据boolbool haveValuehaveValue; / ; / haveValuehaveValue标记标记itemitem是否已被存入内容是否已被存入内容public:public:Store();Store();/ / 缺省形式（无形参）的构造函数缺省形式（无形参）的构造函数T &getElem();/提取数据函数提取数据函数void putElem(const T &x); / /存入数据函数存入数据函数

15、;/以下实现各成员函数。以下实现各成员函数。template template /缺省构造函数的实现缺省构造函数的实现 Store:Store(): haveValue(falsehaveValue(false) ) 19template /template /提取数据函数的实现提取数据函数的实现T &Store:getElem() /如试图提取未初始化的数据，则终止程序如试图提取未初始化的数据，则终止程序if (!if (!haveValuehaveValue) ) coutcout No item present! No item present! endlendl; ;exit(

16、1);exit(1);/使程序完全退出，返回到操作系统。使程序完全退出，返回到操作系统。 return item; / return item; / 返回返回itemitem中存放的数据中存放的数据 template template /存入数据函数的实现存入数据函数的实现 void Store:putElem(const T &x) / / 将将haveValuehaveValue 置为置为truetrue，表示，表示itemitem中已存入数值中已存入数值haveValuehaveValue = true; = true;item = x;item = x;/ / 将将x x值存入

17、值存入itemitem intint main() main() Store s1, s2; s1, s2;s1.putElem(3);s1.putElem(3);s2.putElem(-7);s2.putElem(-7);coutcout s1.getElem() s2.getElem() s1.getElem() s2.getElem() endlendl; ;Student g = 1000, 23 ;Student g = 1000, 23 ;Store s3; s3;s3.putElem(g); s3.putElem(g); coutcout The student id is s3

18、.getElem().id The student id is s3.getElem().id endlendl; ;Store d;coutcout Retrieving object D. ; Retrieving object D. ;coutcout d.getElemd.getElem() () endlendl /由于由于d d未经初始化未经初始化, ,执行函数执行函数D.getElementD.getElement()()时导致程序终止时导致程序终止return 0;return 0; 9.2 群体类群体类线性群体线性群体群体的概念群体的概念直接访问群体直接访问群体-数组类数组类

19、顺序访问群体顺序访问群体-链表类链表类栈类栈类队列类队列类9.2.1 群体的概念群体的概念群体是指由多个数据元素组成的集合体。群体是指由多个数据元素组成的集合体。群体可以分为两个大类：群体可以分为两个大类：线性群体线性群体和和非线性群非线性群体体。线性群体中的元素按位置排列有序，可以线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。非线性群体不用位置顺序来标识元素。线性群体的概念线性群体的概念 线性群体中的元素次序与其位置关系是线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素对应的。在线

20、性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引的不同方法分为直接访问、顺序访问和索引访问。访问。 在本章我们只介绍直接访问和顺序访问。在本章我们只介绍直接访问和顺序访问。第一个元素第二个元素第三个元素最后一个元素9.2.2 数组数组l静态数组是具有固定元素个数的群体，其静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。中的元素可以通过下标直接访问。 缺点：大小在编译时就已经确定，在运缺点：大小在编译时就已经确定，在运行时无法修改。行时无法修改。l动态数组由一系列位置连续的，任意数量动态数组由一系列位置连续的，任意数量相同类型的元素组成。相同类型的元素组成。 优

21、点：其元素个数可在程序运行时改变。优点：其元素个数可在程序运行时改变。l动态数组类模板：例动态数组类模板：例9-3（Array.h）# #ifndefifndef ARRAY_H ARRAY_H#define ARRAY_H#define ARRAY_H#include #include template class template / /数组类模板定义数组类模板定义class Array class Array private:private:T* * list;/ list;/用于存放动态分配的数组内存首地址用于存放动态分配的数组内存首地址intint size; size; /数组大小

22、（元素个数）数组大小（元素个数）public:public:Array(intArray(int szsz = 50); = 50);/构造函数构造函数Array(constArray(const Array Array &a); &a);/拷贝构造函数拷贝构造函数Array();Array();/析构函数析构函数ArrayArray & operator & operator = (const Array (const Array & &rhsrhs); /); /重载重载=“=“T & operator & operator

23、( (intint i); / i); /重载重载”const const T & operator ( & operator (intint i) const; i) const;operator operator T * (); (); /重载到重载到T T* *类型的转换类型的转换operator const operator const T * () const; () const;intint getSizegetSize() const;() const;/取数组的大小取数组的大小void void resize(intresize(int szsz););/修改数

24、组的大小修改数组的大小;26数组类模板的构造函数数组类模板的构造函数/ / 构造函数构造函数template template Array:Array:Array(intArray(int szsz) ) /szsz为数组大小（元素个数），应当非负为数组大小（元素个数），应当非负 / / 将元素个数赋值给变量将元素个数赋值给变量sizesizesize = size = szsz; ; /动态分配动态分配sizesize个个T T类型的元素空间类型的元素空间list = new T size;list = new T size; 数组数组类模板的类模板的拷贝构造函数拷贝构造函数/拷贝构造函数拷

25、贝构造函数template template Array:Array:Array(constArray(const Array &a) Array &a) /从对象从对象a a取得数组大小，并赋值给当前对象的成员取得数组大小，并赋值给当前对象的成员size = a.size;/为对象申请内存并进行出错检查为对象申请内存并进行出错检查list = new Tsize; / / 动态分配动态分配n n个个T T类型的元素空间类型的元素空间/从对象从对象X X复制数组元素到本对象复制数组元素到本对象 for (int i = 0; i size; i+)listi = a.listi

26、; 浅拷贝浅拷贝 list sizeaa的数组元素占用的内存拷贝前拷贝前 list sizeaa的数组元素占用的内存拷贝后拷贝后 list sizebintint main() main() Array Array a(10); a(10); . . Array Array b(ab(a);); . . template template Array:Array(Array:Array(const Array& x) const Array& x) size = size = x.sizex.size; ; list = list = x.listx.list; ; templ

27、ate template Array:Array:Array(constArray(const Array &a) Array &a) size = a.size;list = new Tsize; for (int i = 0; i size; i+)listi = a.listi; 深拷贝深拷贝 list sizeaa的数组元素占用的内存拷贝前拷贝前 list sizeaa的数组元素占用的内存拷贝后拷贝后 list sizebb的数组元素占用的内存数组数组类类模板模板的的重载重载=运算符函数运算符函数/重载重载“=”“=”运算符运算符template template Ar

28、ray &Array:Array &Array:operator = (const Array &rhs) if (&if (&rhsrhs != this) != this) if (size != if (size != rhs.sizerhs.size) ) delete list;delete list;/删除数组原有内存删除数组原有内存size = size = rhs.sizerhs.size; ;/设置设置本对象的数组大小本对象的数组大小list = new list = new TsizeTsize; /重新分配重新分配n n个元素的内存

29、个元素的内存 / /从对象从对象X X复制数组元素到本对象复制数组元素到本对象 for (for (intint i = 0; i size; i+) i = 0; i size; i+)listilisti = = rhs.listirhs.listi; return return * *this;this;/返回当前对象的引用返回当前对象的引用 数组数组类模板的类模板的重载下标操作符函数重载下标操作符函数template template T &Array:T &Array:operator (int n) assert(nassert(n = 0 & n = 0

30、& n size);/越界检查越界检查return return listnlistn; / /返回下标为返回下标为n n的数组元素的数组元素 template template const T &Array:const T &Array:operator (int n) const assert(nassert(n = 0 & n = 0 & n size); /越界检查越界检查return return listnlistn; / /返回下标为返回下标为n n的数组元素的数组元素 数组类的重载下标操作符函数数组类的重载下标操作符函数template

31、T& Array:operator (int n) / 检查下标是否越界检查下标是否越界 if (n size-1) Error(indexOutOfRange,n); / 返回下标为返回下标为n的数组元素的数组元素 return alistn;重载指针转换操作符重载指针转换操作符template template Array:Array:operator T * () return list;return list; /返回返回当前对象中私有当前对象中私有数组的首地址数组的首地址 template template Array:Array:operator const T * ()

32、const return list;return list; /返回返回当前对象中私有当前对象中私有数组的首地址数组的首地址 指针转换运算符的作用指针转换运算符的作用#include #include using namespace std;using namespace std;void void read(read(int *p, , intint n) n) for ( for (intint i = 0; i n; i+) i = 0; i pipi; intint main() main() int a10; read(read(a, 10);, 10); return 0; ret

33、urn 0; #include Array.h#include #include using namespace std;using namespace std;void void read(read(int *p, , intint n) n) for ( for (intint i = 0; i n; i+) i = 0; i pipi; intint main() main() Array a(10); read(read(a, 10);, 10); return 0; return 0; ArrayArray类的应用类的应用l例例9-4求范围求范围2N中的质数，中的质数，N在程序在程序

34、运行时由键盘输入。运行时由键盘输入。 质数（质数（prime numberprime number）又称素数，有无限个。一个大于）又称素数，有无限个。一个大于1 1的自然数，除了的自然数，除了1 1和它本身外，不能被其他自然数（质数）和它本身外，不能被其他自然数（质数）整除。整除。#include #include #include #include #include Array.husing namespace std;using namespace std;intint main() main() Array a(10);/ / 用来存放质数的数组，初始状态有用来存放质数的数组，初始状态有

35、1010个元素。个元素。intint n, count = 0; n, count = 0;coutcout = 2 as upper limit for prime numbers: ; = 2 as upper limit for prime numbers: ;cincin n; n;for (for (intint i = 2; i = n; i+) i = 2; i = n; i+) boolbool isPrimeisPrime = true; = true;for (for (intint j = 0; j count; j+) j = 0; j count; j+)if (i

36、% if (i % aj = 0) = 0) /若若i i被被ajaj 整除，说明整除，说明i i不是质数不是质数isPrimeisPrime = false; break; = false; break; if (if (isPrimeisPrime) ) if (count = if (count = a.getSizea.getSize()() a.resize(counta.resize(count * * 2); 2); acount+ = i; for (for (intint i = 0; i count; i+) i = 0; i count; i+)coutcout setw

37、(8) setw(8) aiai;coutcout endlendl; ;return 0; return 0; 9.2.3 链表链表l链表是一种动态数据结构，可以用来表示链表是一种动态数据结构，可以用来表示顺序访问的线性群体。顺序访问的线性群体。l链表是由系列链表是由系列结点结点组成的，结点可以在运组成的，结点可以在运行时动态生成。行时动态生成。l每一个结点包括每一个结点包括数据域数据域和指向链表中下一和指向链表中下一个结点的个结点的指针指针（即下一个结点的地址）。（即下一个结点的地址）。如果链表每个结点中只有一个指向后继结如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。点

38、的指针，则该链表称为单链表。单链表单链表 data1 data1 data2 data2 data3 data3 datandatan NULL NULLheadheadrearrear单链表的结点类模板单链表的结点类模板template class template class Node class Node private:private: Node Node * *next;next;public:public: T data; data; Node(constNode(const T & T &item,Nodeitem,Node* * next = 0); next

39、= 0); void void insertAfter(NodeinsertAfter(Node * *p);p); Node Node * *deleteAfterdeleteAfter();(); Node Node * *nextNodenextNode() const;() const; ; 41在结点之后插入一个结点在结点之后插入一个结点 data1 data2 p datatemplate template void Node:void Node:insertAfter(Node *p) /p /p节点指针域指向当前节点的后继节点节点指针域指向当前节点的后继节点 p-next =

40、p-next = nextnext; ; next = p; / next = p; /当前节点的指针域指向当前节点的指针域指向p p 删除结点之后的结点删除结点之后的结点 data1 data2 data3Node Node * *Node:Node:deleteAfter(void) Node Node * *tempPtrtempPtr = next; = next; if (next = 0) if (next = 0) return 0; return 0; next = next = tempPtrtempPtr-next; -next; return return tempPtr

41、tempPtr; ; tempPtr链表的基本操作链表的基本操作l生成结点生成结点l插入结点插入结点l查找结点查找结点l删除结点删除结点l遍历链表遍历链表l清空链表清空链表链表类模板链表类模板( (例例9-6)9-6)# #ifndefifndef LINKEDLIST_H LINKEDLIST_H#define LINKEDLIST_H#define LINKEDLIST_H#include #include Node.hNode.h template template class class LinkedListLinkedList private:private:/数据成员：数据成员：N

42、ode Node * *front, front, * *rearrearNode Node * *prevPtrprevPtr, , * *currPtrcurrPtr; ; intint size; size;intint position; position;Node Node * *newNode(constnewNode(const T T & &item,Nodeitem,Node * *ptrNextptrNext=NULL);=NULL); void void freeNode(NodefreeNode(Node * *p);p);void void copy(

43、constcopy(const LinkedListLinkedList &L); &L);public:public:LinkedListLinkedList();();LinkedList(constLinkedList(const LinkedListLinkedList &L); &L); LinkedListLinkedList();();LinkedListLinkedList & operator = (const & operator = (const LinkedListLinkedList &L); &L);

44、intint getSizegetSize() const;() const;boolbool isEmptyisEmpty() const;() const;void void reset(intreset(int pos = 0 pos = 0void next();void next();boolbool endOfListendOfList() const;() const;intint currentPosition(voidcurrentPosition(void) const;) const;void void insertFront(constinsertFront(const

45、 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 deleteFrontdeleteFront();();void void deleteCurrentdeleteCur

46、rent();();T& data();T& data();const T& data() constconst T& data() constvoid clear();void clear();# #endifendif /LINKEDLIST_H /LINKEDLIST_H链表类应用举例链表类应用举例(例例9-7)l从键盘输入从键盘输入10个整数，用这些整数值作为结点个整数，用这些整数值作为结点数据，生成一个链表，按顺序输出链表中结点数据，生成一个链表，按顺序输出链表中结点的数值。的数值。l然后从键盘输入一个待查找整数，在链表中查然后从键盘输入一个待查找整数

47、，在链表中查找该整数，若找到则删除该整数所在的结点（找该整数，若找到则删除该整数所在的结点（如果出现多次，全部删除）。如果出现多次，全部删除）。l然后输出删除结点以后的链表。在程序结束之然后输出删除结点以后的链表。在程序结束之前清空链表。前清空链表。/9_7.cpp/9_7.cpp#include #include #include #include LinkedList.hLinkedList.h using namespace std;using namespace std;intint main() main() LinkedListLinkedList list; list;for (

48、for (intint i = 0; i 10; i+) i = 0; i item; item;list.insertFront(itemlist.insertFront(item);); coutcout List: ; List: ;list.resetlist.reset();();while (!while (!list.endOfListlist.endOfList() () coutcout list.datalist.data() ;() ;list.nextlist.next();(); coutcout endlendl; ;intint key; key;coutcout

49、 Please enter some integer key; key;list.resetlist.reset();();while (!while (!list.endOfListlist.endOfList() () if (if (list.datalist.data() = key) () = key) list.deleteCurrentlist.deleteCurrent();();list.nextlist.next();(); coutcout List: ; List: ;list.resetlist.reset();();while (!while (!list.endO

50、fListlist.endOfList() () coutcout list.datalist.data() ;() ;list.nextlist.next coutcout endlendl; ;return 0;return 0; 9.2.4 特殊的线性群体特殊的线性群体栈栈栈是只能从一端访问的线性群体，可以栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。访问的这一端称栈顶，另一端称栈底。ana2a1入栈出栈栈顶栈底栈的应用举例栈的应用举例函数调用函数调用main调调fun(参数参数)结束结束fun(参数参数)返回返回参数参数当前现场当前现场返回地址返回地址入栈入栈当前

51、现场当前现场返回地址返回地址出栈出栈参数参数出栈出栈当前现场当前现场 返回地址返回地址49栈的基本状态栈的基本状态l栈空栈空 栈中没有元素栈中没有元素l栈满栈满 栈中元素个数达到上限栈中元素个数达到上限l一般状态一般状态 栈中有元素，但未达到栈满状态栈中有元素，但未达到栈满状态栈顶ana1a0入栈出栈数组下标maxn10一般状态一般状态栈顶入栈出栈数组下标初始状态（栈空初始状态（栈空）maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满状态栈满状态5051栈的基本操作栈的基本操作l初始化初始化l入栈入栈l出栈出栈l清空栈清空栈l访问栈顶元素访问栈顶元素l检测栈的状态（满、空）检

52、测栈的状态（满、空）栈类模板栈类模板(例例9-8)/Stack.hStack.h# #ifndefifndef STACK_H STACK_H#define STACK_H#define STACK_H#include #include template class T, template SIZE = 50class Stack class Stack private:private:T T listSIZElistSIZE;intint top; top;public:public:Stack();Stack();void void push(constpush(const T &

53、item); T &item);T pop();T pop();void clear();void clear();const T &peek() const;const T &peek() const;boolbool isEmptyisEmpty() const;() const;boolbool isFullisFull() const;() const;/类的实现略类的实现略栈的应用栈的应用例例9.9 一个简单的整数计算器一个简单的整数计算器实现一个简单的整数计算器，能够进行加、实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输减、

54、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算例如，若要计算3+5则输入则输入3 5 +。乘方运算。乘方运算符用符用表示。每次运算在前次结果基础上进行，表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入若要将前次运算结果清除，可键入c。当键入。当键入q时程序结束。时程序结束。/Calculator.hCalculator.h# #ifndefifndef CALCULATOR_H CALCULATOR_H#define CALCULATOR_H#define CALCULATOR_H#

55、include #include Stack.hStack.h / / 包含栈类模板定义文件包含栈类模板定义文件class Calculator class Calculator /计算器类计算器类private:private:Stack s; s;/ / 操作数栈操作数栈void void enter(doubleenter(double num); num); /将操作数将操作数numnum压入栈压入栈/连续将两个操作数弹出栈，放在连续将两个操作数弹出栈，放在opnd1opnd1和和opnd2opnd2中中boolbool getTwoOperands(doublegetTwoOpera

56、nds(double &opnd1, double &opnd2); &opnd1, double &opnd2);void void compute(charcompute(char op); op); /执行由操作符执行由操作符opop指定的运算指定的运算public:public:void run();void run();/运行计算器程序运行计算器程序void clear();void clear();/清空操作数栈清空操作数栈;# #endifendif /CALCULATOR_H /CALCULATOR_H/Calculator.cppCalcula

57、tor.cpp#include #include Calculator.hCalculator.h #include #include #include #include #include #include using namespace std;using namespace std;/工具函数，用于将字符串转换为实数工具函数，用于将字符串转换为实数inline double inline double stringToDouble(conststringToDouble(const string & string &strstr) ) istringstreamistrin

58、gstream stream(strstream(str););/字符串输入流字符串输入流double result;double result;stream result;stream result;return result;return result; void void Calculator:enter(doubleCalculator:enter(double num) num) /将操作数将操作数numnum压入栈压入栈s.push(nums.push(num);); boolbool Calculator:getTwoOperands(doubleCalculator:getTw

59、oOperands(double &opnd1, double &opnd1, double &opnd2) &opnd2) if (if (s.isEmptys.isEmpty() () /检查栈是否空检查栈是否空cerrcerr Missing operand! Missing operand! endlendl; ;return false;return false; opnd1 = opnd1 = s.pops.pop();(); /将右操作数弹出栈将右操作数弹出栈if (if (s.isEmptys.isEmpty() () /检查栈是否空检查栈是否空

60、cerrcerr Missing operand! Missing operand! endlendl; ;return false;return false; opnd2 = opnd2 = s.pops.pop();(); /将左操作数弹出栈将左操作数弹出栈return true;return true; 56void Calculator:compute(char op) void Calculator:compute(char op) /执行运算执行运算double operand1, operand2;double operand1, operand2;boolbool result = result = getTwoOperandsgetTwoOperands(operand1, operand2); (operand1, operand2); if (result) if (result) /如果成功，执行运算并将运算结果压入栈如果成功，执行运算并将运算结果压入栈switch(op) switch(op) case +: case +: s.pushs.push(operand2 + operand1); break;(operand2 + operand1); break;case -: ca