4.dataStructure数据结构

4.dataStructure数据结构

[TOC]

一 概述

数据结构及其应用的笔记

1 简介

什么是数据结构：它是计算机组织数据的方式，它不是孤立的，它还跟数据的操作有关。

3 常识

3.1 顺序访问和随机访问、数组和链表的简单比较

顺序访问意味着从第一个元素开始逐个地读取元素，比如链表只能顺序访问：要读取链表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。随机访问意味着可直接跳到第十个元素。经常说数组的读取速度更快，这是因为它们支持随机访问。很多情况都要求能够随机访问，因此数组用得很多。

所以说当写入操作多读取操作少时选择链表存储，写入操作少读取操作多时选择数组存储，链表擅长插入和删除，而数组擅长随机访问.其实直接就插入删除的执行函数来看的话，链表和数组在只知道下标的情况下，其时间复杂度都是O（n），性能上是不会有太大差别的。因为数组不需要遍历，能直接取得要操作的对象，但是需要移动其后的所有项，而链表无法直接获取要操作的对象，需要遍历获取，之后直接删除或者插入，而不需要移动其他项。之所以说链表的插入和删除比数组的性能好，并不是说在任何情况下链表的插入和删除效率都要比数组的高，而是链表插入删除的最差时间复杂度也就是O（n），而在已得到要操作的结点的引用时，它就能省去遍历的步骤直接插入删除，时间复杂度为O（1），并且数组会有比如扩容等操作造成很多额外的时间支出，以及内存碎片所导致的空间支出。倘若不考虑这些，在只有下标的情况下执行插入和删除，它们的性能其实是没有太大区别的，就时间复杂度上来看都是O(n)，然而实际情况下是不可能不考虑这些的。

顺序访问的数据是连续的。硬盘的磁头是按一定的顺序访问磁片，磁头不做频繁的寻道，这样带来的结果是速度很快。因为寻道时间是影响磁盘读写速度的主要原因。在平常的应用中顺序访问的应用很少。大文件的连续备份，是顺序读写的。linux的dd命令就是典型的顺序读写。

随机访问主要是磁头在做频繁的移动，原因是数据在磁盘的不连续性，这和数据存放到磁盘的过程有关系，随机访问的速度要比顺序访问慢很多。原因也是因为磁头频繁的寻道，定位，磁头的移动消耗掉很多时间。大部分的应用在磁盘上的读写是随机的。

4 文档和视频

1. 浙江大学的：数据结构 - 网易云课堂

三 基础

数据的逻辑结构分为线性结构和非线性结构

1. 线性结构：数据元素之间一对一的关系

2. 非线性结构

   1. 树：数据元素之间一对多的关系

   2. 图：数据元素之间存在多对多的关系

   3. 多维(>1)数组

   4. 广义表

1 线性结构（linear structure）

简单地说，线性结构是n个数据元素的有序（次序）集合。这里的次序是逻辑层次上讨论，而不考虑存储层次。

1.1 线性表（linear list）

线性表是一种典型的线性结构，它也是最基本、最简单、也是最常用的一种数据结构。其基本特点是线性表中的数据元素是有序且是有限的。在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。在实际应用中，常以栈、队列、字符串等特殊形式使用。

线性表中数据元素之间的关系是一对一的关系，即数据元素都是首尾相接的，这里首尾相接是逻辑层次上的。线性表主要由顺序表示或链式表示。

一般线性表主要由顺序表示或链式表示：

1. 顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据元素。

2. 链式表示：指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。

顺序表（sequence list）

顺序表一般视为数组，使用一组地址连续的存储单元依次存储数据元素。顺序表是在计算机内存中以数组的形式保存的线性表，物理结构为顺序存储的线性表，

特点：

1. 长度固定，必须在内存分配之前确定数组长度；

2. 存储空间连续，即允许随机访问任意元素；

3. 数据存储密集，即在内存中存储的全部是数据；

4. 要访问特定元素，使用元素索引（时间复杂度为O(1)）；

5. 要插入或删除特定元素，需要移动该位置之后的所有元素：所以时间复杂度为O(n)

链表（linked list）

链表是物理结构为随机存储的线性表，逻辑上还是连续的。链表中的每个结点都有一个“指向下一个结点的指针”(双向链表还有指向上一个节点的指针)，相比顺序表，链表需要更多的空间来存放指针，所以每个节点会消耗更多内存。根据指针的数量和指向，可以分为“单链表”、“双链表”、“循环链表”。按照优化过的实现方式还可以分为：静态链表、块状链表、跳跃链表等。

特点：

1. 长度不固定，可以任意增删；

2. 存储空间不连续，以单链表为例每个元素只能访问相邻的一个元素；

3. 数据存储密度小，降低了整体的关联性；

4. 要访问特定元素，必须从表头开始遍历所有元素（时间复杂度为O(n)）。因为只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。

5. 要插入或删除特定元素，不涉及其它元素的变动：

   1. 如果只知道下标时，TC是O(n)，因为需要遍历其前面所有项以得到下标对应的项

      1. 头插 -> 效率比较高；

      2. 尾插 -> 效率相对来说比较低，(因为的一个一个的查找最后一个结点)。

         1. 解决尾插效率低的方案：以空间换时间(待整理)

   2. 如果拥有要操作项的引用，则TC是O(1)，因为无需遍历。

在实际操作中，链表由于要频繁的分配小块内存而分配内存是要耗时的(频繁的插入、删除操作依然会导致内存申请和释放，容易造成内存碎片和触发垃圾回收)，所以真正运行起来往往链表不是那么优秀。

分类：

1. 双向链表

2. 多重链表：多重链表的指针域会有多个，比如包含next和sublist。但包含两个指针域的链表不一定是多重链表，比如双向链表。多重链表用途广泛，比如树、图这种相对复杂的数据结构可以采用多重链表实现。

   1. 十字链表

1.2 栈（Stack）

栈（stack）是一种只允许在一端进行插入或删除操作的线性表。 一般是在栈顶进行插入，删除操作。因此访问元素的顺序是先进后出。 它可以用顺序表或者链表实现。

使用场景：

1. 进制转换

2. 括号匹配的检验

3. 行编辑程序

4. 迷宫求解：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。

5. 表达式求解：前缀、中缀、后缀。

   1. 操作数之间的相对次序不变;

   2. 运算符的相对次序不同;

   3. 中缀式丢失了括弧信息，致使运算的次序不确定

   4. 前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式

   5. 后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。

6. 实现递归：多个函数嵌套调用的规则是：后调用先返回。

7. 浏览器历史纪录，Android中的最近任务，Activity的启动模式，CPU中栈的实现，Word自动保存，解析计算式，解析xml/json。解析XML时，需要校验节点是否闭合，节点闭合的话，有头尾符号相对应，遇到头符号将其放入栈中，遇到尾符号时，弹出栈的内容，看是否有与之对应的头符号，栈的特性刚好符合符号匹配的就近原则。

8. 深度优先搜索

9. 回溯算法

   1. 走迷宫

顺序栈

链栈

共享栈

1.3 队列（Queue）

队列（Queue）简称队，是受限的线性表，只能在线性表的一端进行插入，另一端进行删除。 一般是在队尾进行插入操作，队头进行删除操作。因此访问时的顺序是先进先出。

简单分类：

1. 堆：是特殊的队列，“优先队列”，最好的实现是完全二叉树。

2. 双端队列

散列表(也称哈希表,Hash Table)

散列表也被称为散列映射、映射、字典和关联数组，本质就是 K-V 结构，V可以是链表、数组、数组链表等形式。几乎所有的语言中都实现了散列表这一数据结构。

了解散列表的原理我们首先必须明白一个概念--散列函数(哈希函数)：哈希表是通过关键值(key)来访问的数据结构，也就是说他通过把关键值映射到表中的一个位置来访问记录，以加快 查找速度，这个映射关系就是哈希函数，存放数据的列表叫做散列表。哈希表的构造方法有很多种，比如下面的这几种，虽然有这么多种方法，但是不同的key值可能会映射到同一散列地址上，这样就会造成哈希冲突(HASH COLLISION)/哈希碰撞。一个好的散列函数对于散列表非常重要。好的散列函数必须要讲键均匀的映射的散列表的不同位置，这样才能尽可能减小冲突，并不影响性能。

1. 构造方法

   1. 直接定址法

   2. 数字分析法

   3. 平方取中法

   4. 折叠法

   5. 除留余数法(最常用)：在哈希表中，总空间大小为m，选一个 p，p 满足两个条件：

      1. p <= m(越接近 m 越好)；

      2. p必须是质数;则哈希函数为hash(key) = kep % p; (p<=m)，p为什么一定要选质数呢？经过数学的理论推导，p 为质数时，可以保证模之后概率均等，均匀分布；p 要不是质数，则不满足随机、均匀这些条件，就不能保证每个数字均等存储。

   6. 随机数法

2. 解决冲突

   1. 开放寻址法（open addressing）:缺点是当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，需要从头到尾探测整个散列表，所以最坏情况下的时间复杂度为 O(n)

      1. 线性探测(Linear Probing)和二次探测(Quadratic probing)：两者的缺点是定位准确度不高，查找起来效率较低。

      2. 双散列法(Double hashing)：需要两个哈希函数，第一个元素直接就是记哈希表的下标，第二个记到达该数字的移位量，从而达到直接定位。

   2. 链表法(chaining)/链地址法：哈希表中存放的是指针(指向结点的指针)，在冲突处，通过指针连接起来。

   3. 除留余数法+开链法

3. 常见散列函数

   1. MD5

   2. SHA-1

优点:

1. 哈希表在对大数据的处理查找上，有明显优势。

适用：

1. 以空间换时间的查找算法

1.4 数组

1.5 串（string）

字符串（string）简称串，是由零个或多个字符组成的有穷序列。

2 树

为什么需要树：对数据的常用操作就是存取和插入/删除，而树在这些操作上效率比较高

树是递归结构。

二分查找法（前提条件是有序）

树的一些术语：

1. 节点：二叉树中每个元素都称为节点。

2. 大小：树的大小一般指数的结点数

3. 度：结点的子树的数量(子树的子树不算在内)

4. 层次：规定根节点在1层，每往下1次加1

5. 深度：所有节点中最大的层次就是这棵树的深度

6. 路径和路径长度：从一个节点到另一个节点所经过的节点就是路径，所经过的边的数量就是路径长度。

树的实现：

1. 可以用链表来实现，但是每个节点的指针域数量可能不一样，实现起来就会很困难，不够好。

   1. 可以改进一下，使用儿子-兄弟表示法。

2.1 二叉树

二叉树与树的主要区别：

1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2

2. 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分它是左子树还是右子树，而树是不区分左右的。

3. 二叉树可以为空。

待补充：线索二叉树，二叉搜索树，完全二叉树，哈弗曼树/霍夫曼树

二叉树的实现：

1. 可以用数组，但是可能造成空间浪费

2. 链表

简单分类：

1. 斜二叉树

2. 完美二叉树/满二叉树

3. 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高

二叉树的遍历，一般有四种方式，而且实现上也分递归和非递归。非递归的实现可以借助堆栈/队列实现。

1. 深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。具体说明如下

   1. 中序遍历:遍历后会按节点值升序排列。对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树

   2. 先/前序遍历:效率最高。对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。

   3. 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根

2. 广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

深度优先搜素算法和广度优先搜索算法：

1. 深度优先搜素算法：不全部保留结点，占用空间少；有回溯操作(即有入栈、出栈操作)，运行速度慢。

2. 广度优先搜索算法：保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。

3. 比较：

   1. 通常，深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。 　

   2. 广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。

二叉树的应用：

1. 求二叉树的叶子节点、高度等

2. 二元运算表达式树及其遍历

   1. 先序遍历得到前缀表达式

   2. 中->中缀...

   3. ...

3. 没有中序遍历无法唯一确定一个二叉树

4. 动态查找

完美二叉树/满二叉树

定义似乎有歧义(待整理)

完全二叉树

完全二叉树就是在第n层被填满之前，不会开始填第n+1层深度，并且是从左向右填满。

堆

当完全二叉树中任意一个节点的值总是不大于或不小于其父节点的值时，这个完全二叉树就称为堆

特点：

1. 树的深度是相同节点的二叉树中最少的，维护效率较高；

2. 任意一个节点的值总是不大于或不小于其父节点的值，这个特性非常的有用，堆常常被当做优先队列使用，因为可以快速的访问到“最重要”的元素。

3. 完全二叉树是逻辑上堆的结构，而物理上堆的结构，一般我们选择数组，数组实现堆有几个好处(也可以用普通树来模拟堆，但空间浪费比较大，不太建议这么做)：

   1. 父节点p与左右子节l，r点的关系

      1. 数组下标的关系是l = 2*p+1和r = 2*p+2。这样我们很容易去模拟它，而且在计算机中2*p这样的运算可以用一个左移1位操作来实现，十分高效。

      2. 节点值大小关系是arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]或arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]。

   2. 再加上数组可以随机存取，所以完全二叉树是效率很高的数据结构。

4. 需要注意：堆内的元素并不一定数组下标顺序来排序的，不要误认为大/小根堆中下标为1就是第一大/小，2是第二大/小...

分类：

1. 最小堆/小根堆/小顶堆：一棵完全二叉树，对于任意一个拥有父节点的子节点，其数值均不小于父节点的值，这样层层递推，就是根节点的值最小。就是所有父结点都比子结点要小。

2. 反之就是最大堆/大根堆/大顶堆

最大堆/最小堆的操作:

1. 调整堆/堆化(heapify)/堆的Extract(结合图示更好理解)：我们使用多次筛选来完成一次堆化，以调整成最大堆为例，如果根节点的值不是最大的，那么需要把根结点往下沉，让最大值往上浮。即比较根结点和左、右孩子的值，若根结点的值不小于孩子结点的值，说明根结点并没有破坏堆的性质，不用调整；若根结点的值小于左右孩子结点中的任意一个值，则根结点与孩子结点中较大的一个互换，互换之后又可能破坏了左或右子树的堆性质，于是要对子树继续进行上述调整...。这样的一次调整我们称之为一次筛选。每一次筛选的TC是O(N)，每一次筛选根结点都往下沉，所以筛选次数不会超过完全二叉树的深度：logN向下取整+1，其中n为结点个数,2为底数,所以堆化的TC为O（logN）。调整堆其实就是选择出待排序序列中的最大值/最小值。

   1. 第i次调整堆，就是先把arr中的第i大元素放到首位置arr[0]，然后arr[0]和arr[n-i]互换.这样arr[(n-i)...n]就已经有序，于是又把arr[0...n-i]看成一个堆再进行排序，如此重复。

2. 建立堆(Build Heap，create heap):给定一个乱序数组，将其调整成堆。先构建成完全二叉树，然后依然是通过筛选的方式，首选明白筛选法的前提条件是：根结点的左右子树已经是堆。所以我们在需要自下而上的调整这个完全二叉树，即从最后一个非叶子结点开始调整。TC是O(N)

3. 堆排序：有了筛选法和建堆就构成了堆排序。步骤如下:

   1. 建堆

   2. 将堆顶记录和堆中最后一个记录(n)交换

   3. 筛选法调整堆，堆中记录个数减少一个(n--)，重复第2步。整个过程中堆是在不断的缩减。

4. 堆化(heapify):TC是O(N)

5. 插入/删除：这里的插入/删除是针对最大堆/最小堆的，即插入/删除元素A后使得堆依然为最大堆/最小堆。插入与删除的核心操作其实就是上浮(swim)与下沉(sink),叶结点只能进行上浮,非叶结点(除去根结点)则既可以上浮,也可以下沉。

   1. TC是O(N)。

二叉查找树/二叉搜索树(Binary Sort Tree)/二叉排序树(Binary Sort Tree)

它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

应用：

1. 可以用来解决动态查找的问题

操作：

1. 查找元素，可以用递归也可以用循环。一般来讲，“尾递归”都可以用循环来实现，而且循环实现的效率更高。查找的效率取决于树的高度。

   1. 二叉查找树中对于目标节点的查找过程类似与有序数组的二分查找，并且查找次数不会超过树的深度。最好的情况下，二叉查找树的查找效率为O(log n)；当二叉查找树退化为单链表时，比如，只有右子树的情况,如下图所示，此时查找效率为O(n)。所以二叉查找树越是“矮胖”，也就是每层尽可能地被“塞满”（每个父节点均有两个子节点）时，查找效率越高；为了解决二叉查找树退化为单链表时查找效率低下的问题，引入了平衡二叉树

2. 插入

3. 删除：有点复杂，使用左子树的最大值和右子树的最小值。

二叉平衡树/AVL树

已经知道一个数组二分查找的算法，可以以二叉查找树来实现，但一般该二叉查找树的效率比不上数组的二分查找。这是由于二叉查找树是不平衡的。要想缩短一个二叉搜索树的查找时间，需要将二叉查找树调整为平衡二叉树。主要优点集中在快速查找，查找的时间复杂度保证在O(logN)范围内。

特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

分类：

1. 红黑树（Red Black Tree）：红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能

2. AVL

3. 替罪羊树

4. Treap

5. 伸展树

哈夫曼树（最优二叉树）和哈弗曼编码

根节点到每个叶节点的频率乘以长度是最小的。带全路径的长度之和最小

排序二叉树

操作：

1. 遍历。三种方法:中序遍历,前序遍历,后序遍历

   1. 中序遍历:遍历后会按节点值升序排列

   2. 前序遍历:效率最高

2. 节点查找。三种:最大值,最小值和指定值

2.2 多叉树

B树(B-tree)/平衡多叉树

如果B树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销。B树的查找效率相当高，一般文件系统等都是基于B树来实现的

分类： 2. B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中； 3. B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。很多数据库的索引采用B+树实现 4. B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

3 图

4 矩阵（Matrix）

矩阵可以用二维数组来表示，但是有两个缺陷：

1. 数组的大小需要事先确认。

2. 如果是“稀疏矩阵”（很多零值的矩阵），会造成大量的存储空间浪费。

可以使用十字链表来表示。

五 经验

1. 二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。

七 未整理

1. 线索二叉树