《图解算法》中数据结构总结
涉及到的数据结构：
1. 数组
2. 链表
3. 队列
4. 栈
5. 散列表
6. 图
7. 树
1.数组和链表的比较
-
数组
特点：
使用数组意味着所有元素在内存中都是相连的（紧靠在一起的）
结果：
在数组中添加新元素可能很麻烦，如果没有了空间，就得移到内存的其他地方，因此添加新元素的速度会很慢。
一种解决之道是“预留座位”：即便当前只有3个元素，也请计算机提供10个位置，以防需要添加新元素。缺点：浪费内存；若超过10个，还得转移。 -
链表
特点：
链表中的元素可存储在内存的任何地方，由于链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
结果：
使用链表时，根本就不需要移动元素。链表的优势在插入元素方面。
缺点：
在需要读取链表的最后一个元素时，你不能直接读取，因为你不知道它所处的地址，必须先访问元素#1，从中获取元素#2的地址，再访问元素#2并从中获取元素#3的地址，以此类推，直到访问最后一个元素。
需要同时读取所有元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低。 -
数组和链表的比较
读取：
需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素的地址，以此类推，直到访问第五个元素。
插入：
使用链表时，插入元素很简单，只需修改它前面的那个元素指向的地址。
使用数组时，则必须将后面的元素都向后移。如果没有足够的空间，可能还得将整个数组复制到其他地方。
删除：
链表也是更好的选择，因为只需修改前一个元素指向的地址即可。而使用数组时，删除元素后，必须将后面的元素都向前移。
需要指出的是，仅当能够立即访问要删除的元素时，删除操作的运行时间才为O(1)。
有两种访问方式： 随机访问和顺序访问。数组用得很多，因为它支持随机访问。顺序访问意味着从第一个元素开始逐个地读取元素，链表只能顺序访问。
2.队列与栈
-
栈
栈是一种简单的数据结构，只有两种操作： 压入（插入）和弹出（删除并读取）。 -
队列
队列类似于栈，你不能随机地访问队列中的元素。队列只支持两种操作：入队和出队。
队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构。
3.栈与调用栈
解释：
计算机在内部使用被称为调用栈的栈：每当调用函数时，计算机将函数调用涉及的所有变量的值存储到内存中；当另一个函数被调用时，会继续存放内存；计算机使用一个栈来表示这些内存块，其中第二个内存块位于第一个内存块上面；函数返回时，栈顶的内存被弹出。
递归调用栈：
存在一个递归函数：
详细分析调用fact(3)时调用栈是如何变化的：
- 函数调用时
- 函数返回时
4.散列表
使用散列函数和数组创建了一种被称为散列表（hash table）的数据结构。
-
散列函数
散列函数将输入映射到数字，对应数组的存储位置。
特点：
散列函数总是将同样的输入映射到相同的索引。
散列函数将不同的输入映射到不同的索引。
散列函数知道数组有多大，只返回有效的索引。
数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。 -
数组
存放元素值。
Python提供的散列表实现为字典，你可使用函数dict来创建散列表。
字典由键和值组成。
5.图的概述
-
图定义：
图由节点（node）和边（edge）组成。
一个节点可能与众多节点直接相连，这些节点被称为邻居。
图模拟一组连接。 -
有向图与无向图：
有向图（directed graph），其中的关系是单向的。
无向图（undirected graph）没有箭头，直接相连的节点互为邻居。 -
加权图与非加权图：
每条边都有关联数字的图，这些数字称为权重。
带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。 -
算法解决：
要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。
在python中，可使用字典实现图。
6.树
-
树：
树是一种特殊的图，其中没有往后指的边。 -
二叉查找树（binary search tree）：
对于其中的每个节点，左子节点的值都比它小，而右子节点的值都比它大。
如果你对数据库或高级数据结构感兴趣，请研究如下数据结构： B树，红黑树，堆，
伸展树。