目录
1.1 数据结构概述
1.2 数据结构的分类
1.2.1 逻辑结构
1）集合
2）线性结构
3）树形结构
4）图形结构
1.2.2 物理结构
1）顺序存储
2）链式存储
3）散列存储
4）索引存储
1.3 数据结构的实现
1.2.1 数组
1.2.2 链表
1.2.3 栈
1.2.4 队列
1.2.5 树
1.2.6 堆
1.2.7 散列表
1.2.8 图
1.1 数据结构概述
数据结构是计算机存储、组织数据的方式；通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率，这也是判断数据结构优良的两个维度。数据结构的优良将直接影响着我们程序的性能；
通常情况下，这两个维度是相悖的，即：更高的运行效率往往存储效率较低，更高的存储效率往往运行效率较低。
1.2 数据结构的分类
数据结构的世界非常丰富多彩，在学习之前我们必须先给它归类。数据结构一般分为逻辑结构和物理结构这两大总类，在两大总类下还可以细分出其他分类。
逻辑结构：数据元素之间的逻辑联系（关注数据间的关系）
物理结构：数据元素的存放形式（关注数据的存储方式）
1.2.1 逻辑结构
逻辑结构是指数据对象中数据元素之间相互关系（逻辑关系），即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机存储器的。根据数据元素之间关系的不同特征，通常有下列4类基本结构，复杂程度依次递进。
1）集合
集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
2）线性结构
线性结构：数据结构中的元素存在一对一的相互关系；
3）树形结构
树形结构：数据结构中的元素存在一对多的相互关系；
4）图形结构
图形结构：数据结构中的元素存在多对多的相互关系；
1.2.2 物理结构
数据的物理结构是指数据的逻辑结构在计算机中的存储方式（就是数据存储在磁盘中的方式）。是数据结构在计算机中的实现方法，包括数据元素的表示和元素之间的关系。
物理结构一般有四种：顺序存储，链式存储，散列，索引。
1）顺序存储
顺序存储结构是把数据元素放在地址连续的存储单元中，程序设计中使用数组类型来实现。（逻辑相邻物理相邻）
2）链式存储
把数据元素存储在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，程序设计中使用指针类型来实现。（逻辑相邻物理不一定相邻），程序设计中使用链表来实现。
3）散列存储
散列存储结构通过计算元素的散列值直接确定数据元素的物理位置，设计时需处理哈希冲突（如链地址法、开放寻定法）。
数据元素在存储空间中呈分散分布，物理相邻性与逻辑顺序无直接关联，程序设计常通过哈希表结构实现。（逻辑无相邻性，物理位置由哈希函数决定）
4）索引存储
索引存储结构将数据元素存放在任意存储单元中，同时维护一个独立的索引表（如B树、倒排索引）。访问时先查询索引表获取地址再定位数据，逻辑顺序由索引表维护而非物理位置决定。
程序设计可通过键值对数据库、文件系统目录等实现。（逻辑关系由索引表维护，物理位置可任意分布）
1.3 数据结构的实现
数据结构可视化网站：Data Structure Visualization
常见的数据结构实现有：数组（Array）、栈（Stack）、队列（Queue）、链表（Linked List）、树（Tree）、图（Graph）、堆（Heap）、散列表（Hash）等；
1.2.1 数组
- 数组（Array）：数组是有序元素的序列，在内存中的分配是连续的，数组会为存储的元素都分配一个下标（索引），此下标是一个自增连续的，访问数组中的元素通过下标进行访问；数组下标从0开始访问；
- 数组的优点是：查询速度快；
- 数组的缺点是：增加、删除慢；由于数组为每个元素都分配了索引且索引是自增连续的，因此一但删除或者新增了某个元素时需要调整后面的所有元素的索引；
新增一个元素40到3索引下标位置：
删除2索引元素：
总结：数组查询快，增删慢，适用于频繁查询，增删较少的情况；
1.2.2 链表
- 链表（Linked List）：链表是由一系列节点Node（也可称元素）组成，数据元素的逻辑顺序是通过链表的指针地址实现，通常情况下，每个节点包含两个部分，一个用于存储元素的数据，名叫数据域，另一个则指向下一个相邻节点地址的指针，名叫指针域；根据链表的指向不同可分为单向链表、双向链表、循环链表等；我们本章介绍的是单向链表，也是所有链表中最常见、最简单的链表；
链表的节点（Node）：
完整的链表：
- 链表的优点：新增节点、删除节点快；
在链表中新增一个元素：
在单向链表中，新增一个元素最多只会影响上一个节点，比在数组中的新增效率要高的多；
在链表中删除一个元素：
- 链表的缺点：
- 1）查询速度慢，查询从头部开始一直查询到尾部，如果元素刚好是在最尾部那么查询效率势必非常低；
- 2）链表相对于数组多了一个指针域的开销，内存相对占用会比较大；
总结：数据量较小，需要频繁增加，删除操作的场景，查询操作相对较少；
1.2.3 栈
- 栈（Stack）：是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出从栈顶放入元素的操作叫入栈（压栈），取出元素叫出栈（弹栈）。
入栈操作：
出栈操作：
栈的特点：先进后出，Java中的栈内存就是一个栈的数据结构，先调用的方法要等到后调用的方法结束才会弹栈（出栈）；
Tips：
1）数组实现的栈：https://www.cs.usfca.edu/~galles/visualization/StackArray.html
2）链表实现的栈：https://www.cs.usfca.edu/~galles/visualization/StackLL.html
1.2.4 队列
- 队列（Queue）：队列与栈一样，也是一种线性表，其限制是仅允许在队列的一端进行插入，而在表的另一端进行删除。队列的特点是先进先出，从一端放入元素的操作称为入队，取出元素为出队；
队列的特点：先进先出；
Tips：
1）数组实现的队列：https://www.cs.usfca.edu/~galles/visualization/QueueArray.html
2）链表实现的队列：https://www.cs.usfca.edu/~galles/visualization/QueueLL.html
1.2.5 树
树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
1）每个节点有0个或多个子节点；
2）没有父节点的节点称为根节点；
3）每一个非根节点有且只有一个父节点；
4）每个子节点可以分为多个不相交的子树；
5）右子树永远比左子树大，读取顺序从左到右；
树的分类有非常多种，平衡二叉树（AVL）、红黑树RBL（R-B Tree）、B树（B-Tree）、B+树（B+Tree）等，但最早都是由二叉树演变过去的；
二叉树的特点：每个结点最多有两颗子树
Tips：
1）二叉树：https://www.cs.usfca.edu/~galles/visualization/BST.html
2）平衡二叉树：https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
3）红黑树：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
4）B-Tree：https://www.cs.usfca.edu/~galles/visualization/BTree.html
5）B+Tree：https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
1.2.6 堆
堆（Heap）：堆可以看做是一颗用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。
堆分为两种：大根堆和小根堆，两者的差别在于节点的排序方式。
- 大根堆：父节点的值比每一个子节点的值都要大。
- 小根堆：父节点的值比每一个子节点的值都要小。
这就是所谓的“堆属性”，并且这个属性对堆中的每一个节点都成立。
根据这一属性，那么最大堆总是将其中的最大值存放在树的根节点。而对于最小堆，根节点中的元素总是树中的最小值。堆属性非常有用，因为堆常常被当做优先队列使用，因为可以快速地访问到“最重要”的元素。
Tips：堆的根节点中存放的是最大（大根堆）或者最小（小根堆）元素，但是其他节点的排序顺序是未知的。例如，在一个最大堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。
大小根堆数据结构图：
因为堆有序的特点，因此我们可以使用堆的属性来做数组中的排序，简称为堆排序（Heap Sort）。
常见的堆有二叉堆、斐波那契堆等。
小根堆：Heap Visualization
1.2.7 散列表
- 散列表（Hash），也叫哈希表，是根据键和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到散列表中的一个位置，这样就可以很快找到集合中的对应元素。它利用数组支持按照下标访问的特性，所以散列表其实是数组的一种扩展，由数组演化而来。
散列表首先需要根据key来计算数据存储的位置，也就是数组索引的下标；
- HashValue=hash(key)
散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字（hash值），然后就将hash值对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。
在散列表中，左边是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
散列表：Open Hashing Visualization
1.2.8 图
- 图（Graph）：图是一系列顶点（元素）的集合，这些顶点通过一系列边连接起来组成图这种数据结构。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
图分为有向图和无向图：
- 有向图：边不仅连接两个顶点，并且具有方向；
- 无向图：边仅仅连接两个顶点，没有其他含义；
例如，我们可以把图这种数据结构看做是一张地图：
地图中的城市我们看做是顶点，高铁线路看做是边；很显然，我们的地图是一种无向图，以长沙到上海为例，经过的城市有长沙、南昌、杭州、上海等地；那么从上海也可以按照原有的路线进行返回；
实现了图这种数据结构之后我们可以在此数据结构上做一些复杂的算法计算，如广度优先搜索算法、深度优先搜索算法等；
- 广度搜索：搜索到一个顶点时，先将此顶点的所有子顶点全部搜索完毕，再进行下一个子顶点的子顶点搜索；
例如上图：以武汉为例进行广度搜索，
- 深度搜索：搜索到一个顶点时，先将此顶点某个子顶点搜索到底部（子顶点的子顶点的子顶点…），然后回到上一级，继续搜索第二个子顶点一直搜索到底部；
例如上图：以武汉为例进行深度搜索，
Tips：
- 1）广度搜索：Breadth-First Search
- 2）深度搜索：Depth-First Search Visualization
图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构。我们本次了解到这里即可；
)
)
】)
