C++第九章函数模板ppt课件

1、C+语言程序设计清华大学 郑莉1本章主要内容本章主要内容l模板模板l群体类群体类l群体数据的组织群体数据的组织l深度探索深度探索C+语言程序设计清华大学 郑莉2第一部分：模板第一部分：模板l函数模板函数模板l类模板类模板C+语言程序设计清华大学 郑莉3函数模板函数模板l函数模板可以用来创建一个通用功能的函数，以函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数支持多种不同形参，进一步简化重载函数的函数体设计。体设计。l定义方法：定义方法：ltemplate l函数定义函数定义l模板参数表的内容模板参数表的内容l类型参数：类型参数：class或或typename

2、） 标识符标识符l常量参数：类型说明符常量参数：类型说明符 标识符标识符l模板参数：模板参数：template class 标识符标识符 函 数 模 板C+语言程序设计清华大学 郑莉4求绝对值函数的模板求绝对值函数的模板#include #include using namespace std;using namespace std;templatetemplateT abs(T x) T abs(T x) return x 0? -x : x;return x 0? -x : x; int main() int main() int n = -5;int n = -5;double d =

3、-5.5;double d = -5.5;cout abs(n) endl;cout abs(n) endl;cout abs(d) endl;cout abs(d) endl;return 0;return 0; 函 数 模 板运行结果：运行结果：5 55.55.5C+语言程序设计清华大学 郑莉5求绝对值函数的模板分析求绝对值函数的模板分析l编译器从调用编译器从调用abs()时实参的类型，推时实参的类型，推导出函数模板的类型参数。例如，对导出函数模板的类型参数。例如，对于调用表达式于调用表达式abs(n)，由于实参，由于实参n为为int型，所以推导出模板中类型参数型，所以推导出模板中类型参数

4、T为为int。l当类型参数的含义确定后，编译器将当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：以函数模板为样板，生成一个函数：int abs(int x) return x 0 ? x : x; 函 数 模 板C+语言程序设计清华大学 郑莉6类模板的作用类模板的作用使用类模板使用户可以为类声明一使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数某些成员函数的参数、某些成员函数的返回值，能取任意类型包括基本的返回值，能取任意类型包括基本类型的和用户自定义类型）。类型的和用户自定义类型）。类 模 板C+语

5、言程序设计清华大学 郑莉7类模板的声明类模板的声明l类模板：类模板：ltemplate template lclass class 类名类名l 类成员声明类成员声明 l如果需要在类模板以外定义其成员如果需要在类模板以外定义其成员函数，则要采用以下的形式：函数，则要采用以下的形式：ltemplate template l类型名类型名 类名类名 :函数名参数表）函数名参数表）类 模 板C+语言程序设计清华大学 郑莉8例例9-2 类模板应用举例类模板应用举例#include #include #include #include using namespace std;using namespace

6、std;/ / 结构体结构体StudentStudentstruct Student struct Student int id; / int id; /学号学号 float gpa; / float gpa; /平均分平均分; ; 类 模 板template template class Store /class Store /类模板：实现对任意类型数据进行存取类模板：实现对任意类型数据进行存取private:private:T item;T item;/ item/ item用于存放任意类型的数据用于存放任意类型的数据bool haveValue; / haveValuebool have

7、Value; / haveValue标记标记itemitem是否已被是否已被存入内容存入内容public:public:Store();Store();/ / 缺省形式无形参的构造函数缺省形式无形参的构造函数T &getElem();T &getElem();/提取数据函数提取数据函数void putElem(const T &x); /void putElem(const T &x); /存入数据函数存入数据函数;/以下实现各成员函数。以下实现各成员函数。template template /缺省构造函数的实现缺省构造函数的实现 Store:Store():

8、haveValue(false) Store:Store(): haveValue(false) 9template /template /提取数据函数的实现提取数据函数的实现T &Store:getElem() T &Store:getElem() /如试图提取未初始化的数据，则终止程序如试图提取未初始化的数据，则终止程序if (!haveValue) if (!haveValue) cout No item present! endl;cout No item present! endl;exit(1);exit(1);/使程序完全退出，返回到操作系统使程序完全退出，返回到

9、操作系统。 return item; / return item; / 返回返回itemitem中存放的数据中存放的数据 template template /存入数据函数的实现存入数据函数的实现 void Store:putElem(const T &x) void Store:putElem(const T &x) / / 将将haveValue haveValue 置为置为truetrue，表示，表示itemitem中已存入数值中已存入数值haveValue = true;haveValue = true;item = x;item = x;/ / 将将x x值存入值存入

