Data Structures and Algorithms
TIP
程序=算法+数据结构。
数据结构
数据结构（Data Structure）：带有结构特性的数据元素的集合。
简单而言，「数据结构」 指的是：数据的组织结构，用来组织、存储数据。
展开来讲，数据结构研究的是数据的逻辑结构、物理结构以及它们之间的相互关系，并对这种结构定义相应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。
数据结构的作用，就是为了提高计算机硬件的利用率。比如说：操作系统想要查找应用程序 「Microsoft Word」 在硬盘中的哪一个位置存储。如果对硬盘全部扫描一遍的话肯定效率很低，但如果使用「B+ 树」作为索引，就能很容易的搜索到 Microsoft Word 这个单词，然后很快的定位到 「Microsoft Word」这个应用程序的文件信息，从而从文件信息中找到对应的磁盘位置。
而学习数据结构，就是为了帮助我们了解和掌握计算机中的数据是以何种方式进行组织、存储的。
对于数据结构，我们可以按照数据的 「逻辑结构」 和 「物理结构」 来进行分类。
1.1 数据的逻辑结构
逻辑结构（Logical Structure）：数据元素之间的相互关系。
根据元素之间具有的不同关系，通常我们可以将数据的逻辑结构分为以下四种：
1. 集合结构
集合结构：数据元素同属于一个集合，除此之外无其他关系。
集合结构中的数据元素是无序的，并且每个数据元素都是唯一的，集合中没有相同的数据元素。集合结构很像数学意义上的「集合」。
2. 线性结构
线性结构：数据元素之间是「一对一」关系。
线性结构中的数据元素（除了第一个和最后一个元素），左侧和右侧分别只有一个数据与其相邻。线性结构类型包括：数组、链表，以及由它们衍生出来的栈、队列、哈希表。
- 树形结构
树形结构：数据元素之间是「一对多」的层次关系。
最简单的树形结构是二叉树。这种结构可以简单的表示为：根， 左子树， 右子树。 左子树和右子树又有自己的子树。当然除了二叉树，树形结构类型还包括：多叉树、字典树等。
4. 图形结构
图形结构：数据元素之间是「多对多」的关系。
图形结构是一种比树形结构更复杂的非线性结构，用于表示物件与物件之间的关系。一张图由一些小圆点（称为 「顶点」 或 「结点」）和连结这些圆点的直线或曲线（称为 「边」）组成。
在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。图形结构类型包括：无向图、有向图、连通图等。
1.2 数据的物理结构
物理结构（Physical Structure）：数据的逻辑结构在计算机中的存储方式。
计算机内有多种存储结构，采用最多的是这两种结构：「顺序存储结构」、「链式存储结构」。
1. 顺序存储结构
顺序存储结构（Sequential Storage Structure）：将数据元素存放在一片地址连续的存储单元里，数据元素之间的逻辑关系通过数据元素的存储地址来直接反映。
在顺序存储结构中，逻辑上相邻的数据元素在物理地址上也必然相邻 。
这种结构的优点是：简单、易理解，且实际占用最少的存储空间。缺点是：需要占用一片地址连续的存储单元；并且存储分配要事先进行；另外对于一些操作的时间效率较低（移动、删除元素等操作）。
2. 链式存储结构
链式存储结构（Linked Storage Structure）：将数据元素存放在任意的存储单元里，存储单元可以连续，也可以不连续。
链式存储结构中，逻辑上相邻的数据元素在物理地址上可能相邻，可也能不相邻。其在物理地址上的表现是随机的。链式存储结构中，一般将每个数据元素占用的若干单元的组合称为一个链结点。每个链结点不仅要存放一个数据元素的数据信息，还要存放一个指出这个数据元素在逻辑关系的直接后继元素所在链结点的地址，该地址被称为指针。换句话说，数据元素之间的逻辑关系是通过指针来间接反映的。
这种结构的优点是：存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比顺序存储结构高（插入、移动、删除元素）。缺点是：不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链式存储结构比顺序存储结构的空间开销大。
算法
- 算法（Algorithm）：解决特定问题求解步骤的准确而完整的描述，在计算机中表现为一系列指令的集合，算法代表着用系统的方法描述解决问题的策略机制。
- 算法的基本特性：
- 输入：对于待解决的问题，都要以某种方式交给对应的算法。在算法开始之前最初赋给算法的参数称为输入。一个算法可以有多个输入，也可以没有输入。
- 输出：算法是为了解决问题存在的，最终总需要返回一个结果。所以至少需要一个或多个参数作为算法的输出。
- 有穷性：算法必须在有限的步骤内结束，并且应该在一个可接受的时间内完成。
- 确定性：组成算法的每一条指令必须有着清晰明确的含义，不能令读者在理解时产生二义性或者多义性。就是说，算法的每一个步骤都必须准确定义而无歧义。
- 可行性：算法的每一步操作必须具有可执行性，在当前环境条件下可以通过有限次运算实现。也就是说，每一步都能通过执行有限次数完成，并且可以转换为程序在计算机上运行并得到正确的结果。
- 算法追求的目标：
- 所需运行时间更少（时间复杂度更低）；
- 占用内存空间更小（空间复杂度更低）。
- 现实中算法，往往是需要同时从运行时间、占用空间两个方面考虑问题。当然，运行时间越少，占用空间越小的算法肯定是越好的，但总是会有各种各样的因素导致了运行时间和占用空间不可兼顾。
- 算法的基本标准：
- 正确性：正确性是指算法能够满足具体问题的需求，程序运行正常，无语法错误，能够通过典型的软件测试，达到预期的需求。
- 可读性：可读性指的是算法遵循标识符命名规则，简洁易懂，注释语句恰当，方便自己和他人阅读，便于后期修改和调试。
- 健壮性：健壮性指的是算法对非法数据以及操作有较好的反应和处理。
所用资料
数据结构：
数据结构（C++语言版，第3版），邓俊辉，清华大学出版社，ISBN: 9-787-302-33064-6；
数据结构与算法（Java语言），邓俊辉，清华大学出版社；
算法设计与分析：
- 算法（第4版），Robert Sedgewick，谢路云，人民邮电出版社，ISBN: 978-7-115-29380-0；
- 算法设计与分析——C++语言描述，陈慧南，电子工业出版社，ISBN: 978-7-121-33054-33064；
- 算法分析导论，Robert Sedgewick等，电子工业出版社，ISBN: 9787121353680
还有Oi-Wiki上面的部分内容。
目前使用的语言以Java为主，兼用C++和Python。
计划所有内容
01-Beginning
02-Vector
03-List
04-Stack-and-Queue
05-Sorting
06-Tree
07-Advanced-Search-Tree
08-Tree-Like-DS
09-Dict-Map-and-Hashing
10-Priority-Queue-and-Heap
11-String
12-Graph
13-Search-and-Traverse
14-Divide-and-Conquer
15-Greedy
16-DP
17-Back-Tracking
18-Branch-and-Bound
19-NP-Complete
20-Randomized
21-Approx
22-Genetic
23-Crypto