《数据结构A》第01章 (2)

,单击此处编辑母版标题样式,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,大连东软信息学院,张明会,2011,年,9,月,数据结构,Data Structures in C+,掌握现代信息技术知识,具有概念化和抽象化能力,能力,知识,算法与数据结构,什么是数据结构,数据抽象和抽象数据类型,描述数据结构和算法,算法分析的基本方法,1.1,算法与数据结构,1.2,什么是数据结构,1.3,数据抽象和抽象数据类型,1.4,描述数据结构和算法,1.5,算法分析的基本方法,第,1,章 基础知识,数据结构和算法是计算机学科的基础之一，更是软件技术的基础。,数据的组织和表示方法直接影响使用计算机求解问题的效率。,程序,=,数据结构,+,算法,1.1,算法与数据结构,1.2.1,基本概念,基本术语,数据（,data,）：计算机加工处理的对象。,数据元素：组成数据的基本单位,数值数据,(numerical data),非数值数据,(non-numerical data),1.2,什么是数据结构,什么是数据结构,一个数据结构是由数据元素依据某种逻辑联系组织起来的，对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；一个数据结构必须讨论在该类数据上执行的运算才有意义。,数据结构包括三个方面,逻辑结构,：数据元素间的逻辑关系；,存储结构,：数据在计算机内的表示形式；,运算：在数据上执行的操作,。,1.2.2,数据的逻辑结构,数据的,逻辑结构,对数据元素间逻辑关系的描述被称为数据的,逻辑结构,(,logical structure),，它可以用一个二元组表示：,DS=,（,D,，,R,），其中，,D,是数据元素的有限集合，,R,是,D,中元素序偶的集合。,四类基本逻辑结构,（,a,）集合,结构,（,b,）线性结构,（,c,）,树形结构,（,d,）图状结构,（,a,）集合结构,（,b,）线性结构,（,c,）树型结构,（,d,）图形结构,四类基本结构的示意图,例,：,用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。,（,1,）,S=(D,R),D=,a,b,c,d,e,f,R=(,a,e),(b,c),(c,a),(e,f),(f,d),解：,上述表达式可用图形表示为：,b c a e f d,此结构为,线性,的。,（,2,）,S=(D,R)D=,d,i,|1i5,R=(,d,i,d,j,),ij,d,1,d,5,d,2,d,4,d,3,该结构,是非线性,的。,解：,上述表达式可用图形表示为：,1.2.3,数据的存储表示,顺序存储,需要一块连续的存储空间，并把逻辑上相关的数据元素依次存储在该连续的存储区中,。,Loc,（,a,k,）,102,2*k,链接存储,几种存储结构,顺序结构,链接结构,索引结构,散列结构,Data Link,地址信息称为链。,表示空链。,1.2.4,数据结构的运算,数据结构最常见的运算,创建运算,:,创建一个数据结构；,清除运算,:,删除数据结构中的全部元素；,插入运算,:,在数据结构的指定位置上插入一个新元素；,删除运算,:,将数据结构中的某个元素删除；,静态数据结构和动态数据结构,如果一个数据结构一旦创建，其结构不发生改变，则称为静态数据结构，否则成为动态数据结构。,1.3.1,抽象、数据抽象和过程抽象,抽象：,其实质是抽取共同的和本质的内容，忽略非本质的细节。,数据抽象,：,使程序设计者可以将数据元素间的逻辑关系和数据在计算机内的具体表示分别考虑。,过程抽象：,使程序设计者将一个运算的定义与实现运算的具体方法分开考虑。抽象的好处主要在于降低了问题求解的难度。,1.3,数据抽象和抽象数据类型,1.3.2,封装与信息隐蔽,封装,:,是指把数据和操纵数据的运算组合在一起的机制。使用者只能通过一组允许的运算访问其中的数据。,信息隐蔽：,对使用者隐藏了数据结构或程序的实现细节。,通常将数据和操纵数据的运算组成,模块,。每个模块有一个明确定义的,界面,，模块内部信息只能经过这一界面被外部访问。,1.3.3,数据类型和抽象数据类型,数据类型,是程序设计语言中的概念，它是数据抽象的一种方式。一个,数据类型,定义了一个值的集合以及作用于该,值集,的运算集合。,程序设计语言中，一个数据类型不仅规定了该类型的变量（或常量）的取值范围，还定义了该类型允许的运算。,整型,int,的规范,变量,a,的取值范围是：,-3276832767,对变量,a,执行的操作有：,算术运算,+,、,-,、*、,/,、,%,关系运算,、,=,、,=,、,!=,赋值运算,=,整型,int,的实现,变量,a,在计算机内存储表示方法。,操作的具体实现方法。,抽象数据类型,（,abstract data type ADT,）是一个数据类型，其主要特征是该类型的对象及其运算的规范,与该类型对象的表示和运算的实现分离，实行封装和信息隐蔽，即所谓使用和实现分离。,1.3.4,数据结构与抽象数据类型,逻辑结构和运算的定义组成了,数据结构的,规范,（,specification,）,数据的存储表示和运算算法的描述构成,数据结构的,实现,(implementation),。,从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点。,一种数据结构被视为一个抽象数据类型。,数据结构的抽象层次,抽象层：讨论数据的,逻辑结构,及其,运算定义,，,实现层：讨论数据的,存储表示,以及,运算的算法实现。,1.4.1,数据结构的规范,数据结构被看成是一个类属抽象数据类型,(ADT),，用格式化的自然语言来描述。,数据结构可以,形式地,用一个,C+,的抽象模板类描述。,1.4,描述数据结构和算法,ADT 1.1,栈,ADT,ADT Stack,数据：,0,个或多个元素的线性序列（,a,0,a,1,.,a,n-1,）,其最大允许长度为,MaxStackSize,。,运算：,Create(),：建立一个空栈,Destroy(),：撤消一个栈,Push(x),：值为,x,的新元素进栈，成为栈顶元素,Pop(),：从栈中删除栈顶元素,Top(x),：在,x,中返回栈顶元素,template,class Stack,/,栈类,Stack,是一个模板抽象类，其成员函数为纯虚函数，未定义数据成员。,public:,virtual bool Push(T x)=0;,virtual bool Pop()=0;,virtual bool Top(T&x),const=0;,;,1.4.2,实现数据结构,template,class SeqStack:public Stack,public:,private:,int top;/top,记录最后入栈的元素在,s,的下标,int maxTop;/,最大栈顶指针,T*s;/s,指向动态生成的一维数组，存放元素,;,template,SeqStack:SeqStack(int mSize),maxTop=mSize-1;/,设置栈的容量值,s=new TmSize;/,生成存储栈的数组,top=-1;/top=,1,表示空栈,1.5.1,算法及其性能标准,什么是算法,笼统的说，算法是求解一类问题的任意一种特殊的方法。较严格的说法是一个算法是对特定问题的求解步骤的一种描述，它是指令的有限序列；此外，算法具有下列五个特征：,1.5,算法分析的基本方法,输入,：算法有零个或多个输入,输出,：算法至少产生一个输出,确定性,：算法的每一条指令都有确切的定义，没有二义性。,能行性,：算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。,有穷性,：算法必须总能在执行有限步之后终止。,1.5.2,算法的时间复杂度,算法的时间复杂度,是程序运行从开始到结束所需的时间。,程序步,一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关。,float Sum(float list,const int n),/,此程序的程序步数为,2n,3,float tempsum=0.0;,count+;/,针对赋值语句,for(int i=0;in;i+),count+,；,/,针对,for,循环语句,tempsum+=listi;,count+;/,针对赋值语句,count+;/,针对,for,的最后一次执行,count+;/,针对,return,语句,return tempsum;,1.5.3,渐近时间复杂度,定义,:,（大,O,记号）,设,f(n),和,g(n),是定义在正整数上的正函数，如果存在两个正常数,c,和,n,0,，使得当,n,n,0,时，有,f(n),c g(n),则记作,f(n)=O(g(n),。,定理,如果,f(n),a,m,n,m,+a,m-1,n,m-1,+,+a,1,n+a,0,是,m,次多项式，则,f(n),O(n,m,),例：,T(n),3.6n,3,+2.5 n,2,+2.8,O(n,3,),渐近时间复杂度,使用大,O,记号表示的算法的时间复杂度，称为算法的,渐近时间复杂度,。渐近时间复杂度也常简称为时间复杂度。通常用,O(1),表示常数计算时间，即算法只需执行有限个程序步。,关键操作,很多情况下，可以通过考察一个程序中的关键操作（关键操作被认为是一个程序步）的执行次数来计算算法的渐近时间复杂度。有时也需要同时考虑几个关键操作，以反映算法的执行时间。,例,void Mult(int ann,bnn,cnn,int n),/n,n,矩阵,a,与,b,相乘得到,c,。,for(int i=0;in;i+)/n+1,for(int j=0;jn;j+)/n(n+1),cij=0;/n,2,for(int k=0;kn;k+)/n,2,（,n+1),cij+=aik*bkj;/n,3,程序步为：,2n,3,+3n,2,+2n+1,cij+,aik*bkj,可看成关键操作,渐近时间复杂度为：,T(n)=O(n,3,),算法按时间复杂度分类,多项式时间算法,O(1)O(log,2,n)O(n)O(nlog,2,n),O(n,2,)O(n,3,),指数时间算法,O(2,n,)O(n!)O(n,n,),1.5.4,最好、最坏和平均时间复杂度,例子：,在一个有,n,个元素的数组中查找一个指定元素，某个搜索算法从第一个元素开始，一次检查一个数组元素。,上节课练习,（,1,）在数据结构中，从逻辑上可以把数据结构分成,A.,动态结构和静态结构,B.,紧凑结构和非紧凑结构,C.,线性结构和非线性结构,D.,内部结构和外部结构,(2),两种常用的数据结构的物理存储方式有顺序存储和,_,A.,线性表存储,B.,散列结构存储,C.,集合结构存储,D.,链式存储,(3),对于给定的,n,个元素,可以构造出的四种逻辑结构是,、,、,、,_ _,。,上节课练习,有下列二元组表示的数据结构，请指出属于何种逻辑结构。,S=D,，,R,；,D=a,，,b,，,c,，,d,，,e,，,f,，,g,，,h,；,R=,本章总结,数据结构基本概念,数据结构的分类,算法及时间复杂度计算,