10、itemitem 10int main() int main() Store s1, s2;Store s1, s2;s1.putElem(3);s1.putElem(3);s2.putElem(-7);s2.putElem(-7);cout s1.getElem() s2.getElem() endl;cout s1.getElem() s2.getElem() endl;Student g = 1000, 23 ;Student g = 1000, 23 ;Store s3;Store s3;s3.putElem(g); s3.putElem(g); cout The student id

11、 is s3.getElem().id endl;cout The student id is s3.getElem().id endl;Store d;Store d;cout Retrieving object D. ;cout Retrieving object D. ;cout d.getElem() endlcout d.getElem() endl/由于由于d d未经初始化未经初始化, ,在执行函数在执行函数D.getElement()D.getElement()过程中导致程序终过程中导致程序终止止return 0;return 0; 11C+语言程序设计清华大学 郑莉12第二部分

12、：群体数据第二部分：群体数据l线性群体l线性群体的概念l直接访问群体-数组类l顺序访问群体-链表类l栈类l队列类C+语言程序设计清华大学 郑莉13群体的概念群体的概念群体是指由多个数据元素组成的集群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群合体。群体可以分为两个大类：线性群体和非线性群体。体和非线性群体。线性群体中的元素按位置排列有序线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素，可以区分为第一个元素、第二个元素等。等。非线性群体不用位置顺序来标识元非线性群体不用位置顺序来标识元素。素。C+语言程序设计清华大学 郑莉14线性群体的概念线性群体的概念线性群体

13、中的元素次序与其位置关线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺访问元素的不同方法分为直接访问、顺序访问和索引访问。序访问和索引访问。在本章我们只介绍直接访问和顺序在本章我们只介绍直接访问和顺序访问。访问。第一个元素第二个元素第三个元素最后一个元素C+语言程序设计清华大学 郑莉15数组数组l静态数组是具有固定元素个数的群体，其静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。中的元素可以通过下标直接访问。l缺点：大小在编译时就已经确定，在运行缺点：大小在编译时就已经确定，在运行时无法修改。

14、时无法修改。l动态数组由一系列位置连续的，任意数量动态数组由一系列位置连续的，任意数量相同类型的元素组成。相同类型的元素组成。l优点：其元素个数可在程序运行时改变。优点：其元素个数可在程序运行时改变。lvector就是用类模板实现的动态数组。就是用类模板实现的动态数组。l动态数组类模板：例动态数组类模板：例9-3Array.h）直接访问的线性群体#ifndef ARRAY_H#ifndef ARRAY_H#define ARRAY_H#define ARRAY_H#include #include template /template /数组类模板定义数组类模板定义class Array cl

15、ass Array private:private:T T* * list;/ list;/用于存放动态分配的数组内存首地址用于存放动态分配的数组内存首地址int size;int size; /数组大小元素个数）数组大小元素个数）public:public:Array(int sz = 50);Array(int sz = 50);/构造函数构造函数Array(const Array &a);Array(const Array &a);/拷贝构造函数拷贝构造函数Array();Array();/析构函数析构函数Array & operator = (const Arr

16、ay &rhs); /Array & operator = (const Array &rhs); /重载重载=“=“T & operator (int i); /T & operator (int i); /重载重载”const T & operator (int i) const;const T & operator (int i) const;operator T operator T * * (); (); /重载到重载到T T* *类型的转换类型的转换operator const T operator const T * * (

17、) const; () const;int getSize() const;int getSize() const;/取数组的大小取数组的大小void resize(int sz);void resize(int sz);/修改数组的大小修改数组的大小;16动态数组类模板程序C+语言程序设计清华大学 郑莉17数组类模板模板的构造函数数组类模板模板的构造函数/ / 构造函数构造函数template template Array:Array(int sz) Array:Array(int sz) /sz /sz为数组大小元素个数），应当非负为数组大小元素个数），应当非负assert(sz = 0)

18、;assert(sz = 0);/ / 将元素个数赋值给变量将元素个数赋值给变量sizesizesize = sz;size = sz;/动态分配动态分配sizesize个个T T类型的元素空间类型的元素空间list = new T size;list = new T size; 直接访问的线性群体C+语言程序设计清华大学 郑莉18数组类模板的拷贝构造函数数组类模板的拷贝构造函数/拷贝构造函数拷贝构造函数template template Array:Array(const Array &a) Array:Array(const Array &a) /从对象从对象x x取得数组

