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

第2章面向对象程序设计和算法性能分析2.1抽象数据类型2.2面向对象程序设计和类2.3对象2.4算法、算法设计目标和算法性能分析2.1抽象数据类型2.1.1数据结构计算机是对各种各样的数据进行处理的机器。在计算机中如何组织数据，如何处理数据，从而如何更好地利用数据是计算机学科的基本研究内容。数据（Data）这个术语在计算机数据处理中含义非常广泛，可以认为它是描述客观事物的数字、字符、图形、图像、声音等所有能输入到计算机中并能为计算机接受的电子信号的集合。它们依靠多媒体(多种传输信息媒体)的支持，能为计算机所存储、处理和传输。在本书中所说的数据仅指常规媒体所支持的数字、字符等信号，不包括其他媒体所支持的声音、图形、图像等信号。数据元素（DataElement）是计算机中描述数据的基本单位。在大多数情况下，一个数据元素由若干个数据项组成，数据项是数据不可分割的最小单位。如对学生登记问题中，每个数据元素就可包括学号、姓名、班级等，学号、姓名、班级等就称作该数据元素的数据项。学生登记问题的数据结构是最简单的线性表结构。逻辑结构（LogicalStructure）是数据元素的逻辑表示方式。如图2―1就是一组数据元素的逻辑结构。图2―1学生登记数据元素存储结构（StoreStructure）是数据元素在计算机中的存储方式。数据元素可以有多种存储形式，如图2―1所示的学生登记中的数据元素既可用一个足够大的数组存储，也可用一个如图2―2所示的单链表存储。图2―2单链表存储710001王兵计97-1710002李方计97-1710003王力计97-2操作集合不同的问题要求实现的操作集合将不同，一个数据元素集合上允许（或要求）的所有操作构成了该数据元素的操作集合。如上述学生登记问题就可能要求实现插入、删除、打印等操作。数据结构（DataStructure）表示数据元素间的逻辑结构和存储结构以及这个数据元素集合上的操作集合的总称。如上述学生登记问题中数据元素集合和数据元素集合上的操作集合就构成一种称为线性表的数据结构。数据结构课程研究程序设计中常用的各种数据结构的数据元素间的逻辑关系和这些数据元素集合上的操作集合，它们的不同的存储结构（或称存储方法），以及不同存储结构下各种操作的实现方法。依据数据元素之间的关系，数据结构可分为线性结构和非线性结构两大类。线性结构中各个数据元素依次排列在一个线性序列中。线性结构有线性表、堆栈、队列、字符串、数组等；非线性结构中各个数据元素可能与多个其他数据元素发生联系，非线性结构有二叉树、树、堆、集合、图等。2.1.2数据类型类型是一组值的集合。数据类型（DataType）是指一个类型和定义在该类型上的操作集合。2.1.3抽象数据类型抽象数据类型（AbstractDataType，ADT）是用户在数据类型基础上自己定义和实现的数据类型。类似于在计算机机器语言的位、字节和字的基础上引入整数、浮点数、双精度数、字符等数据类型的思想方法，高级程序设计语言使用者可以在高级程序设计语言整数、浮点数、双精度数、字符等数据类型的基础上引入各种新的数据类型提供给自己或他人使用，从而使自己或他人的程序编制达到更高一级的数据抽象。这种由用户自己定义和实现的新的数据类型称为抽象数据类型。因此我们说，抽象数据类型是用户在数据类型基础上自己定义和实现的数据类型。一种抽象数据类型定义了一种新的数据元素集合和数据元素集合上所允许的操作集合。抽象数据类型是用户通过更高一级抽象得到的新的数据类型。抽象数据类型在更高一级的抽象程度上实现了信息的隐藏和封装。ClassSeqList{private:Datatypedata［MaxListSize］;intsize;//public:SeqList(void);//~SeqList(void);//intListSize(void)const;//返回元素的个数sizeintListEmpty(void)const;//表空返回1；否则返回0intFind(Datatype&item)const;//返回元素itemDatatypeGetData(intpos)const;//返回位置posvoidInsert(constDatatype&item,intpos);//在位置pos插入元素itemDatatypeDelete(constintpos);//删除位置pos的元素并返回voidClearList(void);//};2.1.5模块化软件设计的特点抽象数据类型是软件设计中的模块化方法，而模块化的软件设计方法有以下特点：1代码可重用所设计的抽象数据类型能像整数、浮点数、双精度数、字符等高级程序设计语言中的数据类型一样重复使用。2信息隐藏抽象数据类型封装了数据元素的具体存储方法和各种操作的具体实现方法，抽象数据类型的使用者只需根据调用界面调用它们，无需了解抽象数据类型数据元素存储方法和各种操作实现方法的具体细节，从而像程序设计语言中的数据类型一样实现了信息隐藏。3可靠性提高基于模块的软件开发可以大大降低软件的复杂度，所以可以提高软件的可靠性。4便于软件调试和维护由于抽象数据类型具有信息隐藏的优点，软件设计只需考虑高一级的程序结构，无需考虑封装在抽象数据类型中的实现细节，所以基于抽象数据类型的软件设计便于调试和维护。2.2面向对象程序设计和类面向对象程序设计（OrientedObjectProgramming）是以类设计为核心的一种新的程序设计方法，它是基于抽象数据类型程序设计方法的进一步发展。类（Class）是面向对象程序设计中相同对象的抽象描述。类包括数据成员和方法两部分。数据成员是类封装起来、只允许类方法操作的数据元素。方法是类所提供的操作，把类提供的操作称作方法，是因为类中数据成员的存取只能由类提供的“方法”进行。类的构成：1直接定义按照类的定义构成。2派生派生类是指该类是由一个或一个以上（通常是一个）的已有类派生构造而成。classparent{protected:charversion;public:parent(){version='A';}};classderive1:publicparent{private:intinfo;public:derive1(intnumber){info=number;}voidprint(){coutversioninfo;}};派生类的类构造方法使类具有了继承机制。派生类对象既独自具有该类特有的数据成员和方法，又同时具有基类中共同的数据成员和方法。3合成合成类是指该类是由一个或一个以上的已有类合成构造而成。例如，下例中的线是由两个点构成的，因此线类可由点类合成。classPoint{private:floatx,y;//点的坐标public:Point(floath,floatv);//构造函数floatGetX(void)const;//取x坐标FloatGetY(void)const;//取y坐标voidDraw(void)const;//在{x,y}}ClassLine{private:Pointp1,p2;//线的两个点位置public:Line(Pointa,Pointb);//构造函数voidDraw(void)const;//划线连接点p1和p2}；2.3对象对象（Object）是类的实例化。＃includegraph.hVoidmain(void){Inti=0,j=i;Pointpoint1(0,0),point2(3,4);Lineline1(point1,point2);......}2.4算法、算法设计目标和算法性能分析2.4.1算法算法（Algorithms）是对特定问题求解步骤描述的计算机指令的有限序列。算法满足以下性质：（1）输入性：具有零个或若干个输入量。（2）输出性：至少产生一个输出或执行一个有意义操作。（3）有限性：计算机的指令执行序列是有限的。（4）确定性：每一条指令的含义明确，无二义性。（5）可执行性：每一条指令都应在有限的时间内完成。2.4.2算法设计目标算法设计应满足以下五个目标：（1）正确性：（2）可读性：（3）健壮性：（4）高时间效率：（5）低内存要求算法的高时间效率和低内存要求通常是矛盾的。例如，有些问题若采用较多的内存空间可使时间效率提高，若采用较少的内存空间则使时间效率降低。在目前计算机硬件价格快速下降的趋势下，算法的时间效率应首先予以考虑。2.4.3算法的时间效率算法的时间效率是通过依据该算法编制的程序在计算机上运行所消耗的时间来度量的。程序在计算机上运行所消耗的时间与下列因素有关：（1）书写算法的程序设计语言；（2）编译产生的机器语言代码质量；（3）机器执行指令的速度；（4）问题的规模，即算法的时间效率与算法处理的数据个数n的关系。仅考虑算法本身的因素，则算法的时间效率只与问题的规模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)，称为线性阶；例2―1设数组a和b在前边部分已赋值，求如下两个n阶矩阵相乘运算程序段的时间复杂度。for(i=0;in;i++)for(j=0;jn;j++){c［i］［j］=0;for(k=0;kn;k++)c［i］［j］=c［i］［j］+a［i］［k］*b［k］}解设基本语句的执行次数为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―3下边的算法是用冒泡排序法对数组a中的n个整数类型的数据元素（a［0］--a［n-1］）从小到大排序的算法，求该算法的时间复杂度。voidBubbleSort(inta[],intn){inti,j,flag=1;inttemp;for(i=1;in&&flag==1;i++){flag=0;for(j=0;jn-i;j++){if(a［j］a［j+1］){flag=1;temp=a［j］;a［j］=a［j+1］;a［j+1］=temp;}}}}解这个算法的时间复杂度随待排序数据的不同而不同。当某次排序过程中没有任何两个数组元素交换位置，则表明数组元素已排序完毕，此时算法将因标记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(i0||i*n)return0;/*