第2章面向对象程序设计和算法性能分析课件

第2章面向对象程序设计和算法性能分析2.1抽象数据类型

2.2面向对象程序设计和类2.3对象2.4算法、算法设计目标和算法性能分析第2章面向对象程序设计和算法性能分析2.1抽象数据2.1抽象数据类型

2.1.1数据结构计算机是对各种各样的数据进行处理的机器。在计算机中如何组织数据，如何处理数据，从而如何更好地利用数据是计算机学科的基本研究内容。

数据（Data）这个术语在计算机数据处理中含义非常广泛，可以认为它是描述客观事物的数字、字符、图形、图像、声音等所有能输入到计算机中并能为计算机接受的电子信号的集合。2.1抽象数据类型

2.1.1数据结构它们依靠多媒体(多种传输信息媒体)的支持，能为计算机所存储、处理和传输。在本书中所说的数据仅指常规媒体所支持的数字、字符等信号，不包括其他媒体所支持的声音、图形、图像等信号。

数据元素（DataElement）是计算机中描述数据的基本单位。在大多数情况下，一个数据元素由若干个数据项组成，数据项是数据不可分割的最小单位。如对学生登记问题中，每个数据元素就可包括学号、姓名、班级等，学号、姓名、班级等就称作该数据元素的数据项。学生登记问题的数据结构是最简单的线性表结构。它们依靠多媒体(多种传输信息媒体)的

逻辑结构（LogicalStructure）是数据元素的逻辑表示方式。如图2―1就是一组数据元素的逻辑结构。图2―1学生登记数据元素逻辑结构（LogicalStruc

存储结构（StoreStructure）是数据元素在计算机中的存储方式。数据元素可以有多种存储形式，如图2―1所示的学生登记中的数据元素既可用一个足够大的数组存储，也可用一个如图2―2所示的单链表存储。图2―2单链表存储存储结构（StoreStruct操作集合不同的问题要求实现的操作集合将不同，一个数据元素集合上允许（或要求）的所有操作构成了该数据元素的操作集合。如上述学生登记问题就可能要求实现插入、删除、打印等操作。

数据结构（DataStructure）表示数据元素间的逻辑结构和存储结构以及这个数据元素集合上的操作集合的总称。如上述学生登记问题中数据元素集合和数据元素集合上的操作集合就构成一种称为线性表的数据结构。操作集合不同的问题要求实现的操作集合数据结构课程研究程序设计中常用的各种数据结构的数据元素间的逻辑关系和这些数据元素集合上的操作集合，它们的不同的存储结构（或称存储方法），以及不同存储结构下各种操作的实现方法。依据数据元素之间的关系，数据结构可分为线性结构和非线性结构两大类。线性结构中各个数据元素依次排列在一个线性序列中。线性结构有线性表、堆栈、队列、字符串、数组等；非线性结构中各个数据元素可能与多个其他数据元素发生联系，非线性结构有二叉树、树、堆、集合、图等。数据结构课程研究程序设计中常用的各种2.1.2数据类型

类型是一组值的集合。

数据类型（DataType）是指一个类型和定义在该类型上的操作集合。

2.1.2数据类型2.1.3抽象数据类型

