Skip to content

Latest commit

 

History

History
412 lines (274 loc) · 21.3 KB

数据结构.md

File metadata and controls

412 lines (274 loc) · 21.3 KB
Raw

数据结构

结构，简单的理解就是关系，比如分子结构，就是说组成分子的原子之间的排列方式。严格点说，结构是指各个组成部分相互搭配和排列的方式。在现实世界中， 不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。那数据结构是什么？

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

在计算机中，数据元素并不是孤立、杂乱无序的，而是具有内在联系的数据集合。数据元素之间存在的一种或多种特定关系，也就是数据的组织形式。

按照视点的不同，我们把数据结构分为逻辑结构和物理结构。

逻辑结构

逻辑结构：是指数据对象中数据元素之间的相互关系。其实这也是我们今后最需要关注的问题。逻辑结构分为以下四种：

  • 集合结构 集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。各个数据元素是“平等”的，它们的共同属性是"同属于一个集合"。 数据结构中的集合关系就类似于数学中的集合
  • 线性结构 线性结构：线性结构中的数据元素之间是一对一的关系
  • 树形结构 树形结构：树形结构中的数据元素之间存在一种一对多的层次关系
  • 图形结构 图形结构：图形结构的数据元素是多对多的关系

物理结构

物理结构(也称为存储结构)：是指数据的逻辑结构在计算机中的存储形式。

  • 顺序存储结构 顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的 这种存储结构其实很简单，说白了，就是排队占位。大家都按顺序排好，每个人占一小段空间，大家谁也别插谁的队。数组就是这 样的顺序存储结构。当你告诉计算机，你要建立一个有9个整型数据的数组时，计算机就在内存中找了片空地，按照一个整型所占位置的大小乘以9，开辟一段 连续的空间，于是第一个数组数据就放在第一个位置，第二个数据放在第二个，这样依次摆放。
  • 链式存储结构 链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系，因此 需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置

常见的数据结构:

  • 数组(Array)
  • 栈(Stack)
  • 队列(Queue)
  • 链表(LinkedList)
  • 树(Tree)
  • 哈希表(Hash)
  • 堆(Heap)
  • 图(Graph)

线性表

零个或多个数据元素的有限序列。除第一个元素外，每一个元素有且只有一个直接前驱元素，除了最后一个元素外，每一个元素有且只有一个直接后继元素。 数据元素之间的关系是一对一的关系。

  • 序列 也就是说元素之间是有顺序的。
  • 有限 元素的个数是有限的。

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)； 而插入或删除时，时间复杂度都是O(n)。 这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。当然，它的优缺点还不止这些。

由于线性表的顺序存储结构在插入和删除的时候需要移动大量元素，为了解决这个问题，有了线性表的链式存储结构。 又分为单链表和多链表。

数组(Array)

数组是一种大小固定的数据结构，对线性表的所有操作都可以通过数组来实现。数组是在内存中开辟一段连续的空间，并在此空间存放元素。就像是一排出租屋， 有100个房间，从001到100每个房间都有固定编号，通过编号就可以快速找到租房子的人。虽然数组一旦创建之后，它的大小就无法改变了，但是当数组不能再存储 线性表中的新元素时，我们可以创建一个新的大的数组来替换当前数组。这样就可以使用数组实现动态的数据结构。

int[] arr = new int[10];

数组是最常用的数据结构了。这里就不说了。

优点:

  • 可以通过下标来访问或者修改元素，比较高效

缺点:

  • 增删慢，插入和删除的花费开销比较大，比如当在第一个位置前插入一个元素，那么首先要把所有的元素往后移动一个位置
  • 大小固定，只能存储单一元素

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，链表比较方便插入和删除操作。

用一组地址任意的存储单元存放线性表中的数据元素。以元素(数据元素的映象)+指针(指示后继元素存储位置) = 结点。 以“结点的序列”表示线性表,称作线性链表（单链表）。单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。

链表的结点结构:

         ┌──┬──┐──┐
         │data│next│
         └──┴──┘──┘

data域:存放结点值的数据域 next域:存放结点的直接后继的地址（位置）的指针域（链域）。

链表又分为很多种：静态链表、循环链表、单链表、双向链表

注意:

  • 链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
  • 每个结点只有一个链域的链表称为单链表(Single Linked List)

所谓的链表就好像火车车厢一样，从火车头开始，每一节车厢之后都连着后一节车厢。

单链表插入和删除算法，它们其实都是由两部分组成： 第一部分就是遍历查找第i个元素； 第二部分就是插入和删除元素。 从整个算法来说，我们很容易推导出：它们的时间复杂度都是O(n)。 如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。 但如果，我们希望从第i个位置，插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n－i个元素，每次都是O(n)。 而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是O(1)。 显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

优点:

  • 和数组相比，链表的优势在于长度不受限制，也不需要连续的内存空间。
  • 在进行插入和删除操作时，不需要移动数据项，故尽管某些操作的时间复杂度与数组相同，实际效率上还是比数组要高很多,所以插入快，删除快

缺点:

  • 劣势在于随机访问，无法像数组那样直接通过下标找到特定的数据项
  • 查找慢
  • 相对数组只存储元素，链表的元素还要存储其他元素地址，内存开销相对增大

栈(Stack)

栈是限定仅在表尾进行插入和删除操作的线性表。 我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。

The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top. When a stack is first created, it contains no items.

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫作栈顶，数据称为压栈，移除数据称为弹栈(就像子弹弹夹装弹和取弹一样)。 对栈的基本操作有push(进栈)和pop(出栈)，前者相当于插入，后者相当于删除最后一个元素。栈有时又叫作LIFO(Last In First Out)表， 即后进先出。简单暴力的理解就是吃进去吐出来

优点:

  • 提供了先进后出的存取方式

缺点:

  • 存取其他项很慢

链栈

栈的顺序存储结构，我们现在来看看栈的链式存储结构，简称为链栈。 对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是 否溢出的问题。 对比一下顺序栈与链栈，它们在时间复杂度上是一样的，均为O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题， 但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的 一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

栈的应用-递归

把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。 当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。

那么我们讲了这么多递归的内容，和栈有什么关系呢？这得从计算机系统的内部说起。前面我们已经看到递归是如何执行它的前行和退回阶段的。 递归过程退回的顺序是它前行顺序的逆序。在退回过程中，可能要执行某些动作，包括恢复在前行过程中存储起来的某些数据。这种存储某些数据， 并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符合栈这样的数据结构，因此，编译器使用栈实现递归就没什么好惊讶的了。 简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出， 用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。

队列(Queue)

队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。 队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制 的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。先进先出，简单暴力的理解就是吃进去拉出来

优点:

  • 提供了先进先出的存取方式

缺点:

  • 存取其他项很慢

链队列

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。

串

串（string）是由零个或多个字符组成的有限序列，又名叫字符串。

树(Tree)

树（Tree）是n（n≥0）个结点的有限集。n=0时称为空树。在任意一棵非空树中：

  • 有且仅有一个特定的称为根（Root）的结点；
  • 当n＞1时，其余结点可分为m（m＞0）个互不相交的有限集T1、T2、……、Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

树是由n（n>=1）个有限节点组成一个具有层次关系的集合。
它具有以下特点:每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。

树中结点的最大层次称为树的深度（Depth）。如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

二叉树

二叉树(binary tree)是一棵树，每一个节点都不能有多于两个的子节点。
通常子树被称作“左子树”和“右子树”。二叉树常被用于实现二叉查找树和二叉堆。

image

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

Image
其中data是数据域，lchild和rchild都是指针域，分别存放只想左孩子和右孩子的指针。 如果有需要，还可以再增加一个指向其双亲的指针域，那样就称之为三叉链表

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树遍历方法
  • 前序遍历 规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
  • 中序遍历 规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
  • 后序遍历 规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。
  • 层序遍历 规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

满二叉树和完全二叉树

满二叉树:除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。

完全二叉树:若设二叉树的深度为h，除第h层外，其它各层(1～(h-1))层的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

image

完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才 能优化，二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。

image

我们知道一颗基本的二叉排序树他们都需要满足一个基本性质：即树中的任何节点的值大于它的左子节点，且小于它的右子节点。

按照这个基本性质使得树的检索效率大大提高。我们知道在生成二叉排序树的过程是非常容易失衡的，最坏的情况就是一边倒（只有右/左子树）， 这样势必会导致二叉树的检索效率大大降低(O(n))，所以为了维持二叉排序树的平衡，大牛们提出了各种平衡二叉树的实现算法，在平衡二叉搜索树中， 其高度一般都良好地维持在O(log2n)，大大降低了操作的时间复杂度。如：AVL，SBT，伸展树，TREAP ，红黑树等等。

平衡二叉树

平衡二叉树必须具备如下特性：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一 个子节点，其左右子树的高度都相近。下面给出平衡二叉树的示意图：

image

红黑树

红黑树顾名思义就是结点是红色或者是黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。红黑树是一种自平衡二叉查找树，是在计算机科学中用到的 一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在Leo J. Guibas和 Robert Sedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n) 时间内做查找，插入和删除，这里的n是树中元素的数目。

对于一棵有效的红黑树而言我们必须增加如下规则，这也是红黑树最重要的5点规则:

  • 每个结点都只能是红色或者黑色中的一种。
  • 根结点是黑色的。
  • 每个叶结点（NIL节点，空节点）是黑色的。
  • 如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
  • 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结

这些约束强制了红黑树的关键性质: 从根到叶子最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。

image

黑红树节点的java表示结构:

private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root;//二叉查找树的根节点

//结点数据结构
private class Node{
    private Key key;//键
    private Value value;//值
    private Node left, right;//指向子树的链接:左子树和右子树.
    private int N;//以该节点为根的子树中的结点总数
    boolean color;//由其父结点指向它的链接的颜色也就是结点颜色.

    public Node(Key key, Value value, int N, boolean color) {
        this.key = key;
        this.value = value;
        this.N = N;
        this.color = color;
    }
}

/**
 * 获取整个二叉查找树的大小
 * @return
 */
public int size(){
    return size(root);
}
/**
 * 获取某一个结点为根结点的二叉查找树的大小
 * @param x
 * @return
 */
private int size(Node x){
    if(x == null){
        return 0;
    } else {
        return x.N;
    }
}
private boolean isRed(Node x){
    if(x == null){
        return false;
    }
    return x.color == RED;
}

哈希表(Hash)

哈希表就是一种以 键-值(key-indexed)存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。

优点:

  • 如果关键字已知则存取极快
  • 插入、查找、删除的时间级为O(1)
  • 数据项占哈希表长的一半，或者三分之二时，哈希表的性能最好。

缺点:

  • 删除慢，如果不知道关键字存取慢，对存储空间使用不充分
  • 基于数组，数组创建后难于扩展，某些哈希表被基本填满时性能下降的非常严重；
  • 没有一种简单的方法可以以任何一种顺序（如从小到大）遍历整个数据项；

堆(Heap)

这里所说的堆是数据结构中的堆，而不是内存模型中的堆。堆通常是一个可以被看做一棵树，它满足下列性质:

  • 堆中任意节点的值总是不大于(不小于)其子节点的值；
  • 堆是完全二叉树
  • 常常用数组实现

image

二叉堆是完全二元树或者是近似完全二元树，它分为两种：最大堆和最小堆。 最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

优点:

  • 插入、删除快，对最大数据项存取快

缺点:

  • 对其他数据项存取慢

图(Graph)

图是一种较线性表和树更为复杂的数据结构，在线性表中，数据元素之间仅有线性关系，在树形结构中，数据元素之间有着明显的层次关系，而在图形结构中， 节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。图的应用相当广泛，特别是近年来的迅速发展，已经渗入到诸如语言学、逻辑学、物理、 化学、电讯工程、计算机科学以及数学的其他分支中。 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V,E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

优点:

  • 对现实世界建模

缺点:

  • 有些算法慢且复杂