19、大小，并赋值给当前对象的成员取得数组大小，并赋值给当前对象的成员size = a.size;size = a.size;/为对象申请内存并进行出错检查为对象申请内存并进行出错检查list = new Tsize;/ list = new Tsize;/ 动态分配动态分配n n个个T T类型的元素空间类型的元素空间/从对象从对象X X复制数组元素到本对象复制数组元素到本对象 for (int i = 0; i size; i+)for (int i = 0; i size; i+)listi = a.listi;listi = a.listi; 直接访问的线性群体C+语言程序设计清华大学 郑莉1

20、9浅拷贝浅拷贝 list sizeaa的数组元素占用的内存拷贝前 list sizeaa的数组元素占用的内存拷贝后 list 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; list = x.list; list = x.list; C+语言程序设计清华

21、大学 郑莉20深拷贝深拷贝 list sizeaa的数组元素占用的内存拷贝前 list sizeaa的数组元素占用的内存拷贝后 list sizebb的数组元素占用的内存C+语言程序设计清华大学 郑莉21数组类模板的重载数组类模板的重载=运算符函数运算符函数/重载重载“=”“=”运算符运算符template template Array &Array:operator = (const Array& rhs) Array &Array:operator = (const Array& rhs) if (&rhs != this) if (&rhs

22、 != this) if (size != rhs.size) if (size != rhs.size) delete list;delete list;/删除数组原有内存删除数组原有内存size = rhs.size;size = rhs.size;/设置本对象的数组大小设置本对象的数组大小list = new Tsize;list = new Tsize; /重新分配重新分配n n个元素的内存个元素的内存 /从对象从对象X X复制数组元素到本对象复制数组元素到本对象 for (int i = 0; i size; i+)for (int i = 0; i size; i+)listi =

23、 rhs.listi;listi = rhs.listi; return return * *this;this;/返回当前对象的引用返回当前对象的引用 直接访问的线性群体C+语言程序设计清华大学 郑莉22数组类模板的重载下标操作符函数数组类模板的重载下标操作符函数template template T &Array:operator (int n) T &Array:operator (int n) assert(n = 0 & n = 0 & n size);/越界检查越界检查return listn;return listn; / /返回下标为返回下标为n

24、 n的数组元素的数组元素 template template const T &Array:operator (int n) const const T &Array:operator (int n) const assert(n = 0 & n = 0 & n size); /越界检查越界检查return listn;return listn; / /返回下标为返回下标为n n的数组元素的数组元素 直接访问的线性群体C+语言程序设计清华大学 郑莉23为什么有的函数返回引用为什么有的函数返回引用l如果一个函数的返回值是一个对象的如果一个函数的返回值是一个对象的值

25、，就不应成为左值。值，就不应成为左值。l如果返回值为引用。由于引用是对象如果返回值为引用。由于引用是对象的别名，通过引用当然可以改变对象的别名，通过引用当然可以改变对象的值。的值。直接访问的线性群体C+语言程序设计清华大学 郑莉24重载指针转换操作符重载指针转换操作符template template Array:operator T Array:operator T * * () () return list;return list; /返回私有数组的首地址返回私有数组的首地址 template template Array:operator const T Array:operator c

26、onst T * * () const () const return list;return list; /返回私有数组的首地址返回私有数组的首地址 直接访问的线性群体C+语言程序设计清华大学 郑莉25指针转换运算符的作用指针转换运算符的作用#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

