Data Structures
● 基本概念
1 什么是数据结构
1.1 其他定义
- 数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。 ——Sartaj Sahni 《数据结构、算法与应用》
- 数据结构是 ADT（Abstract Data Type，数据抽象类型）的物理实现。 ——Clifford A.Shaffer 《数据结构与算法分析》
- 数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。 ——中文维基百科
1.2 解决问题方法的效率
- 跟数组的组织方式有关
- 跟空间的利用效率有关
- 跟算法的巧妙程度有关
1.3 最终定义
- 数据对象在计算机中的组织方式
- 逻辑结构
- 物理存储结构
- 数据对象必定与一系列加在其上的操作相关联
- 完成这些操作所用的方法就是算法
1.4 抽象数据类型（Abstract Data Type）
数据类型
- 数据对象集
- 数据集合相关联的操作集
抽象：描述数据类型的方法不依赖于具体实现
- 与存放数据的机器无关
- 与数据存储的物理结构无关
- 与实现操作的算法和编程语言均无关
只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题
2 什么是算法
2.1 定义
- 一个有限指令集
- ≥ 0 的输入
- 0 的输出
- 一定在有限步骤之后终止
- 每一条指令必须
- 有充分明确的目标，不可以有歧义
- 计算机能处理范围内
- 描述应不依赖于任何一种计算机语言以及具体的实现手段
2.2 描述算法的手段
空间复杂度 S(n)
根据算法写成的程序在执行时占用存储空间的长度
时间复杂度 T(n)
根据算法写成的程序在执行时耗费的时间的长度
2.3 评价
- 在分析一般算法的效率时，常常关注
