清华大学c+课件第9章

《清华大学c+课件第9章》由会员分享，可在线阅读，更多相关《清华大学c+课件第9章（92页珍藏版）》请在金锄头文库上搜索。

1、第九章 群体类 和群体数据的组织,清华大学 郑 莉,C+语言程序设计,2,本章主要内容,模板 群体类 群体数据的组织 深度探索,3,第一部分：模板,函数模板 类模板,4,函数模板,函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。 定义方法： template 函数定义,函 数 模 板,5,求绝对值函数的模板,#include using namespace std; template T abs(T x) return x 0? -x : x; int main() int n = -5; double d = -5.5; cout abs(n) e

2、ndl; cout abs(d) endl; return 0; ,函 数 模 板,运行结果： 5 5.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; / 结构体Student struct Student int id; /学号 float gpa; /平均分 ;,类 模 板,template class Store /类模板：实现对任意类型数据进行存取 private: T item; / item用于存放任意

4、类型的数据 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); cout d; cout “Retrieving objec

5、t 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;/用于存放动态分配的数组内存首地址 i

7、nt size; /数组大小（元素个数） public: Array(int sz = 50); /构造函数 Array(const Array ,17,动态数组类模板程序,18,数组类模板模板的构造函数,/ 构造函数 template Array:Array(int sz) /sz为数组大小（元素个数），应当非负 assert(sz = 0); / 将元素个数赋值给变量size size = sz; /动态分配size个T类型的元素空间 list = new T size; ,直接访问的线性群体,19,数组类模板的拷贝构造函数,/拷贝构造函数 template Array:Array(con

8、st Array ,直接访问的线性群体,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; ,#i

10、nclude “Array.h“ #include 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.h“ using namespace std; int main() Array a(10); / 用来存放质数的数组，初始状

11、态有10个元素。 int n, count = 0; cout = 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;

12、 i count; i+) cout setw(8) ai; cout endl; return 0; ,28,29,链表,链表是一种动态数据结构，可以用来表示顺序访问的线性群体。 链表是由系列结点组成的，结点可以在运行时动态生成。 每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。,顺序访问的线性群体,30,单链表,顺序访问的线性群体,31,单链表的结点类模板,template class Node private: Node *next; public: T data; Node(const T,顺序访

13、问的线性群体,32,在结点之后插入一个结点,data1,p,data,template void 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,链表的基

14、本操作,生成结点 插入结点 查找结点 删除结点 遍历链表 清空链表,顺序访问的线性群体,35,链表类模板(例9-6),顺序访问的线性群体,#ifndef LINKEDLIST_H #define LINKEDLIST_H #include “Node.h“ template class LinkedList private: /数据成员： Node *front, *rear Node *prevPtr, *currPtr; int size; int position; Node *newNode(const T ,LinkedList #endif /LINKEDLIST_H,链表类应用举

15、例(例9-7),从键盘输入10个整数，用这些整数值作为结点数据，生成一个链表，按顺序输出链表中结点的数值。然后从键盘输入一个待查找整数，在链表中查找该整数，若找到则删除该整数所在的结点（如果出现多次，全部删除），然后输出删除结点以后的链表。在程序结束之前清空链表。,37,链表类应用举例(例9-7),顺序访问的线性群体,/9_7.cpp #include #include “LinkedList.h“ using 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: “; list.reset(); while (!list.endOfList() cout list.data(