概述

Data Structure，重点是在计算机的程序设计领域中探讨如何在计算机中组织和存储数据并进行高效率的运用。

涉及的内容包含：
数据的逻辑关系、数据的存储结构、排序算法（Algorithm）、查找或搜索等

形象的例子来理解数据结构的作用：

  • 战场：程序运行所需的软件、硬件环境
  • 敌人：项目货模块的功能需求
  • 指挥官：编写程序的程序员
  • 士兵和装备：一行一行的代码
  • 战术和策略：数据结构

总结：
简单来说数据结构就是一种程序设计优化的方法论，研究数据的逻辑结构和物理结构以及他们之间的相互关系，并对这种结构定义相应的运算。目的是加快程序的执行速度、减少内存占用的空间。

计算机的主要工作就是把数据（Data）经过某种运算处理转换为实用的信息（Information）。具体介绍一些数据结构的应用：
树形结构
树形结构是一种相当重要的非线性数据结构，广泛运用在人类社会的族谱、机关的组织结构、计算机的操作系统结构、平面绘图应用、游戏设计等方面。
最短路径
最短路径是指在众多不同的路径中距离最短或者所花费成本最少的路径。寻找最短路径最常见的应用是公共交通运输系统的规划或网络的架设，如都市公交系统、铁路运输系统、通信网络系统等。
现在很多汽车和手机都安装了GPS导航，用于定位和路况查询。其中路程的计算就是以最短路径的理论作为程序设计的依据，为旅行者提供不同的路径作为选择方案。
搜索理论
所谓“搜索引擎”，是一种自动从因特网的众多网站中查找信息，再经过一定的整理后提供给用户进行查询的系统，例如百度、谷歌、搜狗等。
注意，Search这个单词在网络上习惯上翻译为“搜索”，如搜索引擎。而在数据结构的算法描述中，习惯翻译成“查找”。在计算机科学中，“搜索”和“查找”大部分情况下可以互相转换

程序能否快速而高效的完成预定的任务，取决于是**否选对了数据结构。而程序是否能清楚而正确的把问题解决**，则取决于算法。算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体。

程序 = 数据结构+ 算法

程序能否快速而高效地完成预定的任务，取决于是否选对了数据结构，而程序是否能清楚而正确地把问题解决，则取决于算法。算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。
数据结构只是静态的描述了数据元素之间的关系。
高效的程序需要在数据结构的基础上设计和选择算法。
总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体

数据间的逻辑结构：
数据的逻辑结构指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。
逻辑结构包括：集合结构、线性结构、树形结构、图形结构。

  • 集合 : 数据元素之间只有“同属于一个集合”的关系
  • 线性关系 : 数据元素之间存在一对一的关系，对应Java中的线性表：顺序表、链表
  • 树形结构 : 数据元素之间存在一对多的关系：对应Java中的树
  • 网状结构/图状结构 : 数据元素之间存在多对多的关系：对应Java中的图

数据的存储结构：
数据的存储结构(或物理结构)指数据的逻辑结构在计算机存储空间的存放形式。
数据的存储结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。
数据元素的机内表示（映像方法）： 用二进制位（bit）的位串表示数据元素。通常称这种位串为节点（node）。当数据元素有若干个数据项组成时，位串中与个数据项对应的子位串称为数据域（data field）。因此，节点是数据元素的机内表示（或机内映像）。
关系的机内表示（映像方法）：数据元素之间的关系的机内表示可以分为顺序映像和非顺序映像，常用两种存储结构：顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像借助指示元素存储位置的指针（pointer）来表示数据元素之间的逻辑关系。

参考书籍： 数据结构与算法分析 Java语言描述 大话数据结构

真实结构

线性表之顺序表/静态数据结构：数组Array，ArrayList

特点

  1. 使用连续分配的内存空间
  2. 一次申请一大段连续的空间，需要事先声明最大可能要占用的固定内存空间

优点

设计简单，读取与修改表中任意一个元素的时间都是固定的

意味着 : 查找需要的时间为数据结构概述 - 图1 , 插入和删除需要的时间为数据结构概述 - 图2

缺点

  1. 容易造成内存的浪费
  2. 删除或插入数据需要移动大量的数据

存储思路

  1. 所有数据存储在这个连续的空间中
  2. 数组中的每一个元素都是一个具体的数据：所有数据紧密排布，不能有间隔

操作

读内存

查：每个元素都有一个数值下标，可以通过下标瞬间定位到某个元素 ( 复杂度数据结构概述 - 图3)

写内存

增：从头部/中间/尾部插入。 ( 复杂度数据结构概述 - 图4 )

注意：插入元素，引起部分元素后移，代价非常高

删：删除某一元素 , 后面的元素往前移一位 (从后往前) ( 复杂度数据结构概述 - 图5 )

注意：去掉元素，引起部分元素后移，代价非常高

改：修改某一元素 , 找到对应位置直接修改 ( 复杂度数据结构概述 - 图6 )

注意：只需要修改对应位置的元素的内容，不需要申请或者删除

适用范围

  1. 查询操作远多于插入/删除操作的场景

  2. 简单抽象数据结构的基石

    线性表之链表/动态数据结构 : Linked List

    特点

  3. 使用不连续的内存空间

  4. 不需要提前声明好指定大小的内存空间。一次申请一小块内存，按需申请

优点

  1. 充分节省内存空间
  2. 数据的插入和删除方便，不需要移动大量数据

缺点

  1. 设计此数据结构较为麻烦
  2. 查找数据必须按顺序找到该数据为止，麻烦

操作

  1. 查找 : 从头开始遍历直到找到对应元素 , 复杂度数据结构概述 - 图7。节点是没有下标的，只能从链表的表头开始查找某个节点
  2. 插入 : 新建一个值和指针 , 令此新建的指针指到 i+1 的值 , 然后令 i-1 的指针指到新建的值 , 复杂度数据结构概述 - 图8
    1. 申请一小块内存——结点
    2. 插入到链中
      1. 从头部插入
      2. 从尾部插入
      3. 从中间插入
  3. 删除 : 同插入
    1. 从链中剥离结点
    2. 释放这个结点的内存

  4. 更改 : 同删除

    1. 改变这个结点中所存储的值

      适用范围

  5. 插入/删除操作远多于查询操作的场景

  6. 复杂抽象数据结构的基石

存储思路

  1. 每一个小数据单独存在一小块内存中，这个单元被称为结点 (node)
  2. 每一小块内存知道下一小块的地址 (指针实现)
  3. 多个不连续的小内存空间组成，通过内存地址引用形成一个链的结构
  4. 获得表头就可以找到链表中的所有元素

实现结构：链表

单向链表

image.png

环形链表

image.png

双向链表

image.png

抽象结构ADT

栈Stack

图示

image.png

名词

栈顶：插入、删除的这一段为栈顶
栈底：相对于栈顶的另一端
空栈：当表中没有元素时称为空栈

特点

继承于java.util.Vector
后进先出

实现结构

顺序表实现栈

用数组实现
优点：算法简单
缺点：数组大小只能实现规划声明好，太大了浪费空间，太小了不够用

链表实现栈

优点：随时可动态改变链表长度，有效利用内存空间
缺点：算法设计复杂

基本运算

进栈（压栈、入栈）： push(ele);
出栈： pop();
查看栈顶元素： peek();
清栈： clear();
大小：size();
判断是否是空：empty();
查找元素出现的位置：search(Object obj);

使用场景

  1. 二叉树和森林的遍历
  2. CPU的中断处理
  3. 图形的深度优先查找法(DFS)
  4. 递归调用：斐波那契数列；汉诺塔问题
  5. 子程序的调用

    队列Queue

    队列是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表

队列的修改原则：
队列的修改是依照先进先出的原则进行的。新来的成员总是加入队尾（即不允许加塞），每次离开的成员总是队列头上的（不允许中途离队），即当前最老的成员离队

图示

image.png

名词

队头(front)：允许删除的一段称为队头
队尾(rear)：允许添加的一端成为队尾
空队列：当队列中没有元素时成为空队列

特点

先进先出
典型实现：PriorityQueue

实现结构

顺序表实现队列

用数组实现
优点：算法简单
缺点：数组大小固定，无法根据队列实际需要动态申请

链表实现队列

优点：随时可动态改变链表长度，有效利用内存空间
缺点：算法设计复杂

操作

加入元素到队列尾部： add(Object obj); offer(Object obj);
获取队列头部元素，不删除该元素： element(); peek();
获取队列头部元素，并删除该元素： remove(); poll();
清理队列： clear();
得到队列的大小： size();
判断队列是否为空： isEmpty();

使用场景

图形的广度优先查找法（BFS）
可用于计算机各种事件处理的模拟：如：事件队列，消息队列
CPU的作业调度

变形的队列

环形队列
image.png
双向队列
image.png
优先队列
image.png

树Tree

计算机世界的树

image.png

专有名词

结点：树中的元素都称之为结点
根结点：最上面的结点称之为根，一棵树只有一个根，且由根发展而来，从另外一个角度来说，每个根节点都可以认为是其子树的根
父节点：结点的上层结点。如上图，结点K的父节点是E；结点L的父节点是G
子节点：结点的下层结点。如上图，结点E的子节点是K；结点G的子节点是L
兄弟结点：具有相同父节点的结点成为兄弟结点。如上图，F、G、H互为兄弟结点
结点的度数：每个结点所拥有的子树的个数称为结点的度。如上图，结点B的度为3
树叶：度数为0的结点，也叫做终端节点。如上图，D、K、F、L、H、I、J都是树叶
非终端节点（或分支节点）：树叶以外的结点，或度数不为0的结点。如上图，根、A、B、C、E、G
树的深度（或高度）：树中结点的最大层次数。如上图树的深度为4
结点的层数：从根节点到树中某结点所经的路径上的分支树称为该节点的层数，根节点的层数规定为1，其余结点的层数等于其父亲结点的层数+1
同代：在同一棵树中具有相同层数的结点。

二叉树BinaryTree

图示

image.png
image.png

分类

image.png

功能

增删改查

搜索

广度优先搜索

深度优先搜索
  1. 前序遍历：树根 - 左子树 - 右子树
  2. 中序遍历：左子树 - 树根 - 右子树
  3. 后序遍历：左子树 - 右子树 - 树根

    特例

    排序二叉树：
    满足一些条件的二叉树，才被称为排序二叉树。比如：若它的左子树不为空，左子树上的所有节点
    值均小于根节点值；若右子树不为空，右子树上的所有节点值均大于根节点值
    特点：可以非常方便的对树中的所有结点进行排序和检索
    红黑树
    红黑树顾名思义就是结点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡

对于一棵有效的红黑树而言我们必须增加如下规则：

  1. 每个结点都只能是红色或者黑色
  2. 根节点是黑色
  3. 每片叶子都是黑色的
  4. 如果一个结点是红色的，则它的两个子节点都是黑色的，也就是说在一条路径上不能出现相邻的两个红色结点
  5. 从任意一个结点到其每个叶子的所有路径都包含着相同数目的黑色结点

这些约束强制了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果就是这棵树大致上是平衡的，因为插入、删除和查找某个值得最坏情况时间都要求与树的高度成比例，这个高度理论上限允许红黑树只在最坏情况下都是高效的。
TreeSet和TreeMap就是红黑树的典型实现

http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html

使用场景

哈夫曼树

一种带权路径最短的二叉树，在信息检索中很常用

哈夫曼编码

假设需要对一个字符串如“abcdabcaba”进行编码，将它转换为唯一的二进制码，同时要求转换出来的二进制码的长度最小。我们采用哈夫曼树来解决报文编码问题。

  1. 哈夫曼编码：在数据通信中，需要将传送的文字转换成二进制的字符串，现要求为这些字母设计编码。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下，于是频率小编码长，频率高编码短，这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。
  2. 哈夫曼译码：在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。
    B+树

    图

    定义

    由顶点和边所组成的集合

    分类

    有向图

    无向图

    图的表示法

    邻接矩阵发

    邻接表法

    邻接复合链表发

    索引表格法

    图的遍历

    深度优先遍历

    广度优先遍历

    应用场景

    最短路径搜索

    拓扑排序

    其他

    散列表Hash

    堆Heap

数据结构

线性表

顺序表

动态数组

链表

单向链表
双向链表
循环链表
静态链表

栈

顺序栈
链栈

队列

顺序队列
双端队列
循环队列

树

二叉树

二叉树概念

满二叉树
完全二叉树
非完全二叉树

二叉树种类

二叉排序树
二叉平衡树
红黑树
哈夫曼树

遍历方式

前序遍历(递归/非递归)
中序遍历(递归/非递归)
后序遍历(递归/非递归)
层次遍历(使用一个队列)

树

存储方式

图形表示法
广义表表示法
左孩子右兄弟表示法

遍历方式

前序遍历(递归/非递归)
中序遍历(递归/非递归)
后序遍历(递归/非递归)
层次遍历(使用一个队列)

森林

由一棵或者多棵树构成，存储方式和遍历方式同树

图

存储方式

邻接矩阵
邻接表
十字链表

遍历方式

广度优先遍历(BFS)

基本思想：首先访问顶点，再访问顶点的全部未访问的邻结点，再访问邻结点的所有结点。(类似树的层次遍历)

深度优先遍历(DFS)

基本思想：首先访问顶点，再访问顶点的每个邻结点，从该点继续深度优先遍历(类似于树的前序遍历)

特殊应用

最小生成树

普利姆(Prim)算法

选一个顶点开始，查找与顶点相邻且代价(边值)最小的边的另一个顶点，直到最后。

克鲁斯卡尔(Kruskal)算法

选择途中最小的边，直到所有结点都连通

算法对比

普利姆算法更加注重的是结点，点与点之间距离最短的优先；
克鲁斯卡尔算法更加注重的是边，将边排序，最小边排在前面，最大边排在后面

算法

排序

内部排序(只使用内存)

插入排序：直接插入排序，希尔排序
选择排序：简单选择排序，堆排序
交换排序：冒泡排序，快速排序
归并排序
基数排序

外部排序(内存和外存结合使用)

复杂度

类别 排序方法 时间复杂度 空间复杂度 稳定性
平均情况 最好情况 最坏情况 辅助存储
插入排序 直接插入 O(n2) O(n) O(n2) O(1) 稳定
shell排序 O(n1.3) O(n) O(n2) O(1) 不稳定
选择排序 直接选择 O(n2) O(n2) O(n2) O(1) 不稳定
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定
交换排序 冒泡排序 O(n2) O(n) O(n2) O(1) 稳定
快速排序 O(nlog2n) O(nlog2n) O(n2) O(nlog2n) 不稳定
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定
基数排序 O(d(r+n)) O(d(n+rd)) O(d(r+n)) O(d(n+rd)) 稳定
注：基数排序的复杂度中，r代表关键字的技术，d代表长度，n代表关键字的个数

查找

静态查找表

顺序查找

基本原理：从表一端开始逐个和关键字进行比较，若找到一个记录和给定值相等，则查找成功，反之失败。再简单点就是一个一个的比大小，看看是否相等

折半查找(二分查找)

  1. 把序列分成左中右三部分，做部分小于中间值，有部分大于中间值
  2. 把给定值与中间值比较，确定下次查找是在左部分还是右部分

  3. 继续上面两步操作，知道成功或失败

    分块查找

    基本原理：顺序查找和二分查找的折中。先分块，在块中顺序查找

    动态查找表

    二叉排序树(BST)/二叉查找树

  4. 若他的左子树非空，则左子树上所有的结点的值均小于根节点的值

  5. 若他的右子树非空，则右子树上所有的结点的值均大于根节点的值

  6. 左右子树就是两棵二叉排序树

    平衡二叉树(AVL)

  7. 他或者是一颗空树

  8. 或者树中任一结点的左右子树深度相差不超过1

    红黑树(RB-Tree)

    是平衡二叉树的一种改进版本

    B_树

    B树
    二叉树，每个节点只存储一个关键字，等于则命中，小于走左节点，大于走右节点
    B-树
    多路搜索树，每个节点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子节点
    B+树
    在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现。非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中
    B*树
    在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3