Data Structure and Algorithms
数据结构是一种系统化的数据组织方式，以便有效地使用数据。以下术语是数据结构的基础术语。
- 接口：每个数据结构都有一个接口，接口表示数据结构支持的一组操作，接口只提供支持的操作列表、它们可以接受的参数类型以及这些操作的返回类型。
- 实现：实现提供数据结构的内部表示，实现还提供了数据结构操作中使用的算法的定义。
数据结构的特征
- 正确性：数据结构实现应该正确实现其接口
- 时间复杂性：数据结构操作的运行时间或执行时间必须尽可能小
- 空间复杂性：数据结构操作的内存使用量应该尽可能少
数据结构的产生
随着应用程序变得越来越复杂和数据越来越丰富，应用程序现在每天都面临三个常见问题。 数据搜索——考虑一家商店100万( 106 )件商品的库存。如果应用程序要搜索一个项目，它必须在100万( 106 )个项目中搜索一个项目，每次都会减慢搜索速度。随着数据的增长，搜索速度会变慢。 处理器速度——处理器速度虽然很高，但如果数据增长到十亿条记录，速度就会受到限制。 多个请求——由于成千上万的用户可以在一个web服务器上同时搜索数据，即使是快速服务器在搜索数据时也会失败。 为了解决上述问题，数据结构应运而生。数据可以以数据结构的方式组织，使得不需要搜索所有项目，并且几乎可以立即搜索所需的数据。
执行时间
有三种情况通常用于以相对的方式比较各种数据结构的执行时间。
- 最坏情况：这是特定数据结构操作花费最大时间的情况。如果一个操作最差的情况时间是 f(n)，那么这个操作不会花费超过 f(n) 个时间，其中 f(n) 代表n的函数。
- 平均情况：这是描述数据结构操作的平均执行时间的场景。如果一个操作在执行中花费了 f(n) 时间，那么m个操作将花费 mf(n) 时间。
- 最佳情况：这是描述数据结构操作的最小可能执行时间的情况。如果一个操作在执行中花费了时间，那么实际的操作可能会花费时间作为随机数，最大值为 f(n) 时间。
数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
- 数据：所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。
- 数据元素：数据（集合）中的一个 “个体”，数据及结构中讨论的基本单位
- 数据项：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。
-
数据类型：在一种程序设计语言中，变量所具有的数据种类。整型、浮点型、字符型等等
- 逻辑结构：数据之间的相互关系。
- 集合 结构中的数据元素除了同属于一种类型外，别无其它关系。
- 线性结构 数据元素之间一对一的关系
- 树形结构 数据元素之间一对多的关系
- 图状结构或网状结构 结构中的数据元素之间存在多对多的关系
- 物理结构 / 存储结构：数据在计算机中的表示。物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、哈希结构）等
- 在数据结构中, 从逻辑上可以将其分为线性结构和非线性结构
- 数据结构的基本操作的设置的最重要的准则是, 实现应用程序与存储结构的独立。实现应用程序是 “逻辑结构”，存储的是 “物理结构”。逻辑结构主要是对该结构操作的设定，物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、希哈结构）等。
-
顺序存储结构中，线性表的逻辑顺序和物理顺序总是一致的。但在链式存储结构中，线性表的逻辑顺序和物理顺序一般是不同的。
-
算法五个特性： 有穷性、确定性、可行性、输入、输出
- 算法设计要求：正确性、可读性、健壮性、高效率与低存储量需求。(好的算法)
- 算法的描述有伪程序、流程图、N-S 结构图等。E-R 图是实体联系模型，不是程序的描述方式。
- 设计算法在执行时间时需要考虑：算法选用的规模、问题的规模
- 时间复杂度：算法的执行时间与原操作执行次数之和成正比。时间复杂度有小到大：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(n^3)。幂次时间复杂度有小到大 O(2^n)、O(n!)、O(n^n)
- 空间复杂度：若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。