C语言程序设计

1、第九章第九章 群体类群体类和群体数据的组织和群体数据的组织清华大学清华大学 郑郑 莉莉C+语言程序设计C+语言程序设计清华大学 郑莉2本章主要内容本章主要内容l模板模板l群体类群体类l群体数据的组织群体数据的组织C+语言程序设计清华大学 郑莉3第一部分：模板第一部分：模板l函数模板函数模板l类模板类模板C+语言程序设计清华大学 郑莉4函数模板函数模板l函数模板可以用来创建一个通用功能函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。步简化重载函数的函数体设计。l声明方法：声明方法：template 函数声明 函 数 模

2、板C+语言程序设计清华大学 郑莉5求绝对值函数的模板求绝对值函数的模板#includeiostream#include using namespace std;using namespace std;templatetypenametemplate T T abs( abs(T T x) x) return x0?-x:x; return x0?-x:x; intint main() main() int int n=-5; n=-5; double d=-5.5; double d=-5.5; cout coutabs(abs(n n)endl)endl; ; cout coutabs(ab

3、s(d d)endl)endl; ; 函 数 模 板运行结果：运行结果：55.5C+语言程序设计清华大学 郑莉6求绝对值函数的模板分析求绝对值函数的模板分析l编译器从调用编译器从调用abs()时实参的类型，推时实参的类型，推导出函数模板的类型参数。例如，对导出函数模板的类型参数。例如，对于调用表达式于调用表达式abs(n)，由于实参，由于实参n为为int型，所以推导出模板中类型参数型，所以推导出模板中类型参数T为为int。l当类型参数的含义确定后，编译器将当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：以函数模板为样板，生成一个函数：int abs(int x) return

4、x0?-x:x; 函 数 模 板C+语言程序设计清华大学 郑莉7类模板的作用类模板的作用使用类模板使用户可以为类声明一使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类型的和用户自定义类型）。类 模 板C+语言程序设计清华大学 郑莉8类模板的声明类模板的声明l类模板：类模板：template class 类名类成员声明l如果需要在类模板以外定义其成员如果需要在类模板以外定义其成员函数，则要采用以下

5、的形式：函数，则要采用以下的形式：template 类型名 类名:函数名（参数表）类 模 板C+语言程序设计清华大学 郑莉9例例9-2 类模板应用举例类模板应用举例#include iostream#include #include cstdlib#include using namespace std;using namespace std;/ / 结构体结构体StudentStudentstructstruct Student Student int int id; / id; /学号学号 float gpafloat gpa; /; /平均分平均分; ; 类 模 板template te

6、mplate / /类模板：实现对任意类型数据进行存取类模板：实现对任意类型数据进行存取class Storeclass Store private: private: T item; / T item; /用于存放任意类型的数据用于存放任意类型的数据 int haveValueint haveValue;/;/用于标记用于标记itemitem是否已被存入内容是否已被存入内容 public:public: Store(void Store(void); /); /默认形式（无形参）的构造函数默认形式（无形参）的构造函数 GetElem(voidGetElem(void); /); /提取数据函

7、数提取数据函数 void PutElem(Tvoid PutElem(T x);/ x);/存入数据函数存入数据函数;/ / 默认形式构造函数的实现默认形式构造函数的实现template template Store:Store(void): haveValue(0) Store:Store(void): haveValue(0) 10template / template / 提取数据函数的实现提取数据函数的实现T Store:GetElem(voidT Store:GetElem(void) ) / / 如果试图提取未初始化的数据，则终止程序如果试图提取未初始化的数据，则终止程序 if (

8、haveValueif (haveValue = 0) = 0) cout No item present! endl cout No item present! endl; ; exit(1); exit(1); return item; / return item; / 返回返回itemitem中存放的数据中存放的数据 template / template / 存入数据函数的实现存入数据函数的实现 void Store:PutElem(Tvoid Store:PutElem(T x) x) / / 将将haveValuehaveValue 置为置为 TRUETRUE，表示，表示itemi

9、tem中已存入数值中已存入数值 haveValuehaveValue+; +; item = x; / item = x; / 将将x x值存入值存入itemitem 11intint main() main() Student g= 1000, 23; Student g= 1000, 23; Storeint Store S1, S2; S1, S2; Store S3; Store S3; Store D; Store D; S1.PutElem(3); S1.PutElem(3); S2.PutElem(-7); S2.PutElem(-7); cout cout S1.GetElem

