数据结构有助于学习与理清编码逻辑、有助于理解数据库存储、查询原理、提升查询性能，有助于更好地设计功能模块的数据结构。

排序是为了快速查找，可以结合mysql的索引及查找数据原理。

重点：二叉树遍历、二叉树创建、B树、B+树、索引、查找、排序

目录

第一章 概念与术语

概念

  • 数据元素：有一定意义的基本单位。人

  • 数据项：一个数据元素可以由若干个数据项组成，不可分割的最小单位。鼻子、耳朵、眼睛…

  • 数据对象：性质相同的数据元素的集合，是数据的子集。具有相同数量和类型的数据项。

  • 数据结构：不同元素之间不是独立的，而是存在特定关系的，我们将这些成为结构。

第二章 算法

算法的特性

  • 1、输入与输出
  • 2、有穷性：算法在有限步骤之后自动结束，不会出现死循环
  • 3、确定性：每一步骤都有确定的含义，不会出现二义性。
  • 4、可行性：每一步必须是可行的。

算法设计要求

  • 1、正确：如果连正确都谈不上的话
  • 2、可读：算法设计的另一目的是为了便于阅读、理解和交流
  • 3、健壮：一个好的算法应该能对输入不合法数据的情况做合适的处理。
  • 4、高效率与低存储：高效执行，内存及硬盘使用空间尽量低。

时间复杂度

大O记法

  • 常数阶：O(1)，执行常数次数
  • 线性阶：O(n)，单次循环，执行n次
  • 平方阶：O(n2) ，比如嵌套循环
  • 对数阶：O(logn)，比如线性阶里的循环，原来每次递增1执行n次，现在每次递增翻倍，执行x次就退出，则2的x次方 = 上限值n，如：
int count = 1;
int n = 1025;
while(count < n){
    count = count * 2;
}

理解大O推导不算难，难的是对数列的一些相关运算，这更多的是考察你的数学知识和能力。

常见时间复杂度：

常数阶、对数阶、线性阶、nlogn阶、平方阶、立方阶、指数阶…

以上消耗时间复杂度，所消耗的时间从小到大。

第三章 线性表

线性表存储结构

  • 顺序结构：元素在存储地址上之间存在相邻关系
  • 链式结构：

顺序存储结构优缺点

  • 优点：可以快速取得任意元素，无需额外增加空间；
  • 缺点：插入和删除需要移动大量数据，当表变化较大时，难以确定存储空间容量，易造成存储空间碎片

线性表基础

ADT线性表

data 数据

operation 操作：get、add、insert、delete、length、clear、locate等

链式存储

存储单元不再是连续的，每个数据元素除了数据元素信息外，还要存在该元素的后继存储地址。

把存储数据元素的域称为数据域，把存储直接后继位置的域称为指针域。

两部分信息组成元素的存储映像，称为结点node。

n个结点链结成一个链表。每个元素只包含一个指针域，所以称为单链表。

最后一个结点的指针域都为空，记为NULL。

单链表的第一个结点之前附加一个节点 — 头节点，头节点数据域可不存储数据，也可以存储链表公共数据。

如果有头节点，则头指针指向头节点

如果无头节点，则头指针指向第一个结点

单链表与顺序存储结构

  • 时间性能：

  • 查找第i个元素：

  • 顺序结构：O(1)

  • 单链表结构：O(n)

  • 插入和删除

    顺序结构：O(n)

    单链表结构：O(1)

  • 空间性能：

    顺序结构需要预先分配空间，且是连续存储地址，分大了浪费，分小了易发生溢出；

    单链表结构不需要分配存储空间，灵活分配，个数不限。

循环链表

单链表的终端节点指针端由空指针改为指向头结点

双向链表

每个结点除了直接后继指针外，新增一个前驱指针，指向前一个结点

第四章

栈的定义

栈，是限定仅在表尾进行插入和删除操作的线性表

栈，又称为后进先出线性表，LIFO

允许删除和插入的一端为栈顶，另一端为栈底。

栈具有线性关系，即前驱和后继关系。是特殊的线性表，限制了插入和删除的位置。

插入操作：进栈、入栈

删除操作：出栈

通俗点解释就是：进和出是同一个口，所以先进后出，后进先出。

顺序栈和链栈

两者的push和pop进出栈的时间复杂度都为O(1)

顺序栈需要确定一个固定长度的空间，链栈的长度没有限制，但每个元素都需要一个指针域，消耗多些内存。

栈的作用

数组都能用来实现栈的功能。

但栈的引入简化了程序设计的问题，划分了不同关注的层次，使得思考范围缩小，更加聚焦于我们要解决的问题的核心。

递归

一个直接调用自己或通过一系列的调用语句间接调用自己的函数，称作递归函数。

每个递归定义必须至少有一个条件，满足时递归不再进行。

相比较于迭代（使用循环结构），递归使用的是选择结构，递归更简洁清晰易理解，但会消耗大量的时间和内存。

