在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（Structure）。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

逻辑结构

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的

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

集合结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。类似于数学上的集合

线性结构结构中的数据元素之间只存在一对一的关系。比如排队

树形结构结构中的数据元素之间存在一对多的关系。比如家族族谱

图状结构或网状结构结构中的数据元素之间存在多对多的关系。比如地图

物理结构

存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。

顺序存储：存储的物理位置相邻。（p.s. 物理位置即信息在计算机中的位置。）

链接存储：存储的物理位置未必相邻，通过记录相邻元素的物理位置来找到相邻元素。

索引存储：类似于目录，以后可以联系操作系统的文件系统章节来理解。

散列存储：通过关键字直接计算出元素的物理地址（以后详解）。

算法的五个特征

1，有穷性：有限步之后结束

2，确定性：不存在二义性，即没有歧义

3，可行性：比如受限于计算机的计算能力，有些算法虽然理论上可行，但实际上无法完成。

4，输入：能被计算机处理的各种类型数据，如数字，音频，图像等等。

5，输出：一至多个程序输出结果。

算法的复杂度

时间复杂度：

• 它用来衡量算法随着问题规模增大，算法执行时间增长的快慢；

• 是问题规模的函数：T(n)是时间规模函数时间复杂度主要分析T(n)的数量级

• T(n)=O(f(n)) f(n)是算法中基本运算的频度一般我们考虑最坏情况下的时间复杂度

空间复杂度：

• 它用来衡量算法随着问题规模增大，算法所需空间的快慢；

• 是问题规模的函数：S(n)=O(g(n)) ；算法所需空间的增长率和g(n)的增长率相同。

第二章：线性表

线性表的逻辑结构

定义：线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列。其中n为表长。当n=0时线性表是一个空表

特点：线性表中第一个元素称为表头元素；最后一个元素称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。

线性表的顺序存储结构

线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元（比如C语言里面的数组），依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

建立顺序表的三个属性: 1.存储空间的起始位置（数组名data） 2.顺序表最大存储容量（MaxSize） 3.顺序表当前的长度（length）

其实数组还可以动态分配空间，存储数组的空间是在程序执行过程中通过动态存储分配语句分配

总结：

1.顺序表最主要的特点是随机访问（C语言中基于数组），即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。

2.顺序表的存储密度高，每个结点只存储数据元素。无需给表中元素花费空间建立它们之间的逻辑关系（因为物理位置相邻特性决定）

3.顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

顺序表的操作

1.插入

算法思路：

1.判断i的值是否正确

2.判断表长是否超过数组长度

3.从后向前到第i个位置，分别将这些元素都向后移动一位

4.将该元素插入位置i 并修改表长

代码

分析：

最好情况：在表尾插入（即i=n+1），元素后移语句将不执行，时间复杂度为O(1)。

最坏情况：在表头插入（即i=1），元素后移语句将执行 n次，时间复杂度为O(n)。

平均情况：假设pi（pi=1/(n+1) ）是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点时所需移动结点的平均次数为

2.删除

算法思路：

1.判断i的值是否正确

2.取删除的元素

3.将被删元素后面的所有元素都依次向前移动一位

4.修改表长

代码

分析

最好情况：删除表尾元素（即i=n），无须移动元素，时间复杂度为O(1)。

最坏情况：删除表头元素（即i=1），需要移动除第一个元素外的所有元素，时间复杂度为O(n)。

平均情况：假设pi(pi=1/n)是删除第i个位置上结点的概率，则在长度为n的线性表中删除一个结点时所需移动结点的平均次数为

线性表的链式存储结构

线性表的链式存储是指通过一组任意的存储单元来存储线性表中的数据元素。

头结点和头指针的区别？

不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息

为什么要设置头结点？

1.处理操作起来方便例如：对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了

2.无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

单链表的操作

1.头插法建立单链表：

建立新的结点分配内存空间，将新结点插入到当前链表的表头

代码

2.尾插法建立单链表：

建立新的结点分配内存空间，将新结点插入到当前链表的表尾

代码

3.按序号查找结点

在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止,否则返回最后一个结点指针域NULL。

代码

4.按值查找结点

从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL。

代码

5．插入

插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i−1个结点，再在其后插入新结点。

算法思路： 1.取指向插入位置的前驱结点的指针 ① p=GetElem(L,i-1); 2.令新结点*s的指针域指向*p的后继结点 ② s->next=p->next; 3.令结点*p的指针域指向新插入的结点*s ③ p->next=s;

6．删除

删除操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i−1个结点，即被删结点的前驱结点，再将其删除。

算法思路： 1.取指向删除位置的前驱结点的指针 p=GetElem(L,i-1); 2.取指向删除位置的指针 q=p->next; 3.p指向结点的后继指向被删除结点的后继 p->next=q->next 4.释放删除结点 free(q);

双链表

定义

1.插入：(方法不唯一) ① s->next=p->next; ② p->next->prior=s; ③ s->prior=p; ④ p->next=s;

2.删除： ① p->next=q->next; ② q->next->prior=p; ③ free(q);

循环链表&&静态链表

循环单链表：循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环

循环双链表：类比循环单链表，循环双链表链表区别于双链表就是首尾结点构成环

