第一章绪论 ●综上三个例子,描述这类非数值计算问题的数学模型 不再是数学方程,而是诸如表、树和图之类的数据结 构。 ●因此,简单说来,数据结构是一门研究非数值计算的 程序设计问题中计算机的操作对象以及它们之间的关 系和操作等等的学科。 数据结构就是研究数据的逻辑结构和物理结构它们之 间相互关系,并对这种结构定义相应的运算,而且确 保经过这些运算后所得到的新结构仍然是原来的结构 类型。 北京邮电大学自动化学院 21
北京邮电大学自动化学院 21 ⚫ 综上三个例子，描述这类非数值计算问题的数学模型 不再是数学方程，而是诸如表、树和图之类的数据结 构。 ⚫ 因此，简单说来，数据结构是一门研究非数值计算的 程序设计问题中计算机的操作对象以及它们之间的关 系和操作等等的学科。 ⚫ 数据结构就是研究数据的逻辑结构和物理结构它们之 间相互关系，并对这种结构定义相应的运算，而且确 保经过这些运算后所得到的新结构仍然是原来的结构 类型。 第一章 绪 论
1.2基本概念和术语 数据(Data):是对客观事物的符号表示,在计算机科 学中是指所有能输入到计算机中并被计算机程序处 理的符号的总称。 ●对计算机科学而言,数据的含义极为广泛,如图 像、声音等都可以通过编码而归之于数据的范畴。 数据元素 Data element:是数据的基本单位,在计 算机程序中通常作为一个整体进行考虑和处理。 例如,例1-2中的“树”中的一个棋盘格局,例1 3中的“图”中的一个园圈都被称为一个数据元 素。 北京邮电大学自动化学院
北京邮电大学自动化学院 22 ⚫ 数据(Data):是对客观事物的符号表示，在计算机科 学中是指所有能输入到计算机中并被计算机程序处 理的符号的总称。 ⚫ 对计算机科学而言，数据的含义极为广泛，如图 像、声音等都可以通过编码而归之于数据的范畴。 ⚫ 数据元素(Data Element):是数据的基本单位，在计 算机程序中通常作为一个整体进行考虑和处理。 ⚫ 例如，例1－2中的“树”中的一个棋盘格局，例1 －3中的“图”中的一个园圈都被称为一个数据元 素。 1.2 基本概念和术语
1.2基本概念和术语 ●一个数据元素可由若干个数据项组成。例如,例1-1中 本书的书目信息为一个数据元素,而书目信息中的每一项 (如书名、作者名等)为一个数据项。 数据项是数据的不可分割的最小单位。 数据对象( Data Object):是性质相同的数据元素的集合, 是数据的一个子集。例如,整数数据对象是集合N={0, ±1,士2,…},字母字符数据对象是集合C={A,B, 数据结构( Data structure):是相互之间存在一种或多种 特定关系的数据元素的集合。 北京邮电大学自动化学院
北京邮电大学自动化学院 23 ⚫ 一个数据元素可由若干个数据项组成。例如，例1－1中一 本书的书目信息为一个数据元素，而书目信息中的每一项 （如书名、作者名等）为一个数据项。 ⚫ 数据项是数据的不可分割的最小单位。 ⚫ 数据对象(Data Object)：是性质相同的数据元素的集合， 是数据的一个子集。例如，整数数据对象是集合N＝{0， ±1，±2，…}，字母字符数据对象是集合C＝ {A，B， C，…}。 ⚫ 数据结构(Data Structure)：是相互之间存在一种或多种 特定关系的数据元素的集合。 1.2 基本概念和术语
1.2基本概念和术语 ●数据结构主要指逻辑结构和物理结构。数据之间的相互关系称 为逻辑结构。通常分为四类基本结构: 集合结构中的数据元素除了同属于一种类型外,别无其 它关系。 ○x○>○ 、线性结构结构中的数据元素之间存在一对一的关系。 三、树型结构结构中的数据元素之间存在一对多的关系。 ●四、图状结构或网状结构结构中的数据元素之间存在多对多 的关系。 北京邮电大学自动化学院
北京邮电大学自动化学院 24 ⚫ 数据结构主要指逻辑结构和物理结构。数据之间的相互关系称 为逻辑结构。通常分为四类基本结构： ⚫ 一、集合 结构中的数据元素除了同属于一种类型外，别无其 它关系。 ⚫ 二、线性结构 结构中的数据元素之间存在一对一的关系。 ⚫ 三、树型结构 结构中的数据元素之间存在一对多的关系。 ⚫ 四、图状结构或网状结构 结构中的数据元素之间存在多对多 的关系。 1.2 基本概念和术语
1.2基本概念和术语 ●数据结构的形式定义为:数据结构是一个二元组: Data-Structure=(D,s) ●其中:D是数据元素的有限集,S是D上关系的有限 集。 例复数的数据结构定义如下: Complex=(C,R) ●其中:C是含两个实数的集合【C,C2,分别表 示复数的实部和虚部。R={P},P是定义在集合上的 种关系{(C1,c2〉} 北京邮电大学自动化学院
北京邮电大学自动化学院 25 ⚫ 数据结构的形式定义为：数据结构是一个二元组： ⚫ Data-Structure=(D，S) ⚫ 其中：D是数据元素的有限集，S是D上关系的有限 集。 ⚫ 例 复数的数据结构定义如下： Complex=(C，R) ⚫ 其中：C是含两个实数的集合﹛C1，C2﹜，分别表 示复数的实部和虚部。R={P}，P是定义在集合上的 一种关系{〈C1，C2〉}。 1.2 基本概念和术语