基本概念和术语.ppt

《基本概念和术语.ppt》由会员分享，可在线阅读，更多相关《基本概念和术语.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章第一章 绪论绪论1.1 什么是数据结构什么是数据结构1.2 基本概念和术语基本概念和术语1.4 算法和算法分析算法和算法分析1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现1.2 基本概念和术语基本概念和术语一、数据、数据元素三、数据类型四、抽象数据类型二、数据对象、数据结构数据数据:是对客观事物的符号表示，在计算机科学中是对客观事物的符号表示，在计算机科学中是指所有能是指所有能输入输入到计算机中且能被计算机程序到计算机中且能被计算机程序处理处理的符号的符号(数值、字符等数值、字符等)的总称。的总称。例如，一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序

2、或文字处理程序的处理对象是字符串。因此，对计算机科学而言，数据的含义极为广泛，如图象、声音等都可以通过编码而归之于数据的范畴。一、数据、数据元素一、数据、数据元素数值性数据数值性数据非数值性数据非数值性数据数据元素数据元素:是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。例如，例12中的“树”中的一个棋盘格局，例13中的“图”中的一个圆圈都被称为一个数据元素。有时，一个数据元素可由若干个数据项一个数据元素可由若干个数据项组成组成，例如，例11中一本书的书目信息中的每一项（如书名、作者名等）为一个数据项，数据项是数据的不可分割数据项是数据的不可分割的最小单位。的最小单位。如:整数“5

3、”,字符“N”等。-是不可分割的“原子”其中每个款项称为一个“数据项数据项”它是数据结构中讨论的最小最小单位数据元素也可以由若干款项构成。数据元素也可以由若干款项构成。例如：描述一个学生的数据元素称之为组合项称之为组合项年月日姓 名学 号班 号性别出生日期入学成绩原子项原子项数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N=0，+/-1，+/-2，字母字符数据对象是集合C=A，B，Z。数据结构数据结构是相互之间存在的一种或多种特定的关系的数据元素的集合。从上面中三个例子可以知道，在任何问题中，数据元素之间都不是孤立存在的，而是在它们之间存在着某种关系，这

4、种数据元素相互之间关系称为结构结构。例如，当用三个三个 4 位的十进制数位的十进制数表示一个含12 位数的十进制数时，位数的十进制数时，3214,6587,9345 a1(3214),a2(6587),a3(9345)则在数据元素 a1、a2和a3 之间存在着“次序次序”关系关系 a1,a2、a2,a3 3214，6587，93456587，3214，9345例如例如:a1a2a3a2a1a3又例，在 2行 3列的二维数组中六个元素a1,a2,a3,a4,a5,a6之间存在两个关系:行的次序关系行的次序关系:row=,col=,a1a2a3a4a5a6列的次序关系列的次序关系:若在6个数据元素

5、a1,a2,a3,a4,a5,a6之间存在如下的次序关系次序关系:|i=1,2,3,4,5 数据结构数据结构是相互之间存在着某种逻辑相互之间存在着某种逻辑关系的数据元素的集合关系的数据元素的集合。可见，不同的“关系关系”构成不同的“结构结构”则构成一维数组一维数组的定义。从关系关系或结构结构分，数据结构，数据结构可归结为以下四类四类:线性线性结构树形树形结构图状图状结构集合集合结构集合：结构中的数据元素之间除了集合：结构中的数据元素之间除了“同属于一个集合同属于一个集合”的关系外，别无其他关系。的关系外，别无其他关系。线性结构：结构中的数据元素之间存在一个对一个的关系。线性结构：结构中的数据元

6、素之间存在一个对一个的关系。树形结构：结构中的数据元素之间存在一个对多个的关系。树形结构：结构中的数据元素之间存在一个对多个的关系。图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。6）数据的物理结构（又称存储结构）：是数据结构在计算）数据的物理结构（又称存储结构）：是数据结构在计算 机中的表示。它包括数据元素的表示和关系的表示。机中的表示。它包括数据元素的表示和关系的表示。数据元素之间的关系在计算机中又有两种不同的表示方法：数据元素之间的关系在计算机中又有两种不同的表示方法：顺序映像顺序映像 特点：借助元素在存储器中的

7、相对位置来表示数据特点：借助元素在存储器中的相对位置来表示数据 元素之间的逻辑关系。元素之间的逻辑关系。非顺序映像非顺序映像 特点：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。特点：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。例如：假设用两个字长的位串表示一个实数，则可以用地址相邻的例如：假设用两个字长的位串表示一个实数，则可以用地址相邻的4个字长的位串个字长的位串表示一个复数，如图表示一个复数，如图1.3（a）为表示复数为表示复数z13.02.3i和和z20.7+4.8i的顺序存储结的顺序存储结构。图构。图1.3（b）为表示复数为表示复数z1的链式存储结构，其中实部和虚部

