《C第九章函数模板》由会员分享，可在线阅读，更多相关《C第九章函数模板（89页珍藏版）》请在金锄头文库上搜索。
1、C+语言程序设计清华大学 郑莉1本章主要内容本章主要内容l模板模板l群体类群体类l群体数据的组织群体数据的组织l深度探索深度探索C+语言程序设计清华大学 郑莉2第一部分：第一部分：模板模板l函数模板函数模板l类模板类模板C+语言程序设计清华大学 郑莉3函数模板函数模板l函数模板可以用来创建一个通用功能的函数，以函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数支持多种不同形参，进一步简化重载函数的函数体设计。体设计。l定义方法：定义方法：template 函数定义l模板参数表的内容模板参数表的内容类型参数：class（或typename） 标识符常量参数：类型
2、说明符 标识符模板参数：template class 标识符 函 数 模 板C+语言程序设计清华大学 郑莉4求绝对值函数的模板求绝对值函数的模板# #include include iostreamusing namespace std;using namespace std;templatetypename template T T abs( abs(T T x x) ) return x 0? -x : x;return x 0? -x : x; int mainint main() () int n = -int n = -5;5;double d = -double d = -5.5;
3、5.5;cout abs(cout abs(n n) endl) endl; ;cout abs(cout abs(d d) endl;) endl;return 0;return 0; 函 数 模 板运行结果：运行结果：55.5C+语言程序设计清华大学 郑莉5求绝对值函数的模板分析求绝对值函数的模板分析l编译器从调用编译器从调用abs()时实参的类型，推时实参的类型，推导出函数模板的类型参数。例如，对导出函数模板的类型参数。例如，对于调用表达式于调用表达式abs(n)，由于实参，由于实参n为为int型，所以推导出模板中类型参数型，所以推导出模板中类型参数T为为int。l当类型参数的含义确定后
4、，编译器将当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：以函数模板为样板，生成一个函数：int abs(int x) return x 0 ? x : x; 函 数 模 板C+语言程序设计清华大学 郑莉6类模板的作用类模板的作用使用类模板使用户可以为类声明一使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类型的和用户自定义类型）。类 模 板C+语言程序设计清华大学 郑莉7类模板的
5、声明类模板的声明l类模板：类模板：template class 类名类成员声明l如果需要在类模板以外定义其成员如果需要在类模板以外定义其成员函数，则要采用以下的形式：函数，则要采用以下的形式：template 类型名 类名:函数名（参数表）类 模 板C+语言程序设计清华大学 郑莉8例例9-2 类模板应用举例类模板应用举例#include #include #include #include using namespace std;using namespace std;/ / 结构体结构体StudentStudentstruct Student struct Student int id; /
6、 int id; /学号学号 float gpa; /float gpa; /平均分平均分; ; 类 模 板template template class Store /class Store /类模板：实现对任意类型数据进行存取类模板：实现对任意类型数据进行存取private:private:T item;T item;/ item/ item用于存放任意类型的数据用于存放任意类型的数据bool haveValue; / haveValuebool haveValue; / haveValue标记标记itemitem是否已被存是否已被存入内容入内容public:public:Store();
7、Store();/ / 缺省形式（无形参）的构造函数缺省形式（无形参）的构造函数T &getElem();T &getElem();/提取数据函数提取数据函数void putElem(const T &x); /void putElem(const T &x); /存入数据函数存入数据函数;/以下实现各成员函数。以下实现各成员函数。template template /缺省构造函数的实现缺省构造函数的实现 Store:Store(): haveValue(false) Store:Store(): haveValue(false) 9template /template /提取数据函数的实现提
8、取数据函数的实现T &Store:getElem() T &Store:getElem() /如试图提取未初始化的数据，则终止程序如试图提取未初始化的数据，则终止程序if (!haveValue) if (!haveValue) cout No item present! endl;cout No item present! endl;exit(1);exit(1);/使程序完全退出，返回到操作系统。使程序完全退出，返回到操作系统。 return item; / return item; / 返回返回itemitem中存放的数据中存放的数据 template template /存入数据函数的
9、实现存入数据函数的实现 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值存入值存入itemitem 10int main() int main() Store s1, s2;Store s1, s2;s1.putElem(3);s1.putElem(3);s2.putEl
10、em(-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 is s3.getElem().id endl;cout The student id is s3.getElem().id endl;Store d;Store d;cout Retri
11、eving 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第二部分：第二部分：群群体数据体数据l线性群体线性群体线性群体的概念直接访问群体-数组类顺序访问群体-链表类栈类队列类C+语言程序设计清华大学 郑莉13群体的概念群体的概念群体群体是指由多个数据元素
12、组成的集是指由多个数据元素组成的集合体。群体可以分为两个大类：合体。群体可以分为两个大类：线性群线性群体体和和非线性群体非线性群体。线性群体中的元素按位置排列有序，线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元非线性群体不用位置顺序来标识元素。素。C+语言程序设计清华大学 郑莉14线性群体的概念线性群体的概念线性群体中的元素次序与其位置关线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照系是对应的。在线性群体中，又可按照访问元素的不同方法分为访问元素的不同方法分为直接访问直接访问、顺顺序访问序
13、访问和和索引访问索引访问。在本章我们只介绍直接访问和顺序在本章我们只介绍直接访问和顺序访问。访问。第一个元素第二个元素第三个元素最后一个元素C+语言程序设计清华大学 郑莉15数组数组l静态数组是具有固定元素个数的群体，其静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。中的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修改。l动态数组由一系列位置连续的，任意数量动态数组由一系列位置连续的，任意数量相同类型的元素组成。相同类型的元素组成。优点：其元素个数可在程序运行时改变。lvector就是用类模板实现的动态数组。就是用类模板实现的动态数组。l动态数组类模板
14、：例动态数组类模板：例9-3（Array.h）直接访问的线性群体#ifndef ARRAY_H#ifndef ARRAY_H#define ARRAY_H#define ARRAY_H#include #include template /template /数组类模板定义数组类模板定义class Array class Array private:private:T* list;/T* list;/用于存放动态分配的数组内存首地址用于存放动态分配的数组内存首地址int size;int size; /数组大小（元素个数）数组大小（元素个数）public:public:Array(int sz
15、 = 50);Array(int sz = 50);/构造函数构造函数Array(const Array &a);Array(const Array &a);/拷贝构造函数拷贝构造函数Array();Array();/析构函数析构函数Array & operator = (const Array &rhs); /Array & operator = (const Array &rhs); /重载重载=“T & operator (int i); /T & operator (int i); /重载重载”const T & operator (int i) const;const T & ope
16、rator (int i) const;operator T * ();operator T * (); /重载到重载到T*T*类型的转换类型的转换operator const T * () const;operator const T * () const;int getSize() const;int getSize() const;/取数组的大小取数组的大小void resize(int sz);void resize(int sz);/修改数组的大小修改数组的大小;16动态数组类模板程序C+语言程序设计清华大学 郑莉17数组类模板模板的构造函数数组类模板模板的构造函数/ / 构造函数构
17、造函数template template Array:Array(int sz) Array:Array(int sz) /sz /sz为数组大小（元素个数），应当非负为数组大小（元素个数），应当非负assert(sz = 0);assert(sz = 0);/ / 将元素个数赋值给变量将元素个数赋值给变量sizesizesize = sz;size = sz;/动态分配动态分配sizesize个个T T类型的元素空间类型的元素空间list = new T size;list = new T size; 直接访问的线性群体C+语言程序设计清华大学 郑莉18数组类模板的拷贝构造函数数组类模板的拷
18、贝构造函数/拷贝构造函数拷贝构造函数template template Array:Array(const Array &a) Array:Array(const Array &a) /从对象从对象x x取得数组大小，并赋值给当前对象的成员取得数组大小，并赋值给当前对象的成员size = a.size;size = a.size;/为对象申请内存并进行出错检查为对象申请内存并进行出错检查list = new Tsize;/ list = new Tsize;/ 动态分配动态分配n n个个T T类型的元素空间类型的元素空间/从对象从对象X X复制数组元素到本对象复制数组元素到本对象 for (i
19、nt i = 0; i size; i+)for (int i = 0; i size; i+)listi = a.listi;listi = a.listi; 直接访问的线性群体C+语言程序设计清华大学 郑莉19浅拷贝浅拷贝 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(cons
20、t Array& x) const Array& x) size = x.size; size = x.size; list = x.list; list = x.list; C+语言程序设计清华大学 郑莉20深拷贝深拷贝 list sizeaa的数组元素占用的内存拷贝前 list sizeaa的数组元素占用的内存拷贝后 list sizebb的数组元素占用的内存C+语言程序设计清华大学 郑莉21数组类模板的重载数组类模板的重载=运算符函数运算符函数/重载重载“= =”运算符运算符template template Array &Array:operator = (const Array& r
21、hs) Array &Array:operator = (const Array& rhs) if (&rhs != this) if (&rhs != 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复制数组元素到本对
22、象复制数组元素到本对象 for (int i = 0; i size; i+)for (int i = 0; i size; i+)listi = rhs.listi;listi = rhs.listi; return *this;return *this;/返回当前对象的引用返回当前对象的引用 直接访问的线性群体C+语言程序设计清华大学 郑莉22数组类模板的重载下标操作符函数数组类模板的重载下标操作符函数template template T &Array:operator (int n) T &Array:operator (int n) assert(n = 0 & n = 0 & n
23、size);/越界检查越界检查return listn;return listn; / /返回下标为返回下标为n 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为什么有的函数返回引用为什么有的
24、函数返回引用l如果一个函数的返回值是一个对象的如果一个函数的返回值是一个对象的值，就不应成为左值。值，就不应成为左值。l如果返回值为引用。由于引用是对象如果返回值为引用。由于引用是对象的别名，通过引用当然可以改变对象的别名，通过引用当然可以改变对象的值。的值。直接访问的线性群体C+语言程序设计清华大学 郑莉24重载指针转换操作符重载指针转换操作符template template Array:operator T * () Array:operator T * () return list;return list; /返回私有数组的首地址返回私有数组的首地址 template template
25、 Array:operator const T * () const Array:operator const T * () const return list;return list; /返回私有数组的首地址返回私有数组的首地址 直接访问的线性群体C+语言程序设计清华大学 郑莉25指针转换运算符的作用指针转换运算符的作用#include #include using namespace std;using namespace std;void read(void read(int *pint *p, int n) , int n) for (int i = 0; i n; i+) for (
26、int i = 0; i pi; cin pi; int main() int main() int a10;int a10; read( read(a a, 10);, 10); return 0; return 0; #include Array.h#include Array.h#include #include using namespace std;using namespace std;void read(void read(int *pint *p, int n) , int n) for (int i = 0; i n; i+) for (int i = 0; i pi; ci
27、n pi; int main() int main() Array a(10);Array a(10); read( read(a a, 10);, 10); return 0; return 0; 直接访问的线性群体C+语言程序设计清华大学 郑莉26Array类的应用类的应用l例例9-4求范围求范围2N中的质数，中的质数，N在程序在程序运行时由键盘输入。运行时由键盘输入。直接访问的线性群体#include #include #include #include #include Array.h#include Array.husing namespace std;using namespace
28、 std;int main() int main() 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 =
29、true;bool isPrime = true;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 * 2);if (count = a.getSize() a.resize(coun
30、t * 2);acount+ = i;acount+ = 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 cla
32、ss Node class Node private:private: Node *next; Node *next;public:public: T data; T data; Node(const T& item,Node* next = 0); Node(const T& item,Node* next = 0); void insertAfter(Node *p); void insertAfter(Node *p); Node *deleteAfter(); Node *deleteAfter(); Node *nextNode() const; Node *nextNode() c
33、onst; ; 顺序访问的线性群体C+语言程序设计清华大学 郑莉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 顺序访问的线性群体C+语言程序设计清华大学 郑莉32 删除结
34、点之后的结点删除结点之后的结点顺序访问的线性群体 data1 data2 data3Node *Node:deleteAfter(void) Node *Node:deleteAfter(void) Node *tempPtr = next; Node *tempPtr = next; if (next = 0) if (next = 0) return 0; return 0; next = tempPtr-next; next = tempPtr-next; return tempPtr; return tempPtr; tempPtrC+语言程序设计清华大学 郑莉33链表的基本操作链表的
35、基本操作l生成结点生成结点l插入结点插入结点l查找结点查找结点l删除结点删除结点l遍历链表遍历链表l清空链表清空链表顺序访问的线性群体C+语言程序设计清华大学 郑莉34链表类模板链表类模板(例例9-6)顺序访问的线性群体#ifndef LINKEDLIST_H#ifndef LINKEDLIST_H#define LINKEDLIST_H#define LINKEDLIST_H#include Node.h#include Node.htemplate template class LinkedList class LinkedList private:private:/数据成员：数据成员：N
36、ode *front, *rearNode *front, *rearNode *prevPtr, *currPtr; Node *prevPtr, *currPtr; int size;int size;int position;int position;Node *newNode(const T &item,Node Node *newNode(const T &item,Node *ptrNext=NULL);*ptrNext=NULL);void freeNode(Node *p);void freeNode(Node *p);void copy(const LinkedList& L
37、);void copy(const LinkedList& L);public:public:LinkedList();LinkedList();LinkedList(const LinkedList &L); LinkedList(const LinkedList &L); LinkedList();LinkedList();LinkedList & operator = (const LinkedList & operator = (const LinkedList &L); LinkedList &L); int getSize() const;int getSize() const;b
38、ool isEmpty() 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(c
39、onst 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& data() constconst T& data() co
40、nstvoid clear();void clear();#endif /LINKEDLIST_H#endif /LINKEDLIST_HC+语言程序设计清华大学 郑莉35链表类应用举例链表类应用举例(例例9-7)顺序访问的线性群体/9_7.cpp/9_7.cpp#include #include #include LinkedList.h#include LinkedList.husing namespace std;using namespace std;int main() int main() LinkedList list;LinkedList list;for (int i = 0
41、; i 10; i+) for (int i = 0; i item;cin item;list.insertFront(item);list.insertFront(item); cout List: ;cout List: ;list.reset();list.reset();while (!list.endOfList() while (!list.endOfList() cout list.data() ;cout list.data() ;list.next();list.next(); cout endl;cout endl;int key;int key;cout Please
42、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();list.next();list.next(); cout List: ;cout List: ;list.reset();list.reset();while (!list.endOfList()
43、while (!list.endOfList() cout list.data() ;cout list.data() ;list.nextlist.next cout endl;cout endl;return 0;return 0; C+语言程序设计清华大学 郑莉36特殊的线性群体特殊的线性群体栈栈栈是只能从一端访问的线性群体，栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈可以访问的这一端称栈顶，另一端称栈底。底。ana2a1入栈出栈栈顶栈底特殊的线性群体栈C+语言程序设计清华大学 郑莉37栈的应用举例栈的应用举例表达式处理表达式处理ba/a/b+c*d(a)t1+a/b
44、+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一般状态一般状态栈中有元素，但未达到栈满状态特殊的线性群体栈栈顶ana1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态（栈空）maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满状态39C+语言程序设计清华大学 郑莉40栈的基本操作栈的基本操作l初始化初始化l入栈入栈l出栈出栈l清空栈清空栈l
45、访问栈顶元素访问栈顶元素l检测栈的状态（满、空）检测栈的状态（满、空）特殊的线性群体栈C+语言程序设计清华大学 郑莉41栈类模板栈类模板(例例9-8)特殊的线性群体栈/Stack.h/Stack.h#ifndef STACK_H#ifndef STACK_H#define STACK_H#define STACK_H#include #include template class T, template int SIZE = 50class Stack class Stack private:private:T listSIZE;T listSIZE;int top;int top;publi
46、c: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+语言程序设计清华大学 郑莉42栈的应用栈的应用l例例9.9 一个简单的整数计算器一个简单
47、的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算3+5则输入3 5 +。乘方运算符用表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入c。当键入q时程序结束。lCalculator.h Calculator.cpp 9_9.cpp特殊的线性群体栈/Calculator.h/Calculator.h#ifndef CALCULATOR_H#ifndef CALCULATOR_H#define CALCULATOR_H#define CALCULATOR_H#include Sta
48、ck.h#include Stack.h/ / 包含栈类模板定义文件包含栈类模板定义文件class Calculator class Calculator /计算器类计算器类private:private:Stack s;Stack s; / / 操作数栈操作数栈void enter(double num);void enter(double num); /将操作数将操作数numnum压入栈压入栈/连续将两个操作数弹出栈，放在连续将两个操作数弹出栈，放在opnd1opnd1和和opnd2opnd2中中bool getTwoOperands(double &opnd1, double &opnd
49、2);bool getTwoOperands(double &opnd1, double &opnd2);void compute(char op);void compute(char op);/执行由操作符执行由操作符opop指定的运算指定的运算public:public:void run();void run();/运行计算器程序运行计算器程序void clear();void clear();/清空操作数栈清空操作数栈;#endif /CALCULATOR_H#endif /CALCULATOR_H43/Calculator.cpp/Calculator.cpp#include Calc
50、ulator.h#include Calculator.h#include #include #include #include #include #include using namespace std;using namespace std;/工具函数，用于将字符串转换为实数工具函数，用于将字符串转换为实数inline double stringToDouble(const string &str) inline double stringToDouble(const string &str) istringstream stream(str);istringstream stream(s
51、tr);/字符串输入流字符串输入流double result;double result;stream result;stream result;return result;return result; void Calculator:enter(double num) void Calculator:enter(double num) /将操作数将操作数numnum压入栈压入栈s.push(num);s.push(num); 44bool Calculator:getTwoOperands(double &opnd1, double bool Calculator:getTwoOperand
52、s(double &opnd1, double &opnd2) &opnd2) if (s.isEmpty() if (s.isEmpty() /检查栈是否空检查栈是否空cerr Missing operand! 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
53、 operand! endl;return false;return false; opnd2 = s.pop();opnd2 = s.pop(); /将左操作数弹出栈将左操作数弹出栈return true;return true; 45void Calculator:compute(char op) void Calculator:compute(char op) /执行运算执行运算double operand1, operand2;double operand1, operand2;bool result = getTwoOperands(operand1, operand2); bool
54、 result = getTwoOperands(operand1, operand2); if (result) if (result) /如果成功，执行运算并将运算结果压入栈如果成功，执行运算并将运算结果压入栈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
55、;case *: s.push(operand2 * operand1); break;case *: s.push(operand2 * operand1); break;case /:case /:if (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 / ope
56、rand1);break;break;case : s.push(pow(operand2, operand1); break;case : s.push(pow(operand2, operand1); 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(st
57、r0) case c: s.clear(); break;case c: s.clear(); break;case -: /case -: /遇遇-需判断是减号还是负号需判断是减号还是负号if (str.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 :
58、compute(str0);compute(str0);default: /default: /若读入的是操作数，转换为整型后压入栈若读入的是操作数，转换为整型后压入栈enter(stringToDouble(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 ma
59、in() int main() Calculator c;Calculator c;c.run();c.run();return 0;return 0; 48C+语言程序设计清华大学 郑莉49特殊的线性群体特殊的线性群体队列队列队列是只能向一端添加元素，从另队列是只能向一端添加元素，从另一端删除元素的线性群体一端删除元素的线性群体a1 a2an-1 an队头队尾入队出队a0C+语言程序设计清华大学 郑莉50队列的基本状态队列的基本状态l队空队空队列中没有元素l队满队满队列中元素个数达到上限l一般状态一般状态队列中有元素，但未达到队满状态特殊的线性群体队列a0 a1an-1 an队头队尾入队出队
60、数组下标 0 1 n-1 n max(一般状态)队头队尾入队出队数组下标 0 1 n-1 n max(队空状态) a0 a1 an-1 an amax队头队尾入队出队数组下标 0 1 n-1 n max(队满状态)元素移动方向元素移动方向51C+语言程序设计清华大学 郑莉52循环队列循环队列在想象中将数组弯曲成环形，元素在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组到数组最后一个元素时，便再回到数组开头。开头。特殊的线性群体队列1234m-1m-2m-30amam+1am+2a3队头队尾a4am-2am-3a
61、m-1队满状态 元素个数=m1234m-1m-2m-30队尾队头队空状态 元素个数=0队尾1234m-1m-2m-30a0a1a2a3队头一般状态53C+语言程序设计清华大学 郑莉54第三部分：第三部分：群群体数据的组织体数据的组织l插入排序插入排序l选择排序选择排序l交换排序交换排序l顺序查找顺序查找l折半查找折半查找C+语言程序设计清华大学 郑莉55排序（排序（sorting）l排序排序是计算机程序设计中的一种重要操作，是计算机程序设计中的一种重要操作，它的功能是将一个它的功能是将一个数据元素数据元素的任意序列，重的任意序列，重新排列成一个按新排列成一个按关键字关键字有序的序列。有序的序列
62、。数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。l在排序过程中需要完成两种基本操作：在排序过程中需要完成两种基本操作：比较两个数的大小调整元素在序列中的位置群体数据的组织C+语言程序设计清华大学 郑莉56内部排序与外部排序内部排序与外部排序l内部排序：内部排序：待排序的数据元素存放在待排序的数据元素存放在计算机内存中进行的排序过程。计算机内存中进行的排序过程。l外部排序：外部排序：待排序的数据元素数量很待排序的数据元素数量很大，以致内存存中一次不能容纳全部大，以致内存存中一次不能
63、容纳全部数据，在排序过程中尚需对外存进行数据，在排序过程中尚需对外存进行访问的排序过程。访问的排序过程。群体数据的组织C+语言程序设计清华大学 郑莉57内部排序方法内部排序方法l插入排序插入排序l选择排序选择排序l交换排序交换排序群体数据的组织C+语言程序设计清华大学 郑莉58插入排序的基本思想插入排序的基本思想l每一步将一个待排序元素按其关键字值的大小插入到已排每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。序序列的适当位置上，直到待排序元素插入完为止。初始状态：初始状态： 5 4 10 20 12 35 4 10 20 12 3插入操作：插入
64、操作：1 1 44 4 5 10 20 12 3 4 5 10 20 12 32 2 1010 4 5 10 20 12 3 4 5 10 20 12 33 3 2020 4 5 10 20 12 3 4 5 10 20 12 34 4 1212 4 5 10 12 20 3 4 5 10 12 20 35 5 33 3 4 5 10 12 20 3 4 5 10 12 20C+语言程序设计清华大学 郑莉59直接插入排序直接插入排序l在插入排序过程中，由于寻找插入位置的在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序算法，方法不同又可以分为不同的插入排序算法，这里我们只介绍
65、最简单的直接插入排序算这里我们只介绍最简单的直接插入排序算法。法。l例例9-11 直接插入排序函数模板（直接插入排序函数模板（9_11.h）群体数据的组织template template void insertionSort(T a, int n) void insertionSort(T a, int n) int i, j;int i, j;T temp;T temp;for (int i = 1; i n; i+) for (int i = 1; i 0 & temp 0 & temp aj - 1) aj = aj - 1;aj = aj - 1;j-;j-; aj = temp;a
66、j = temp; 直接插入排序函数模板（9_11.h）60C+语言程序设计清华大学 郑莉61选择排序的基本思想选择排序的基本思想每次从待排序序列中选择一个关键字最小的元素，每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。最后，直至全部排完。5 4 10 20 12 5 4 10 20 12 3 3 初始状态：初始状态：3 3 4 4 10 20 12 5 10 20 12 53 4 10 20 12 3 4 10 20 12 5 5 第 i i 次选择后，将选出的那个记录与第
67、i i 个记录做交换交换。3 4 5 20 12 3 4 5 20 12 1010 . .C+语言程序设计清华大学 郑莉62直接选择排序直接选择排序l在选择类排序方法中，从待排序序列在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是通的选择排序方法，其中最简单的是通过顺序比较找出待排序序列中的最小过顺序比较找出待排序序列中的最小元素，称为直接选择排序。元素，称为直接选择排序。l例例9-12 直接选择排序函数模板（直接选择排序函数模板（9-12.h）群体数据的组织template template void mySwap
68、(T &x, T &y) void mySwap(T &x, T &y) T temp = x;T temp = x;x = y;x = y;y = temp;y = temp; template template void selectionSort(T a, int n) void selectionSort(T a, int n) for (int i = 0; i n - 1; i+) for (int i = 0; i n - 1; i+) int leastIndex = i;int leastIndex = i;for (int j = i + 1; j n; j+)for (i
69、nt j = i + 1; j n; j+)if (aj aleastIndex)if (aj aleastIndex)leastIndex = j;leastIndex = j;mySwap(ai, aleastIndexmySwap(ai, aleastIndex);); 直接选择排序函数模板（9-12.h）63C+语言程序设计清华大学 郑莉64交换排序的基本思想交换排序的基本思想两两比较待排序序列中的元素，并两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。全部满足顺序要求为止。群体数据的组织C+语言程序设计清华大学
70、郑莉65最简单的交换排序方法最简单的交换排序方法 起泡排序起泡排序对具有对具有n个元素的序列按升序进行起泡排序的个元素的序列按升序进行起泡排序的步骤：步骤：首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，依次类推，直到第n-1和第n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第n个位置。对前n-1个元素进行第二趟起泡排序，将其中最大元素交换到第n-1个位置。如此继续，直到某一趟排序未发生任何交换时，排序完毕。对n个元素的序列，起泡排序最多需要进行n-1趟。群体数据的组织C+语言程序设计清华大学 郑莉66起泡排序举例
71、起泡排序举例对整数序列对整数序列 8 5 2 4 3 按升序排序按升序排序8524352438243582345823458初始状态第一趟结果第二趟结果第三趟结果第四趟结果小的逐渐上升每趟沉下一个最大的群体数据的组织C+语言程序设计清华大学 郑莉67例例9-13 起泡排序函数模板起泡排序函数模板template template void mySwap(T &x, T &y) void mySwap(T &x, T &y) T temp = x;T temp = x;x = y;x = y;y = temp;y = temp; template template void bubbleSort
72、(T a, int n) void bubbleSort(T a, int n) int i = n int i = n 1; 1;while (i 0) while (i 0) int lastExchangeIndex = 0;int lastExchangeIndex = 0;for (int j = 0; j i; j+)for (int j = 0; j i; j+)if (aj + 1 aj) if (aj + 1 aj) mySwap(aj, aj + 1);mySwap(aj, aj + 1);lastExchangeIndex = j;lastExchangeIndex =
73、j; i = lastExchangeIndex;i = lastExchangeIndex; 群体数据的组织C+语言程序设计清华大学 郑莉68顺序查找顺序查找l其基本思想其基本思想从序列的首元素开始，逐个元素与待查找的关键字进行比较，直到找到相等的。若整个序列中没有与待查找关键字相等的元素，就是查找不成功。l顺序查找函数模板顺序查找函数模板例9-14群体数据的组织template template int seqSearch(const T list, int n, int seqSearch(const T list, int n, const T &key) const T &key)
74、for(int i = 0; i n; i+)for(int i = 0; i n; i+)if (listi = key)if (listi = key)return i; return i; return -1; return -1; 顺序查找函数模板69C+语言程序设计清华大学 郑莉70折半查找的基本思想折半查找的基本思想对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。群体数据的组织C+语言程序设计清华大学 郑莉71折半查找举例折半查找举例用折半查找法，在下列序列中
75、查找值为用折半查找法，在下列序列中查找值为2121的元素：的元素：L=1L=15 51313191921213737565664647575808088889292H=11H=11M M =INT(L+H)/2)=6 =INT(L+H)/2)=65 51313191921213737L=1L=1H H=M-1=5=M-1=5M=INT(L+H)/2)=3M=INT(L+H)/2)=3M M21213737H HL=M+1=4L=M+1=4L LM=INT(L+H)/2)=4M=INT(L+H)/2)=4M MC+语言程序设计清华大学 郑莉72例例9-15 折半查找函数模板折半查找函数模板tem
76、plate template int binSearch(const T list, int n, const T &key) int binSearch(const T list, int n, const T &key) int low = 0;int low = 0;int high = n - 1;int high = n - 1;while (low = high) while (low = high) int mid = (low + high) / 2;int mid = (low + high) / 2;if (key = listmid) if (key = listmid)
77、 return mid;return mid;else if (key listmid)else if (key listmid)high = mid high = mid 1; 1;elseelselow = mid + 1;low = mid + 1; return -1;return -1; 群体数据的组织C+语言程序设计清华大学 郑莉类模板类模板 vs 类类l类模板不能表示具体的数据类型，但类模板的实类模板不能表示具体的数据类型，但类模板的实例化类是数据类型例化类是数据类型l例：如要使例：如要使reverse函数接收函数接收Array的参数的参数void reverse(Array &
78、arr);l错误！Array是模板，不能当作一个数据类型。void reverse(Array &arr);l正确。Array是数据类型。template reverse (Array &arr);l正确。T虽未定，但Array表示的是一个类模板实例。l同一模板在不同参数下的实例是完全无关的类型同一模板在不同参数下的实例是完全无关的类型彼此不兼容，无法相互赋值通过Store的对象调用的成员函数，无法直接访问Store对象的私有成员73深度探索C+语言程序设计清华大学 郑莉函数模板函数模板 vs 函数函数l函数模板本身不是函数函数模板本身不是函数编译器不会为函数模板本身生成目标代码只有函数模板的
79、实例能被调用l例：考虑下列模板例：考虑下列模板template void outputArray(const T *array, int count);若a是int数组，outputArray(a, 10)等价于outputArray(a, 10)，被调用的是outputArray实例74深度探索C+语言程序设计清华大学 郑莉隐含实例化隐含实例化l模板的实例化模板的实例化根据函数模板生成具体的函数、或根据类模板生成具体的类的过程l隐含实例化隐含实例化编译器会自动按需对模板实例化所有会被使用的模板实例会被生成对类模板的隐含实例化并不意味着对它成员函数的定义也进行实例化，当类模板成员函数会被使用时
80、，才会被实例化75深度探索C+语言程序设计清华大学 郑莉多文件结构中模板的组织多文件结构中模板的组织l模板实例化机制带来的新问题模板实例化机制带来的新问题不能把下面与模板相关的定义放在源文件中l函数模板的定义l类模板成员函数l类模板静态数据成员l解决方法解决方法把与模板相关的定义放在头文件中最通常的解决办法l编译器有特殊处理，保证不会有连接冲突使用export关键字编译器支持不好使用模板的显式实例化机制76深度探索C+语言程序设计清华大学 郑莉显式实例化显式实例化l语法形式语法形式template 实例化目标的声明;l作用作用一个模板实例无论是否在本编译单元中被使用，都会被生成l例例templ
81、ate void outputArray(const int *array, int count);template class Store;l在多文件结构中的用途在多文件结构中的用途使用在程序中可能会被用到的各种参数对模板显式实例化，使得与模板相关的定义可以放在源文件中77深度探索C+语言程序设计清华大学 郑莉为模板定义特殊的实现为模板定义特殊的实现l为什么要定义特殊的实现？为什么要定义特殊的实现？模板抓住了算法与数据结构上的共性，但忽略了类型的个性设计出的模板对于具体的数据类型而言未必具有最好的效率l例：例：Stack类模板类模板如果以bool作为类型参数，则有7/8的空间浪费Stack中
82、的list数组占32个字节，实际上4个字节就够78深度探索C+语言程序设计清华大学 郑莉模板的特化模板的特化l什么是特化什么是特化为一个模板在特定参数下提供特殊定义l既适用于类模板，既适用于类模板，又适用于函数模板又适用于函数模板l对对Stack特化的类定义特化的类定义template template class Stack class Stack private:private:unsigned list;unsigned list;int top;int top;public:public:Stack();Stack();void push(bool item);void push(bo
83、ol item);bool pop();bool pop();void clear();void clear();bool peek() const;bool peek() const;bool isEmpty() const;bool isEmpty() const;bool isFull() const;bool isFull() const;79深度探索/特化类的部分成员函数定义特化类的部分成员函数定义void Stack:push(bool item) void Stack:push(bool item) assert(!isFull();assert(!isFull();+top;+
84、top;list = (list 1) | (item ? 1 : 0);list = (list 1) | (item ? 1 : 0); bool Stack:pop() bool Stack:pop() assert(!isEmpty();assert(!isEmpty();bool result = (list & 1) = 1);bool result = (list & 1) = 1);list = 1; -top; list = 1; -top; return result;return result; 80C+语言程序设计清华大学 郑莉类模板的偏特化类模板的偏特化l对对Stac
85、k特化的问题特化的问题适用范围过窄，SIZE必须是32l类模板的偏特化类模板的偏特化将一部分参数固定，而使另一部分参数可变，设计特殊的定义只适用于类模板l对对Stack偏特化的类偏特化的类定义定义template template class Stack class Stack private:private:enum enum UNIT_BITS = sizeof(unsigned) * 8,UNIT_BITS = sizeof(unsigned) * 8,ARRAY_SIZE = (SIZE - 1) / UNIT_BITS + 1ARRAY_SIZE = (SIZE - 1) / UNI
86、T_BITS + 1;unsigned listARRAY_SIZE;unsigned listARRAY_SIZE;int top;int top;public:public:Stack();Stack();void push(bool item);void push(bool item);bool pop();bool pop();void clear();void clear();bool peek() const;bool peek() const;bool isEmpty() const; bool isEmpty() const; bool isFull() const;bool
87、isFull() const;81深度探索/偏特化类的部分成员函数定义偏特化类的部分成员函数定义template template void Stack:push(bool item) void Stack:push(bool item) assert(!isFull();assert(!isFull();int index = +top / UNIT_BITS;int index = +top / UNIT_BITS;listindex = (listindex 1) | (item ? 1 : 0);listindex = (listindex 1) | (item ? 1 : 0); t
88、emplate template bool Stack:pop() bool Stack:pop() assert(!isEmpty();assert(!isEmpty();int index = top- / UNIT_BITS;int index = top- / UNIT_BITS;bool result = (listindex & 1) = 1);bool result = (listindex & 1) = 1);listindex = 1; listindex = 1; return result;return result; 82C+语言程序设计清华大学 郑莉类模板的偏特化类模
89、板的偏特化l偏特化不仅允许将一部分模板参数固定，还偏特化不仅允许将一部分模板参数固定，还允许将某一个模板参数所能表示的类型范围允许将某一个模板参数所能表示的类型范围缩窄，例缩窄，例template class X ;l原模板，T可以是所有类型参数template class X ;l针对指针类型进行偏特化template class X ;l针对常指针类型进行偏特化对于X，后两个偏特化版本皆能匹配，但由于第二个更为特殊，会被选中83深度探索C+语言程序设计清华大学 郑莉函数模板的重载函数模板的重载l函数模板不支持偏特函数模板不支持偏特化，但可重载，从而化，但可重载，从而完成与类模板偏特化完成与
90、类模板偏特化类似的功能类似的功能l若对函数模板的一次若对函数模板的一次使用能与多个函数模使用能与多个函数模板匹配，最特殊的那板匹配，最特殊的那个会被选中个会被选中l例：针对参数为指针例：针对参数为指针类型的情形，为类型的情形，为myMax定义特殊实定义特殊实现现template template T myMax(T a, T b) T myMax(T a, T b) return (a b) ? a : b;return (a b) ? a : b; template template T *myMax(T *a, T *b) T *myMax(T *a, T *b) return (*a *
91、b) ? a : b;return (*a *b) ? a : b; 84深度探索C+语言程序设计清华大学 郑莉模板元编程模板元编程l什么是模板元编程什么是模板元编程在模板实例化的同时利用编译器完成一些计算任务l模板元编程可以把一些通常在运行时模板元编程可以把一些通常在运行时才能计算的任务提前到编译时，从而：才能计算的任务提前到编译时，从而：提高程序运行效率提供一些方便l例：模板元编程的计算结果可以作为静态数组的大小85深度探索C+语言程序设计清华大学 郑莉例：编译时计算例：编译时计算n!template template struct Factorial /struct Factorial
92、/计算计算N N的阶乘的阶乘 enum enum VALUE = N * FactorialN VALUE = N * Factorial:VALUE 1:VALUE ; ;template template struct Factorial /struct Factorial /设定设定N = 0N = 0时时N N的阶乘的阶乘enum VALUE = 1 ;enum VALUE = 1 ;86深度探索C+语言程序设计清华大学 郑莉Factorial的分析的分析lFactorial的使用的使用例：int s Factorial:VALUE ;lFactorial:VALUE的计算过程的计算过
93、程首先试图实例化Factorial；要计算Factorial的VALUE，需实例化Factorial，然后是Factorial实例化Factorial时，由于Factorial:VALUE的值已确定，Factorial的VALUE值可计算，完成实例化；Factorial到Factorial的实例化相继完成87C+语言程序设计清华大学 郑莉88例：整数次乘方的展开例：整数次乘方的展开template template struct Power struct Power template template static T value(T x) static T value(T x) return
94、 x * PowerN - return x * Power:value(x);1:value(x); ;template template struct Power struct Power template template static T value(T x) static T value(T x) return x; return x; ;template template inline T power(T v) inline T power(T v) return Power:value(v);return Power:value(v); C+语言程序设计清华大学 郑莉89小结与复习建议小结与复习建议l主要内容主要内容模板、群体类和群体数据的组织l达到的目标达到的目标理解模板的作用，学会简单的应用。以群体类以及查找、排序算法为综合例题，对前面章节的内容进行全面复习；掌握一些常用的数据结构和算法，能够解决一些略复杂的问题，也为下一章学习C+标准模板库打下基础。l实验任务实验任务实验九
