第09章_群体类和群体数据的组织.ppt

1、本章主要内容,函数模板 类模板 String类 群体类 群体数据的组织,9.0 函数模板,函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。 声明方法： template 函数声明,函 数 模 板,求绝对值函数的模板,#include using namespace std; template T abs(T x) return x0?-x:x; void main() int n=-5; double d=-5.5; coutabs(n)endl; coutabs(d)endl; ,运行结果： 5 5.5,求绝对值函数的模板分析,编译器从调用abs(

2、)时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。 当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：int abs(int x) return x0?-x:x; ,类模板用于设计一个通用类，使这个类的数据成员的类型、成员函数的参数能够按照需要进行改变（即参数化） 声明类模板的一般形式为： template class class_name 其中，Ttype是一个标识符，代表所声明的类模板中参数化的类型名。注意：模板类的成员函数必须是函数模板。 定义了类模板以后，就可以创建这个类的实例： Clas

3、s_name 对象1，对象n； type用具体的数据类型代入，系统根据代入的数据类型生成所需的类，并创建该类的对象。,9.1 类模板,/EX9_1.cpp : 演示类模板的定义和使用 #include #include struct student/声明一个结构体类型 int id ; int score ; ; template/声明一个类模板 class buffer private: T a ; int empty ; public: buffer( void ) ;/声明buffer类的构造函数 T get( void ) ; void put( T x) ; ;,template/定

4、义buffer类的构造函数模板 buffer:buffer( void ):empty(0) template/定义成员函数get模板 T buffer:get(void) if (empty=0) cout/定义成员函数put模板 void buffer:put(T x) empty+; a = x; ,void main(void) student s = 1022, 78 ; buffer i1, i2 ;/声明整型对象i1, i2 buffer stu1 ;/声明结构体对象stu1 buffer d ;/声明双精度对象d i1.put(13) ;/对象i1调用put执行了empty+

5、i2.put(-101) ;/对象i2调用put执行了empty+ couti1.get( ) i2.get( ) endl ; stu1.put( s ) ;/对象stu1调用put执行了empty+ coutthe students id is stu1.get( ).idendl ; coutthe students score is stu1.get( ).scoreendl ; coutd.get( )endl ;/对象d没有调用put去执行empty+ /，可能直接exit而不执行return a,程序运行结果为： 13 -101 the students id is 1022 t

6、he students score is 78 the buffer is empty!,1. string类对象的定义与初始化 形式1：string 对象名(字符串)/ 表示可选项 或 string 对象名=字符串/ 表示可选项 形式2：（生成由n个“字符”组成的字符串） string 对象名(n，字符) 2. string类对象的操作 通过string类对象的成员函数调用与重载运算符(、 . ,string类,/EX9_2.cpp : 演示string类的应用 #include #include using namespace std ; void main( ) string s1(He

7、llo), s2, s3, s4 ;/定义string对象 s2 = s1 ; /用=号进行赋值(重载运算符=) s3.assign(s1); /调用成员函数assign( )进行赋值 couts1=s1.data( ), s2=s2.data( ) , s3=s3.data( )endl ; couts1的长度=s1.length( )endl; /输出字符串长度 char a =China!, b6 ; s1 = a ;/string对象s1接收字符数组a的赋值 couts1=s1.data( )endl ; for( int i=0; i5; i+ ) bi = s2i ;/此语句也可表

8、示为:bi=s2.at(i); b5= 0; cout字符数组b= bendl ; /字符串的连接 s4=s2+ +s1; /用+进行字符串的连接(重载运算符+) s3=s2.append( s1 ) ; /s2与s1连接并赋给s3，注意连接后的s2结果,couts2=s2.data( ), s3=s3.data( ), s4= s4.data( )endl ; int f=pare( 6, 5, s4, 7, 5 ) ;/将s3的第6个开始的5个字符与/s4的第7个开始的5个字符进行比较 if ( f=0 ) couts3与s4比较的部分相等n; else couts3与s4比较的部分不相等

