2019.12.2
1.3数据结构与抽象数据类型 学习记录
1.2什么是数据结构
结构：实体 + 关系
数据结构的组合：
逻辑，存储，运算三个方面：
- 按照逻辑关系组织起来的一批数据
- 按一定的存储方法把它存储在计算机中
- 在这些数据上定义了一个运算的集合
数据结构的逻辑组织：
线性结构
- 线性表（表，栈，队列，串等）[前驱后继关系]
非线性结构
- 树（二叉树，Huffman树，二叉检索树等）[层次化关系]
- 图（有向图，无向图等）[无向，受限少]
数据的存储结构
逻辑结构到物理存储空间的映射。对于数据结构里所定义的每一个节点，申请的内存空间必须是连续存储的区域
除非指针指向别的扩展地址。
计算机主存储器（内存）
- 非负整数地址编码，相邻单元的集合
- 基本单位是字节
- 访问不同地址所需时间基本相同（即随机访问）
数据结构的存储结构组成（四类形式）：顺序，链接，索引，散列
抽象数据类型
简称ADT(Abstract Data Type)
- 定义了一组运算的数学模型
- 与物理存储结构无关
- 使软件系统建立在数据之上(面向对象)
抽象数据类型的标准格式
ADT 抽象数据类型名
{
Data:
数据元素之间逻辑关系的定义；
Operation:
操作1；
操作2；
...
} 就像“超级玛丽”这个经典的任天堂游戏，里面的游戏主角是马里奥，我们给他定义了基本操作，前进、后退、跳、打子弹等。这就是一个抽象数据类型，定义了一个数据对象、对象中各元素之间的关系及对数据元素的操作。