《数据结构》-基本概念和术语

第一章 绪论,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 = ,列的次序关系:,若在 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 03020632 0634,041506110613, 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,e2RealSet 数据关系： 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 数据对象：De1,e2,e3e1,e2,e3ElemSet 数据关系：R1 , 基本操作： InitTriplet( &T, v1, v2, v3 ) 操作结果：构造三元组T,元素e1,e2和e3分别被赋以参数v1,v2和v3的值。 DestroyTriplet( &T ) 操作结果：三元组T被销毁。,Get( T, i, &e ) 初始条件：三元组T已存在，1i3。 操作结果：用e返回T的第i元的值。Put( &T, i ,e ) 初始条件：三元组T已存在，1i3。 操作结果：改变T的第i元的值为e。 IsAscending( T ) 初始条