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

1、第九章 群体类 和群体数据的组织,成都信息工程学院计算机系,C+语言程序设计,2,本章主要内容,模板 群体类 群体数据的组织,3,第一部分：模板,函数模板 类模板,4,函数模板,函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。 声明方法： template 函数声明,函 数 模 板,5,求绝对值函数的模板,#include using namespace std; template T abs(T x) return x0?-x:x; int main() int n=-5;double d=-5.5;coutabs(n)endl;coutabs(d

2、)endl; ,函 数 模 板,运行结果： 5 5.5,6,求绝对值函数的模板分析,编译器从调用abs()时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。 当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数： int abs(int x) return x0?-x:x; ,函 数 模 板,7,类模板的作用,使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。,类 模 板,8,类模板的声明,类模板： t

3、emplate class 类名 类成员声明 如果需要在类模板以外定义其成员函数，则要采用以下的形式： template 类型名 类名:函数名（参数表）,类 模 板,9,例9-2 类模板应用举例,#include #include using namespace std; / 结构体Student struct Student int id; /学号float gpa; /平均分 ;,类 模 板,template /类模板：实现对任意类型数据进行存取 class Store private:T item; /用于存放任意类型的数据int haveValue;/用于标记item是否已被存入内容p

4、ublic:Store(void); /默认形式（无形参）的构造函数GetElem(void); /提取数据函数void PutElem(T x);/存入数据函数 ; / 默认形式构造函数的实现 template Store:Store(void): haveValue(0) ,10,template / 提取数据函数的实现 T Store:GetElem(void) / 如果试图提取未初始化的数据，则终止程序if (haveValue = 0) cout / 存入数据函数的实现 void Store:PutElem(T x) / 将haveValue 置为 TRUE，表示item中已存入数值

5、 haveValue+; item = x; / 将x值存入item ,11,int main() Student g= 1000, 23; Store S1, S2; Store S3;Store D; S1.PutElem(3); S2.PutElem(-7); cout S1.GetElem() “ “ S2.GetElem()endl; S3.PutElem(g); cout “The student id is “ S3.GetElem().idendl;cout “Retrieving object D “ ;cout D.GetElem() endl; /输出对象D的数据成员/

6、由于D未经初始化,在执行函数D.GetElement()时出错 ,12,13,第二部分：群体数据,线性群体 线性群体的概念 直接访问群体-数组类 顺序访问群体-链表类 栈类 队列类,14,群体的概念,群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。 线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。 非线性群体不用位置顺序来标识元素。,15,线性群体的概念,线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。 在本章我们只介绍直接访问和顺序访问。,16,数组,静态数组是具有固定元素

7、个数的群体，其中的元素可以通过下标直接访问。 缺点：大小在编译时就已经确定，在运行时无法修改。 动态数组由一系列位置连续的，任意数量相同类型的元素组成。 优点：其元素个数可在程序运行时改变。 动态数组类模板：例9-3（9_3.h）,直接访问的线性群体,#ifndef ARRAY_CLASS #define ARRAY_CLASS using namespace std; #include #include #ifndef NULL const int NULL = 0; #endif / NULL enum ErrorType invalidArraySize, memoryAllocatio