10、() S1.GetElem() S2.GetElem()endl S2.GetElem()endl; ; S3.PutElem(g); S3.PutElem(g); cout cout The student id is The student id is S3.GetElem().idendl S3.GetElem().idendl; ; cout cout Retrieving object D ; Retrieving object D ; cout D.GetElem() endl cout D.GetElem() endl; /; /输出对象输出对象D D的数据成员的数据成员 / /

11、 由于由于D D未经初始化未经初始化, ,在执行函数在执行函数D.GetElementD.GetElement()()时出错时出错 12C+语言程序设计清华大学 郑莉13第二部分：群体数据第二部分：群体数据l线性群体线性群体 线性群体的概念 直接访问群体-数组类 顺序访问群体-链表类 栈类 队列类C+语言程序设计清华大学 郑莉14群体的概念群体的概念群体群体是指由多个数据元素组成的集是指由多个数据元素组成的集合体。群体可以分为两个大类：合体。群体可以分为两个大类：线性群线性群体体和和非线性群体非线性群体。线性群体中的元素按位置排列有序，线性群体中的元素按位置排列有序，可以区分为第一个元素、第二

12、个元素等。可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元非线性群体不用位置顺序来标识元素。素。C+语言程序设计清华大学 郑莉15线性群体的概念线性群体的概念线性群体中的元素次序与其位置关线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照系是对应的。在线性群体中，又可按照访问元素的不同方法分为访问元素的不同方法分为直接访问直接访问、顺顺序访问序访问和和索引访问索引访问。在本章我们只介绍直接访问和顺序在本章我们只介绍直接访问和顺序访问。访问。第一个元素第二个元素第三个元素最后一个元素C+语言程序设计清华大学 郑莉16数组数组l静态数组是具有固定元素个数的群体，其静

13、态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。中的元素可以通过下标直接访问。 缺点：大小在编译时就已经确定，在运行时无法修改。l动态数组由一系列位置连续的，任意数量动态数组由一系列位置连续的，任意数量相同类型的元素组成。相同类型的元素组成。 优点：其元素个数可在程序运行时改变。l动态数组类模板：例动态数组类模板：例9-3（9_3.h）直接访问的线性群体#ifndef#ifndef ARRAY_CLASS ARRAY_CLASS#define ARRAY_CLASS#define ARRAY_CLASSusing namespace std;using namespace st

14、d;#include iostream#include #include cstdlib#include #ifndef#ifndef NULL NULLconst intconst int NULL = 0; NULL = 0;#endif#endif / NULL / NULLenum ErrorTypeenum ErrorType invalidArraySize, memoryAllocationError invalidArraySize, memoryAllocationError, , indexOutOfRange indexOutOfRange ; ;char char *

15、*errorMsgerrorMsg = = Invalid array size, Memory allocation error, Invalid array size, Memory allocation error, Invalid index: ; Invalid index: ;动态数组类模板程序17template template class Arrayclass Array private: private: T T* * alist alist; ; int int size; size; void Error(ErrorType error,int badIndex voi

16、d Error(ErrorType error,int badIndex=0) const;=0) const; public: public: Array(int sz Array(int sz = 50); = 50); Array(const Array(const Array& A); Array& A); Array(void); Array(void); Array& operator= (const Array& rhs Array& operator= (const Array& rhs); ); T& operator(

17、int T& operator(int i); i); operator T operator T* * (void) const; (void) const; int ListSize(void int ListSize(void) const; ) const; void Resize(int sz void Resize(int sz); ); ;18C+语言程序设计清华大学 郑莉19数组类模板的构造函数数组类模板的构造函数/ / 构造函数构造函数template template Array:Array(int szArray:Array(int sz) ) if (sz if

18、 (sz=0)=0) /sz /sz为数组大小（元素个数），若小于为数组大小（元素个数），若小于0 0则输出错误信息则输出错误信息 Error(invalidArraySizeError(invalidArraySize);); size=sz size=sz;/ ;/ 将元素个数赋值给变量将元素个数赋值给变量sizesize alist=new Tsize alist=new Tsize;/;/动态分配动态分配sizesize个个T T类型的元素空间类型的元素空间 if (alistif (alist=NULL) =NULL) / /如果分配内存不成功，输出错误信息如果分配内存不成功，输出错