当循环双链表为空表时，其头结点的prior域和next域都等于Head。

静态链表：静态链表是用数组来描述线性表的链式存储结构。

数组第一个元素不存储数据，它的指针域存储第一个元素所在的数组下标。链表最后一个元素的指针域值为-1。

例子

第三章：栈和队列

栈

栈（Stack）：只允许在一端进行插入或删除操作的线性表。

栈顶（Top）：线性表允许进行插入和删除的那一端。

栈底（Bottom）：固定的，不允许进行插入和删除的另一端

特点： 1.栈是受限的线性表，所以自然具有线性关系。 2.栈中元素后进去的必然先出来，即后进先出 LIFO（Last In First Out）

栈中元素后进去的必然先出来，即后进先出LIFO（Last In First Out）

顺序栈

栈是线性表的特例，那栈的顺序存储也是线性表顺序存储的简化。栈的顺序存储结构也叫作顺序栈。

顺序栈的操作

1.判空：

2.进栈：

3.出栈：

4.读取栈顶元素：

共享栈

顺序栈的存储空间大小需要事先开辟好，很多时候对每个栈各自单独开辟存储空间的利用率不如将各个栈的存储空间共享

示意图

共享栈的结构

共享栈的操作：（进栈）

链式栈

栈是线性表的特例，线性表的存储结构还有链式存储结构，所以也可以用链表的方式来实现栈。栈的链式存储结构也叫作链栈。

特点 1.链栈一般不存在栈满的情况。 2.空栈的判定条件通常定为top==NULL；

结构

链式栈的操作

1.进栈

2.出栈

队列

队列是只允许在一端进行插入，而在另一端进行删除的线性表

队头（Front）：允许删除的一端，又称为队首。

队尾（Rear）：允许插入的一端。

先进入队列的元素必然先离开队列，即先进先出（First In First Out）简称FIFO

顺序队列

用数组来实现队列，可以将队首放在数组下标为0的位置。

循环队列

把数组“掰弯”，形成一个环。Rear指针到了下标为4的位置还能继续指回到下标为0的地方。这样首尾相连的顺序存储的队列就叫循环队列

入队：rear=(rear+1)%MaxSize

出队：front=(front+1)%MaxSize

循环队列的操作

1.入队：

2.出队：

链式队列

队列的链式存储结构，其实就是线性表的单链表，只不过需要加点限制，只能表尾插入元素，表头删除元素。

为了方便操作，我们分别设置队头指针和队尾指针，队头指针指向头结点，队尾指针指向尾结点。

链式队列的操作

1.入队：我们知道队列只能从队尾插入元素，队头删除元素。于是入队就是在队尾指针进行插入结点操作。链队的插入操作和单链表的插入操作是一致的。

2.出队：出队就是头结点的后继结点出队，然后将头结点的后继改为它后面的结点。

双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列

栈的应用

1、括号匹配：假设有两种括号，一种圆的()，一种方的[]，嵌套的顺序是任意的。

算法思想：若是左括号，入栈；若是右括号，出栈一个左括号判断是否与之匹配；检验到字符串尾，还要检查栈是否为空。只有栈空，整个字符串才是括号匹配的。

代码

2、表达式求值：

规则：从左到右扫描表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈然后跟这个符号进行运算，最后将运算结果进栈，直到最终获得结果。

3、递归：

要理解递归，你要先理解递归，直到你能理解递归。如果在一个函数、过程或数据结构的定义中又应用了它自身，那么这个函数、过程或数据结构称为是递归定义的，简称递归。递归最重要的是递归式和递归边界。

1.阶乘

时间复杂度：O(NlogN)

2.斐波那契数列

时间复杂度 O(2^n)

第四章：树

树的基本概念

树是递归定义的结构

结点

根节点：树只有一个根结点

结点的度：结点拥有的子树的数量

度为0：叶子结点或者终端结点

度不为0：分支结点或者非终端结点

分支结点除去根结点也称为内部结点

树的度：树中所有结点的度数的最大值

结点关系

祖先结点

根结点到该结点的唯一路径的任意结点

子孙结点

双亲结点

根结点到该结点的唯一路径上最接近该结点的结点

孩子结点

兄弟结点

有相同双亲结点的结点

层次，高度，深度，树的高度

层次：根为第一层，它的孩子为第二层，以此类推

结点的深度：根结点开始自顶向下累加

结点的高度：叶节点开始自底向上累加

树的高度（深度）：树中结点的最大层数

树的性质

1.树中的结点数等于所有结点的度数加1。

证明：不难想象，除根结点以外，每个结点有且仅有一个指向它的前驱结点。也就是说每个结点和指向它的分支一一对应。假设树中一共有b个分支，那么除了根结点，整个树就包含有b个结点，所以整个树的结点数就是这b个结点加上根结点，设为n，则n=b+1。而分支数b也就是所有结点的度数，证毕。

2.度为m的树中第i层上至多有m^(i−1)个结点（i≥1）。

证明：（数学归纳法）首先考虑i=1的情况：第一层只有根结点，即一个结点，i=1带入式子满足。假设第i-1层满足这个性质，第i-1层最多有m i-2个结点。 ……… .......... i-1层 ……… 又因为树的度为m,所以对于第i-1层的每个结点，最多有m个孩子结点。所以第i层的结点数最多是i-1层的m 倍，所以第i层上最多有m ^(i-1)个结点。

