《群体类和群体数据的组织.ppt》由会员分享，可在线阅读，更多相关《群体类和群体数据的组织.ppt（54页珍藏版）》请在三一文库上搜索。
1、本章主要内容,函数模板 类模板 String类 群体类 群体数据的组织,9.0 函数模板,函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。 声明方法： template 函数声明,函 数 模 板,模板参数表,模板参数表由用逗号分隔的模板参数构成，可以包括以下形式内容： 1）typename/class 标识符 如typename T,指明可以接收一个类型参数。这些类型参数代表的是类型，可以是内部类型或者自定义类型。 2）类型说明符 标志符 如 int val，指明可以接收一个由类型说明符所规定类型的常量作为参数。 3）template class 标
2、志符 如templateclass Container指明可以接收一个类模板作为参数。,求绝对值函数的模板,#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()时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。 当类型参数的含义
3、确定后，编译器将以函数模板为样板，生成一个函数： int abs(int x) return x0?-x:x; ,类模板用于设计一个通用类，使这个类的数据成员的类型、成员函数的参数能够按照需要进行改变（即参数化） 声明类模板的一般形式为： template class class_name 其中，Ttype是一个标识符，代表所声明的类模板中参数化的类型名。注意：模板类的成员函数必须是函数模板。 定义了类模板以后，就可以创建这个类的实例： Class_name 对象1，对象n； type用具体的数据类型代入，系统根据代入的数据类型生成所需的类，并创建该类的对象。,9.1 类模板,/EX9_1.c
4、pp : 演示类模板的定义和使用 #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 /定义buffer类的构造函数模板 buffer:buffer( void ):empty(0) template /
5、定义成员函数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+ i2.put(-101) ; /对象i2调用put执行了empty+ couti1.get( )“ “
6、i2.get( ) endl ; stu1.put( s ) ; /对象stu1调用put执行了empty+ cout“the students id is “stu1.get( ).idendl ; cout“the students score is “stu1.get( ).scoreendl ; coutd.get( )endl ; /对象d没有调用put去执行empty+ /，可能直接exit而不执行return a,程序运行结果为： 13 -101 the students id is 1022 the students score is 78 the buffer is empt
7、y!,1. string类对象的定义与初始化 形式：string 对象名(“字符串“) / 表示可选项 或 string 对象名=“字符串” / 表示可选项 2. string类对象的操作 通过string类对象的成员函数与重载运算符(、 . ,string类,/EX9_2.cpp : 演示string类的应用 #include #include using namespace std ; void main( ) string s1(“Hello“), s2, s3, s4 ; /定义string对象 s2 = s1 ; /用“=“号进行赋值(重载运算符=) s3.assign(s1); /
8、调用成员函数assign( )进行赋值 cout“s1=“s1.data( )“, s2=“s2.data( ) “, s3=“s3.data( )endl ; cout“s1的长度=“s1.length( )endl; /输出字符串长度 char a =“China!“, b6 ; s1 = a ; /string对象s1接收字符数组a的赋值 cout“s1=“s1.data( )endl ; for( int i=0; i5; i+ ) bi = s2i ; / b5= 0; cout“字符数组b= “bendl ; /字符串的连接 s4=s2+“ “+s1; /用“+“进行字符串的连接(
9、重载运算符+) s3=s2.append( s1 ) ; /s2与s1连接并赋给s3，注意连接后的s2结果,cout“s2=“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 ) cout“s3与s4比较的部分相等“n“; else cout“s3与s4比较的部分不相等“n“; /取子字符串操作 string sz=s2.substr( 5, 5 ) ; /取s2的第5个开始的5个字符 cou
10、t“子字符串sz=“sz.data( )endl ; s1.swap(s4) ; /交换s1与s4 cout“s1=“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所指的数组，从s10处开始复制len个字符 ptlen= 0 ; coutptendl ; s2 = pt ; /string类对象s2接收
11、字符型指针的赋值 couts2.data( )endl ; ,程序运行结果为: 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 群体数据,群体的概念,群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群
12、体。 线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。,非线性群体不用位置顺序来标识元素。,9.2.1 线性群体的概念,线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。 9.2.2 直接访问群体数组 静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修改。 动态数组由一系列位置连续的，任意数量相同类型的元素组成。优点：其元素个数可在程序运行时改变。动态数组类模板举例参见P293301,#ifndef ARRAY_CLASS #define ARRAY
13、_CLASS using namespace std; #include #include #ifndef NULL const int NULL = 0; #endif / NULL enum ErrorType invalidArraySize, memoryAllocationError, indexOutOfRange ; char *errorMsg = “Invalid array size“, “Memory allocation error“, “Invalid index: “ ;,动态数组类模板程序,17,template class Array private: T* a
14、list; int size; void Error(ErrorType error) const; public: Array(int sz = 50); Array(const Array #endif,18,19,数组类模板的构造函数,/ 构造函数 template Array:Array(int sz) if (sz = 0) /sz为数组大小（元素个数），若小于0，则输出错误信息 Error(invalidArraySize); size = sz; / 将元素个数赋值给变量size alist = new Tsize; /动态分配size个T类型的元素空间 if (alist =
15、NULL) /如果分配内存不成功，输出错误信息 Error(memoryAllocationError); ,直接访问的线性群体,20,数组类的拷贝构造函数,template Array:Array(const Array ,直接访问的线性群体,21,浅拷贝,void main(void) Array A(10); Array B(A); ,template Array:Array( const Array ,22,深拷贝,23,数组类的重载“=“运算符函数,template Array ,直接访问的线性群体,错误报告函数,template void Array: Error(ErrorTyp
16、e error) const cout errorMsgerror endl; throw error; ,25,数组类的重载下标操作符函数,template T ,直接访问的线性群体,26,为什么有的函数返回引用,如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成为左值。 如果返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变对象的值。,直接访问的线性群体,27,重载指针转换操作符,template Array:operator T* (void) const / 返回当前对象中私有数组的首地址 return alist; ,直接访问的线性群体,28,指针转换运算符的
17、作用,#include using namespace std; void main() int a10; void read(int *p, int n); read(a, 10); void read(int *p, int n) for (int i=0; ipi; ,void main() Array a(10); void read(int *p, n); read(a, 10); void read(int *p, int n) for (int i=0; ipi; ,直接访问的线性群体,右边read(a, 10);中a是Array类型对象，编译器会为其寻找一个可以将其转换为int
18、指针的函数或规则，试图执行(int *)a,，以匹配void read(int *p, int n)函数，若找不到，则编译出错，由于类中重载了指针转换符，因此 (int *)a 将得到a中数组指针，匹配成功。,29,Array类的应用,例9-4求范围2N中的质数，N在程序运行时由键盘输入。,直接访问的线性群体,void main(void) Array A(10); int n; int primecount = 0, i, j; cout = 2 as upper limit for prime numbers: “; cin n; Aprimecount+ = 2; / 2是一个质数 fo
19、r(i = 3; i i/2) Aprimecount+ = i; for (i = 0; i primecount; i+) cout setw(5) Ai; if (i+1) % 10 = 0) cout endl; ,30,9.2.3 顺序访问群体链表,链表是一种动态数据结构，可以用来表示顺序访 问的线性群体。 链表是由系列结点组成的，结点可以在运行时动 态生成。 每一个结点包括数据域和指向链表中下一个结点 的指针（即下一个结点的地址）。如果链表每个结点 中只有一个指向后继结点的指针，则该链表称为单链 表。 链表模板和应用举例参见P302307,9.2.4 特殊的线性群体栈,栈是只能从一
20、端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。,1. 栈的应用举例函数调用,2. 栈的基本状态,栈空： 栈中没有元素 栈满： 栈中元素个数达到上限 一般状态：栈中有元素，但未达到栈满状态,35,3. 栈的基本操作,初始化 入栈 出栈 清空栈 访问栈顶元素 检测栈的状态（满、空） 栈类模板和应用举例参见P307313,9.2.5 特殊的线性群体队列,队列是只能向一端添加元素，从另一端删除元素的线性群体,1. 队列的基本状态,队空： 队列中没有元素 队满： 队列中元素个数达到上限 一般状态：队列中有元素，但未达到队满状态,2. 循环队列,在想象中将数组弯曲成环形，元素出队时，后继元素不移
21、动，每当队尾达到数组最后一个元素时，便再回到数组开头。 队列类模板参见P313316,9.3 群体数据的组织,插入排序 选择排序 交换排序,顺序查找 折半查找,排序（sorting）,排序是计算机程序设计中的一种重要操作，它的 功能是将一个数据元素的任意序列，重新排列成一个按 关键字有序的序列。 数据元素： 数据的基本单位。在计算机中通常作为一个整体 进行考虑。一个数据元素可由若干数据项组成。 关键字： 数据元素中某个数据项的值，用它可以标识（识 别）一个数据元素。 在排序过程中需要完成两种基本操作： 比较两个数的大小 调整元素在序列中的位置,内部排序与外部排序,内部排序： 待排序的数据元素存
22、放在计算机内存中进行的排 序过程。内部排序方法: 插入排序 选择排序 交换排序 外部排序： 待排序的数据元素数量很大，以致内存存中一次 不能容纳全部数据，在排序过程中尚需对外存进行访 问的排序过程。,9.3.1 插入排序,每一步将一个待排序元素按其关键字值的大小插入到已排 序序列的适当位置上，直到待排序元素插入完为止。,直接插入排序,/9_11.h : 直接插入排序函数模板 template void InsertionSort(T A , int n) int i, j ; T temp; for (i = 1; i 0 / 插入位置找到，立即插入 ,9.3.2 选择排序,每次从待排序序列中
23、选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。,直接选择排序,/9_12.h : 直接选择排序函数模板 template void Swap ( T / 将这一趟找到的最小元素与A I 交换 ,9.3.3 交换排序,两两比较待排序序列中的元素，并交换不满足顺序要求的各 对元素，直到全部满足顺序要求为止。 最简单的交换排序方法起泡排序。 对具有n个元素的序列按升序进行起泡排序的步骤： 首先将第一个元素与第二个元素进行比较，若为逆序，则将 两元素交换。然后比较第二、第三个元素，依次类推，直到第n- 1和第n个元素进行了比较和交换。此过程称为第一趟起
24、泡排序。 经过第一趟，最大的元素便被交换到第n个位置。 对前n-1个元素进行第二趟起泡排序，将其中最大元素交换 到第n-1个位置。 如此继续，直到某一趟排序未发生任何交换时，排序完毕。 对n个元素的序列，起泡排序最多需要进行n-1趟。,起泡排序举例：对整数序列 8 5 2 4 3 按升序排序,/9_13.h : 起泡排序函数模板,template void Swap (T ,template void BubbleSort(T A , int n) int i, j ; int lastExchangeIndex ; i = n-1; while ( i 0 ) lastExchangeInd
25、ex = 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 顺序查找,基本思想是从序列的首元素开始，逐个元素与待查找的关 键字进行比较，直到找到相等的。若整个序列中没有与待查找 关键字相等的元素，就是查找不成功。 /9_14.h : 顺序查找函数模板 template int SeqSearch( T list , int n, T key ) for( int i=0; i n; i+ ) if (
26、 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 midvalue ; low=0 ; high=n-1 ; while (low = high) / low = high表示整个数组尚未查找完 mid = (low+high)/2; / 求中间元素的下标 midvalue = listmid; / 取出中间元素的值 if (key = midvalue) return mid; / 若找到,返回下标 else if (key midvalue) high = mid-1; / 将查找范围缩小到数组的前一半 else low = mid+1; / 将查找范围缩小到数组的后一半 return -1; / 没有找到，返回-1 ,