基本概念和术语

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 绪论,1.1 什么是数据结构,1.2 基本概念和术语,1.4 算法和算法分析,1.3 抽象数据类型的表示与实现,1.2,基本概念和术语,一、数据、数据元素,三、数据类型,四、抽象数据类型,二、数据对象、数据结构,数据:,是对客观事物的符号表示，在计算机科学中是指所有能,输入,到计算机中且能被计算机程序,处理的符号(数值、字符等),的总称。,例如，一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处理程序的处理对象是字符串。因此，对计算机科学而言，数据的含义极为广泛，如图象、声音等都可以通过编码而归之于数据的范畴。,一、数据、数据元素,数值性数据,非数值性数据,数据元素:,是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。,例如，例12中的“树”中的一个棋盘格局，例13中的“图”中的一个圆圈都被称为一个数据元素。有时，,一个数据元素可由若干个数据项组成,，例如，例11中一本书的书目信息中的每一项（如书名、作者名等）为一个数据项，,数据项是数据的不可分割的最小单位。,如:整数“,5,”,字符“,N,”,等。,-是不可分割的“原子”,其中每个款项称为一个,“数据项”,它是数据结构中讨论的,最小,单位,数据元素也可以由若干款项构成。,例如：,描述一个学生的数据元素,称之为组合项,年 月 日,姓 名学 号班 号性别出生日期入学成绩,原子项,数据对象,是性质相同的数据元素的集合，是数据的一个子集。,例如，,整数数据对象是集合,N=0，+/-1，+/-2，,字母字符数据对象是集合,C=A，B，Z。,数据结构,是相互之间存在的一种或多种特定的关系的数据元素的集合。,从上面中三个例子可以知道，在任何问题中，数据元素之间都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间关系称为,结构,。,例如，当用,三个,4,位的十进制数,表示一个含,12,位数的十进制数时，,3214,6587,9345,a1,(3214),a2,(6587),a3,(9345),则在数据元素,a1、a2,和,a3,之间存在着,“次序”关系,a1,a2,、,a2,a3,3214，6587，9345,6587，3214，9345,例如:,a1 a2 a3,a2 a1 a3,又例，在,2,行,3,列的二维数组,中六个元素,a1,a2,a3,a4,a5,a6,之间存在两个关系:,行的次序关系,:,row=,col,=,a1 a2,a3,a4 a5 a6,列的次序关系,:,若在,6 个数据元素,a1,a2,a3,a4,a5,a6,之间存在如下的,次序关系,:,|i=1,2,3,4,5,数据结构,是,相互之间存在着某种逻辑关系的数据元素的集合,。,可见，不同的,“,关系,”,构成不同的,“,结构,”,则构成,一维数组,的定义。,从,关系,或,结构,分,，数据结构,可归结为以下,四类:,线性,结构,树形,结构,图状,结构,集合,结构,集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。,线性结构：结构中的数据元素之间存在一个对一个的关系。,树形结构：结构中的数据元素之间存在一个对多个的关系。,图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。,6,）数据的物理结构（又称存储结构）：是数据结构在计算,机中的表示。它包括数据元素的表示和关系的表示。,数据元素之间的关系在计算机中又有两种不同的表示方法：,顺序映像,特点：借助元素在存储器中的相对位置来表示数据,元素之间的逻辑关系。,非顺序映像,特点：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。,例如：假设用两个字长的位串表示一个实数，则可以用地址相邻的,4,个字长的位串表示一个复数，如图,1.3（,a）,为表示复数,z13.02.3i,和,z20.7+4.8i,的顺序存储结构。图,1.3（,b）,为表示复数,z1,的链式存储结构，其中实部和虚部之间的关系用值为“,0415”,的指针来表示（,0415,是虚部的存储地址）。,(,a),顺序存储结构,(,b),链式存储结构,图1.3,复数存储结构示意图,0300,0302,0632,0634,0415,0611,0613,3.0,-2.3,-0.7,4.8,-2.3,3.0,0415,数据的逻辑结构和物理结构是密切相关的两个方面。,在任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。,7,）数据类型：是一个值的集合和定义在这个值集上的一组,操作的总称。,按“值”的不同特性，在高级程序语言中可分为：,原子类型：其值不可分解。,例如，,C,语音中的基本类型（整型、实型、字符型,和枚举类型）、指针类型和空类型。,结构类型：其值是由若干成分按某种结构组成的，故可分解，并且其,成分可以是非结构的，也可以是结构的。,例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数,组等。,8,）抽象数据类型（,ADT）：,是指一个数学模型以及定义在该模型上的一组操作。,抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部,如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性,不变，都不影响其外部的使用。,其形式定义为：（一个三元组）,（,D,S,P）,其中，,D,是数据对象，,S,是,D,上的关系集，,P,是对,D,的基本操作集。,各种高级程序设计语言中都拥有“整数”类型，尽管它们在不同处理器上实现的方法不同，但对程序员而言是“相同的”，因为它们的数学特性相同。,从“数学抽象”的角度看，可称它为一个“抽象数据类型”。,按“值”的不同特性，可细分为：,原子类型：属原子类型的变量的值是不可分解的。,固定聚合类型：属该类型的变量，其值由确定数目的,成分按某种结构组成。,例如，复数是由两个实数依确定的次序关系构成。,可变聚合类型：和固定聚合类型相比较，构成可变聚,合类型“值”的成分数目不确定。,例如，可定义一个“有序整数序列”的抽象数据类型，其中序列的长度是可变的。,我们采用以下格式定义抽象数据类型：,ADT,抽象数据类型名,数据对象：,数据关系：,基本操作：,ADT,抽象数据类型名,其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：,基本操作名（参数表）,初始条件：,操作结果：,9,）多形数据类型：是指其值的成分不确定的数据类型。,例如，,定义抽象数据类型,“,复数,”,数据对象：,De1,e2e1,e2,RealSet,数据关系：,R1|e1,是复数的实数部分,|,e2,是复数的虚数部分,ADT Complex,基本操作：,AssignComplex,(&Z,v1,v2),操作结果：构造复数,Z,其实部和虚部,分别被赋以参数,v1,和,v2,的值。,DestroyComplex,(&Z),操作结果：复数,Z,被销毁。,GetReal,(Z,&,realPart,),初始条件：复数已存在。,操作结果：用,realPart,返回复数,Z,的实部值。,GetImag,(Z,&,ImagPart,),初始条件：复数已存在。,操作结果：用,ImagPart,返回复数,Z,的虚部值。,Add(z1,z2,&sum),初始条件：,z1,z2,是复数。,操作结果：用,sum,返回两个复数,z1,z2,的,和值。,ADT Complex,void Assign(Complex*A,ItemType,real,ItemType,virtual),A-r=real;,A-v=virtual;,/*Assign()*/,void Add(Complex*A,Complex B),A-r+=B.r;,A-v+=B.v;,/*Add()*/,复数抽象数据类型的,C,语言实现,#,include,#include,complex.h,void main,(),complex z1,z2,z3,z4,z;,float,RealPart,ImagPart,;,InitComplex,(z1,8.0,6.0);,InitComplex,(z2,4.0,3.0);,Add,(z1,z2,z3);,Multiply,(z1,z2,z4);,if(,Division,(z4,z3,z),GetReal,(z,RealPart,);,GetImag,(z,ImagPart,);,/if,ADT,有两个重要特征:,数据抽象,用,ADT,描述程序处理的实体时，强调的是其,本质的特征,、,其所能完成的功能,以及它和,外部用户的接口,（即,外界使用它的方法,）,数据封装,将实体的,外部特性和其内部实现细节分离,，并且,对外部用户隐藏,其内部实现细节,抽象数据类型的描述方法,抽象数据类型可用,（,D，S，P）,三元组表示,其中，,D,是数据对象，,S,是,D,上的关系集，,P,是对,D,的基本操作集。,ADT,抽象数据类型名,数据对象：,数据对象的定义,数据关系：,数据关系的定义,基本操作：,基本操作的定义,ADT,抽象数据类型名,其中基本操作的定义格式为:,基本操作名,（参数表）,初始条件：,初始条件描述,操作结果,：操作结果描述,赋值参数,只为操作提供输入值；,引用参数,以,&,打头，除可提供输入值外，,还将返回操作结果。,初始条件,描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。,操作结果,说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。,例二 抽象数据类型三元组的定义：,ADT Triplet,数据对象：,D,e1,e2,e3e1,e2,e3,ElemSet,数据关系：,R1,基本操作：,InitTriplet,(,&T,v1,v2,v3),操作结果：构造三元组,T,元素,e1,e2,和,e3,分别被赋以参数,v1,v2,和,v3,的值。,DestroyTriplet,(,&T),操作结果：三元组,T,被销毁。,Get(T,i,&e),初始条件：三元组,T,已存在，1,i3。,操作结果：用,e,返回,T,的第,i,元的值。,Put(,&T,i,e),初始条件：三元组,T,已存在，1,i3。,操作结果：改变,T,的第,i,元的值为,e。,IsAscending,(T),初始条件：三元组,T,已存在。,操作结果：如果,T,的三个元素按升序排列，则返回1，否则返回0。,IsDescending,(T),初始条件：三元组,T,已存在。,操作结果：如果,T,的三个元素按降序排列，则返回1，否则返回0。,Max(T,&e),初始条件：三元组,T,已存在。,操作结果：用,e,返回,T,的三个元素中的最大值。,Min(T,&e),初始条件：三元组,T,已存在。,操作结果：用,e,返回,T,的三个元素中的最小值。,ADT Triplet,