3.高度为h的m叉树至多有(m^h-1)/(m-1)个结点

4.具有n个结点的m叉树的最小高度为logm(n(m-1)+1)

树的存储结构

顺序存储结构

双亲表示法：用一组连续的存储空间存储树的结点，同时在每个结点中，用一个变量存储该结点的双亲结点在数组中的位置。

链式存储结构

孩子表示法：把每个结点的孩子结点排列起来存储成一个单链表。所以n个结点就有n个链表；如果是叶子结点，那这个结点的孩子单链表就是空的；然后n个单链表的的头指针又存储在一个顺序表（数组）中。

孩子兄弟表示法：顾名思义就是要存储孩子和孩子结点的兄弟，具体来说，就是设置两个指针，分别指向该结点的第一个孩子结点和这个孩子结点的右兄弟结点。

二叉树

定义

二叉树是n（n≥0）个结点的有限集合： ① 或者为空二叉树，即n=0。 ② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

1.每个结点最多有两棵子树。

2.左右子树有顺序

二叉树的五种基本形态：

1.空树

2.只有一个根结点

3.根结点只有左子树

4.根结点只有右子树

5.根结点既有左子树又有右子树

特殊二叉树

1.斜树

2.满二叉树:

3.完全二叉树

二叉树的性质

1.非空二叉树上叶子结点数等于度为2的结点数加1

2.非空二叉树上第K层上至多有2^k−1个结点（K≥1）

3.高度为H的二叉树至多有2^H-1个结点（H≥1）

4.具有N个（N>0）结点的完全二叉树的高度为 [log2(N+1)]或[log2N] +1。

二叉树的存储结构

顺序存储

二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。

链式存储

二叉树每个结点最多两个孩子，所以设计二叉树的结点结构时考虑两个指针指向该结点的两个孩子。

二叉树的遍历

先序遍历： 1）访问根结点； 2）先序遍历左子树； 3）先序遍历右子树。

递归

非递归

中序遍历： 1）中序遍历左子树； 2）访问根结点； 3）中序遍历右子树。

递归

非递归

后序遍历： 1）后序遍历左子树； 2）后序遍历右子树； 3）访问根结点。

递归

非递归

层次遍历：若树为空，则什么都不做直接返回。否则从树的第一层开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

线索二叉树

N个结点的二叉链表，每个结点都有指向左右孩子的结点指针，所以一共有2N个指针，而N个结点的二叉树一共有N-1条分支，也就是说存在2N-(N-1)=N+1个空指针。比如左图二叉树中有6个结点，那么就有7个空指针。

大量的空余指针能否利用起来？

指向前驱和后继的指针称为线索，加上线索的二叉链表就称为线索链表，相应的二叉树就称为线索二叉树

对二叉树以某种次序遍历使其变为线索二叉树的过程就叫做线索化

哈夫曼树和哈夫曼编码

算法的描述如下： 1）将这N个结点分别作为N棵仅含一个结点的二叉树，构成森林F。 2）构造一个新结点，并从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。 3）从F中删除刚才选出的两棵树，同时将新得到的树加入F中。 4）重复步骤2）和3），直至F中只剩下一棵树为止。

第五章：图

图的基本概念

定义：树是N（N≥0）个结点的有限集合，N=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足： 1）有且仅有一个特定的称为根的结点。 2）当N>1时，其余结点可分为m（m>0）个互不相交的有限集合T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根结点的子树。

图G由顶点集V和边集E组成，记为G=(V，E)

V(G)表示图G中顶点的有限非空集。用|V|表示图G中顶点的个数，也称为图G的阶

E(G)表示图G中顶点之间的关系（边）集合。用|E|表示图G中边的条数。

分类

有向图

有向边（弧）的有限集合

弧是顶点的有序对

<v,w>

v是弧尾，w是弧头

v邻接到w或w邻接自v

无向图

无向边的有限集合

边是顶点的无序对

（v,w）

（v,w）=(w,v)

w，v互为邻接点

简单图

1.不存在顶点到自身的边

2.同一条边不重复出现

多重图

若图G中某两个结点之间的边数多于一条，又允许顶点通过通过同一个边和自己关联

完全图

无向完全图

如果任意两个顶点之间都存在边

有向完全图

如果任意两个顶点之间都存在方向相反的两条弧

子图

连通图：图中任意两个顶点都是连通的

连通分量：无向图中的极大连通子图

连通

顶点A到顶点B有路径

极大

1.顶点足够多

2.极大连通子图包含这些依附这些顶点的所有边

结论1:如果一个图有n个顶点，并且有小于n-1条边，则此图必是非连通图。

强连通：顶点V到顶点W和顶点W到顶点V都有路径

强连通图：图中任一对顶点都是强连通的

连通图的生成树：包含图中全部n个顶点，但是只有n-1条边的极小连通子图

结论2:生成树去掉一条边则变成非连通图，加上一条边就会形成回路。

度：以该顶点为一个端点的边数目

无向图中顶点V的度是指依附于该顶点的边的条数，记为TD(v)