抽象数据类型（AbstractDataType，ADT）是用户在数据类型基础上自己定义和实现的数据类型。类似于在计算机机器语言的位、字节和字的基础上引入整数、浮点数、双精度数、字符等数据类型的思想方法，高级程序设计语言使用者可以在高级程序设计语言整数、浮点数、双精度数、字符等数据类型的基础上引入各种新的数据类型提供给自己或他人使用，从而使自己或他人的程序编制达到更高一级的数据抽象。这种由用户自己定义和实现的新的数据类型称为抽象数据类型。2.1.3抽象数据类型因此我们说，抽象数据类型是用户在数据类型基础上自己定义和实现的数据类型。一种抽象数据类型定义了一种新的数据元素集合和数据元素集合上所允许的操作集合。抽象数据类型是用户通过更高一级抽象得到的新的数据类型。抽象数据类型在更高一级的抽象程度上实现了信息的隐藏和封装。因此我们说，抽象数据类型是用户在数据ClassSeqList{private:Datatypedata［MaxListSize］;intsize;//数据元素个数public:SeqList(void);//构造函数~SeqList(void);//析构函数intListSize(void)const;//返回元素的个数sizeintListEmpty(void)const;//表空返回1；否则返回0intFind(Datatype&item)const;//返回元素item在表中的位置DatatypeGetData(intpos)const;//返回位置pos的元素voidInsert(constDatatype&item,intpos);//在位置pos插入元素itemDatatypeDelete(constintpos);//删除位置pos的元素并返回voidClearList(void);//把表清空};ClassSeqList2.1.5模块化软件设计的特点抽象数据类型是软件设计中的模块化方法，而模块化的软件设计方法有以下特点：1代码可重用所设计的抽象数据类型能像整数、浮点数、双精度数、字符等高级程序设计语言中的数据类型一样重复使用。2.1.5模块化软件设计的特点2信息隐藏抽象数据类型封装了数据元素的具体存储方法和各种操作的具体实现方法，抽象数据类型的使用者只需根据调用界面调用它们，无需了解抽象数据类型数据元素存储方法和各种操作实现方法的具体细节，从而像程序设计语言中的数据类型一样实现了信息隐藏。2信息隐藏3可靠性提高基于模块的软件开发可以大大降低软件的复杂度，所以可以提高软件的可靠性。4便于软件调试和维护由于抽象数据类型具有信息隐藏的优点，软件设计只需考虑高一级的程序结构，无需考虑封装在抽象数据类型中的实现细节，所以基于抽象数据类型的软件设计便于调试和维护。3可靠性提高2.2面向对象程序设计和类

面向对象程序设计（OrientedObjectProgramming）是以类设计为核心的一种新的程序设计方法，它是基于抽象数据类型程序设计方法的进一步发展。2.2面向对象程序设计和类面类（Class）是面向对象程序设计中相同对象的抽象描述。类包括数据成员和方法两部分。数据成员是类封装起来、只允许类方法操作的数据元素。方法是类所提供的操作，把类提供的操作称作方法，是因为类中数据成员的存取只能由类提供的“方法”进行。类（Class）是面向对象程序设计中类的构成：1直接定义按照类的定义构成。2派生派生类是指该类是由一个或一个以上（通常是一个）的已有类派生构造而成。类的构成：classparent{protected: charversion;public: parent(){version='A';}};classderive1:publicparent{private: intinfo;public: derive1(intnumber){ info=number; } voidprint(){ cout<<version<<info; }};派生类的类构造方法使类具有了继承机制。派生类对象既独自具有该类特有的数据成员和方法，又同时具有基类中共同的数据成员和方法。classparent{派生类的类构造方法使类具有了继承机3合成合成类是指该类是由一个或一个以上的已有类合成构造而成。例如，下例中的线是由两个点构成的，因此线类可由点类合成。classPoint{private:floatx,y;//点的坐标public:Point(floath,floatv);//构造函数floatGetX(void)const;//取x坐标3合成FloatGetY(void)const;//取y坐标voidDraw(void)const;//在{x,y}处划点}；ClassLine{private:Pointp1,p2;//线的两个点位置public:Line(Pointa,Pointb);//构造函数voidDraw(void)const;//划线连接点p1和p2}；FloatGetY(void)const;2.3对象对象（Object）是类的实例化。2.3对象对象（O＃include"graph.h"Voidmain(void){Inti=0,j=i;Pointpoint1(0,0),point2(3,4);Lineline1(point1,point2);......}＃include"graph.h"2.4算法、算法设计目标和算法性能分析2.4.1算法

算法（Algorithms）是对特定问题求解步骤描述的计算机指令的有限序列。算法满足以下性质：2.4算法、算法设计目标和算法性能分析2.4.1算（1）输入性：具有零个或若干个输入量。（2）输出性：至少产生一个输出或执行一个有意义操作。（3）有限性：计算机的指令执行序列是有限的。（4）确定性：每一条指令的含义明确，无二义性。（5）可执行性：每一条指令都应在有限的时间内完成。（1）输入性：具有零个或若干个输入量。2.4.2算法设计目标算法设计应满足以下五个目标：（1）正确性：

（2）可读性：（3）健壮性：（4）高时间效率：（5）低内存要求2.4.2算法设计目标（3）健壮性：算法的高时间效率和低内存要求通常是矛盾的。例如，有些问题若采用较多的内存空间可使时间效率提高，若采用较少的内存空间则使时间效率降低。在目前计算机硬件价格快速下降的趋势下，算法的时间效率应首先予以考虑。算法的高时间效率和低内存要求通常是矛2.4.3算法的时间效率算法的时间效率是通过依据该算法编制的程序在计算机上运行所消耗的时间来度量的。程序在计算机上运行所消耗的时间与下列因素有关：（1）书写算法的程序设计语言；（2）编译产生的机器语言代码质量；（3）机器执行指令的速度；（4）问题的规模，即算法的时间效率与算法处理的数据个数n的关系。2.4.3算法的时间效率仅考虑算法本身的因素，则算法的时间效率只与问题的规模n有关。因此算法的时间效率是问题规模的函数，算法的时间效率也称作算法的时间复杂度T(n)。算法的时间效率分析通常采用O(f(n))表示法。仅考虑算法本身的因素，则算法的时间定义：T(n)=O(f(n))当且仅当存在正常数c和n0，对所有的n(n≥n0)满足T(n)≤cf(n)。换句话说，O(f(n))给出了函数f(n)的上界。事实上分析一个算法中基本语句的执行次数就可求出该算法的时间复杂度。

（1）x=x+1；时间复杂度为O(1)，称为常量阶；（3）for(i=1;i<=n;i++) for(j=1;j<=n;j++)x=x+1;时间复杂度为O(n2),称为平方阶。（2）for(i=1;i<=n;i++)x=x+1;时间复杂度为O(n)，称为线性阶；定义：T(n)=O(f(n))当且仅例2―1设数组a和b在前边部分已赋值，求如下两个n阶矩阵相乘运算程序段的时间复杂度。for(i=0;i<n;i++)for(j=0;j<n;j++){c［i］［j］=0;for(k=0;k<n;k++)c［i］［j］=c［i］［j］+a［i］［k］*b［k］

}例2―1设数组a和b在前边部分解设基本语句的执行次数为f(n)，有f(n)=n2+n3因程序段的时间复杂度T(n)=f(n)=n2+n3≤c*n3=O(n3)，其中c为常数，所以该程序段的时间复杂度为O(n3)。解例2―2设n为如下程序段处理的数据个数，求如下程序段的时间复杂度。for(i=1;i<=n;i=2*i)printf(“i=%d／n”,i);／*基本语句*／解设基本语句的执行次数为f(n)，有2f(n)-1≤n,即有f(n)≤lbn+1因程序段的时间复杂度T(n)=f(n)≤lbn+1≤c*lbn=O(lbn)，其中c为常数，所以该程序段的时间复杂度为O(lbn)。例2―2设n为如下程序段处理的数据例2―3下边的算法是用冒泡排序法对数组a中的n个整数类型的数据元素（a［0］--a［n-1］）从小到大排序的算法，求该算法的时间复杂度。voidBubbleSort(inta[],intn){inti,j,flag=1;inttemp;for(i=1;i<n&&flag==1;i++){flag=0;for(j=0;j<n-i;j++){例2―3下边的算法是用冒泡排序法对if(a［j］>a［j+1］){flag=1;temp=a［j］;a［j］=a［j+1］;a［j+1］=temp;}}}}if(a［j］>a［j+1］)解这个算法的时间复杂度随待排序数据的不同而不同。当某次排序过程中没有任何两个数组元素交换位置，则表明数组元素已排序完毕，此时算法将因标记flag=0不满足循环条件而结束。但是，在最坏情况下，每次排序过程中都至少有两个数组元素交换位置，因此，应按最坏情况计算该算法的时间复杂度。设基本语句的执行次数为f(n)，最坏情况下有f(n)=n+4*n2/2因算法的时间复杂度T(n)=f(n)=n+4*n2≤c*n2=O(n2)，其中c为常数，所以该算法的时间复杂度为O(n2)。解这个算法的时间复杂度随待排序数例2―4下边算法是在一个有n个数据元素的数组a中删除第i个位置的数组元素，要求当删除成功时数组元素个数减1，求该算法的时间复杂度。其中，数组下标从0至n-1。IntDelete(inta［］,int*n,inti){intj;if(i<0||i>*n)return0;/*删除位置错误，失败返回*/

for(j=i+1;j<*n;j++)a［j-1］=a［j］;/*顺次移位填补*/例2―4下边算法是在一个有n个数(*n)--;/*数组元素个数减1*/return1;/*删除成功返回*/}解这个算法的时间复杂度随删除数据的位置不同而不同。当删除最后一个位置的数组元素时有i=n-1,j=i+1=n，此时因不需移位填补而循环次数为0；当删除倒数最后一个位置的数组元素时有i=n-2,j=i+1=n-1，此时因只需移位填补一次而循环次数为1;依此类推,当删除第一个位置的数组元素时有i=0,j=i+1=1，此时因需移位填补n-1次而循环次数为n-1。此时算法的时间复杂度应是删除数据的位置等概率取值情况下的平均时间复杂度。(*n)--;假设删除任何位置上的数据元素都是等概率的（一般情况下均可作等概率假设），设Pi为删除第i个位置上数据元素的概率，则有Pi=1/n，设E为删除数组元素的平均次数，则有假设删除任何位置上的数据元素都是等概因该算法的时间复杂度T(n)=E≤(n+1)／2≤c*n=O(n)，其中c为常数，所以该算法的时间复杂度为O(n)。算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有多项式时间复杂度的算法是可接受、可实际使用的算法；具有指数时间复杂度的算法是只有当n足够小时才可使用的算法。表2―1给出了多项式增长和指数增长的比较。从表2―1可以看出，当n=50时，多项式函数n3=125000，而指数函数2n=1.0×1015，n!=3.0×1064，nn=8.9×1084。因该算法的时间复杂度T(n)=E表2-1多项式增长和指数增长的比较表2-1多项式增长和指数增长的比较2.4.4算法的符号命名、书写格式和注释格式本书算法的符号命名和书写格式采用规范的软件工程方法。学生在算法设计和上机实习过程中应学习这种书写规则。算法中的各种符号命名方法规定为：（1）变量名和数据成员名字母均小写；若单词多于一个时，第二个单词首字母大写。有些教科书中变量名和数据成员名首字母均大写。但频繁地转换字母的大小写对于键盘输入十分不便，所以一个单词时首字母不大写。当变量名的单词多于一个时，如果第二个单词首字母不大写，则变量名的含义很难理解。例如，后面章节中的变量名list,myList，数据成员名data，next,leftChild,rightChild的书写是规范的。2.4.4算法的符号命名、书写格式和注