数据结构中的基本概念与术语.ppt

，，，，消毒粉，，防霉剂，，，，，，，，防腐剂 4、数据结构 数据结构 定义1---- 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(Structure)。 数据结构的形式定义为：数据结构是一个二元组 Data_Structure=(D，S) (1-1) 其中：D是数据元素的有限集， S是D上关系的有限集。 例1-6 在计算机科学中，复数可取如下定义：复数是一种数据结构 Complex=(C，R) (1-2) 其中：C是含两个实数的集合{c1，c2}；R={P}，而P是定义在集合C上的一种关系 {c1，c2}，其中有序偶c1，c2表示c1是复数的实部，c2是复数的虚部。 例1-7 假设我们需要编制一个事务管理的程序，管理学校科学研究课题小组的各项事务，则首先要为程序的操作对象——课题小组设计一个数据结构。假设每个小组由一位教师、一至三名研究生及一至六名本科生组成，小组成员之间的关系是：教师指导研究生，而由每位研究生指导一至两名本科生。则可以如下定义数据结构： Group = (P，R) (1—3) 其中: P = {T，G1，…，Gn，S11…Snm} 1=n=3，1=m=2， R = {R1, R2} R1 = {T, Gi | 1=i=n, 1=n=3 } R2 = {Gi, Sij | 1=i=n, 1=j=m, 1=n=3, 1=m=2} 6、存储结构（Storge Structure): 数据结构在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构。 四种基本的存储方法： （1）顺序存储方法（顺序存储结构） （2）链接存储方法（链式存储结构） （3）索引存储方法 （4）散列存储方法 同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。 如何描述存储结构呢？ 我们可以借用高级程序语言中提供的 “数据类型”来描述它. 例如:可以用 “一维数组”类型来描述顺序存储结构， 以C语言提供的“指针”来描述链式存储结构。 8、数据类型(DataType) 在一种程序设计语言中，变量所具有的数据种类。 例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 例2、在C语言中 数据类型：基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义 按“值”的不同特性，高级程序语言中的数据类型可分为两类： 一类是非结构的原子类型。原子类型的值是不可分解的。如：C语言中的基本类型(整型、实型、字符型和枚举类型)、指针类型和空类型。 另一类是结构类型。结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。例如数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。在某种意义上，数据结构可以看成是“一组具有相同结构的值”，则结构类型可以看成由一种数据结构和定义在其上的一组操作组成。 9、抽象数据类型(Abstract Data Type简称ADT) 是指一个数学模型以及定义在该模型上的一组操作，面向逻辑层次。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。 它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 抽象数据类型的表示： 和数据结构的形式定义相对应，抽象数据类型可用以下三元组示 (D，S，P) (1—4) 其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。 抽象数据类型定义格式： ADT抽象数据类型名{ 数据对象：数据对象的定义