一、什么是数据结构
-
结构：实体 + 关系，比如分子结构，关系图等
-
数据结构：按照逻辑关系组织起来的一批数据，按一定的存储方法所把它存储在计算机中，并在这些数据上定义了一个运算的集合
二、数据的逻辑结构
- 线性结构
线性表（表、栈、队列、串等） - 非线性结构
树（二叉树、Huffman树、二叉检索树等）
图（有向图、无向图等） - 图 ⊇ 树 ⊇ 二叉树 ⊇ 线性表
三、数据的存储结构
-
将逻辑结构的结点映射到内存中，每一个结点都对应一个唯一的连续存储区域
-
内存可以看作从低地址到高地址的一个编码的线性结构，可以根据地址立即访问想要访问的内存单元，不需要搜索
-
存储结构主要有顺序、链接、索引和散列四种形式
- 顺序存储对应于数组
- 链接存储对应于链表
- 索引是对数据建立一个索引表，通过这个表有效的找到相应数据的存储地址
- 散列是一种特殊的索引结构，本身也是一种存储结构，通过关键码的映射关系，在整个散列表中用单位时间快速地找到其存储地址
四、抽象数据类型 ADT（Abstract Data Type）
- 定义了一组运算的数学模型
- 与物理存储结构无关
- 使软件系统建立在数据之上(面向对象)
五、定义抽象数据类型
抽象数据类型就是在逻辑结构上的运算，可以理解为抽象数据结构二元组 <数据对象D, 数据操作P>
先定义逻辑结构，再定义运算
- 逻辑结构：数据对象及其关系
- 运算：数据操作
就像面向对象语言中所定义的类（特别是抽象类），封装了数据成员和函数成员
