1.2 什么是数据结构

结构：实体 + 关系

数据结构：

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

数据结构的逻辑组织

线性结构

• 线性表（表，栈，队列，串等）

非线性结构

• 树（二叉树，Huffman树, 二叉检索树等）
  

• 图（有向图，无向图等）

关系：

数据的存储结构

• 逻辑结构到物理存储空间的映射
• 计算机主存储器（内存）
  • 非负整数地址编码，相邻单元的集合
    • 基本单位是字节
    • 访问不同地址所需时间基本相同（即随机访问）

存储结构分类：顺序、链接、索引、散列

抽象数据类型

简称ADT（Abstract Data Type）

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

模块化的思想的发展

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

抽象数据结构二元组

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

定义过程

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

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