27、, int n) for (int i = 0; i pi;int main() Array a(10); read(a, 10); return 0;直接访问的线性群体C+语言程序设计清华大学 郑莉26Array类的应用类的应用l例例9-4求范围求范围2N中的质数，中的质数，N在程序在程序运行时由键盘输入。运行时由键盘输入。直接访问的线性群体#include #include #include #include #include Array.h#include Array.husing namespace std;using namespace std;int main() int main

28、() Array a(10);Array a(10);/ / 用来存放质数的数组，初始状态有用来存放质数的数组，初始状态有1010个元素。个元素。int n, count = 0;int n, count = 0;cout = 2 as upper limit for prime numbers: ;cout = 2 as upper limit for prime numbers: ;cin n;cin n;for (int i = 2; i = n; i+) for (int i = 2; i = n; i+) bool isPrime = true;bool isPrime = true

29、;for (int j = 0; j count; j+)for (int j = 0; j count; j+)if (i % aj = 0) if (i % aj = 0) /若若i i被被ajaj整除，说明整除，说明i i不是质数不是质数isPrime = false; break;isPrime = false; break; if (isPrime) if (isPrime) if (count = a.getSize() a.resize(count if (count = a.getSize() a.resize(count * * 2); 2);acount+ = i;acou

30、nt+ = i; for (int i = 0; i count; i+)for (int i = 0; i count; i+)cout setw(8) ai;cout setw(8) ai;cout endl;cout endl;return 0;return 0; 27C+语言程序设计清华大学 郑莉28链表链表l链表是一种动态数据结构，可以用来链表是一种动态数据结构，可以用来表示顺序访问的线性群体。表示顺序访问的线性群体。l链表是由系列结点组成的，结点可以链表是由系列结点组成的，结点可以在运行时动态生成。在运行时动态生成。l每一个结点包括数据域和指向链表中每一个结点包括数据域和指向链表中

31、下一个结点的指针即下一个结点的下一个结点的指针即下一个结点的地址）。如果链表每个结点中只有一地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称个指向后继结点的指针，则该链表称为单链表。为单链表。顺序访问的线性群体C+语言程序设计清华大学 郑莉29单链表单链表 data1 data1 data2 data2 data3 data3 datan NULL datan NULLheadheadrearrear顺序访问的线性群体C+语言程序设计清华大学 郑莉30单链表的结点类模板单链表的结点类模板template template class Node class Node privat

32、e:private: Node Node * *next;next;public:public: T data; T data; Node(const T& item,Node Node(const T& item,Node* * next = 0); next = 0); void insertAfter(Node void insertAfter(Node * *p);p); Node Node * *deleteAfter();deleteAfter(); Node Node * *nextNode() const;nextNode() const; ; 顺序访问的线性群

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

34、顺序访问的线性群体 data1 data2 data3Node Node * *Node:deleteAfter(void) Node:deleteAfter(void) Node Node * *tempPtr = next; tempPtr = next; if (next = 0) if (next = 0) return 0; return 0; next = tempPtr-next; next = tempPtr-next; return tempPtr; return tempPtr; tempPtrC+语言程序设计清华大学 郑莉33链表的基本操作链表的基本操作l生成结点生成结点

35、l插入结点插入结点l查找结点查找结点l删除结点删除结点l遍历链表遍历链表l清空链表清空链表顺序访问的线性群体C+语言程序设计清华大学 郑莉34链表类模板链表类模板(例例9-6)顺序访问的线性群体#ifndef LINKEDLIST_H#define LINKEDLIST_H#include Node.htemplate class LinkedList private:/数据成员：Node *front, *rearNode *prevPtr, *currPtr; int size;int position;Node *newNode(const T &item,Node *ptrNe

36、xt=NULL);void freeNode(Node *p);void copy(const LinkedList& L);public:LinkedList();LinkedList(const LinkedList &L); LinkedList();LinkedList & operator = (const LinkedList & operator = (const LinkedList &L); LinkedList &L); int getSize() const;int getSize() const;bool isEmpty(

37、) const;bool isEmpty() const;void reset(int pos = 0void reset(int pos = 0void next();void next();bool endOfList() const;bool endOfList() const;int currentPosition(void) const;int currentPosition(void) const;void insertFront(const T &item);void insertFront(const T &item);void insertRear(const

38、 T &item);void insertRear(const T &item);void insertAt(const T &item);void insertAt(const T &item);void insertAfter(const T &item);void insertAfter(const T &item);T deleteFront();T deleteFront();void deleteCurrent();void deleteCurrent();T& data();T& data();const T&

39、; data() constconst T& data() constvoid clear();void clear();#endif /LINKEDLIST_H#endif /LINKEDLIST_HC+语言程序设计清华大学 郑莉35链表类应用举例链表类应用举例(例例9-7)顺序访问的线性群体/9_7.cpp#include #include LinkedList.husing namespace std;int main() LinkedList list;for (int i = 0; i item;list.insertFront(item);cout List: ;list.

40、reset();while (!list.endOfList() cout list.data() ;list.next();cout endl;int key;int key;cout Please enter some integer cout key;cin key;list.reset();list.reset();while (!list.endOfList() while (!list.endOfList() if (list.data() = key) if (list.data() = key) list.deleteCurrent();list.deleteCurrent()

41、;list.next();list.next(); cout List: ;cout List: ;list.reset();list.reset();while (!list.endOfList() while (!list.endOfList() cout list.data() ;cout list.data() ;list.nextlist.next cout endl;cout endl;return 0;return 0; C+语言程序设计清华大学 郑莉36特殊的线性群体特殊的线性群体栈栈栈是只能从一端访问的线性群体，栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈

42、可以访问的这一端称栈顶，另一端称栈底。底。ana2a1入栈出栈栈顶栈底特殊的线性群体栈C+语言程序设计清华大学 郑莉37栈的应用举例栈的应用举例表达式表达式处理处理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)特殊的线性群体栈C+语言程序设计清华大学 郑莉38栈的基本状态栈的基本状态l栈空栈空l栈中没有元素栈中没有元素l栈满栈满l栈中元素个数达到上限栈中元素个数达到上限l一般状态一般状态l栈中有元素，但未达到栈满状态栈中有元素，但未达到栈满状态特殊的线性群体栈栈顶

43、ana1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态栈空）maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满状态39C+语言程序设计清华大学 郑莉40栈的基本操作栈的基本操作l初始化初始化l入栈入栈l出栈出栈l清空栈清空栈l访问栈顶元素访问栈顶元素l检测栈的状态满、空）检测栈的状态满、空）特殊的线性群体栈C+语言程序设计清华大学 郑莉41栈类模板栈类模板(例例9-8)特殊的线性群体栈/Stack.h#ifndef STACK_H#define STACK_H#include template class Stack private:T listSIZE

44、;int top;public:public:Stack();Stack();void push(const T &item);void push(const T &item);T pop();T pop();void clear();void clear();const T &peek() const;const T &peek() const;bool isEmpty() const;bool isEmpty() const;bool isFull() const;bool isFull() const;/类的实现略类的实现略C+语言程序设计清华大学 郑莉4

45、2栈的应用栈的应用l例例9.9 一个简单的整数计算器一个简单的整数计算器l实现一个简单的整数计算器，能够进行实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计符之间都以空白符分隔。例如，若要计算算3+5则输入则输入3 5 +。乘方运算符用。乘方运算符用表示。每次运算在前次结果基础上进表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入行，若要将前次运算结果清除，可键入c。当键入。当键入q时程序结束。时程序结束。lCalculat

46、or.h Calculator.cpp 9_9.cpp特殊的线性群体栈/Calculator.h/Calculator.h#ifndef CALCULATOR_H#ifndef CALCULATOR_H#define CALCULATOR_H#define CALCULATOR_H#include Stack.h#include Stack.h / / 包含栈类模板定义文件包含栈类模板定义文件class Calculator class Calculator /计算器类计算器类private:private:Stack s;Stack s; / / 操作数栈操作数栈void enter(dou

47、ble num);void enter(double num); /将操作数将操作数numnum压入栈压入栈/连续将两个操作数弹出栈，放在连续将两个操作数弹出栈，放在opnd1opnd1和和opnd2opnd2中中bool getTwoOperands(double &opnd1, double &opnd2);bool getTwoOperands(double &opnd1, double &opnd2);void compute(char op);void compute(char op); /执行由操作符执行由操作符opop指定的运算指定的运算publi

48、c:public:void run();void run();/运行计算器程序运行计算器程序void clear();void clear();/清空操作数栈清空操作数栈;#endif /CALCULATOR_H#endif /CALCULATOR_H43/Calculator.cpp/Calculator.cpp#include Calculator.h#include Calculator.h#include #include #include #include #include #include using namespace std;using namespace std;/工具函数，

49、用于将字符串转换为实数工具函数，用于将字符串转换为实数inline double stringToDouble(const string &str) inline double stringToDouble(const string &str) istringstream stream(str);istringstream stream(str);/字符串输入流字符串输入流double result;double result;stream result;stream result;return result;return result; void Calculator:ent

50、er(double num) void Calculator:enter(double num) /将操作数将操作数numnum压入栈压入栈s.push(num);s.push(num); 44bool Calculator:getTwoOperands(double &opnd1, double bool Calculator:getTwoOperands(double &opnd1, double &opnd2) &opnd2) if (s.isEmpty() if (s.isEmpty() /检查栈是否空检查栈是否空cerr Missing operand

51、! endl;cerr Missing operand! endl;return false;return false; opnd1 = s.pop();opnd1 = s.pop(); /将右操作数弹出栈将右操作数弹出栈if (s.isEmpty() if (s.isEmpty() /检查栈是否空检查栈是否空cerr Missing operand! endl;cerr Missing operand! endl;return false;return false; opnd2 = s.pop();opnd2 = s.pop(); /将左操作数弹出栈将左操作数弹出栈return true;r

52、eturn true; 45void Calculator:compute(char op) void Calculator:compute(char op) /执行运算执行运算double operand1, operand2;double operand1, operand2;bool result = getTwoOperands(operand1, operand2); bool result = getTwoOperands(operand1, operand2); if (result) if (result) /如果成功，执行运算并将运算结果压入栈如果成功，执行运算并将运算结果压

53、入栈switch(op) switch(op) case +: 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

54、 (operand1 = 0) if (operand1 = 0) /检查除数是否为检查除数是否为0 0cerr Divided by 0! endl;cerr Divided by 0! endl;s.clear();s.clear();/除数为除数为0 0时清空栈时清空栈 else elses.push(operand2 / operand1);s.push(operand2 / operand1);break;break;case : s.push(pow(operand2, operand1); break;case : s.push(pow(operand2, operand1);

55、break;default:default:cerr Unrecognized operator! endl;cerr Unrecognized operator! endl;break;break; cout = s.peek() ;cout = s.peek() str, str != q) while (cin str, str != q) switch(str0) switch(str0) case c: s.clear(); break;case c: s.clear(); break;case -: /case -: /遇遇-需判断是减号还是负号需判断是减号还是负号if (str.

56、size() 1)if (str.size() 1)enter(stringToDouble(str);enter(stringToDouble(str);elseelsecompute(str0);compute(str0);break;break;case +:case +:/遇到其它操作符时遇到其它操作符时case case * *:case /:case /:case :case :compute(str0);compute(str0);default: /default: /若读入的是操作数，转换为整型后压入栈若读入的是操作数，转换为整型后压入栈enter(stringToDoubl

57、e(str); break;enter(stringToDouble(str); break; void Calculator:clear() void Calculator:clear() /清空操作数栈清空操作数栈s.clear(); s.clear(); 47/9_9.cpp/9_9.cpp#include Calculator.h#include Calculator.hint main() int main() Calculator c;Calculator c;c.run();c.run();return 0;return 0; 48C+语言程序设计清华大学 郑莉49特殊的线性群体

58、特殊的线性群体队列队列队列是只能向一端添加元素，从另队列是只能向一端添加元素，从另一端删除元素的线性群体一端删除元素的线性群体a1 a2an-1 an队头队尾入队出队a0C+语言程序设计清华大学 郑莉50队列的基本状态队列的基本状态l队空队空l队列中没有元素队列中没有元素l队满队满l队列中元素个数达到上限队列中元素个数达到上限l一般状态一般状态l队列中有元素，但未达到队满状态队列中有元素，但未达到队满状态特殊的线性群体队列a0 a1an-1 an队头队尾入队出队数组下标 0 1 n-1 n max(一般状态)队头队尾入队出队数组下标 0 1 n-1 n max(队空状态) a0 a1 an-1

59、 an amax队头队尾入队出队数组下标 0 1 n-1 n max(队满状态)元素移动方向元素移动方向51C+语言程序设计清华大学 郑莉52循环队列循环队列在想象中将数组弯曲成环形，元素在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组到数组最后一个元素时，便再回到数组开头。开头。特殊的线性群体队列1234m-1m-2m-30amam+1am+2a3队头队尾a4am-2am-3am-1队满状态 元素个数=m1234m-1m-2m-30队尾队头队空状态 元素个数=0队尾1234m-1m-2m-30a0a1a2a3

60、队头一般状态53C+语言程序设计清华大学 郑莉54第三部分：群体数据的组织第三部分：群体数据的组织l插入排序插入排序l选择排序选择排序l交换排序交换排序l顺序查找顺序查找l折半查找折半查找C+语言程序设计清华大学 郑莉55排序排序sorting）l排序是计算机程序设计中的一种重要操作，排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。新排列成一个按关键字有序的序列。l数据元素：数据的基本单位。在计算机中通数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可常作为一个整体进行考虑。一个数据元素可由若干数据项组成。由若干数据项组成。l关键字：数据元素中某个数据项的值，用它关键字：数据元素中某个数据项的值，用它可以标识识别一个数据元素。可以标识识别一个数据元素。l在排序过程中需要完成两种基本操作：在排序过程中需要完成两种基本操作：l比较两个数的大小比较两个数的大小l调整元素在序列中的位置调整元素在序列中的位置群体数据的组织C+语言程序设计清华大学 郑莉56内部排序与外部排序内部排序与外部排序l内部排序：待排序的数据元素存放在内部排序：待排序的数据元素存放在计算机内存中进行的排序过程。计算机内存中进行的排序过程。l外部排序：待排