【1.2】数据结构及抽象数据类型

一、概念

结构 = 实体+关系

数据结构:

• 按照逻辑关系组织起来的 一批数据,
• 按一定的存储方法把它存 储在计算机中
• 在这些数据上定义了一个 运算的集合

1.1 数据结构的逻辑组织

• 线性结构：
• 线性表(表，栈，队列，串等)
• 非线性结构
• 树(二叉树，Huffman树，二叉检索树等)
• 图(有向图，无向图等)

图 ⊇ 树 ⊇ 二叉树 ⊇ 线性表

1.2 数据的存储结构

逻辑结构到物理存储空间的映射

计算机主存储器(内存)：

• 非负整数地址编码，相邻单元的集合
• 基本单位是字节
• 访问不同地址所需时间基本相同(即随机访问)

对逻辑结构(K ，r)，其中r∈R

对结点集 K 建立一个从 K 到存储器 M 的单元的映射:K→M，对于 每一个结点 j∈K 都对应一个唯一的连续存储区域c ∈ M

关系元组(j1 ，j2)∈r (其中j1， j2∈ K 是结点)

四类:顺序、链接、索引、散列

1.3 抽象数据类型

简称ADT (Abstract Data Type) ：

• 定义了一组运算的数学模型
• 与物理存储结构无关
• 使软件系统建立在数据之上(面向对象)

模块化的思想的发展：

• 隐藏运算实现的细节和内部数据结构
• 软件复用

抽象数据结构二元组：

<数据对象D，数据操作P>

先定义逻辑结构，再定义运算

• 逻辑结构:数据对象及其关系
• 运算:数据操作

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾蛟