常见数据结构原理及算法思想

yoyo 6/6/2021 数据结构算法思想

# 1. 数据结构

# 1.1 概述

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。本文将介绍以下八个常见的数据结构。

# 1.2 研究内容

数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。一般有以下几种常用运算：

检索：检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
插入：往数据结构中增加新的节点。
删除：把指定的结点从数据结构中去掉。
更新：改变指定节点的一个或多个字段的值。
排序：把节点按某种指定的顺序重新排列。例如递增或递减。

# 2. 常用数据结构

# 2.1 数组

数组是一种线性结构，而且在物理内存中也占据着一块连续空间。

优点：访问数据简单。
缺点：添加和删除数据比较耗时间。
使用场景：频繁查询，对存储空间要求不大，很少增加和删除的情况。

数据访问：由于数据是存储在连续空间内，所以每个数据的内存地址都是通过数据小标算出，所以可以直接访问目标数据（这叫做“随机访问”）。比如下方，可以直接使用a[2]访问Red。

数组-数据访问

数据添加：数据添加需要移动其他数据。首先增加足够的空间，然后把已有的数据一个个移开。

数据删除：反过来，如果想要输出数据Green，也是一样挨个把数据往反方向移动。

# 2.2 链表

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域（内存空间），另一个是指向下一个结点地址的指针域。

优点：数据添加和删除方便
缺点：访问比较耗费时间
适用场景：数据量较小，需要频繁增加，删除操作的场景

数组和链表数据结构对比列表如下：

	访问	添加	删除
链表	慢	快	快
数组	快	慢	慢

数据访问：因为数据都是分散存储的，所以想要访问数据，只能从第一个数据开始，顺着指针的指向逐一往下访问。

数据添加：将Blue的指针指向的位置变成Green，然后再把Green的指针指向Yellow。

数据删除：只要改变指针的指向就可以了，比如删除Yellow，只需把Green指针指向的位置从Yellow编程Red即可。虽然Yellow本身还存储在内存中，但是不管从哪里都无法访问这个数据，所以也就没有特意去删除它的必要了。今后需要用到Yellow所在的存储空间时，只要用新数据覆盖掉就可以了。

# 2.3 栈

栈也是一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数据。从栈顶放入元素的操作叫入栈，取出元素叫出栈。

特点：后进先出（Last In First Out，简称LIFO）

# 2.4 队列

队列中的添加和删除数据的操作分别是在两端进行的。队列可以在一端添加元素，在另一端取出元素。

特点：先进先出（First In First Out，简称FIFO）

[1] 数据入队：队列的插入操作，叫做入队。它是将数据元素从队尾进行插入的过程。

[2] 数据出队：队列的删除操作，叫做出队。它是将队首元素进行删除的过程

[3] 清空队列：队列的清空操作，就是一直出队，直到队列为空的过程，当队首和队尾重合时，就代表队尾为空了。

[4] 获取队首数据：对于一个队列来说只能获取队首数据。

[5] 获取队列元素个数：队列元素个数一般用一个额外变量存储，入队时加一，出队时减一。这样获取队列元素的时候就不需要遍历整个队列。

[6] 队列的判空：当队列元素个数为零时，就是一个空队，空队不允许出队操作。

# 2.5 树

它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；

在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。二叉树是树的特殊一种，具有如下特点：

每个结点最多有两颗子结点。
左子树和右子树是有顺序的，次序不能颠倒。
即使某结点只有一个子树，也要区分左右子树。

二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。

二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构在二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如MySQL的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树，这些二叉树的功能强大，但算法上比较复杂。

# 2.6 堆

堆是一种图的树形结构，被用于实现“优先队列”。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点”，数据就存储在这些结点中。

标准定义上，我们认为一颗树满足以下的两点，就是一个堆。

一颗完全二叉树
每个节点的值大于等于（或小于等于）其子树中每个节点的值

根据子节点与父节点值的大小关系，可以把堆分为：

最大堆：任意父节点都比其子节点的值要大
最小堆：任意父节点都比其子节点的值要小

比如下图中， 1、2 为最大堆，3 是最小堆，4 不是堆。

堆的判定

树的存储方式一般有链式存储和线性存储，分别对应我们常见的链表和数组两种方式，对于完全二叉树而言，用数组来存储是非常节省存储空间的，因为不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点，所以堆我们一般也用数组来存储。

使用数组实现堆

[1] 堆的插入：往堆中插入一个元素后，为了保持堆的特性，我们需要对插入元素的位置进行调整，这个过程叫做堆化（heapify），以最大堆为例：

堆化的过程其实非常简单，比如上图中我们往最大堆中插入一个元素 “22”，为了保持堆的特性，只需要顺着节点所在的路径，向上与其父节点进行对比交换，直到满足大小关系即可。

堆的插入-2

[2] 堆的删除：先删除叶子节点（最后一个元素），把它放到堆顶（与堆顶元素交换），然后从上往下进行堆化。

堆的删除

# 2.7 散列表

散列表（Hash Table），也叫哈希表，是实现字典操作的一种有效数据结构。用的是数组支持按照下标随机访数据的时候，时间复杂度为O(1)特性，所以散列表其实就是数组的一种扩展，由数组演化而来。

我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中，对应下标的位置；当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

散列表

# 2.8 图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。按照顶点指向的方向可分为无向图和有向图。

邻接矩阵是图的常用存储表示，它的底层依赖一个二维数组。它用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

优点是邻接矩阵的存储方式简单直接，可以高效的获取两个顶点的关系，计算方便（如：求解最短路径 Floyd-Warshall 算法），缺点是比较浪费存储空间。

# 3. 算法思想

# 3.1 递推法

递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

# 3.2 递归法

程序调用自身的编程技巧称为递归。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

注意：递归就是在过程或函数里调用自身。在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

# 3.3 穷举法

穷举法，或称为暴力破解法，其基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解。它也常用于对于密码的破译，即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码组合的范围。

# 3.4 贪心算法

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。

贪婪算法是一种改进了的分级处理方法，其核心是根据题意选取一种量度标准，然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量，如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。

对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。

# 3.5 分治法

分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法所能解决的问题一般具有以下几个特征：

该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

# 3.6 动态规划法

动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。

# 3.7 迭代法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法，即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令进行重复执行，在每次执行这组指令时，都从变量的原值推出它的一个新值。

# 3.8 分支界限法

分支界限法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支，这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限，因此这种算法一般可以求得最优解。

与贪心算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法效率更高。

# 3.9 回溯法

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

其基本思想是，在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。