数据结构的知识点

温故而知新，每次复习都会有新的收获。

总体

数据结构包括三部分：

1. 逻辑结构

2. 存储结构

3. 数据的操作

逻辑结构指的是脱离计算机，人类对数据之间的逻辑的理解。比如，10月1号和10月2号，他俩存在先后的逻辑关系。逻辑结构主要分两大类：线性和非线性。

存储结构又称物理结构，数据的逻辑结构在计算机存储空间中的存放形式成为数据的存储结构。

包括四种基本的存储映射方法：

1. 顺序映射：数组 2. 链式映射：LinkedList 3. 索引映射，会建立一个索引表，不知道哪些数据结构用了这种映射 4. 散列映射：HashMap、HashSet

栈

以前对栈的理解仅限于知道，而且每次看到这个字都会想起青岛的栈桥，但两者没什么联系。

栈的定义：仅能在表尾进行插入和删除的线性表。

栈顶：允许插入删除的一端。

因为只能在一端进行操作，后进先出，栈具有记忆的特性，对有执行顺序的数据一般用栈来表示。

队列

与之相对的就是队列了。 队列的定义：限定了插入和删除的线性表，只允许在一端插入（队尾 rear），在另一端删除（对头 front）。

队列就像排队一样，先进先出。

线性单链表

就是链式映射的表，每个元素都包含值和下一个元素的地址，这种链表要得到其中一个元素必须从开头开始找，因此，单链表是非随机存储结构。

什么是随机存储结构，就是说访问数据的任意一个元素，所用的时间都是相同的，与位置无关，我们的随机存储器RAM就是这样的。

双向链表

就是每个元素含有值和它前后两个元素的地址。

树

树的定义：以分支关系定义的层次结构。

度：结点（书上写的不是节点，是结点）拥有的子树数为该结点的度。

树的度：这棵树中各结点的度的最大值。

层次：结点的层次从根开始算起，根节点的层次为第一层。

深度：树的最大层次为深度。

二叉树

• 满二叉树：理论上讲，深度为k的树有2^k-1个结点；通俗点讲，就是一个树全满了。
• 完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。

二叉树有很多有用的性质：

1. 在二叉树的第i层，最多有结点数 2^i-1;

2. 深度为k的二叉树，最多有2^k-1;

3. 任意一颗二叉树，若终端结点数（并非是度为0的结点，只是在末尾的结点）有n₁,度为2的结点有n₂,那么n₁ = n₂ + 1;

二叉树的三种遍历

1. 先序遍历（根左右）

2. 中序遍历（左根右）

3. 后序遍历（左右根）

面试时是要掌握通过其他两个求另一个。可以看一下这个教程http://www.cr173.com/html/18891_1.html