(1.2.1)--1.2基本概念和术语

1 第 二 讲：数据结构的基本概念和术语 数据结构与算法 2 @ 指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它 与数据的存储无关，是独立于计算机的。与数据的存储无关，是独立于计算机的。 @ 逻辑结构细分为四类： l 集合：仅同属一个集合。 l 线性结构： l 树形结构 l 图 ontents 1 、数据的逻辑结构、数据的逻辑结构 线性结构 非线性结构 2. 数据的存储结构数据的存储结构 l 数据的逻辑关系在计算机存储器中的映像；是逻辑结 构用计算机语言的实现。 3 a bc def 4 l 顺序存储方式 l 链式存储方式 l 索引存储结构 l 散列存储结构 ontents 2 、 存储结构（物理结构）、 存储结构（物理结构） 存储时需解决： 存储时需解决： 1 1 ）数据元素 ）数据元素 2 2 ）数据元素之间的关系 ）数据元素之间的关系 (1) 顺序存储方式 • 假设有一线性数据结构（ a1, a2, a3 ），每个数据元素占 2 个存储单元，存储区的起始地址是 10 ，如何采用顺序存 储结构存储该数据结构？ 5 特点：将逻辑上相关的数据元素依次存储在地址连特点：将逻辑上相关的数据元素依次存储在地址连 续的存储空间。续的存储空间。 a1a2a3 内存地址存储内容 10a1 12a2 14a3 Loc(ai) = 10 + 2 × （ i- 1 ） (2) 链式存储方式 • 假设有一线性数据结构（ a1, a2, a3 ），存储区的起始地 址是 1400 ，如何采用链式存储结构存储该数据结构？ 6 特点：数据元素可以存储在是连续的或不连续的存储空间 特点：数据元素可以存储在是连续的或不连续的存储空间 。。 a1a2a3 存储地址 存储内容 （元素值） 指针 （后继地址） 1345a2 1536 ……. ……. ……. 1400a1 1345 …….……. ……. 1536a3 ∧ 1536a21345a1∧a3 1400 h 链式存储示意图链式存储示意图 2. 数据的存储结构示例数据的存储结构示例 l 例：复数 3. 0－ 2. 3i 的两种存储方式： l 同一种逻辑结构可采用同一种逻辑结构可采用不同的存储方法不同的存储方法，这主要考，这主要考 虑的是运算方便及算法的时空要求。虑的是运算方便及算法的时空要求。 7 顺序存储顺序存储 4 0304 链式存储链式存储 0304 2. 数据的存储结构数据的存储结构 （ 3 ）索引存储结构 建立附加的索引表来标识结点的地址建立附加的索引表来标识结点的地址 （ 4 ）散列存储结构 将数据元素的关键字与存储位置之间建立散列将数据元素的关键字与存储位置之间建立散列 表 表 小结 • 1. 顺序存储和链式存储是两种最基本的存储表示方法 • 2. 存储时不仅保存了数据元素，还保存了数据元素之间 的逻辑关系 8 • 是在数据的逻辑结构上定义的操作算法，它在数是在数据的逻辑结构上定义的操作算法，它在数 据的存储结构上实现。据的存储结构上实现。 • 最常用的运算主要有最常用的运算主要有 5 种：种： Ø插入、删除、修改、查找、排序 。 插入、删除、修改、查找、排序 。 9 ontents 3. 数据的运算数据的运算 10 @数据 (Data): 是指所有能输入到计算机中并被计算 机程序处理的符号的总称。 数据结构的基本概念 ontents 1.2 基本概念和术语基本概念和术语 ：： 姓名姓名电话号码电话号码 周一周一1234567 陈二陈二13612345588 张三张三15866667777 李四李四13056112345 11 @数据 (Data): 是指所有能输入到计算机中并被计算 机程序处理的符号的总称。 @数据元素 数据元素 ( (Data Element): 数据中的一个“个体个体” , 是数据的基本单位基本单位。 @数据项 数据项 (Data Item): 是组成是组成数据元素的最小单位最小单位。 @数据对象 数据对象 (Data Object) ：是性质相同的数据元素是性质相同的数据元素 的集合。是数据的一个子集。的集合。是数据的一个子集。 数据结构的基本概念 ontents 基本概念和术语：基本概念和术语： 12 @ 数据类型（ D ata Type）：一个值的集合和定义在这 个值集上的一组操作的总称。 在一种程序设计语言中，特指变量所具有的数据种类。 数据结构的基本概念 ontents 基本概念和术语：基本概念和术语： 例如，例如， C/C++ 中的中的 int 就是整型数据类型就是整型数据类型（（ 16 位计算机）。位计算机）。 - -32768~32767 ＋、－、＋、－、 * 、／ 、／  值的集合值的集合 一组操作一组操作 据型就是数类已经实现了的数据结构。 13 @抽象数据类型（ A D T）：由用户定义，用以表示 应用问题的数学模型。 Ø 是指一个数学模型以及定义在该模型上的一组操作。是指一个数学模型以及定义在该模型上的一组操作。 Ø 它由基本的数据类型构成，并包括一组相关的操作。它由基本的数据类型构成，并包括一组相关的操作。 Ø 它与数据类型实质上是一个概念，但其特征是使用与它与数据类型实质上是一个概念，但其特征是使用与 实现分离（独立于计算机）。实现分离（独立于计算机）。 ontents 抽象数据类型（抽象数据类型（ ADT ）：）： 数据结构的基本概念 14 @抽象数据类型（ A D T）可用三元组来表示 可用三元组来表示： A D T= ( D( D ，， S S ，， T )T ) 数据对象 D上关系集 D上的基本操作集 ontents 抽象数据类型（抽象数据类型（ ADT ）如何定义）如何定义 ：： 数据结构的基本概念 ADTADT 抽象数据类型名抽象数据类型名 { { 数据对象： 数据对象： 数据关系：数据关系： 基本操作 ：基本操作 ： } ADT} ADT 抽象数据类型抽象数据类型 ADT ADT 常用常用 定义格式定义格式 15 ontents 例：抽象数据类型“复数”的定义例：抽象数据类型“复数”的定义 数据结构的概念 ADT Complex { 数据对象： 数据对象： D ＝ {e1,e2 ｜ e1,e2 RealSet }∈ 数据关系： 数据关系： R1 ＝ { | e1 是复数的实数部分 , | e2 是复数的虚数部分 } 基本操作： 基本操作： AssignComplex( &Z, v1, v2 ) 操作结果：构造复数 Z, 其实部和虚部分别被赋以参数 v1 和 v2 的值。 DestroyComplex( &Z) 操作结果：复数 Z 被销毁。 16 基本操作： 基本操作： GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用 realPart 返回复数 Z 的实部值。 GetImag( Z, &ImagPart ) 初始条件：复数已存在。 操作结果：用 ImagPart 返回复数 Z 的虚部值。 Add( z1,z2, &sum ) 初始条件： z1,