有向图中顶点V的度分为出度和入度

入度（ID）是以顶点v为终点的有向边的数目

出度（OD）是以顶点V为起点的有向边的数目

简单路径和简单回路：顶点不重复出现的路径称为简单路径。对于回路，除了第一个和最后一个顶点其余顶点不重复出现的回路称为简单回路

权和网：图中每条边考研赋予一定意义的数值，这个数值叫做这条边的权，有权值得图称为带权图，也叫做网

路径和路径长度：顶点p到q之间的路径是指顶点序列怕保存的，p,a,b,c,d,……q。路径上边的数目就是路径长度

回路（环）：第一个和最后一个顶点相同的路径称为回路或者环

距离：从顶点u到v的最短路径长度。不存在路径则为无穷

图的存储结构

邻接矩阵（顺序存储）

邻接表（链式存储）

十字链表（有向图）

邻接多重表（无向图）

图的遍历

深度优先遍历

深度优先搜索(DFS:Depth-First-Search):深度优先搜索类似于树的先序遍历算法

空间复杂度：由于DFS是一个递归算法，递归是需要一个工作栈来辅助工作，最多需要图中所有顶点进栈，所以时间复杂度为O(|V|)

时间复杂度：1)邻接表：遍历过程的主要操作是对顶点遍历它的邻接点，由于通过访问边表来查找邻接点，所以时间复杂度为O(|E|),访问顶点时间为O(|V|),所以总的时间复杂度为O(|V|+|E|) 2)邻接矩阵：查找每个顶点的邻接点时间复杂度为O(|V|),对每个顶点都进行查找，所以总的时间复杂度为O(|V|2)

广度优先遍历

广度优先搜索(BFS:Breadth-First-Search):广度优先搜索类似于树的层序遍历算法

空间复杂度：BFS需要借助一个队列，n个顶点均需要入队一次，所以最坏情况下n个顶点在队列，那么则需要O(|V|)的空间复杂度。

时间复杂度： 1)邻接表：每个顶点入队一次，时间复杂度为O(|V|),对于每个顶点，搜索它的邻接点，就需要访问这个顶点的所有边，所以时间复杂度为O(|E|)。所以总的时间复杂度为O(|V|+|E|) 2)邻接矩阵：每个顶点入队一次，时间复杂度为O(|V|),对于每个顶点，搜索它的邻接点，需要遍历一遍矩阵的一行，所以时间复杂度为O(|V|),所以总的时间复杂度为O(|V|2)

图的应用

最小生成树

普利姆（Prlm）

①从图中找第一个起始顶点v0，作为生成树的第一个顶点，然后从这个顶点到其他顶点的所有边中选一条权值最小的边。然后把这条边的另一个顶点v和这条边加入到生成树中。

②对剩下的其他所有顶点，分别检查这些顶点与顶点v的权值是否比这些顶点在lowcost数组中对应的权值小，如果更小，则用较小的权值更新lowcost数组。

③从更新后的lowcost数组中继续挑选权值最小而且不在生成树中的边，然后加入到生成树。

④反复执行②③直到所有所有顶点都加入到生成树中。

克鲁斯卡尔（Kruskal）

将图中边按照权值从小到大排列，然后从最小的边开始扫描，设置一个边的集合来记录，如果该边并入不构成回路的话，则将该边并入当前生成树。直到所有的边都检测完为止。

最短路径

迪杰斯特拉

一个源点到其余顶点的最短路径

该算法设置一个集合S记录已求得的最短路径的顶点，可用一个数组s[]来实现，初始化为0，当s[vi]=1时表示将顶点vi放入S中，初始时把源点v0放入S中。此外，在构造过程中还设置了两个辅助数组： dist[]：记录了从源点v0到其他各顶点当前的最短路径长度，dist[i]初值为arcs[v0][i]。 path[]：path[i]表示从源点到顶点i之间的最短路径的前驱结点，在算法结束时，可根据其值追溯得到源点v0到顶点vi的最短路径。假设从顶点0出发，也就是顶点0为源点，集合S最初只包含顶点0，邻接矩阵arcs表示带权有向图，arcs[i][j]表示有向边<i，j>的权值，若不存在有向边<i，j>，则arcs[i][j]为∞。Dijkstra算法的步骤如下： 1）初始化：集合S初始为{0}，dist[]的初始值dist[i]=arcs[0][i]，i=1，2，…，n-1。 2）找出dist[]中的最小值dist[j]，将顶点j加入集合S，即修改s[vj]=1。 3）修改从v0出发到集合V-S上任一顶点vk可达的最短路径长度：如果dist[j] + arcs[j][k]< dist[k]，则令dist[k]=dist[j] + arcs[j][k]。另外更新path[k]=j(也就是顶点j加入集合之后如果有新的路径使得到顶点k路径变短的话就将到顶点k的路径长度修改成较短的) 4）重复2）～3）操作共n-1次，直到所有的顶点都包含在S中。

弗洛伊德

所有顶点到所有顶点的最短路径

算法思想：递推产生一个n阶方阵序列A(−1)，A(0)，…，A(k)，…，A(n−1) 其中A(k)[i][j]表示从顶点vi到顶点vj的路径长度，k表示绕行第k个顶点的运算步骤。初始时，对于任意两个顶点vi和vj，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以∞作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点k(k=0，1，…，n-1)作为中间顶点。如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径

非带权图

两点之间经过边数最少的路径

带权图

两点之间经过的边上权值之和最小的路径

拓扑排序

AOV

如果我们把每个环节看成图中一个顶点，在这样一个有向图中，用顶点表示活动，用弧表示活动之间的优先关系，那么这样的有向图称为AOV网(Activity On Vertex)

拓扑排序就是对一个有向图构造拓扑序列的过程，构造会有两种结果：如果此图全部顶点都被输出了，说明它是不存在回路的AOV网；如果没有输出全部顶点，则说明这个图存在回路，不是AOV网。

拓扑排序算法：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为弧尾的弧。重复这个步骤直到输出图中全部顶点，或者找不到入度为0的顶点为止。

关键路径

AOE(Activity On Edge):在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网称为AOE网。

第六章：查找

查找的基本概念和顺序查找

查找定义：在数据集合中寻找满足某种条件的数据元素的过程称为查找

关键字：数据元素中某个可以以唯一标识该元素的数据项

平均查找长度（ASL：Average Search Length）:在查找的过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值

顺序查找(线性查找)，主要用于在线性表中进行查找。从查找表的一端开始，顺序扫描查找表，依次将扫描到的关键字和待查找的值key进行比较。如果相等，则查找成功。如果扫描结束仍然没有发现相等的数据元素，则查找失败。

时间复杂度为O(n)

折半查找

算法思路：

首先将给定值key与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中。然后在缩小的范围内继续进行同样的查找，如此重复直到找到为止，或者确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。

折半查找分析

折半查找判定树

对于折半查找，查找的比较次数就是从根结点到该结点经历的结点数

时间复杂度为O(logn)

分块查找

分块查找又称为索引顺序查找

分块查找思想：

①确定待查找值在哪个块（折半查找） ②在确定的块中查找待查找值（顺序查找）

分块查找分析

由于分块查找实际是进行两次查找，所以整个算法的平均查找长度是两次查找的平均查找长度之和。即ASL分块=ASL折半+ASL顺序

二叉排序树

二叉排序树(Binary Search Tree 也叫二叉搜索树)或者是一棵空树，或者是具有以下性质的二叉树 ①若左子树不空，则左子树上所有结点的值均小于它的根结点的值。 ②若右子树不空，则右子树上所有结点的值均大于它的根结点的值。 ③它的左右子树也是一棵二叉排序树。

算法思想

由于二叉排序树的特点(左子树<根结点<右子树),所以每次查找一个关键字，需要先和根结点进行比较：如果这个关键字小于根结点的值，则再到这个根结点的左子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。如果这个关键字大于根结点的值，则再到这个根结点的右子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。

查找关键字代码

插入关键字代码

1)空树：直接插入新结点返回成功 2)树不空：检查是否存在关键字重复的结点： ①存在：返回插入失败 ②不存在：检查根结点的值和待插入关键字值的大小关系递归插入左右子树

构造代码

删除结点

①删除的是叶子结点

方法：直接删去该结点即可

②删除的是仅有左子树或者右子树的结点

方法：“子承父业”

③删除的是左右子树都有的结点

仿照②类型，先将一个孩子“继承父业”，另一个孩子“归顺”于这个孩子方法：找到待删除结点的直接前驱或者直接后继结点，用该结点来替换待删除结点，再删除该结点。

二叉排序树分析

查找时间复杂度是O(n)

平衡二叉树(AVL树)

平衡二叉树(AVL树)是特殊的二叉排序树，特殊的地方在于左右子树的高度之差绝对值不超过1，而且左右子树又是一棵平衡二叉树。

平衡因子

定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是−1、0或1。

平衡调整

平衡二叉树的建立过程和二叉排序树的建立过程是相似的，都是从一棵空树开始陆续插入结点。不同的地方在于对于平衡二叉树的建立过程中，由于插入结点可能会破坏结点的平衡性，所以需要进行平衡调整。

LL调整(左孩子的左子树上插入结点导致)

最小不平衡子树根结点的平衡因子为2>0 它的左孩子结点平衡因子为1>0 两个都大于0，所以直接右旋就可以调整

RR调整(右孩子的右子树上插入结点导致)

最小不平衡子树根结点的平衡因子为-2<0 它的右孩子结点平衡因子为-1<0 两个都小于0，所以直接左旋就可以调整

LR调整(左孩子的右子树上插入结点导致)

RL调整(右孩子的左子树上插入结点导致)

分析

含有n个结点平衡二叉树的最大深度为O(log2n)，因此，平衡二叉树的平均查找长度为O(log2n)

B树和B+树

2-3树

2-3树是一种多路查找树：2和3的意思就是2-3树包含两种结点

1)2结点包含一个元素和两个孩子(或者没有孩子)。 ①左子树包含的元素小于该结点的元素值，右子树包含的元素大于该结点的元素值 ②2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子

2)3结点包含一大一小两个元素和三个孩子(或者没有孩子)。(两个元素按大小顺序排列好) ①左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。 ②3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子

3)2-3树所有叶子结点都在同一层次

2-3-4树