19、误信息 Error(memoryAllocationErrorError(memoryAllocationError);); 直接访问的线性群体C+语言程序设计清华大学 郑莉20数组类的拷贝构造函数数组类的拷贝构造函数template template Array:Array(const Array& X)Array:Array(const Array& X) int n=X.size int n=X.size; ; size=n; size=n; alist alist=new Tn; =new Tn; if (alist if (alist=NULL) =NULL) Err

20、or(memoryAllocationError Error(memoryAllocationError);); T T* * srcptr=X.alist;/ X.alist srcptr=X.alist;/ X.alist是对象是对象X X的数组首地址的数组首地址 T T* * destptr=alist; / alist destptr=alist; / alist是本对象中的数组首地址是本对象中的数组首地址 while(nwhile(n-) / -) / 逐个复制数组元素逐个复制数组元素 * *destptr+ = destptr+ = * *srcptrsrcptr+;+; 直接访问

21、的线性群体C+语言程序设计清华大学 郑莉21浅拷贝浅拷贝 alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBintint main() main() Arrayint Array A(10); A(10); . . Arrayint Array B(A); B(A); . . template template Array:Array(Array:Array( const Array& X) const Array& X) size = X.size; size = X.size; alist= X.a

22、list alist= X.alist; ; C+语言程序设计清华大学 郑莉22深拷贝深拷贝 alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBB的数组元素占用的内存C+语言程序设计清华大学 郑莉23数组类的重载数组类的重载=运算符函数运算符函数template template Array& Array:operator=(const Array& rhsArray& Array:operator=(const Array& rhs) ) int n = rhs.size int n

23、= rhs.size; ; if (size != n) if (size != n) delete alist delete alist; ; alist alist = new Tn; = new Tn; if (alist if (alist = NULL) = NULL) Error(memoryAllocationError Error(memoryAllocationError);); size = n; size = n; T T* * destptr = alist destptr = alist; ; T T* * srcptr = rhs.alist srcptr = rh

24、s.alist; ; while (n-) while (n-) * *destptr+ = destptr+ = * *srcptrsrcptr+;+; return return * *this;this; 直接访问的线性群体C+语言程序设计清华大学 郑莉24数组类的重载下标操作符函数数组类的重载下标操作符函数template template T& Array:operator (intT& Array:operator (int n) n) / / 检查下标是否越界检查下标是否越界 if (n size-1)if (n size-1) Error(indexOutOfR

25、ange,n Error(indexOutOfRange,n);); / / 返回下标为返回下标为n n的数组元素的数组元素 return alistnreturn alistn; 直接访问的线性群体C+语言程序设计清华大学 郑莉25为什么有的函数返回引用为什么有的函数返回引用l如果一个函数的返回值是一个对象的如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成值，它就被认为是一个常量，不能成为左值。为左值。l如果返回值为引用。由于引用是对象如果返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变的别名，所以通过引用当然可以改变对象的值。对象的值。直接访问的线性群体C+语言

26、程序设计清华大学 郑莉26重载指针转换操作符重载指针转换操作符template template Array:operator TArray:operator T* * (void) const (void) const / /返回当前对象中私有数组的首地址返回当前对象中私有数组的首地址 return alistreturn alist; ; 直接访问的线性群体C+语言程序设计清华大学 郑莉27指针转换运算符的作用指针转换运算符的作用#include iostream#include using namespace std;using namespace std;intint main() m

