C++语言程序设计(清华大学郑莉)九ppt课件.ppt

第九章第九章 群体类群体类和群体数据的组织和群体数据的组织清华大学清华大学 郑郑 莉莉C+语言程序设计C+语言程序设计清华大学 郑莉2本章主要内容本章主要内容l模板模板l群体类群体类l群体数据的组织群体数据的组织l深度探索深度探索C+语言程序设计清华大学 郑莉3第一部分：模板第一部分：模板l函数模板函数模板l类模板类模板C+语言程序设计清华大学 郑莉4函数模板函数模板l函数模板可以用来创建一个通用功能的函数，以函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数支持多种不同形参，进一步简化重载函数的函数体设计。体设计。l定义方法定义方法：template 函数定义l模板模板参数表的内容参数表的内容 类型参数：class（或typename） 标识符 常量参数：类型说明符 标识符 模板参数：template class 标识符 函 数 模 板C+语言程序设计清华大学 郑莉5求绝对值函数的模板求绝对值函数的模板# #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 = - n = -5;5;double d = -double d = -5.5;5.5;coutcout abs( abs(n n) ) endlendl; ;coutcout abs( abs(d d) ) endlendl; ;return 0;return 0; 函 数 模 板运行结果：运行结果：55.5C+语言程序设计清华大学 郑莉6求绝对值函数的模板分析求绝对值函数的模板分析l编译器从调用编译器从调用abs()时实参的类型，推时实参的类型，推导出函数模板的类型参数。例如，对导出函数模板的类型参数。例如，对于调用表达式于调用表达式abs(n)，由于实参，由于实参n为为int型，所以推导出模板中类型参数型，所以推导出模板中类型参数T为为int。l当类型参数的含义确定后，编译器将当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：以函数模板为样板，生成一个函数：int abs(int x) return x 0 ? x : x; 函 数 模 板C+语言程序设计清华大学 郑莉7类模板的作用类模板的作用使用类模板使用户可以为类声明一使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类型的和用户自定义类型）。类 模 板C+语言程序设计清华大学 郑莉8类模板的声明类模板的声明l类模板：类模板：template class 类名类成员声明l如果需要在类模板以外定义其成员如果需要在类模板以外定义其成员函数，则要采用以下的形式：函数，则要采用以下的形式：template 类型名 类名:函数名（参数表）类 模 板C+语言程序设计清华大学 郑莉9例例9-2 类模板应用举例类模板应用举例#include #include #include #include using namespace std;using namespace 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 haveValue; / haveValue标记标记itemitem是否已被是否已被存入内容存入内容public:public:Store();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) 10template /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);/使程序完全退出，返回到操作系统。使程序完全退出，返回到操作系统。 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值存入值存入itemitem 11int 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 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; 12C+语言程序设计清华大学 郑莉13第二部分：群体数据第二部分：群体数据l线性群体线性群体 线性群体的概念 直接访问群体-数组类 顺序访问群体-链表类 栈类 队列类C+语言程序设计清华大学 郑莉14群体的概念群体的概念群体群体是指由多个数据元素组成的集是指由多个数据元素组成的集合体。群体可以分为两个大类：合体。群体可以分为两个大类：线性群线性群体体和和非线性群体非线性群体。线性群体中的元素按位置排列有序，线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元非线性群体不用位置顺序来标识元素。素。C+语言程序设计清华大学 郑莉15线性群体的概念线性群体的概念线性群体中的元素次序与其位置关线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照系是对应的。在线性群体中，又可按照访问元素的不同方法分为访问元素的不同方法分为直接访问直接访问、顺顺序访问序访问和和索引访问索引访问。在本章我们只介绍直接访问和顺序在本章我们只介绍直接访问和顺序访问。访问。第一个元素第二个元素第三个元素最后一个元素C+语言程序设计清华大学 郑莉16数组数组l静态数组是具有固定元素个数的群体，其静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。中的元素可以通过下标直接访问。 缺点：大小在编译时就已经确定，在运行时无法修改。l动态数组由一系列位置连续的，任意数量动态数组由一系列位置连续的，任意数量相同类型的元素组成。相同类型的元素组成。 优点：其元素个数可在程序运行时改变。lvector就是用类模板实现的动态数组。就是用类模板实现的动态数组。l动态数组类模板：例动态数组类模板：例9-3（Array.h）直接访问的线性群体# #ifndefifndef ARRAY_H ARRAY_H#define ARRAY_H#define ARRAY_H#include #include template /template /数组类模板定义数组类模板定义class Array class Array private:private:T T* * list;/ list;/用于存放动态分配的数组内存首地址用于存放动态分配的数组内存首地址intint size; size; /数组大小（元素个数）数组大小（元素个数）public:public:Array(Array(intint szsz = 50); = 50);/构造函数构造函数Array(const Array &a);Array(const Array &a);/拷贝构造函数拷贝构造函数Array();Array();/析构函数析构函数Array & operator = (const Array &Array & operator = (const Array &rhsrhs); /); /重载重载=“=“T & operator (T & operator (intint i i); /); /重载重载”const T & operator (const T & operator (intint i i) const;) const;operator T operator T * * (); (); /重载到重载到T T* *类型的转换类型的转换operator const T operator const T * * () const; () const;intint getSizegetSize() const;() const;/取数组的大小取数组的大小void resize(void resize(intint szsz););/修改数组的大小修改数组的大小;17动态数组类模板程序C+语言程序设计清华大学 郑莉18数组类模板模板的构造函数数组类模板模板的构造函数/ / 构造函数构造函数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+语言程序设计清华大学 郑莉19数组数组类模板的类模板的拷贝构造函数拷贝构造函数/拷贝构造函数拷贝构造函数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 (int i = 0; i size; i+)for (int i = 0; i size; i+)listi = a.listi;listi = a.listi; 直接访问的线性群体C+语言程序设计清华大学 郑莉20浅拷贝浅拷贝 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深拷贝深拷贝 list sizeaa的数组元素占用的内存拷贝前 list sizeaa的数组元素占用的内存拷贝后 list sizebb的数组元素占用的内存C+语言程序设计清华大学 郑莉22数组数组类类模板模板的的重载重载=运算符函数运算符函数/重载重载“=”“=”运算符运算符template template Array &Array:operator = (const Array& rhs) 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复制数组元素到本对象复制数组元素到本对象 for (int i = 0; i size; i+)for (int i = 0; i size; i+)listi = rhs.listi;listi = rhs.listi; return return * *this;this;/返回当前对象的引用返回当前对象的引用 直接访问的线性群体C+语言程序设计清华大学 郑莉23数组数组类模板的类模板的重载下标操作符函数重载下标操作符函数template template T &Array:operator (T &Array:operator (intint n) n) assert(n = 0 & n = 0 & n size);/越界检查越界检查return listn;return listn; / /返回下标为返回下标为n n的数组元素的数组元素 template template const T &Array:operator (const T &Array:operator (intint n) const n) const assert(n = 0 & n = 0 & n size); /越界检查越界检查return listn;return listn; / /返回下标为返回下标为n n的数组元素的数组元素 直接访问的线性群体C+语言程序设计清华大学 郑莉24为什么有的函数返回引用为什么有的函数返回引用l如果一个函数的返回值是一个对象的如果一个函数的返回值是一个对象的值，就不应成为左值。值，就不应成为左值。l如果返回值为引用。由于引用是对象如果返回值为引用。由于引用是对象的别名，通过引用当然可以改变对象的别名，通过引用当然可以改变对象的值。的值。直接访问的线性群体C+语言程序设计清华大学 郑莉25重载指针转换操作符重载指针转换操作符template template Array:operator T Array:operator T * * () () return list;return list; /返回私有数组的首地址返回私有数组的首地址 template template Array:operator const T Array:operator const T * * () const () const return list;return list; /返回私有数组的首地址返回私有数组的首地址 直接访问的线性群体C+语言程序设计清华大学 郑莉26指针转换运算符的作用指针转换运算符的作用#include #include using namespace std;using namespace std;void read(void read(int int * *p p, int n) , int n) for (int i = 0; i n; i+) for (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 int * *p p, int n) , int n) for (int i = 0; i n; i+) for (int i = 0; i pi; cin pi; int main() int main() Array a(10);Array a(10); read( read(a a, 10);, 10); return 0; return 0; 直接访问的线性群体C+语言程序设计清华大学 郑莉27Array类的应用类的应用l例例9-4求范围求范围2N中的质数，中的质数，N在程序在程序运行时由键盘输入。运行时由键盘输入。直接访问的线性群体#include #include #include #include #include Array.h#include Array.husing namespace std;using namespace 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 = 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 if (count = a.getSize() a.resize(count * * 2); 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; 28C+语言程序设计清华大学 郑莉29链表链表l链表是一种动态数据结构，可以用来链表是一种动态数据结构，可以用来表示顺序访问的线性群体。表示顺序访问的线性群体。l链表是由系列链表是由系列结点结点组成的，结点可以组成的，结点可以在运行时动态生成。在运行时动态生成。l每一个结点包括每一个结点包括数据域数据域和指向链表中和指向链表中下一个结点的下一个结点的指针指针（即下一个结点的（即下一个结点的地址）。如果链表每个结点中只有一地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称个指向后继结点的指针，则该链表称为单链表。为单链表。顺序访问的线性群体C+语言程序设计清华大学 郑莉30单链表单链表 data1 data1 data2 data2 data3 data3 datan NULL datan NULLheadheadrearrear顺序访问的线性群体C+语言程序设计清华大学 郑莉31单链表的结点类模板单链表的结点类模板template template class Node class Node private: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; ; 顺序访问的线性群体C+语言程序设计清华大学 郑莉32在结点之后插入一个结点在结点之后插入一个结点 data1 data2 p datatemplate template void Node:void Node:insertAfterinsertAfter(Node (Node * *p) p) /p /p节点指针域指向当前节点的后继节点节点指针域指向当前节点的后继节点 p-next = next; p-next = next; next = p; / next = p; /当前节点的指针域指向当前节点的指针域指向p p 顺序访问的线性群体C+语言程序设计清华大学 郑莉33 删除结点之后的结点删除结点之后的结点顺序访问的线性群体 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+语言程序设计清华大学 郑莉34链表的基本操作链表的基本操作l生成结点生成结点l插入结点插入结点l查找结点查找结点l删除结点删除结点l遍历链表遍历链表l清空链表清空链表顺序访问的线性群体C+语言程序设计清华大学 郑莉35链表类模板链表类模板(例例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:/数据成员：数据成员：Node Node * *front, front, * *rearrearNode Node * *prevPtr, prevPtr, * *currPtr; currPtr; int size;int size;int position;int position;Node Node * *newNode(const T &item,Node newNode(const T &item,Node * *ptrNext=NULL);ptrNext=NULL);void freeNode(Node void freeNode(Node * *p);p);void copy(const LinkedList& L);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;bool 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(const 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() constvoid clear();void clear();#endif /LINKEDLIST_H#endif /LINKEDLIST_HC+语言程序设计清华大学 郑莉36链表类应用举例链表类应用举例(例例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; 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 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() while (!list.endOfList() cout list.data() ;cout list.data() ;list.nextlist.next cout endl;cout endl;return 0;return 0; C+语言程序设计清华大学 郑莉37特殊的线性群体特殊的线性群体栈栈栈是只能从一端访问的线性群体，栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈可以访问的这一端称栈顶，另一端称栈底。底。ana2a1入栈出栈栈顶栈底特殊的线性群体栈C+语言程序设计清华大学 郑莉38栈的应用举例栈的应用举例表达式处理表达式处理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+语言程序设计清华大学 郑莉39栈的基本状态栈的基本状态l栈空栈空 栈中没有元素l栈满栈满 栈中元素个数达到上限l一般状态一般状态 栈中有元素，但未达到栈满状态特殊的线性群体栈栈顶ana1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态（栈空）maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满状态40C+语言程序设计清华大学 郑莉41栈的基本操作栈的基本操作l初始化初始化l入栈入栈l出栈出栈l清空栈清空栈l访问栈顶元素访问栈顶元素l检测栈的状态（满、空）检测栈的状态（满、空）特殊的线性群体栈C+语言程序设计清华大学 郑莉42栈类模板栈类模板(例例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;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+语言程序设计清华大学 郑莉43栈的应用栈的应用l例例9.9 一个简单的整数计算器一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算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 Stack.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 &opnd2);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_H44/Calculator.cpp/Calculator.cpp#include Calculator.h#include Calculator.h#include #include #include #include #include #include using namespace std;using namespace std;/工具函数，用于将字符串转换为实数工具函数，用于将字符串转换为实数inline double stringToDouble(const string &str) inline double stringToDo