2-3-4树也是一种多路查找树：2和3和4的意思就是2-3-4树包含三种结点

2)3结点包含一大一小两个元素和三个孩子(或者没有孩子)。 ①左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。 ②3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子

3)4结点包含小中大三个元素和四个孩子(或者没有孩子)。 ①左子树包含的元素小于该结点最小的元素值，第二个子树包含大于最小的元素值小于中间元素值的元素，第三个子树包含大于中间元素值小于最大元素值的元素，右子树包含的元素大于该结点最大的元素值。 ②4结点要不有四个孩子，要不就没有孩子，不允许有一个或两个或三个孩子

4)2-3-4树所有叶子结点都在同一层次

B树

B树也是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，我们把树中结点最大的孩子数目称为B树的阶。通常记为m。一棵m阶B树或为空树，或为满足如下特性的m叉树：

1）树中每个结点至多有m棵子树。（即至多含有m-1个关键字) ("两棵子树指针夹着一个关键字")

2）若根结点不是终端结点，则至少有两棵子树。(至少一个关键字)

3）除根结点外的所有非叶结点至少有 ⌈m/2⌉棵子树。（即至少含有⌈m/2⌉-1个关键字）

4）所有非叶结点的结构如下：

5）所有的叶子结点出现在同一层次上，不带信息。(就像是折半查找判断树中查找失败的结点)

1.B树的查找操作

查找过程：①先让待查找关键字key和结点的中的关键字比较，如果等于其中某个关键字，则查找成功。 ②如果和所有关键字都不相等，则看key处在哪个范围内，然后去对应的指针所指向的子树中查找。 Eg:如果Key比第一个关键字K1还小，则去P0指针所指向的子树中查找，如果比最后一个关键字Kn还大，则去Pn指针所指向的子树中查找。

2.B树的插入操作

分裂的方法：取这个关键字数组中的中间关键字(⌈n/2⌉)作为新的结点，然后其他关键字形成两个结点作为新结点的左右孩子。

3.B树的删除操作

B树中的删除操作与插入操作类似，但要稍微复杂些，要使得删除后的结点中的关键字个数≥⌈m/2⌉-1 ，因此将涉及结点的“合并”问题。由于删除的关键字位置不同，可以分为关键字在终端结点和不在终端结点上两种情况。

1）如果删除的关键字在终端结点上（最底层非叶子结点）： ①结点内关键字数量大于⌈m/2⌉-1 ，这时删除这个关键字不会破坏B树的定义要求。所以直接删除。 ②结点内关键字数量等于⌈m/2⌉-1 ，并且其左右兄弟结点中存在关键字数量大于⌈m/2⌉-1 的结点，则去兄弟阶段中借关键字。 ③结点内关键字数量等于⌈m/2⌉-1 ，并且其左右兄弟结点中不存在关键字数量大于⌈m/2⌉-1 的结点，则需要进行结点合并。

2）如果删除的关键字不在终端结点上（最底层非叶子结点）：需要先转换成在终端结点上，再按照在终端结点上的情况来分别考虑对应的方法。

相邻关键字：对于不在终端结点上的关键字,它的相邻关键字是其左子树中值最大的关键字或者右子树中值最小的关键字。

第一种情况：存在关键字数量大于⌈m/2⌉-1 的左子树或者右子树，在对应子树上找到该关键字的相邻关键字，然后将相邻关键字替换待删除的关键字。

第二种情况：左右子树的关键字数量均等于⌈m/2⌉-1 ，则将这两个左右子树结点合并，然后删除待删除关键字。

B+树

B+树是常用于数据库和操作系统的文件系统中的一种用于查找的数据结构

m阶的B+树与m阶的B树的主要差异在于： 1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有(n+1)棵子树。 2）在B+树中，每个结点（非根内部结点）关键字个数n的范围是 ⌈m/2⌉≤n≤m（根结点1≤n≤m），在B树中，每个结点（非根内部结点）关键字个数n的范围是⌈m/2⌉ -1≤n≤m-1（根结点：1≤n≤m-1）。 3）在B+树中，叶结点包含信息，所有非叶结点仅起到索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。 4）在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

散列表

散列表：根据给定的关键字来计算出关键字在表中的地址的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr。

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为“冲突”，这些发生碰撞的不同关键字称为同义词。

构造散列函数的tips：

1）散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。

2）散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间，从而减少冲突的发生。

3）散列函数应尽量简单，能够在较短的时间内就计算出任一关键字对应的散列地址。

1.常用Hash函数的构造方法：

1.开放定址法：直接取关键字的某个线性函数值为散列地址，散列函数为H(key)=a×key+b。式中，a和b是常数。这种方法计算最简单，并且不会产生冲突

2.除留余数法：假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字转换成散列地址。散列函数为H(key)=key % p 除留余数法的关键是选好p，使得每一个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性

3.数字分析法：设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，则应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合

4.平方取中法：顾名思义，取关键字的平方值的中间几位作为散列地址。具体取多少位要看实际情况而定。这种方法得到的散列地址与关键字的每一位都有关系，使得散列地址分布比较均匀。

5.折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以短一些），然后取这几部分的叠加和作为散列地址，这种方法称为折叠法。关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到散列地址。

2.常用Hash函数的冲突处理办法：