8、nError, indexOutOfRange ; char *errorMsg = “Invalid array size“, “Memory allocation error“,“Invalid index: “ ;,动态数组类模板程序,17,template class Array private:T* alist; int size; void Error(ErrorType error,int badIndex=0) const;public:Array(int sz = 50); Array(const Array,18,19,数组类模板的构造函数,/ 构造函数 template

9、Array:Array(int sz) if (sz=0)/sz为数组大小（元素个数），若小于0则输出错误信息Error(invalidArraySize);size=sz;/ 将元素个数赋值给变量sizealist=new Tsize;/动态分配size个T类型的元素空间if (alist=NULL) /如果分配内存不成功，输出错误信息Error(memoryAllocationError); ,直接访问的线性群体,20,数组类的拷贝构造函数,template Array:Array(const Array ,直接访问的线性群体,21,浅拷贝,int main() Array A(10);A

10、rray B(A);,template Array:Array(const Array ,22,深拷贝,23,数组类的重载“=“运算符函数,template Array ,直接访问的线性群体,24,数组类的重载下标操作符函数,template T ,直接访问的线性群体,25,为什么有的函数返回引用,如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成为左值。 如果返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变对象的值。,直接访问的线性群体,26,重载指针转换操作符,template Array:operator T* (void) const /返回当前对象中私有数组

11、的首地址return alist; ,直接访问的线性群体,27,指针转换运算符的作用,#include using namespace std; int main() int a10;void read(int *p, int n);read(a, 10); void read(int *p, int n) for (int i=0; ipi; ,int main() Array a(10);void read(int *p, n);read(a, 10); void read(int *p, int n) for (int i=0; ipi; ,直接访问的线性群体,28,Array类的应用,

12、例9-4求范围2N中的质数，N在程序运行时由键盘输入。,直接访问的线性群体,#include #include #include “9_3.h“ using namespace std; int main() Array A(10);int n; int primecount = 0, i, j;cout = 2 as upper limit for prime numbers: “;cin n; Aprimecount+ = 2; / 2是一个质数for(i = 3; i i/2) Aprimecount+ = i;for (i = 0; i primecount; i+) cout set

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

14、,33,在结点之后插入一个结点,data1,p,data,template void Node:InsertAfter(Node *p) /p节点指针域指向当前节点的后继节点p-next = next; next = p; /当前节点的指针域指向p ,顺序访问的线性群体,34,删除结点之后的结点,顺序访问的线性群体,data1,Node *Node:DeleteAfter(void) Node *tempPtr = next; if (next = NULL) return NULL;next = tempPtr-next; return tempPtr; ,tempPtr,35,链表的基本操

15、作,生成结点 插入结点 查找结点 删除结点 遍历链表 清空链表,顺序访问的线性群体,36,链表类模板(例9-6),顺序访问的线性群体,/9_6.h #ifndef LINKEDLIST_CLASS #define LINKEDLIST_CLASS #include #include using namespace std; #ifndef NULL const int NULL = 0; #endif / NULL #include “9_5.h“ template class LinkedList private:Node *front, *rear;Node *prevPtr, *curr

16、Ptr;int size;int position;Node *GetNode(const T,public:LinkedList(void);LinkedList(const LinkedList #endif / LINKEDLIST_CLASS,37,链表类应用举例(例9-7),顺序访问的线性群体,#include #include “9_6.h“ #include “9_6.cpp“ using namespace std; int main() LinkedList Link;int i, key, item;for (i=0;i item;Link.InsertFront(item

17、);cout “List: “;Link.Reset();while(!Link.EndOfList() coutLink.Data()“ “;Link.Next(); ,cout key;Link.Reset();while (!Link.EndOfList() if(Link.Data() = key) Link.DeleteAt();Link.Next();cout “List: “;Link.Reset();while(!Link.EndOfList() cout Link.Data() “ “;Link.Next(); cout endl; ,38,特殊的线性群体栈,栈是只能从一端访

18、问的线性群体，可以访问的这一端称栈顶，另一端称栈底。,特殊的线性群体栈,39,栈的应用举例函数调用,特殊的线性群体栈,40,栈的应用举例表达式处理,特殊的线性群体栈,41,栈的基本状态,栈空 栈中没有元素 栈满 栈中元素个数达到上限 一般状态 栈中有元素，但未达到栈满状态,特殊的线性群体栈,42,43,栈的基本操作,初始化 入栈 出栈 清空栈 访问栈顶元素 检测栈的状态（满、空）,特殊的线性群体栈,44,栈类模板(例9-8),特殊的线性群体栈,/9-8.h #ifndef STACK_CLASS #define STACK_CLASS #include #include using names

19、pace std; const int MaxStackSize=50;template class Stack private:T stacklistMaxStackSize; int top;,public:Stack (void); void Push (const T /类的实现略,45,栈的应用,例9.9 一个简单的整数计算器 实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算“3+5“则输入“3 5 +“。乘方运算符用“表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入“c“。当

20、键入“q“时程序结束。 9-9.h 9-9.cpp,特殊的线性群体栈,/9_9.h #include #include #include #include using namespace std; enum Boolean False, True; #include “9_8.h“ class Calculator private:Stack S; void Enter(int num); Boolean GetTwoOperands(int,46,void Calculator:Enter(int num) S.Push(num); Boolean Calculator:GetTwoOper

21、ands(int ,47,void Calculator:Compute(char op) Boolean result;int operand1, operand2;result = GetTwoOperands(operand1, operand2);if (result) switch(op) case +: S.Push(operand2+operand1); break;case -: S.Push(operand2-operand1); break;case *: S.Push(operand2*operand1); break; case /: if (operand1 = 0)

22、 cerr“Divide by 0!“endl; S.ClearStack();else S.Push(operand2/operand1);break;case : S.Push(pow(operand2,operand1); break;cout=S.Peek() ; elseS.ClearStack(); ,48,void Calculator:Run(void) char c20; while(cinc, *c != q)switch(*c) case c: S.ClearStack(); break;case -: if (strlen(c)1) Enter(atoi(c); els

23、e Compute(*c); break;case +:case *:case /:case : Compute(*c); break;default: Enter(atoi(c); break; void Calculator:Clear(void) S.ClearStack(); ,49,/9_9.cpp #include “9-9.h“int main() Calculator CALC;CALC.Run(); ,50,51,特殊的线性群体队列,队列是只能向一端添加元素，从另一端删除元素的线性群体,52,队列的基本状态,队空 队列中没有元素 队满 队列中元素个数达到上限 一般状态 队列中

24、有元素，但未达到队满状态,特殊的线性群体队列,元素移动方向,元素移动方向,53,54,循环队列,在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。,特殊的线性群体队列,55,56,例9-10 队列类模板,特殊的线性群体队列,#ifndef QUEUE_CLASS #define QUEUE_CLASS #include #include using namespace std; const int MaxQSize=50; template class Queue private:int front,rear,count; T qlistM

25、axQSize;,public:Queue (void); void QInsert(const T /成员函数的实现略,57,第三部分：群体数据的组织,插入排序 选择排序 交换排序 顺序查找 折半查找,58,排序（sorting）,排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。 数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。 关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。 在排序过程中需要完成两种基本操作： 比较两个数的大小 调整元素在序列中的位置,群体数据的组

26、织,59,内部排序与外部排序,内部排序：待排序的数据元素存放在计算机内存中进行的排序过程。 外部排序：待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。,群体数据的组织,60,内部排序方法,插入排序 选择排序 交换排序,群体数据的组织,61,插入排序的基本思想,每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。,初始状态： 5 4 10 20 12 3,62,直接插入排序,在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序算法，这里我们只介绍最简单的直接插入排序算法。 例9-11

27、 直接插入排序函数模板（9_11.h）,群体数据的组织,template void InsertionSort(T A, int n) int i, j;T temp;for (i = 1; i 0 ,直接插入排序函数模板（9_11.h）,63,64,选择排序的基本思想,每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。,3 4 10 20 12 5,3 4 10 20 12 5,第 i 次选择后，将选出的那个记录与第 i 个记录做交换。,65,直接选择排序,在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排

28、序方法，其中最简单的是通过顺序比较找出待排序序列中的最小元素，称为直接选择排序。 例9-12 直接选择排序函数模板（9-12.h）,群体数据的组织,template void Swap (T ,直接选择排序函数模板（9-12.h）,66,67,交换排序的基本思想,两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。,群体数据的组织,68,最简单的交换排序方法 起泡排序,对具有n个元素的序列按升序进行起泡排序的步骤： 首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，依次类推，直到第n-1和第n个元素进行了比较和交换。此过

29、程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第n个位置。 对前n-1个元素进行第二趟起泡排序，将其中最大元素交换到第n-1个位置。 如此继续，直到某一趟排序未发生任何交换时，排序完毕。对n个元素的序列，起泡排序最多需要进行n-1趟。,群体数据的组织,69,起泡排序举例,对整数序列 8 5 2 4 3 按升序排序,8 5 2 4 3,5,2,4,3,8,2,4,3,5,8,2,3,4,5,8,2,3,4,5,8,初始状态,第一趟结果,第二趟结果,第三趟结果,第四趟结果,小的逐渐上升,每趟沉下一个最大的,群体数据的组织,70,例9-13 起泡排序函数模板,template void Sw

30、ap (T ,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 (Aj+1 Aj) Swap(Aj,Aj+1);lastExchangeIndex=j; i=lastExchangeIndex; ,群体数据的组织,71,顺序查找,其基本思想 从序列的首元素开始，逐个元素与待查找的关键字进行比较，直到找到相等的。若整个序列中没有与待查找关键字相等的元素，就是查找不成功。 顺序查

31、找函数模板 例9-14,群体数据的组织,template int SeqSearch(T list,int n,T key) for(int i=0;i n;i+)if (listi = key)return i; return -1; ,顺序查找函数模板,72,73,折半查找的基本思想,对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。,群体数据的组织,74,折半查找举例,用折半查找法，在下列序列中查找值为21的元素：,M=INT(L+H)/2)=3,L=M+1=4,M=

32、INT(L+H)/2)=4,75,例9-15 折半查找函数模板,template int BinSearch(T list, int n, T key) int mid, low, high;T midvalue;low=0;high=n-1;while (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; ,群体数据的组织,76,小结与复习建议,主要内容 模板、群体类和群体数据的组织 达到的目标 理解模板的作用，学会简单的应用。 以群体类以及查找、排序算法为综合例题，对前面章节的内容进行全面复习； 掌握一些常用的数据结构和算法，能够解决一些略复杂的问题，也为下一章学习C+标准模板库打下基础。 实验任务 实验九,