后缀表达式

规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到没有数字和符号，得到最终结果。

后缀表达式：9 3 1 - 3 * + 10 2 /

中缀表达式转后缀表达式

中缀表达式：9 + (3-1) × 3 + 10 ÷ 2

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

后缀表达式：9 3 1 - 3 * + 10 2 /

队列定义

队列：只允许在一端插入操作，在另一端进行删除操作的线性表。

队列是一种先进先出的线性表，简称FIFO。

循环队列

第五章 串

朴素的模式匹配算法

正常的匹配逻辑，但最坏情况是O((n-m+1)*m)

KMP匹配算法

第六章 树

树的定义

线性表是一对一的线性结构，树可以解决一对多的数据结构。

树的存储结构

顺序存储很难满足。

链式存储：双亲表示法、孩子表示法、孩子兄弟表示法。

二叉树

斜树、满二叉树、完全二叉树

二叉树存储结构

二叉链表：设计一个数据域、两个指针域是比较自然的想法。

二叉树遍历方法

前序遍历

中序遍历

后续遍历

层序遍历

研究这么多遍历的方法干什么？

我们用图形的方式来表现树的结构，应该说是非常直观和容易理解的，但是对于计算机来说，它只是顺序、循环、判断等方式来处理，也就是说，它只会处理线性序列， 而上面四种遍历方法，其实都是在把树中的结点变成某种意义的线性序列。

前序遍历法

算法可以采用递归，简单明了:

function preOrderTraverse(BiTree T){
   if(T->data == null){
      return;
   }
   print(T->data);
   preOrderTraverse(T->lChild);  //先序遍历左子树
   preOrderTraverse(T->rChild);   //先序遍历右子树
}

中序遍历

function preOrderTraverse(BiTree T){
   if(T->data == null){
      return;
   }
   preOrderTraverse(T->lChild);  //先序遍历左子树
   print(T->data);
   preOrderTraverse(T->rChild);   //先序遍历右子树
}

后序遍历

function preOrderTraverse(BiTree T){
   if(T->data == null){
      return;
   }
   preOrderTraverse(T->lChild);  //先序遍历左子树
   preOrderTraverse(T->rChild);   //先序遍历右子树
   print(T->data);
}

哈夫曼二叉树（最优二叉树）

应用：

  • a、判断语法结构优化
  • b、哈夫曼编码（压缩与解压）

如何构造哈夫曼二叉树：

结合有权值路径。

从树中一个结点到另一个结点之间的分支构成两个结点之间的路劲，路径上的分支数目称作路劲长度。

第七章 图

最小生成树

经典的两种算法，普利姆算法和克鲁斯卡尔算法

最短路径

拓扑排序

关键路径

最早开始时间和最晚开始时间相等时，意味着这任务路径就是关键路径。

程序终归是字符串、数组、对象的处理，程序的逻辑就三种：顺序、判断、循环

第八章 查找

顺序查找 线性查找

从表的第一个或最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录。

算法：循环遍历数组/对象/表

时间复杂度：O(n)

优点：算法简单，对静态查找表的记录没有任何要求

不足：当n很大时，效率极为低下

有序表查找 - 折半查找（二分查找）

有序二叉树排序，才能使用折半查找

/**
*	$arr 查找数组
*	$searchValue 查找值
**/
binarySearch($arr,$searchValue){
	$low = 0;
	$high = count($arr) - 1;
	while($low <= $high){
		$mid = floor(($low+$high)/2);
		if($arr[$mid] < $searchVaule){
			$low = $mid;
		}else if($arr[$mid] > $searchValue){
			$high = $arr[$mid];
		}else{
			return $arr[$mid]
		}
	}
	return false;
}

时间复杂度：O(logn)

有序表查找 - 插值查找

算法：

基于二分查找的基础进行改良，改良原理：

二分查找中的中值下标

mid = floor((low + high) *  1 / 2)

通过等式变换：

mid = floor( low + (high - low)  * 1 / 2)

算法科学家将这个1/2进行改良：

mid = floor( low + (high  - low) * (($searchValue - $arr[low]) / ($arr[high] - $arr[low])) )

时间复杂度：O(logn)

优点：对于数据分布均匀，表较大的情况下比折半查找法要好很多

不足：对于分布极端不均匀的数据，插值查找未必是很合适的选择

有序表查找 - 斐波那契数列

时间复杂段 O(logn)

线性索引查找

索引：就是把一个关键字与它对应的记录相关联的过程。

索引按照结构可以分为：线性索引、树形索引、多级索引。

所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。

线性索引：稠密索引、分块索引、倒排索引

  • 稠密索引：指在线性索引中，将数据集中的每个记录对应一个索引项。比如开卷考的时候一个本子记录每一个问题的答案在课本的哪一页，这个本子就是稠密索引。

  • 分块索引：把数据集的记录分成若干块，并且这些块：块内无序、块间有序、最大关键码、存储了块中的记录个数。比如：图书馆藏书分类摆放就是一个典型的分块索引。

  • 倒排索引：比如搜索引擎给出搜索结果数的存储方式就是就典型的倒排索引，一个关键词命中的文章数，关键词与文章编号进行关联索引存储。关键词：关键词：文章编号[1,3,2,4]