9、n; /取子字符串操作 string sz=s2.substr( 5, 5 ) ; /取s2的第5个开始的5个字符 cout子字符串sz=sz.data( )endl ; s1.swap(s4) ;/交换s1与s4 couts1=s1.data(), s4=s4.data()endl ; cout字符串China在s1中的位置为： s1.find(China)endl; int len=s1.length( ) ; char *pt=new charlen+1 ; /定义字符型指针并动态分配空间 s1.copy(pt,len,0) ; /将s1复制到pt所指的数组(相当于pt= ,程序运行结果

10、为: s1=Hello, s2=Hello, s3=Hello s1的长度=5 s1=China! 字符数组b= Hello s2=HelloChina!, s3=HelloChina!, s4=Hello China! s3与s4比较的部分相等 子字符串sz=China s1=Hello China!, s4=China! 字符串China在s1中的位置为: 6 Hello China! Hello China!,9.2 群体数据,群体的概念,群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。 线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。

11、,非线性群体不用位置顺序来标识元素。,9.2.1 线性群体的概念,线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。 9.2.2 直接访问群体数组 静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修改。 动态数组由一系列位置连续的，任意数量相同类型的元素组成。优点：其元素个数可在程序运行时改变。动态数组类模板举例参见P293301,9.2.3 顺序访问群体链表,链表是一种动态数据结构，可以用来表示顺序访 问的线性群体。 链表是由系列结点组成的，结点可以在运行时动 态生成

12、。 每一个结点包括数据域和指向链表中下一个结点 的指针（即下一个结点的地址）。如果链表每个结点 中只有一个指向后继结点的指针，则该链表称为单链 表。 链表模板和应用举例参见P302307,9.2.4 特殊的线性群体栈,栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。,1. 栈的应用举例函数调用,2. 栈的基本状态,栈空：栈中没有元素 栈满：栈中元素个数达到上限 一般状态：栈中有元素，但未达到栈满状态,20,3. 栈的基本操作,初始化 入栈 出栈 清空栈 访问栈顶元素 检测栈的状态（满、空） 栈类模板和应用举例参见P307313,9.2.5 特殊的线性群体队列,队列是只能向一

13、端添加元素，从另一端删除元素的线性群体,1. 队列的基本状态,队空：队列中没有元素 队满：队列中元素个数达到上限 一般状态：队列中有元素，但未达到队满状态,2. 循环队列,在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。 队列类模板参见P313316,9.3 群体数据的组织,插入排序 选择排序 交换排序,顺序查找 折半查找,排序（sorting）,排序是计算机程序设计中的一种重要操作，它的 功能是将一个数据元素的任意序列，重新排列成一个按 关键字有序的序列。 数据元素： 数据的基本单位。在计算机中通常作为一个整体 进行考虑。一个数据元素可

14、由若干数据项组成。 关键字： 数据元素中某个数据项的值，用它可以标识（识 别）一个数据元素。 在排序过程中需要完成两种基本操作： 比较两个数的大小 调整元素在序列中的位置,内部排序与外部排序,内部排序： 待排序的数据元素存放在计算机内存中进行的排 序过程。内部排序方法: 插入排序 选择排序 交换排序 外部排序： 待排序的数据元素数量很大，以致内存存中一次 不能容纳全部数据，在排序过程中尚需对外存进行访 问的排序过程。,9.3.1 插入排序,每一步将一个待排序元素按其关键字值的大小插入到已排 序序列的适当位置上，直到待排序元素插入完为止。,直接插入排序,/9_11.h : 直接插入排序函数模板

15、template void InsertionSort(T A , int n) int i, j ; T temp; for (i = 1; i 0 / 插入位置找到，立即插入 ,9.3.2 选择排序,每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。,直接选择排序,/9_12.h : 直接选择排序函数模板 template void Swap ( T / 将这一趟找到的最小元素与A I 交换 ,9.3.3 交换排序,两两比较待排序序列中的元素，并交换不满足顺序要求的各 对元素，直到全部满足顺序要求为止。 最简单的交换排序方法起

16、泡排序。 对具有n个元素的序列按升序进行起泡排序的步骤： 首先将第一个元素与第二个元素进行比较，若为逆序，则将 两元素交换。然后比较第二、第三个元素，依次类推，直到第n- 1和第n个元素进行了比较和交换。此过程称为第一趟起泡排序。 经过第一趟，最大的元素便被交换到第n个位置。 对前n-1个元素进行第二趟起泡排序，将其中最大元素交换 到第n-1个位置。 如此继续，直到某一趟排序未发生任何交换时，排序完毕。 对n个元素的序列，起泡排序最多需要进行n-1趟。,起泡排序举例：对整数序列 8 5 2 4 3 按升序排序,/9_13.h : 起泡排序函数模板,template void Swap (T ,

17、template void BubbleSort(T A , int n) int i, j ; int lastExchangeIndex ; i = n-1; while ( i 0 ) lastExchangeIndex = 0 ; for ( j = 0 ; j I ; j+ ) if ( A j+1 A j ) Swap( A j , A j+1 ) ; lastExchangeIndex = j ; i = lastExchangeIndex ; ,9.3.4 顺序查找,基本思想是从序列的首元素开始，逐个元素与待查找的关 键字进行比较，直到找到相等的。若整个序列中没有与待查找 关键

18、字相等的元素，就是查找不成功。 /9_14.h : 顺序查找函数模板 template int SeqSearch( T list , int n, T key ) for( int i=0; i n; i+ ) if ( list i = key ) return i;/若找到，返回该元素下标 return -1; /没找到，返回-1 ,9.3.5 折半查找,先按关键字排序，将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。,/9_15.h : 折半查找函数模板 template int BinSearch( T list , int n, T key ) int mid, low, high ; T