1.绪论
基本概念和术语
数据: 是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别并输入给计算机处理的符号集合。
数据元素: 是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。
数据项: 一个数据元素可以由若干个数据构成。数据项是数据不可分割的最小单位。
数据对象: 是性质相同的数据元素的集合，是数据的子集。
数据结构: 是相互之间存在的一种或多种特定关系的数据元素的集合。
逻辑结构和物理结构
逻辑结构
逻辑结构指数据对象中数据元素之间的互相关系。
(1)集合结构
(2)线性结构
(3)树形结构
(4)图形结构
物理结构(存储结构)
(1)顺序存储结构
(2)链式存储结构
抽象数据类型
数据类型是指一组性质相同的值得集合及定义在此集合上的一些操作的总称。
抽象数据类型(Abstract Data Type,ADT)是指一个数学模型及定义在该模型删的一组操作
ADT 抽象数据类型名
Data
数据元素间逻辑关系的定义
operation
操作1
初始条件
操作结果描述
操作2
...
操作n
...
endADT
2.算法
算法的定义
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
算法的设计要求
算法的特性
(1)输入输出
算法有零个或多个输入
算法有一个或多个输出
(2)有穷性
指算法在执行有限步骤后，自动结束而不会出现无限循环，并且每个步骤在可接受的时间内完成。
(3)确定性
算法的每一步都具有确定的含义，不会出现二义性。
(4)可行性
算法的每一步都必须是可行的，也就是说每一步都能通过执行有限次数完成。
算法效率的度量方法
一个程序的运行时间，依赖于算法的好坏和问题的输入规模
函数的渐进增长
函数的渐进增长: 给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N,f(n)总是比g(n)大，那么，我们说f(n)的增长渐进快于g(n)
判断一个算法的效率时，函数中的常熟和其他次要项常常可以忽略，更应该关注最高阶项的阶数
算法时间复杂度
算法的时间复杂度记作: T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
用O()来体现算法时间复杂度的记法，我们称之为大O记法。
随着n的增大，T(n)增长最慢的算法为最优算法。
推导大O阶方法
1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中，只保留最高阶项。
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。
得到的结果就是大O阶。
常见时间复杂度
执行次数函数 阶 非正式术语
12 O(1) 常数阶
2n+3 O(n) 线性阶
3n^2+2n+1 O(n^2) 平方阶
5log2n+20 O(logn) 对数阶
2n+3nlog2n+19 O(nlogn) nlogn阶
6n^3+4 O(n^3) 立方阶
2^n O(2^n) 指数阶
时间复杂度耗时从小到大依次是
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
ps: O(logn) 每次计算都会缩减为搜索集合的x分之一
空间复杂度
3.线性表
线性表的定义
线性表指零个或多个数据元素的有限序列。序列意味着元素之间是有顺序的。
线性表的个数n(n>=0)定义为线性表的长度，当n=0时,称为空表
线性表的抽象数据类型
ADT 线性表(List)
Data
线性表的数据对象集合为{a1,a2,...an}，每个元素的类型均为DataType,其中，除第一个元素a1外，每个元素有且只有一个直接前驱元素，除最后一个元素an外，每个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系
Operation
InitList(*L) 初始化操作，建立一个空线性表L
ListEmpty(L) 若线性表为空,返回true,否则返回false
ClearList(*L) 将线性表清空
GetElem(L,i,*e) 将线性表中的第i个位置元素返回给e
LocateElem(L,e) 在线性表L中查找与给定值e相等的元素，如果查找成功，返回钙元素在表中序号表示成功;否则，返回0表示失败。
ListInsert(*L,i,e) 在线性表L中的第i个位置插入新元素e
ListDelete(*L,i,*e) 删除线性表L中第一个位置元素，并用e返回其值
ListLength(L) 返回线性表L的元素个数
endADT
上述操作是最基本的，对于不同的应用，线性表的操作是不同的，对于其他操作，可以用基本操作的组合来实现
顺序存储结构
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
由于是顺序存储的，于是知道首地址就可以知道第i个元素的地址 LOC(ai)=LOC(a1)+(i-1)*c 其中C是一个数据元素占用的存储单元。
像这样可以随时算出任意元素地址的结构，我们通常称为随机存储结构
线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1);而插入或删除时，时间复杂度都是O(n)。这说明它比较适合元素个数不太变化，更多的是存取数据的应用。
优点
无需为表示表中元素之间的逻辑关系而增加额外的存储空间(如存储指针)
可以快速地存取表中任一位置的元素
缺点
插入和删除操作需要移动大量元素
当线性表长度变化较大时，难以确定存储空间的容量
造成存储空间的碎片
链式存储结构
为表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需要一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据与，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(node)
n个结点链结成一个链表，即为线性表的链式存储结构。
因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
图
链表中的第一个结点的存储位置叫做头指针。
有时候为了方便操作，会在单链表第一个结点前添加一个结点，称为头结点。头结点的数据域可以不存储任何信息，头结点的指针域存储指向第一个结点的指针。
单链表
读取
插入与删除
对于插入和删除数据越频繁的操作，单链表的效率优势就越是明显。
整表创建与删除
头插法
尾插法
时间性能
单链表在找出某位置的指针后，插入和删除时间仅为O(1)。
单链表的读取时间是O(n)
经验性结论
若线性表需要频繁查找，很少进行插入和删除操作，宜采用顺序存储结构。
若需要频繁插入和删除时，宜采用单链表结构。
静态链表
循环链表
把单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表行程一个环，这种头尾相接的单链表称之为单循环链表，简称循环链表。
为了使空链表与非空链表处理一致，通常设置一个头结点。
双向链表
双向链表是在单链表的每个结点中，在设置一个指向其前驱结点的指针域。
既然单链表有循环链表，那么双向链表也可以是循环表。
4.栈和队列
栈的定义
栈是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称先进后出的线性表，简称LIFO结构。
5.树
树的定义
结点所拥有的子树的个数称为该结点的度(Degree); 树中各结点度的最大值称为该树的度
树的抽象数据类型
树的存储结构
双亲表示法
孩子表示法(多重链表表示法)
孩子兄弟表示法
二叉树的定义(Binary Tree)
二叉树的特点
每个结点最多两棵子树，有左右之分
特殊二叉树
斜树
只有左子节点或只有右子节点的二叉树称为斜二叉树
满二叉树 节点数为2^k-1 k是层数
所有的分支要么左右子节点都有，要么没有子节点，且所有叶子结点都在同一层上
完全二叉树
在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树
二叉树的性质
性质1: 在二叉树的第i层上**至多**有2^(i-1)个结点
性质2: 深度为k的二叉树**至多**有2^k-1个结点
性质3: 对于任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2，则n0=n2+1
性质4: 具有n个结点的完全二叉树的深度为[log2n]+1 []表示取整
性质5: 如果一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第log2n+1层，每层从左到右)，对任一结点1(1<=i<=n)有:
(1)如果i=1,则结点i是二叉树的根,无双亲；如果i>1，则其双亲是结点[i/2]
(2)如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其做孩子是结点2i
(3)如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1
二叉树的存储结构
二叉树循序存储结构
二叉链表
遍历二叉树
前序遍历 根左右
中序遍历 左根右
后序遍历 左右根
层序遍历 从第一层开始从左往右依次遍历
已知前序或后序遍历序列及中序遍历序列，可以唯一确定一棵二叉树
线索二叉树
如果所用的二叉树需经常遍历或查找对象时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。
赫夫曼树及应用(最优二叉树)
带权路径长度WPL最小的二叉树称作赫夫曼树。
赫夫曼编码
6.图
7.查找
查找概论
查找表(search table)是由同一类型的数据元素(或记录)构成的集合。
关键字(key)是数据元素中某个数据项的值，又称键值。
若此关键字可以唯一地标识一个记录，则称此关键字为主关键字(primary key)。
对于那些可以识别多个元素(或记录)的关键字，我们称之为次关键字(secondary key)。
查找(searching)就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素(或记录)。
查找表按操作方式来分有两种
静态查找表: 只做查找操作的查找表
动态查找表: 在查找过程中同时插入查找表不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
顺序表查找
顺序查找又叫线性查找，是最基本的查找技术，它的查找过程是:从表中第一个(或最后一个)记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果知道最后一个(或第一个)记录，其关键字和给定值比较都不等时，则表中没有索茶的记录，查找不成功。
复杂度为O(n)，当n很大时，效率低下
有序表查找
折半查找
折半查找又称二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大排序)，线性表必须采用顺序存储(重点)。
折半查找的基本思想是:在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的作伴去继续查找；若给定值大于中间记录的关键字，则在中间记录的有搬去继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，直到失败为止。
时间复杂度O(logn)
插值查找
插值查找是根据要查找的关键字key与最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式(key-a[low])/(a[high]-a[low])
时间复杂度为O(logn),二对于关键字分布比较均匀的查找表来说，插值算法的平均性能要比二分查找好的多。
线性索引查找
索引就是把一个关键字和它对应的记录相关联的过程。
索引是为了加快查找速度而设计的一种数据结构。
<<<<<<< Updated upstream
所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。
=======
所谓线性索引就是讲索引项集合组织为线性结构，也称为索引表。
Stashed changes
稠密索引
稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。
分块索引
背景: 稠密索引因为索引项和数据集的记录个数相同，所以空间代价很大。为了减少索引的个数，我们可以对数据集进行分割，使分块有序，然后对每个块建立一个索引项，从而减少索引项的个数。
定义: 对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引
分块有序是把数据集的记录分成若干块，且这些块满足2个条件
1块内无序
2块间有序两个条件
分析说明: 分块索引效率高于顺序查找的O(n),但是与二分查找的O(logn)还是有不小差距。分块索引在兼顾了对细分块不需要有序的情况下，大大增加了整体超找的速度，所以普遍被用于数据库表查找等技术中。
倒排索引
背景: 搜索引擎无论你查找什么信息，都可以在极短时间内给你信息，是如何实现的呢？倒排索引是最简单最基础的搜索技术。
定义: 索引项的通用结构是
次关键码(如下例中英文单词)
记录号表(如下例中文章编号)
其中记录号表存储具有相同次关键字的所有记录的记录号。这样的索引方法就是倒排索引。
如
句1 books and frieds should be few but good
句2 a good book is a good friend.
按照倒排索引可拆为下述数据
英文单词 文章编号
a 2
and 1
be 1
book 1,2
… …
二叉树排序
背景: 如果查找的数据集是有序线性表，并且是顺序存储的，查找可以用折半、插值等算法实现，不过因为有序在插入和删除操作上，就需要耗费大量的时间。有没有一种插入和删除效率不错，有可以比较高效地实现查找的算法呢？
定义: 二叉查找树，又称二叉搜索树。它或者是一棵空树，或者是具有下列性质的二叉树。
* 若它的左子树不空，则`左子树`上所有结点的值均小于它的根结构的值
* 若它的右子树不空，则`右子树`上所有结点的值均大于它的根结点的值
* 它的左右子树叶分别是 二叉查找树
二叉查找树进行中序遍历可得到一个有序序列
结点i的左结点下标是2i,右结点下标是2i+1
解释说明: 构造 二叉查找树不是为了排序，而是为了提高查找和插入的速度。在一个有序数据集上的查找速度总是要快于无序的数据集的，而且 二叉查找树这种链式存储结构，也有利于插入和删除的速度。
查找时，每次都可以根据与当前节点的值比较，然后排除一半的结果
平衡二叉树(AVL树)
背景: 二叉查找树越平衡，查找复杂度越低，所以对一个集合按 二叉查找树查找，最好把它构建成一棵平衡的 二叉查找树。这就引申出一个问题，如何让 二叉查找树平衡。
定义: 平衡二叉树是一种 二叉查找树，其中每个结点的左子树和右子树的高度差至多等于1。
二叉树结点左子树深度减去右子树深度的值成为平衡因子。(此资料中深度等于高度)
距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。
时间复杂度: 平衡二叉树查找时间复杂度为O(logn),插入删除复杂度为O(logn)
多路查找树(B树)
背景: 要操作的数据集非常大，大到超过内存大小，只能不断从硬盘等存储设备中调入调出。一旦涉及到这样的外部存储设备，访问该元素的时间已经不仅仅是寻找该元素所需比较次数的函数，必须考虑对外部存储设备的访问时间及访问次数。一个结点只能存储一个元素，当元素非常多时，就使得要么树的度特别大,要么树的高度特别大，甚至两者都必须足够大才行。这就使得内存存取外存次数非常多(一次去一个结点的元素),成为了时间效率上的瓶颈，迫使我们打破一个结点只存储一个元素的限制，为此引入多路查找树的概念。
<<<<<<< Updated upstream
定义: 多路查找树，每一个结点的孩子数可以多于两个，且每个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。
=======
定义: 多路查找树，每一个结点的孩子数可以多于两个，且每个结点处可以存储多个元素。
Stashed changes
2-3树
定义: 2-3数是这样一棵多路查找树，其中每个结点都具有两个孩子(我们称它为2结点)或三个孩子(我们称它为3结点)
一个2结点包含一个元素和两个孩子(或没有孩子)，且与 二叉查找树类似，左子树包含的元素小于该元素，右子树包含的元素大于钙元素。不过与 二叉查找树不同的是，这个2结点要么没孩子，要么就有两个，不能只有一个孩子。
一个3结点包含一小一大两个元素和三个孩子(或没有孩子)，一个3结点要么没有孩子，要么具有3个孩子。如果某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
2-3树的所有的叶子结点都在同一层次上。
2-3-4数
定义: 其实就是2-3树的扩展，包含了4结点的使用。
B树
定义: B树是一种平衡的多路查找树，结点最大的孩子数目成为B树的阶，因此2-3树是3阶B树，2-3-4树是4阶B树
特点:
如果根节点不是叶结点，则其至少有两棵子树。
所有叶子结点都位于同一层次。
....
解释说明:
示例
B+树
背景: 对于树结构来说，我们可以通过中序遍历来顺序访问树中的元素，这一切都是在内存中进行的。
可是在B树结构中，我们往返于各个结点也就意味着，我们必须得在硬盘的页面之间进行多次访问，而且我们每次经过结点遍历时，都会对结点中的元素进行一次遍历，这非常糟糕，有没有可能让遍历时每个元素只访问一次呢？
定义: 为了能解决所有元素遍历等基本问题，我们在原有的B树结构基础上，加上了新的元素组织方式，这就是B+树。
在B树中每个元素在该树中只出现一次，而在B+树中，所有元素都会存放于叶子结点中，分支结点上保存冗余的元素(作用类似索引)，每个叶子结点保存一个指向后一叶子结点的指针。
特点: (1)有n棵子树的结点中包含有n个关键字
(2)所有叶子结点中包含全部关键字的信息，及指向含这些关键字记录指针，叶子结点本身依关键字的大小自小而大顺序链接。
(3)所有分支结点可以看成是索引，结点中仅含有其子树中的最大(或最小)关键字
解释说明: 这样的数据结构最大的好处是，如果要随机查找，就从根结点触发，与B树的查找方式相同，只不过即使在分支结点找到了待查找的关键字，它也只是用来索引的，不能提供实际记录的访问，还是需要到达包含此挂件自的终端结点。
如果我们是需要从最小关键字进行从小到大的顺序查找，我们可以从最左侧的叶子节点出发，不经过分支结点，而是延着指指向下一叶子的指针就可遍历所有的关键字。
B+树特别适合带有范围的查找。
散列表查找(哈希表)
背景: 前面的顺序表查找时，查询关键字要从表头开始，挨个比较记录a[i]与key的值，直到相等才算找成功，返回i。到了有序查找我们利用a[i]的<或>来折半查找，直到相等返回i。最终我们的目的都是为了找i,其实也就是相对的下表，再通过顺序存储的存储位置计算方法，LOC(ai)+LOC(a1)+(i-1)*c,也就是通过第一个元素内存存储位置加上i-1个单位位置，得到最后的内存地址
此时，发现，为了查找结果，之前方法的"比较"都是不可避免的，那么能否有一种方法跳过比较直接通过关键key得到查找的内存存储位置呢？
定义:散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系，使得每个关键字key对应一个存储位置f(key)。
我们把这种对应关系f称为散列函数，又称为哈希(hash)函数。按照这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。
时间复杂度: 理想情况下为O(1)
查询步骤: (1)存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。
(2)查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录
所以散列技术，既是一种存储方法，也是一种查找方法
散列技术最适合求解的问题是查找与给定值相等的记录
冲突
定义: 理想情况下，每个关键字通过散列函数计算出来的地址都是不一样的，可现实中，这只是一个理想。我们时常会碰到两个关键字key1!=key2，但是又f(key1)==f(key2)，这种现象我们称之为冲突。
散列函数的构造方法
思考: 什么样的散列函数是最好的呢？
(1)计算简单。
(2)散列地址分布均匀
直接定址法
定义: f(key) =a*key+b (其中ab为常数)
解析: 直接定址法简单，不会冲突，但是这需要事先知道关键字的分布情况，故虽然简单，但是不常用。
数字分析法
定义: 抽取关键字的补一份来计算散列存储位置的方法，这在散列函数中是常常用到的手段。
平方取中法
除留余数法
定义: f(key)=key mod p (p<=m)
解析: 除留余数法是最常用的构造散列函数的方法。其关键在于p的选择。
处理散列冲突的方法
开放定址法
定义: 一点发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。fi(key)=(f(key)+di) MOD m (di=1,2..m-1)
地址m冲突，那么找(f(key)+1) mod m ...(f(key)+i) mod m ，直到找到空缺位置。这种解决冲突的开放定址法称之为线性探测法。
本来不是同义词缺需要争夺一个地址的情况，我们称为堆积。
拉链法
应用
数组就是非常简单的哈希应用
跳跃表查找
背景: 有序链表查找并不能使用二分查找，我们可以使用AVL树等进行查找，但是都相对复杂，我们从有序链表每层抽出一定的节点作为索引，多次重复这个步骤便构成了跳跃表，跳跃表解决了有序链表结构查找特定值困难的问题
定义:
性质:
(1) 由多层结构组成
(2) 每一层都是一个有序的链表
(3) 最底层包含全部元素
(4) 如果一个元素出现在level i的链表中，则它在level i以下的层中都会出现
(5) 每个结点包含两个指针，一个指向同一链表的下一个元素，一个指向下面一层的元素
应用: Redis、LevelDb
时间复杂度: O(logn)
资料
8.排序
概念定义
内外排序
外排序
外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。
外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。而后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果
外排序典型的有N路归并排序等
内排序
内排序按排序中借助的操作可分为插入排序、交换排序、选择排序、归并排序
稳定性
稳定排序
插入、冒泡、归并
不稳定排序
选择、快速、希尔、堆
常见排序
冒泡排序
时间复杂度: O(n^2)
选择排序
时间复杂度: O(n^2)
解析: 比冒泡排序稍好
插入排序
时间复杂度: O(n^2)
希尔排序
特殊的插入排序，插入排序是步长为1的希尔排序
堆排序
定义: 堆是具有下列性质的完全二叉树:
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
堆排序是利用堆(假设利用大顶堆)进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆定的根节点。将它移走(其实就是讲其与堆数组的末尾元素交换，此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
时间复杂度: O(nlogn)
归并排序
定义: 归并排序就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]([x]表示不小于x的最小整数)个长度为2或1的有序子序列；再两两归并，...,如此反复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。
时间复杂度: O(nlogn)
快速排序
时间复杂度: O(nlogn)
FAQ
1.log时间复杂度的计算
https://www.zhihu.com/question/20503898