1.开放定址法：将产生冲突的Hash地址作为自变量，通过某种冲突解决函数得到一个新的空闲的Hash地址。

1）线性探测法：冲突发生时，顺序查看表中下一个单元（当探测到表尾地址m-1时，下一个探测地址是表首地址0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。

2）平方探测法：设发生冲突的地址为d,平方探测法得到的新的地址序列为d+12，d-12，d+22，d-22...... 平方探测法是一种较好的处理冲突的方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。

3）再散列法：又称为双散列法。需要使用两个散列函数，当通过第一个散列函数H(Key)得到的地址发生冲突时，则利用第二个散列函数Hash2(Key)计算该关键字的地址增量。

4）伪随机序列法：当发生地址冲突时，地址增量为伪随机数序列，称为伪随机序列法。

2.拉链法：对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。拉链法适用于经常进行插入和删除的情况。

3.散列表的查找过程：类似于构造散列表，给定一个关键字Key。先根据散列函数计算出其散列地址。然后检查散列地址位置有没有关键字。 1)如果没有，表明该关键字不存在，返回查找失败。 2)如果有，则检查该记录是否等于关键字。 ①如果等于关键字，返回查找成功。 ②如果不等于，则按照给定的冲突处理办法来计算下一个散列地址，再用该地址去执行上述过程。

4.散列表的查找性能：和装填因子有关。

α越大，表示装填的记录越“满”，发生冲突的可能性就越大，反之发生冲突的可能性越小

第七章：排序

排序的基本知识

定义：排序就是将原本无序的序列重新排列成有序的序列。

排序的稳定性

如果待排序表中有两个元素Ri、Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，如果使用某一排序算法排序后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

插入类排序

直接插入排序

直接插入排序：首先以一个元素为有序的序列，然后将后面的元素依次插入到有序的序列中合适的位置直到所有元素都插入有序序列。

时间复杂度为O(n)

直接插入排序是稳定性是稳定的。

折半插入排序

折半插入排序将比较和移动这两个操作分离出来，也就是先利用折半查找找到插入的位置，然后一次性移动元素，再插入该元素。

折半插入排序的时间复杂度为O(n^2)

稳定性：和直接插入排序稳定性相同，是稳定的。

希尔排序

希尔排序的基本思想：希尔排序本质上还是插入排序，只不过是把待排序序列分成几个子序列，再分别对这几个子序列进行直接插入排序。

①先以增量5来分割序列，也就是下标为0,5,10,15...的关键字分成一组，下标为1,6,11,16..分成一组,然后对这些组分别进行直接插入排序，这就完成了一轮希尔排序。

②缩小增量(d1=n/2，di+1= [di/2]，比如10个数据序列，第一次增量d1=10/2=5,第二次增量d2= [d1/2]= [5/2]=2,并且最后一个增量等于1),所以第二轮以增量为2进行类似的排序过程。

③接下来的第三轮，第四轮...都是类似的过程，直到最后一轮以增量为1。此时就是前面所说的直接插入排序。

时间复杂度：... 希尔排序的时间复杂度约为O(n^1.3) 在最坏情况下希尔排序的时间复杂度为O(n^2)

空间复杂度：希尔排序的空间复杂度为O(1)

稳定性：不稳定，由于不同的增量可能就会把相等的关键字划分到两个直接插入排序中进行排序，可能就会造成相对顺序变化。

交换类排序

冒泡排序

假设待排序表长为n，从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完。我们称它为一趟冒泡，结果将最小的元素交换到待排序列的第一个位置。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟冒泡的结果把序列中的最小元素放到了序列的最终位置，……，这样最多做n-1趟冒泡就能把所有元素排好序。

空间复杂度：交换时开辟了存储空间来存储中间变量，所以空间复杂度为O(1)

时间复杂度

稳定性：当两个关键字相等，if判断条件不成立，所以不会发生数据移动。所以是稳定的。

快速排序

快速排序是一种基于分治法的排序方法。每一趟快排选择序列中任一个元素作为枢轴(pivot)(通常选第一个元素)，将序列中比枢轴小的元素都移到枢轴前边，比枢轴大的元素都移到枢轴后边。

时间复杂度：最好情况下时间复杂度为O(nlogn) ,待排序序列越无序，算法效率越高。最坏情况下时间复杂度为O(n^2)，待排序序列越有序，算法效率越低。

空间复杂度：由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为 ⌈log2(n+1)⌉(每次partition都很均匀)递归树的深度O(logn) 最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n)；

稳定性：快速排序是不稳定的，是因为存在交换关键字。

选择类排序

简单选择排序

空间复杂度：需要额外的存储空间仅为交换元素时借助的中间变量，所以空间复杂度是O(1)

时间复杂度：关键操作在于交换元素操作，整个算法由双重循环组成，外层循环从0到n-2一共n-2+1=n-1次，对于第i层外层循环，内层循环执行n-1-(i+1)+1=n-i-1次。当i=0,内层循环执行n-1次，当i=n-2,内层循环执行1次，所以是一个等差数列求和,一共为(1+n-1)(n-1)/2=n(n-1)/2 ,所以时间复杂度为O(n^2)

稳定性：不稳定原因就在于交换部分会打破相对顺序