索引项有序也就是意味着我们要查找关键字时，可以用到二分查找、插值查找、斐波那契查找。

二叉排序树（二叉查找树）

假设数据无需存储，增删效率都过的去，但无需造成查找效率很低。

如果查找的数据集是有序线性表，并且顺序存储，查找可以用折半、插值、斐波那契等查找算法，但因为有序，在增删操作上需要耗费大量的时间。

定义：

它或者是一颗空树，或者具备以下性质：

  • a、若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值
  • b、若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值
  • c、它的左右子树也分别为二叉排序树

查找算法：

从根结点开始，递归遍历整棵二叉排序树：

function search(T，searchValue){
    if T空树
        return false;
    else if 当前结点值T->data == 查找值searchValue
        return true;
    else if 当前结点值T->data > 查找值searchValue
        search(T->lChild,searchValue);
    else 
        search(T->rChild,searchValue);
}

插入算法：在查找基础上判断并插入

删除算法：需要消耗查询及前驱结点移动位置的时间

多路查找树

其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。

4种特殊形式：2-3树、2-3-4树、B树、B+树；

2-3树、2-3-4树是特殊的B树；

2-3树是3阶B树，2-3-4树是4阶B树；

B树的目的就是为了实现快速查找（有点类似于有序表的分块查找）

B树是一种平衡的多路查找树。结点最大的孩子数目称为B树的阶。

B树的数据结构就是为内外存的数据交互准备。

比如说一棵树B树的阶1001（即1个结点包含1000个关键字），高度为2，它可以存储超过10亿个关键字，我们只要让根结点（1000个关键字）持久地保留在内存中，那么在这棵树上，寻找某一个关键字最多需要两次硬盘的读取即可，一次查找根结点，一次查找某个叶子结点。

B+树

在B树中每一个元素在该树中只出现一次，有可能是根结点，有可能在分支结点

而在B+树中，出现在分支结点中的元素会被当做它们该分支结点位置的中序后继者（叶子结点）中再次出现。另外每一个叶子结点都会保存一个指向后一叶子结点的指针。

所有叶子结点包含全部关键字的信息，及指向这些关键字记录的指针，叶子结点本身依靠关键字的大小，自小而大顺序链接。

所有分支结点可以看成索引，结点中仅含有其子树中的最大（最小）关键字。

如果是随机查询，从根结点出发，与B树的查找方式相同，只不过即使在分支结点找到了待查找的关键字，它也只是索引，不能提供实际记录的访问，还是需要到达次关键字的终端结点。

如果是需要从最小关键字进行小到大的顺序查找，可以从最左侧的叶子结点出发，不经过分支结点，而是沿着指向下一叶子的指针就可遍历所有的关键字。

B+树还很适合带范围的查找，从根结点先找开始值，然后再在叶子结点按顺序查找到符合范围的所有记录。

散列表查找（哈希表）

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。

查找时，根据这个确定的对应关系f，找到给定值key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上。

这里将这种对应关系f，称为散列函数，又称为哈希函数。

采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。

建议：散列技术最适合的求解问题是查找与给定值相等的记录。省去了顺序查找的比较步骤。

理想情况下，通过散列函数计算出来的地址都是不一样的，但现实中还是会碰到f(key1) == f(key2)的问题。也就是我们常听到的哈希冲突。

哈希冲突：再次说明快速、简单、精确三者必舍去其一。

第九章 排序

多个关键字的排序可以转换成单个关键字的排序

根据记录是否全部放在内存中，分为内排序和外排序，外排序由于记录数太多，整个排序过程需要再内外存之间多次交换数据。

内排序：插入排序、交换排序、选择排序、归并排序

学习排序算法的目的：更多的并不是为了去实现编程算法，而是通过学习来提高我们编写算法能力，以便于解决更多复杂和灵活的应用性问题。

冒泡排序

思路最简单、最容易理解。

算法：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

从底部往上循环比较，前者大于后者，后者上浮。

不断的交换，通过交换完成最终的排序。

注意：优化大部分数据都已经不需要交换排序的情况，减少不必要的比较，外部一次大循环发现后续没有数据被交换则表示后续数据都是有序的，不必要继续进行循环比较。

简单选择排序

O(n²)

直接插入排序

O(n²)

希尔排序

有前提条件的排序

O(n㏒n)

堆排序

堆是具有下列性质的完全二叉树：

每个结点的值都大于或等于其左右孩子结点的值，称为大堆顶，或者每个结点的值都小于或等于其左右孩子结点的值，称为小堆顶

归并排序

两两比较合并，形成一棵倒置的完全二叉树

快速排序

@todo 2017