27、ain() intint a10; a10; void read( void read(intint * *p p, int, int n); n); read( read(a a, 10);, 10); void read(void read(intint * *p p, int, int n) n) for (int for (int i=0; in; i+) i=0; ipi;pi; intint main() main() ArrayintArray a(10); a(10); void read( void read(intint * *p p, n);, n); read( rea

28、d(a a, 10);, 10); void read(void read(intint * *p p, int, int n) n) for (int for (int i=0; in; i+) i=0; ipi;pi; 直接访问的线性群体C+语言程序设计清华大学 郑莉28Array类的应用类的应用l例例9-4求范围求范围2N中的质数，中的质数，N在程序在程序运行时由键盘输入。运行时由键盘输入。直接访问的线性群体#include iostream#include #include iomanip#include #include 9_3.h#include 9_3.husing namesp

29、ace std;using namespace std;intint main() main() Arrayint Array A(10); A(10); int int n; n; int primecount int primecount = 0, i, j; = 0, i, j; cout cout = 2 as upper limit for prime numbers: ; = 2 as upper limit for prime numbers: ; cin cin n; n; Aprimecount Aprimecount+ = 2; / 2+ = 2; / 2是一个质数是一个质

30、数 for(ifor(i = 3; i n; i+) = 3; i n; i+) if (primecount = A.ListSize() A.Resize(primecount if (primecount = A.ListSize() A.Resize(primecount + 10); + 10); if (i % 2 = 0) continue; if (i % 2 = 0) continue; j = 3; j = 3; while (j = i/2 & i % j != 0) j += 2; while (j i/2) Aprimecount if (j i/2) Apr

31、imecount+ = i;+ = i; for (i = 0; i primecount for (i = 0; i primecount; i+); i+) cout setw(5) Ai cout setw(5) Ai; if (i+1) % 10 = 0) cout endl if (i+1) % 10 = 0) cout endl; ; cout endl cout endl; ; 29C+语言程序设计清华大学 郑莉30链表链表l链表是一种动态数据结构，可以用来链表是一种动态数据结构，可以用来表示顺序访问的线性群体。表示顺序访问的线性群体。l链表是由系列链表是由系列结点结点组成的，结

32、点可以组成的，结点可以在运行时动态生成。在运行时动态生成。l每一个结点包括每一个结点包括数据域数据域和指向链表中和指向链表中下一个结点的下一个结点的指针指针（即下一个结点的（即下一个结点的地址）。如果链表每个结点中只有一地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称个指向后继结点的指针，则该链表称为单链表。为单链表。顺序访问的线性群体C+语言程序设计清华大学 郑莉31单链表单链表 data1 data1 data2 data2 data3 data3 datan datan NULL NULLheadheadrearrear顺序访问的线性群体C+语言程序设计清华大学 郑莉32

33、单链表的结点类模板单链表的结点类模板template template class Nodeclass Node private: private: Node Node * *next;next; public: public: T data; T data; Node(const T& item,Node Node(const T& item,Node* * ptrnext ptrnext = NULL); = NULL); void InsertAfter(Node void InsertAfter(Node * *p);p); Node Node * *DeleteAft

34、er(voidDeleteAfter(void);); Node Node * *NextNode(voidNextNode(void) const;) const; ; 顺序访问的线性群体C+语言程序设计清华大学 郑莉33在结点之后插入一个结点在结点之后插入一个结点 data1 data2 p datatemplate template void Node:void Node:InsertAfterInsertAfter(Node(Node * *p)p) /p /p节点指针域指向当前节点的后继节点节点指针域指向当前节点的后继节点 p-next = next; p-next = next;

35、next = p; / next = p; /当前节点的指针域指向当前节点的指针域指向p p 顺序访问的线性群体C+语言程序设计清华大学 郑莉34 删除结点之后的结点删除结点之后的结点顺序访问的线性群体 data1 data2 data3Node Node * *Node:DeleteAfter(voidNode:DeleteAfter(void) ) Node Node * *tempPtrtempPtr = next; = next; if (next = NULL) if (next = NULL) return NULL; return NULL; next = tempPtr nex

36、t = tempPtr-next; -next; return tempPtr return tempPtr; ; tempPtrC+语言程序设计清华大学 郑莉35链表的基本操作链表的基本操作l生成结点生成结点l插入结点插入结点l查找结点查找结点l删除结点删除结点l遍历链表遍历链表l清空链表清空链表顺序访问的线性群体C+语言程序设计清华大学 郑莉36链表类模板链表类模板(例例9-6)顺序访问的线性群体/9_6.h/9_6.h#ifndef#ifndef LINKEDLIST_CLASS LINKEDLIST_CLASS#define LINKEDLIST_CLASS#define LINKED

37、LIST_CLASS#include iostream#include #include cstdlib#include using namespace std;using namespace std;#ifndef#ifndef NULL NULLconst intconst int NULL = 0; NULL = 0;#endif#endif / NULL / NULL#include 9_5.h#include 9_5.htemplate template class LinkedListclass LinkedListprivate:private: Node Node * *fro

38、nt, front, * *rear;rear; Node Node * *prevPtr, prevPtr, * *currPtrcurrPtr; ; int int size; size; int int position; position; Node Node * *GetNode(constGetNode(const T& item, T& item, Node Node * *ptrNextptrNext=NULL);=NULL); void FreeNode(Node void FreeNode(Node * *p);p); void CopyList void

39、CopyList( ( const LinkedList const LinkedList& L);& L);public:public: LinkedList(void LinkedList(void);); LinkedList(const LinkedList(const LinkedList LinkedList& L); & L); LinkedList(void LinkedList(void);); LinkedList LinkedList& operator=(& operator=( const LinkedList cons

40、t LinkedList& L);& L); int int ListSize(void ListSize(void) const; ) const; int int ListEmpty(void ListEmpty(void) const; ) const; void Reset(int void Reset(int pos = 0); pos = 0); void Next(void void Next(void); ); int int EndOfList(void EndOfList(void) const;) const; int int CurrentPositio

41、n(void CurrentPosition(void) const; ) const; void InsertFront(const void InsertFront(const T& item); T& item); void InsertRear(const void InsertRear(const T& item); T& item); void InsertAt(const void InsertAt(const T& item); T& item); void InsertAfter(const void InsertAfter(c

42、onst T& item); T& item); T DeleteFront(void T DeleteFront(void); ); void DeleteAt(void void DeleteAt(void); ); T& Data(void T& Data(void);); void ClearList(void void ClearList(void););#endif#endif / LINKEDLIST_CLASS / LINKEDLIST_CLASSC+语言程序设计清华大学 郑莉37链表类应用举例链表类应用举例(例例9-7)顺序访问的线性群体#in

43、clude iostream#include #include 9_6.h#include 9_6.h#include 9_6.cpp#include 9_6.cppusing namespace std;using namespace std;intint main() main() LinkedListint LinkedList Link; Link; int int i, key, item; i, key, item; for (i=0;i 10;i+) for (i=0;i item;item; Link.InsertFront(item Link.InsertFront(item

44、);); cout cout List: ; List: ; Link.Reset Link.Reset();(); while(!Link.EndOfList while(!Link.EndOfList()() coutLink.Data coutLink.Data() ;() ; Link.Next Link.Next(); (); coutcout endl endl; ; cout cout key; key; Link.Reset Link.Reset();(); while (!Link.EndOfList while (!Link.EndOfList()() if(Link.Da

45、ta if(Link.Data() = key) () = key) Link.DeleteAt Link.DeleteAt();();Link.NextLink.Next();(); cout cout List: ; List: ; Link.Reset Link.Reset();(); while(!Link.EndOfList while(!Link.EndOfList()() cout cout Link.Data Link.Data() ;() ; Link.Next Link.Next(); (); cout cout endl endl; ; C+语言程序设计清华大学 郑莉38

46、特殊的线性群体特殊的线性群体栈栈栈是只能从一端访问的线性群体，栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈可以访问的这一端称栈顶，另一端称栈底。底。ana2a1入栈出栈栈顶栈底特殊的线性群体栈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/

47、b+c*dt3=t1+t2(e)t2t1+a/b+c*dt2=c*d(d)特殊的线性群体栈C+语言程序设计清华大学 郑莉41栈的基本状态栈的基本状态l栈空栈空 栈中没有元素l栈满栈满 栈中元素个数达到上限l一般状态一般状态 栈中有元素，但未达到栈满状态特殊的线性群体栈栈顶ana1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态（栈空）maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满状态42C+语言程序设计清华大学 郑莉43栈的基本操作栈的基本操作l初始化初始化l入栈入栈l出栈出栈l清空栈清空栈l访问栈顶元素访问栈顶元素l检测栈的状态（满、空）检测栈的状态

48、（满、空）特殊的线性群体栈C+语言程序设计清华大学 郑莉44栈类模板栈类模板(例例9-8)特殊的线性群体栈/9-8.h/9-8.h#ifndef#ifndef STACK_CLASS STACK_CLASS#define STACK_CLASS#define STACK_CLASS#include iostream#include #include cstdlib#include using namespace std;using namespace std;const int MaxStackSizeconst int MaxStackSize=50;=50; template templa

49、te class Stackclass Stackprivate:private: T stacklistMaxStackSize T stacklistMaxStackSize; ; int int top; top; public:public: Stack (void); Stack (void); void Push (const T& item); void Push (const T& item); T Pop (void); T Pop (void); void ClearStack(void void ClearStack(void); ); T Peek (v

50、oid) const; T Peek (void) const; int int StackEmpty(void StackEmpty(void) const;) const; int int StackFull(void StackFull(void) const;) const;/类的实现略类的实现略C+语言程序设计清华大学 郑莉45栈的应用栈的应用l例例9.9 一个简单的整数计算器一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算3+5则输入3 5 +。乘方运算符用表示。每次运算在

51、前次结果基础上进行，若要将前次运算结果清除，可键入c。当键入q时程序结束。l9-9.h 9-9.cpp特殊的线性群体栈/9_9.h/9_9.h#include iostream#include #include cmath#include #include cstdlib#include #include cstring#include using namespace std;using namespace std;enumenum Boolean False, True; Boolean False, True;#include 9_8.h #include 9_8.h class clas

52、s CalculatorCalculator private: private: Stackint Stack S; S; void Enter(int void Enter(int num); num); Boolean GetTwoOperands(int& opnd1, int Boolean GetTwoOperands(int& opnd1, int& opnd2);& opnd2); void Compute(char void Compute(char op); op); public: public: void Run(void void Run

53、(void); ); void Clear(void void Clear(void); ); ;46void Calculator:void Calculator:EnterEnter(int(int num) num) S.Push(num); S.Push(num); Boolean Calculator:Boolean Calculator:GetTwoOperandsGetTwoOperands( ( int int& opnd1,int& opnd2)& opnd1,int& opnd2) if (S.StackEmpty if (S.StackEm

54、pty() () cerr Missing operand! endl cerr Missing operand! endl; ; return False; return False; opnd1 = S.Pop(); opnd1 = S.Pop(); if (S.StackEmpty if (S.StackEmpty()() cerr Missing operand! endl cerr Missing operand! endl; ; return False; return False; opnd2 = S.Pop(); opnd2 = S.Pop(); return True; re

55、turn True; 47void Calculator:void Calculator:ComputeCompute(char op)(char op) Boolean result; Boolean result; int int operand1, operand2; operand1, operand2; result = GetTwoOperands(operand1, operand2); result = GetTwoOperands(operand1, operand2); if (result) if (result) switch(op switch(op) ) case

56、+: S.Push(operand2+operand1); break; case +: S.Push(operand2+operand1); break; case -: S.Push(operand2-operand1); break; case -: S.Push(operand2-operand1); break; case case * *: S.Push(operand2: S.Push(operand2* *operand1); break; operand1); break; case /: case /: if (operand1 = 0) if (operand1 = 0)

57、 cerrDivide by 0!endl; S.ClearStack cerrDivide by 0!endl; S.ClearStack();(); else S.Push(operand2/operand1); else S.Push(operand2/operand1); break; break; case : S.Push(pow(operand2,operand1); break; case : S.Push(pow(operand2,operand1); break; cout=S.Peek cout=S.Peek() ;()c, c, * *c != q)c != q) sw

58、itch( switch(* *c)c) case c: S.ClearStack case c: S.ClearStack(); break;(); break; case -: case -:if (strlen(c)1) Enter(atoi(cif (strlen(c)1) Enter(atoi(c); ); else Compute(else Compute(* *c); c); break;break; case +: case +: case case * *: case /: case /: case : Compute( case : Compute(* *c); break

59、;c); break; default: Enter(atoi(c default: Enter(atoi(c); break;); break; void Calculator:void Calculator:ClearClear(void(void) ) S.ClearStack S.ClearStack(); (); 49/9_9.cpp#include 9-9.hint main() Calculator CALC; CALC.Run();50C+语言程序设计清华大学 郑莉51特殊的线性群体特殊的线性群体队列队列队列是只能向一端添加元素，从另队列是只能向一端添加元素，从另一端删除元素的

60、线性群体一端删除元素的线性群体a1 a2an-1 an队头队尾入队出队a0C+语言程序设计清华大学 郑莉52队列的基本状态队列的基本状态l队空队空 队列中没有元素l队满队满 队列中元素个数达到上限l一般状态一般状态 队列中有元素，但未达到队满状态特殊的线性群体队列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(队满状态)元素移动方向元素移动方向53C+语言程序设计清华大学 郑莉54循环队列循环队列在想象中将数组弯曲成环形，元素在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组到数组最后一个元素时，便再回到数组开头。开头。特殊的线性群体队列1234m-1m-2m-30amam+1am+2a3队头队尾a4am-2am-3am-1队满状态 元素个数=m1234m-1m-2m-30队尾队头队空状态 元素