堆排序

什么是堆？

堆是一棵完全二叉树，而且满足任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。

如果是每个结点的值都不小于它的左右孩子结点的值，则称为大顶堆。

如果是每个结点的值都不大于它的左右孩子结点的值，则称为小顶堆。

什么是堆排序？

我们知道对于一个堆来说，它的根结点是整个堆中所有结点的值的最大值(大顶堆)或者最小值(小顶堆)。所以堆排序的思想就是每次将无序序列调节成一个堆，然后从堆中选择堆顶元素的值，这个值加入有序序列，无序序列减少一个，再反复调节无序序列，直到所有关键字都加入到有序序列。

时间复杂度：堆排序的总时间可以分为①建堆部分+②n-1次向下调整堆堆排序的时间复杂度为O(n)+O(nlog2n)=O(nlog2n)

堆排序不稳定

归并排序

假定待排序表含有n个记录，则可以看成是n个有序的子表，每个子表长度为1，然后两两归并，得到 ⌈n/2⌉个长度为2或1的有序表；再两两归并，……如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2-路归并排序。

例如：49 38 65 97 76 13 27

①首先将整个序列的每个关键字看成一个单独的有序的子序列

②两两归并，49和38归并成{38 49} ，65和97归并成{65 97}，76和13归并成{13 76}，27没有归并对象

③两两归并，{38 49}和{65 97}归并成{38 49 65 97}，{13,76}和27归并成{13 27 76}

④两两归并，{38 49 65 97}和{13 27 76}归并成{13 27 38 49 65 76 97}

时间复杂度：O(nlog2n)

空间复杂度:因为需要将这个待排序序列转存到一个数组，所以需要额外开辟大小为n的存储空间，即空间复杂度为O(n)

稳定性：稳定

基数排序

基数排序(也叫桶排序)是一种很特别的排序方法，它不是基于比较进行排序的，而是采用多关键字排序思想（即基于关键字各位的大小进行排序的），借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序。

例子：53, 3, 542, 748, 14, 214, 154, 63, 616

补充位数：053, 003, 542, 748, 014, 214, 154, 063, 616

桶实际是一个队列，先进先出(从桶的上面进，下面出)

关键字数量为n,关键字的位数为d,比如748 d=3，r为关键字的基的个数，就是组成关键字的数据的种类，比如十进制数字一共有0至9一共10个数字，即r=10

空间复杂度：需要开辟关键字基的个数个队列，所以空间复杂度为O(r)

时间复杂度：需要进行关键字位数d次"分配"和"收集"，一次"分配"需要将n个关键字放进各个队列中，一次"收集"需要将r个桶都收集一遍。所以一次"分配"和一次"收集"时间复杂度为O(n+r)。d次就需要O(d(n+r))的时间复杂度。

稳定性：由于是队列，先进先出的性质，所以在分配的时候是按照先后顺序分配，也就是稳定的，所以收集的时候也是保持稳定的。即基数排序是稳定的排序算法。

外部排序

需要将待排序的记录存储在外存上，排序时再把数据一部分一部分的调入内存进行排序。在排序过程中需要多次进行内存和外存之间的交换，对外存文件中的记录进行排序后的结果仍然被放到原有文件中。这种排序的方法就叫做外部排序。

如何得到初始的归并段

置换选择排序：解决排序段放入内存的问题

如何减少多个归并段的归并次数

最佳归并树：最少的归并次数（I/O次数）

如何每次m路归并快速得到最小的关键字

败者树：减少比较次数

二叉树与树与森林

树与二叉树

如何将一棵树转化成二叉树？

树的孩子兄弟表示法与二叉树的二叉链表表示法都是用到两个指针

将孩子兄弟表示法理解成二叉链表

树转换成二叉树的手动模拟方法：

①将同一结点的各个孩子用线串连起来

②将每个结点的子树分支，从左往右，除了第一个以外全部删除

如何将一棵二叉树转化成树？

二叉树转换成树的手动模拟方法：

①将二叉树从上到下分层，并调节成水平方向。 (分层方法：每遇到左孩子则为一层)

②找到每一层的双亲结点，方法为它的上一层相连的那个结点就是双亲结点。例如bcd这一层，与它相连的上一层结点即为a,所以bcd这三个结点的双亲结点都是a.

③将每一层结点和其双亲结点相连，同时删除该双亲结点各个孩子结点之间的联系。

森林与二叉树

森林：森林是m（m≥0）棵互不相交的树的集合

如何将森林转换成二叉树？

森林转换成树的手动模拟方法：

①将森林中每棵树都转换成二叉树

②将第二棵树作为第一棵树的根结点的右子树，将第三棵树作为第二棵树的根结点的右子树..依次类推

如何将二叉树转换成森林？

二叉树转换成森林的手动模拟方法：

反复断开二叉树根结点的右孩子的右子树指针，直到不存在根结点有右孩子的二叉树为止。

树与森林的遍历

先序：先访问根结点，再访问根结点的每棵子树。访问子树也是按照先序的要求

后序：先访问根结点的每棵子树，再访问根结点。访问子树也是按照先序的要求

树的先序遍历等于它对应二叉树的先序遍历，后序遍历等于它对应的二叉树的中序遍历