《C++语言程序设计(清华大学郑莉)九ppt课件.ppt》由会员分享，可在线阅读，更多相关《C++语言程序设计(清华大学郑莉)九ppt课件.ppt（90页珍藏版）》请在三一办公上搜索。
1、第九章 群体类和群体数据的组织,清华大学 郑 莉,C+语言程序设计,2,本章主要内容,模板群体类群体数据的组织深度探索,3,第一部分：模板,函数模板类模板,4,函数模板,函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。定义方法：template 函数定义模板参数表的内容类型参数：class（或typename） 标识符常量参数：类型说明符 标识符模板参数：template class 标识符,函 数 模 板,5,求绝对值函数的模板,#include using namespace std;templateT abs(T x) return x 0?
2、-x : x;int main() int n = -5;double d = -5.5;cout abs(n) endl;cout abs(d) endl;return 0;,函 数 模 板,运行结果：55.5,6,求绝对值函数的模板分析,编译器从调用abs()时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：int abs(int x) return x 0 ? x : x;,函 数 模 板,7,类模板的作用,使用类模板使用户可以为类声明一种模式
3、，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。,类 模 板,8,类模板的声明,类模板：template class 类名类成员声明如果需要在类模板以外定义其成员函数，则要采用以下的形式：template 类型名 类名:函数名（参数表）,类 模 板,9,例9-2 类模板应用举例,#include #include using namespace std;/ 结构体Studentstruct Student int id; /学号 float gpa; /平均分;,类 模 板,template class Store /类模板：
4、实现对任意类型数据进行存取private:T item;/ item用于存放任意类型的数据bool haveValue; / haveValue标记item是否已被存入内容public:Store();/ 缺省形式（无形参）的构造函数T /以下实现各成员函数。template /缺省构造函数的实现 Store:Store(): haveValue(false) ,10,template /提取数据函数的实现T / 将x值存入item,11,int main() Store s1, s2;s1.putElem(3);s2.putElem(-7);cout s3;s3.putElem(g); co
5、ut d;cout Retrieving object D. ;cout d.getElem() endl/由于d未经初始化,在执行函数D.getElement()过程中导致程序终止return 0;,12,13,第二部分：群体数据,线性群体线性群体的概念直接访问群体-数组类顺序访问群体-链表类栈类队列类,14,群体的概念,群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。,15,线性群体的概念,线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问
6、元素的不同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。,16,数组,静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修改。动态数组由一系列位置连续的，任意数量相同类型的元素组成。优点：其元素个数可在程序运行时改变。vector就是用类模板实现的动态数组。动态数组类模板：例9-3（Array.h）,直接访问的线性群体,#ifndef ARRAY_H#define ARRAY_H#include template /数组类模板定义class Array private:T* list;/用于存放动态分配的数组
7、内存首地址int size;/数组大小（元素个数）public:Array(int sz = 50);/构造函数Array(const Array ,17,动态数组类模板程序,18,数组类模板模板的构造函数,/ 构造函数template Array:Array(int sz) /sz为数组大小（元素个数），应当非负assert(sz = 0);/ 将元素个数赋值给变量sizesize = sz;/动态分配size个T类型的元素空间list = new T size;,直接访问的线性群体,19,数组类模板的拷贝构造函数,/拷贝构造函数template Array:Array(const Arra
8、y ,直接访问的线性群体,20,浅拷贝,int main() Array a(10); . Array b(a); .,template Array:Array(const Array,21,深拷贝,22,数组类模板的重载=运算符函数,/重载“=”运算符template Array /返回当前对象的引用,直接访问的线性群体,23,数组类模板的重载下标操作符函数,template T /返回下标为n的数组元素,直接访问的线性群体,24,为什么有的函数返回引用,如果一个函数的返回值是一个对象的值，就不应成为左值。如果返回值为引用。由于引用是对象的别名，通过引用当然可以改变对象的值。,直接访问的线性
9、群体,25,重载指针转换操作符,template Array:operator T * () return list;/返回私有数组的首地址template Array:operator const T * () const return list;/返回私有数组的首地址,直接访问的线性群体,26,指针转换运算符的作用,#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#incl
10、ude using namespace std;void read(int *p, int n) for (int i = 0; i pi;int main() Array a(10); read(a, 10); return 0;,直接访问的线性群体,27,Array类的应用,例9-4求范围2N中的质数，N在程序运行时由键盘输入。,直接访问的线性群体,#include #include #include Array.husing namespace std;int main() Array a(10);/ 用来存放质数的数组，初始状态有10个元素。int n, count = 0;cout
11、= 2 as upper limit for prime numbers: ;cin n;for (int i = 2; i = n; i+) bool isPrime = true;for (int j = 0; j count; j+)if (i % aj = 0) /若i被aj整除，说明i不是质数isPrime = false; break;if (isPrime) if (count = a.getSize() a.resize(count * 2);acount+ = i;for (int i = 0; i count; i+)cout setw(8) ai;cout endl;re
12、turn 0;,28,29,链表,链表是一种动态数据结构，可以用来表示顺序访问的线性群体。链表是由系列结点组成的，结点可以在运行时动态生成。每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。,顺序访问的线性群体,30,单链表,顺序访问的线性群体,31,单链表的结点类模板,template class Node private: Node *next;public: T data; Node(const T,顺序访问的线性群体,32,在结点之后插入一个结点,data1,p,data,template void
13、 Node:insertAfter(Node *p) /p节点指针域指向当前节点的后继节点 p-next = next; next = p; /当前节点的指针域指向p ,顺序访问的线性群体,33,删除结点之后的结点,顺序访问的线性群体,data1,Node *Node:deleteAfter(void) Node *tempPtr = next; if (next = 0) return 0; next = tempPtr-next; return tempPtr; ,tempPtr,34,链表的基本操作,生成结点插入结点查找结点删除结点遍历链表清空链表,顺序访问的线性群体,35,链表类模板(
14、例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 ,LinkedList #endif /LINKEDLIST_H,36,链表类应用举例(例9-7),顺序访问的线性群体,/9_7.cpp#include #include LinkedList.husin
15、g namespace std;int main() LinkedList list;for (int i = 0; i item;list.insertFront(item);cout List: ;list.reset();while (!list.endOfList() cout list.data() ;list.next();cout endl;,int key;cout key;list.reset();while (!list.endOfList() if (list.data() = key) list.deleteCurrent();list.next();cout List
16、: ;list.reset();while (!list.endOfList() cout list.data() ;list.nextcout endl;return 0;,37,特殊的线性群体栈,栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。,特殊的线性群体栈,38,栈的应用举例表达式处理,特殊的线性群体栈,39,栈的基本状态,栈空栈中没有元素栈满栈中元素个数达到上限一般状态栈中有元素，但未达到栈满状态,特殊的线性群体栈,40,41,栈的基本操作,初始化入栈出栈清空栈访问栈顶元素检测栈的状态（满、空）,特殊的线性群体栈,42,栈类模板(例9-8),特殊的线性群体栈,/
17、Stack.h#ifndef STACK_H#define STACK_H#include template class Stack private:T listSIZE;int top;,ublic:Stack();void push(const T /类的实现略,43,栈的应用,例9.9 一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算3+5则输入3 5 +。乘方运算符用表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入c。当键入q时程序结束。Calculator.
18、h Calculator.cpp 9_9.cpp,特殊的线性群体栈,/Calculator.h#ifndef CALCULATOR_H#define CALCULATOR_H#include Stack.h/ 包含栈类模板定义文件class Calculator /计算器类private:Stack s;/ 操作数栈void enter(double num);/将操作数num压入栈/连续将两个操作数弹出栈，放在opnd1和opnd2中bool getTwoOperands(double #endif /CALCULATOR_H,44,/Calculator.cpp#include Calcu
19、lator.h#include #include #include using namespace std;/工具函数，用于将字符串转换为实数inline double stringToDouble(const string ,45,bool Calculator:getTwoOperands(double ,46,void Calculator:compute(char op) /执行运算double operand1, operand2;bool result = getTwoOperands(operand1, operand2); if (result) /如果成功，执行运算并将运算结
20、果压入栈switch(op) case +: s.push(operand2 + operand1); break;case -: s.push(operand2 - operand1); break;case *: s.push(operand2 * operand1); break;case /:if (operand1 = 0) /检查除数是否为0cerr Divided by 0! endl;s.clear();/除数为0时清空栈 elses.push(operand2 / operand1);break;case : s.push(pow(operand2, operand1); b
21、reak;default:cerr Unrecognized operator! endl;break;cout = s.peek() ;/输出本次运算结果 elses.clear();/操作数不够，清空栈,47,void Calculator:run() /读入并处理后缀表达式string str;while (cin str, str != q) switch(str0) case c: s.clear(); break;case -: /遇-需判断是减号还是负号if (str.size() 1)enter(stringToDouble(str);elsecompute(str0);bre
22、ak;case +:/遇到其它操作符时case *:case /:case :compute(str0);default: /若读入的是操作数，转换为整型后压入栈enter(stringToDouble(str); break;void Calculator:clear() /清空操作数栈s.clear(); ,48,/9_9.cpp#include Calculator.hint main() Calculator c;c.run();return 0;,49,50,特殊的线性群体队列,队列是只能向一端添加元素，从另一端删除元素的线性群体,51,队列的基本状态,队空队列中没有元素队满队列中元
23、素个数达到上限一般状态队列中有元素，但未达到队满状态,特殊的线性群体队列,元素移动方向,元素移动方向,52,53,循环队列,在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。,特殊的线性群体队列,54,55,第三部分：群体数据的组织,插入排序选择排序交换排序顺序查找折半查找,56,排序（sorting）,排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。关键字：数据元素中某个数据项的值，用它
24、可以标识（识别）一个数据元素。在排序过程中需要完成两种基本操作：比较两个数的大小调整元素在序列中的位置,群体数据的组织,57,内部排序与外部排序,内部排序：待排序的数据元素存放在计算机内存中进行的排序过程。外部排序：待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。,群体数据的组织,58,内部排序方法,插入排序选择排序交换排序,群体数据的组织,59,插入排序的基本思想,每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。,初始状态： 5 4 10 20 12 3,60,直接插入排序,在插入排序过程中
25、，由于寻找插入位置的方法不同又可以分为不同的插入排序算法，这里我们只介绍最简单的直接插入排序算法。例9-11 直接插入排序函数模板（9_11.h）,群体数据的组织,template void insertionSort(T a, int n) int i, j;T temp;for (int i = 1; i 0 ,直接插入排序函数模板（9_11.h）,61,62,选择排序的基本思想,每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。,3 4 10 20 12 5,3 4 10 20 12 5,第 i 次选择后，将选出的那个记录与
26、第 i 个记录做交换。,63,直接选择排序,在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是通过顺序比较找出待排序序列中的最小元素，称为直接选择排序。例9-12 直接选择排序函数模板（9-12.h）,群体数据的组织,template void mySwap(T ,直接选择排序函数模板（9-12.h）,64,65,交换排序的基本思想,两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。,群体数据的组织,66,最简单的交换排序方法 起泡排序,对具有n个元素的序列按升序进行起泡排序的步骤：首先将第一个元素与第二个元素进行
27、比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，依次类推，直到第n-1和第n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第n个位置。对前n-1个元素进行第二趟起泡排序，将其中最大元素交换到第n-1个位置。如此继续，直到某一趟排序未发生任何交换时，排序完毕。对n个元素的序列，起泡排序最多需要进行n-1趟。,群体数据的组织,67,起泡排序举例,对整数序列 8 5 2 4 3 按升序排序,85243,5,2,4,3,8,2,4,3,5,8,2,3,4,5,8,2,3,4,5,8,初始状态,第一趟结果,第二趟结果,第三趟结果,第四趟结果,小的逐渐上升,每
28、趟沉下一个最大的,群体数据的组织,68,例9-13 起泡排序函数模板,template void mySwap(T ,template void bubbleSort(T a, int n) int i = n 1;while (i 0) int lastExchangeIndex = 0;for (int j = 0; j i; j+)if (aj + 1 aj) mySwap(aj, aj + 1);lastExchangeIndex = j;i = lastExchangeIndex;,群体数据的组织,69,顺序查找,其基本思想从序列的首元素开始，逐个元素与待查找的关键字进行比较，直到找
29、到相等的。若整个序列中没有与待查找关键字相等的元素，就是查找不成功。顺序查找函数模板例9-14,群体数据的组织,template int seqSearch(const T list, int n, const T ,顺序查找函数模板,70,71,折半查找的基本思想,对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。,群体数据的组织,72,折半查找举例,用折半查找法，在下列序列中查找值为21的元素：,M=INT(L+H)/2)=3,L=M+1=4,M=INT(L+H)/2)
30、=4,73,例9-15 折半查找函数模板,template int binSearch(const T list, int n, const T ,群体数据的组织,类模板 vs 类,类模板不能表示具体的数据类型，但类模板的实例化类是数据类型例：如要使reverse函数接收Array的参数void reverse(Array 正确。T虽未定，但Array表示的是一个类模板实例。同一模板在不同参数下的实例是完全无关的类型彼此不兼容，无法相互赋值通过Store的对象调用的成员函数，无法直接访问Store对象的私有成员,74,深度探索,函数模板 vs 函数,函数模板本身不是函数编译器不会为函数模板本身
31、生成目标代码只有函数模板的实例能被调用例：考虑下列模板template void outputArray(const T *array, int count);若a是int数组，outputArray(a, 10)等价于outputArray(a, 10)，被调用的是outputArray实例,75,深度探索,隐含实例化,模板的实例化根据函数模板生成具体的函数、或根据类模板生成具体的类的过程隐含实例化编译器会自动按需对模板实例化所有会被使用的模板实例会被生成对类模板的隐含实例化并不意味着对它成员函数的定义也进行实例化，当类模板成员函数会被使用时，才会被实例化,76,深度探索,多文件结构中模板的
32、组织,模板实例化机制带来的新问题不能把下面与模板相关的定义放在源文件中函数模板的定义类模板成员函数类模板静态数据成员解决方法把与模板相关的定义放在头文件中最通常的解决办法编译器有特殊处理，保证不会有连接冲突使用export关键字编译器支持不好使用模板的显式实例化机制,77,深度探索,显式实例化,语法形式template 实例化目标的声明;作用一个模板实例无论是否在本编译单元中被使用，都会被生成例template void outputArray(const int *array, int count);template class Store;在多文件结构中的用途使用在程序中可能会被用到的各种
33、参数对模板显式实例化，使得与模板相关的定义可以放在源文件中,78,深度探索,为模板定义特殊的实现,为什么要定义特殊的实现？模板抓住了算法与数据结构上的共性，但忽略了类型的个性设计出的模板对于具体的数据类型而言未必具有最好的效率例：Stack类模板如果以bool作为类型参数，则有7/8的空间浪费Stack中的list数组占32个字节，实际上4个字节就够,79,深度探索,模板的特化,什么是特化为一个模板在特定参数下提供特殊定义既适用于类模板，又适用于函数模板对Stack特化的类定义,template class Stack private:unsigned list;int top;public:
34、Stack();void push(bool item);bool pop();void clear();bool peek() const;bool isEmpty() const;bool isFull() const;,80,深度探索,/特化类的部分成员函数定义void Stack:push(bool item) assert(!isFull();+top;list = (list :pop() assert(!isEmpty();bool result = (list ,81,类模板的偏特化,对Stack特化的问题适用范围过窄，SIZE必须是32类模板的偏特化将一部分参数固定，而使另一
35、部分参数可变，设计特殊的定义只适用于类模板对Stack偏特化的类定义,template class Stack private:enum UNIT_BITS = sizeof(unsigned) * 8,ARRAY_SIZE = (SIZE - 1) / UNIT_BITS + 1;unsigned listARRAY_SIZE;int top;public:Stack();void push(bool item);bool pop();void clear();bool peek() const;bool isEmpty() const; bool isFull() const;,82,深度
36、探索,/偏特化类的部分成员函数定义template void Stack:push(bool item) assert(!isFull();int index = +top / UNIT_BITS;listindex = (listindex bool Stack:pop() assert(!isEmpty();int index = top- / UNIT_BITS;bool result = (listindex ,83,类模板的偏特化,偏特化不仅允许将一部分模板参数固定，还允许将某一个模板参数所能表示的类型范围缩窄，例template class X ;原模板，T可以是所有类型参数tem
37、plate class X ;针对指针类型进行偏特化template class X ;针对常指针类型进行偏特化对于X，后两个偏特化版本皆能匹配，但由于第二个更为特殊，会被选中,84,深度探索,函数模板的重载,函数模板不支持偏特化，但可重载，从而完成与类模板偏特化类似的功能若对函数模板的一次使用能与多个函数模板匹配，最特殊的那个会被选中例：针对参数为指针类型的情形，为myMax定义特殊实现,template T myMax(T a, T b) return (a b) ? a : b;template T *myMax(T *a, T *b) return (*a *b) ? a : b;,8
38、5,深度探索,模板元编程,什么是模板元编程在模板实例化的同时利用编译器完成一些计算任务模板元编程可以把一些通常在运行时才能计算的任务提前到编译时，从而：提高程序运行效率提供一些方便例：模板元编程的计算结果可以作为静态数组的大小,86,深度探索,例：编译时计算n!,template struct Factorial /计算N的阶乘 enum VALUE = N * Factorial:VALUE ;template struct Factorial /设定N = 0时N的阶乘enum VALUE = 1 ;,87,深度探索,Factorial的分析,Factorial的使用例：int s Fac
39、torial:VALUE ;Factorial:VALUE的计算过程首先试图实例化Factorial；要计算Factorial的VALUE，需实例化Factorial，然后是Factorial实例化Factorial时，由于Factorial:VALUE的值已确定，Factorial的VALUE值可计算，完成实例化；Factorial到Factorial的实例化相继完成,88,89,例：整数次乘方的展开,template struct Power template static T value(T x) return x * Power:value(x); ;template struct Power template static T value(T x) return x; ;,template inline T power(T v) return Power:value(v);,90,小结与复习建议,主要内容模板、群体类和群体数据的组织达到的目标理解模板的作用，学会简单的应用。以群体类以及查找、排序算法为综合例题，对前面章节的内容进行全面复习；掌握一些常用的数据结构和算法，能够解决一些略复杂的问题，也为下一章学习C+标准模板库打下基础。实验任务实验九,