8、之间的关系用值为的链式存储结构，其中实部和虚部之间的关系用值为“0415”的指针来表示（的指针来表示（0415是虚部的存储地址）。是虚部的存储地址）。(a)顺序存储结构 (b)链式存储结构图1.3 复数存储结构示意图0300 03020632 0634 041506110613 3.0-2.3-0.74.8-2.33.00415数据的逻辑结构和物理结构是密切相关的两个方面。在任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。7）数据类型：是一个值的集合和定义在这个值集上的一组）数据类型：是一个值的集合和定义在这个值集上的一组 操作的总称。操作的总称。按按“值值”

9、的不同特性，在高级程序语言中可分为：的不同特性，在高级程序语言中可分为：原子类型：其值不可分解。原子类型：其值不可分解。例如，例如，C语音中的基本类型（整型、实型、字符型语音中的基本类型（整型、实型、字符型 和枚举类型）、指针类型和空类型。和枚举类型）、指针类型和空类型。结构类型：其值是由若干成分按某种结构组成的，故可分解，并且其结构类型：其值是由若干成分按某种结构组成的，故可分解，并且其 成分可以是非结构的，也可以是结构的。成分可以是非结构的，也可以是结构的。例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数 组等。组等。

10、8）抽象数据类型（）抽象数据类型（ADT）：）：是指一个数学模型以及定义在该模型上的一组操作。是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。不变，都不影响其外部的使用。其形式定义为：（一个三元组）其形式定义为：（一个三元组）（D,S,P）其中，其中，D是数据对象，是数据对象，S是是D上的关系集，上的关系集，P是对是对D的基

11、本操作集。的基本操作集。各种高级程序设计语言中都拥有“整数”类型，尽管它们在不同处理器上实现的方法不同，但对程序员而言是“相同的”，因为它们的数学特性相同。从“数学抽象”的角度看，可称它为一个“抽象数据类型”。按按“值值”的不同特性，可细分为：的不同特性，可细分为：原子类型：属原子类型的变量的值是不可分解的。原子类型：属原子类型的变量的值是不可分解的。固定聚合类型：属该类型的变量，其值由确定数目的固定聚合类型：属该类型的变量，其值由确定数目的 成分按某种结构组成。成分按某种结构组成。例如，复数是由两个实数依确定的次序关系构成。例如，复数是由两个实数依确定的次序关系构成。可变聚合类型：和固定聚合

12、类型相比较，构成可变聚可变聚合类型：和固定聚合类型相比较，构成可变聚 合类型合类型“值值”的成分数目不确定。的成分数目不确定。例如，可定义一个例如，可定义一个“有序整数序列有序整数序列”的抽象数据类型，其中序列的长度是可变的。的抽象数据类型，其中序列的长度是可变的。我们采用以下格式定义抽象数据类型：我们采用以下格式定义抽象数据类型：ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT 抽象数据类型名抽象数据类型名 其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：基

13、本操作名（参数表）基本操作名（参数表）初始条件：初始条件：操作结果：操作结果：9）多形数据类型：是指其值的成分不确定的数据类型。）多形数据类型：是指其值的成分不确定的数据类型。例如，例如，定义抽象数据类型“复数复数”数据对象：数据对象：De1,e2e1,e2RealSet 数据关系：数据关系：R1|e1是复数的实数部分,|e2 是复数的虚数部分 ADT Complex 基本操作：基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&re

14、alPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的 和值。ADT ComplexvoidAssign(Complex*A,ItemTypereal,ItemTypevirtual)A-r=real;A-v=virtual;/*Assign()*/voidAdd(Complex*A,ComplexB)A-r+=B.r;A-v+=B.v;/*Add()*/复

15、数抽象数据类型的C语言实现#include#includecomplex.hvoid 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);/ifADT 有两个重要特征:数据抽象数据抽象 用ADT描述程序处理的实体时，强调的是其本质的特征本质的特征、其所能完成的其所能

16、完成的功能功能以及它和外部用户的接口外部用户的接口（即外界外界使用它的方法使用它的方法）数据封装数据封装 将实体的外部特性和其内部外部特性和其内部实现细节分离实现细节分离，并且对外部用户隐藏对外部用户隐藏其内部实现细节其内部实现细节抽象数据类型的描述方法抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示其中，D是数据对象，S是 D上的关系集，P是对 D的基本操作集。ADT抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义 数据关系：数据关系：数据关系的定义 基本操作：基本操作：基本操作的定义 ADT 抽象数据类型名其中基本操作的定义格式为:基本操作名基本操作名（参数表

17、）初始条件：初始条件：初始条件描述 操作结果操作结果：操作结果描述 赋值参数赋值参数 只为操作提供输入值；引用参数引用参数 以&打头，除可提供输入值外，还将返回操作结果。初始条件初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。例二抽象数据类型三元组的定义：ADT Triplet 数数据据对对象象：De1,e2,e3e1,e2,e3ElemSet数据关系：数据关系：R1,基本操作：基本操作：InitTriplet(&T,v1,v2,v3)操作结果

18、：构造三元组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)初始条件：三元组T已存在。操作结果：如果T的三个元素按升序排列，则返回1，否则返回0。IsDescending(T)初始条件：三元组T已存在。操作结果：如果T的三个元素按降序排列，则返回1，否则返回0。Max(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的三个元素中的最大值。Min(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的三个元素中的最小值。ADT Triplet