这本书我是在网上下载的电子版，所以可能会有一些错别字，但是无伤大雅；《大话数据结构》被誉为程序员面试必读书籍，我大概用了 3 天的时间详读了一遍，感觉作者的文笔很好，而且很擅长通过生活中的小故事总结相关知识和算法思路，对于计算机初级童鞋来说是一本很好的数据结构入门读物，而且作者对于代码的讲解很详尽，接近逐行解释了，和其他数据结构的书籍形成了鲜明的对比，总体评价五星吧；不过我是在刷完 Leetcode 的 easy 题才看的这本书，感觉先看这本书再刷题的话会好很多

一、数据结构与算法

1、如果你交给某人一个程序，你将折磨他一整天；如果你教某人如何编写程序，你将折磨他一辈子

2、数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科

3、数据元素的存储结构形式有两种：顺序存储和链式存储

• 顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的（谁也别插谁的队）
• 链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的（需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置）

4、算法具有五个基本特性：输入、输出、有穷性、确定性和可行性

5、好的算法，应该具有正确性、可读性、健壮性、高效率和低存储量的特征

6、推导时间复杂度大 O 阶方法：

1. 用常数 1 取代运行时间中的所有加法常数
2. 在修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数

7、循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数

8、常见的时间复杂度所耗费的时间：

9、最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。

在应用中，这是一种最重要的需求，通常，除非特别制定，我们提到的运行时间都是最坏情况的运行时间 平均运行时间是所有情况中最有意义的，因为它是期望的运行时间

10、算法的空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数

二、线性表

1、描述顺序存储结构需要三个属性：

• 存储空间的起始位置：数组 data，它的存储位置就是存储空间的存储位置
• 线性表的最大存储容量：数组长度 MaxSize
• 线性表的当前长度：length

2、插入算法的思路：

1. 如果插入位置不合理，抛出异常
2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
3. 从最后一个元素开始向前遍历到第 i 个位置，分别将它们都向后移动一个位置
4. 将要插入元素填入位置 i 处
5. 表长加 1

3、删除算法的思路：

1. 如果删除位置不合理，抛出异常
2. 取出删除元素
3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
4. 表长减 1

4、线性表的顺序存储结构的优缺点：

优点：

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素

缺点：

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的“碎片”

5、单链表

n 个结点（ai 的存储映像）链结成一个链表，即为线性表（a1,a2,…,an）的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起

有时，为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针：

6、头指针与头结点的异同

头指针

• 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
• 头指针具有标识作用，所以常用头指针冠以链表的名字
• 无论链表是否为空，头指针均不为空。头指针式链表的必要元素

头结点

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
• 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
• 头结点不一定是链表必须要素

7、获取链表第 i 个数据的算法思路

1. 声明一个结点 p 指向链表第一个结点，初始化 j 从 1 开始
2. 当 j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加 1
3. 若到链表末尾 p 为空，则说明第 i 个元素不存在
4. 否则查找成功，返回结点 p 的数据

8、单链表第 i 个数据插入结点的算法思路

1. 声明一结点 p 指向链表第一个结点，初始化 j 从 1 开始
2. 当 j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加 1
3. 若到链表末尾 p 为空，则说明第 i 个元素不存在
4. 否则查找成功，在系统中生成一个空结点 s
5. 将数据元素 e 赋值给 s -> data
6. 单链表的插入标准语句 s->next=p->next;p->next=s
7. 返回成功

9、单链表第 i 个数据删除结点的算法思路

1. 声明一结点 p 指向链表第一个结点，初始化 j 从 1 开始
2. 当 j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加 1
3. 若到链表末尾 p 为空，则说明第 i 个元素不存在
4. 否则查找成功，将欲删除的结点 p -> next 赋值给 q
5. 单链表的删除标准语句 p->next=q->next
6. 将 q 结点中的数据赋值给 e，作为返回
7. 释放 q 结点
8. 返回成功

10、单链表整表创建的算法思路

1. 声明一结点 p 和计数器变量 i
2. 初始化一空链表 L
3. 让 L 的头结点的指针指向 NULL，即建立一个带头结点的单链表
4. 循环：

• 生成一新结点赋值给 p
• 随机生成一数字赋值给 p 的数据域 p->data
• 将 p 插入到头结点与前一新节点之间

11、单链表的整表删除

1. 声明一结点 p 和 q
2. 将第一个结点赋值给 p
3. 循环：

• 将下一结点赋值给 q
• 释放 p
• 将 q 赋值给 p

12、单链表结构和顺序存储结构做对比

13、所谓的成功男人就是 3 岁时不尿裤子，5 岁能自己吃饭……80 岁能自己吃饭，90 岁能不尿裤子

14、循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list）:

循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断 p->next 是否为空，现在则是 p->next 不等于头结点，则循环未结束

15、合并两个循环链表

p=rearA->next;                   /* 保存A表的头结点，即① */
rearA->next=rearB->next->next;   /* 将本是指向B表的第一个结点（不是头结点） */
                                 /* 赋值给rearA->next，即 ②*/
rearB->next=p;                   /* 将原A表的头结点赋值给rearB->next，即③ */
free(p);                         /* 释放p */

16、双向链表

双向链表（double linked list）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域

17、双向链表的插入

假设存储元素 e 的结点为 s，要实现将结点 s 插入到结点 p 和 p->next 之间需要下面几步：

s->prior=p;           /* 把 p 赋值给 s 的前驱，如图中① */
s->next=p->next;      /* 把 p->next 赋值给 s 的后继，如图中② */
p->next->prior=s;     /* 把 s 赋值给 p->next 的前驱，如图中③ */
p->next=s;            /* 把 s 赋值给 p 的后继，如图中④ */

18、线性表的总结

三、栈与队列

1、栈的定义

栈（stack）是限定仅在表尾进行插入和删除操作的线性表，我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈

2、当栈存在一个元素时，top 等于 0，因此通常把空栈的判定条件定位 top 等于 -1（索引值从 0 开始）

3、用一个数组来存储两个栈

数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为 0 处，另一个栈为栈的末端，即下标为数组长度 n - 1 处。这样，如果两个栈增加元素，就是两端点向中间延伸

两个栈见面之时，也就是两个指针之间相差 1 时，即 top1 + 1 == top2为栈满

4、递归定义

一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数；每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出

5、队列定义

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表；允许插入的一端称为队尾，允许删除的一端称为队头

6、队列的链式存储结构

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列；队头指针指向链队列的头结点，而队尾指针指向终端结点：

空队列时，front 和 rear 都指向头结点

7、在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列

8、栈和队列的存储结构

9、关于栈和队列的人生感悟

人生，就像是一个很大的栈演变。出生时你赤条条地来到人世，慢慢地长大，渐渐地变老，最终还得赤条条地离开世间。
人生，又仿佛是一天一天小小的栈重现。童年父母每天抱你不断地进出家门，壮年你每天奔波于家与事业之间，老年你每天独自蹒跚于养老院的门里屋前。
人生，更需要有进栈出栈精神的体现。在哪里跌倒，就应该在哪里爬起来。无论陷入何等困境，只要抬头能仰望蓝天，就有希望，不断进取，你就可以让出头之日重现。困难不会永远存在，强者才能勇往直前。
人生，其实就是一个大大的队列演变。无知童年、快乐少年，稚傲青年，成熟中年，安逸晚年。
人生，又是一个又一个小小的队列重现。春夏秋冬轮回年年，早中晚夜循环天天。变化的是时间，不变的是你对未来执着的信念。
人生，更需要有队列精神的体现。南极到北极，不过是南纬90度到北纬90度的队列，如果你中途犹豫，临时转向，也许你就只能和企鹅相伴永远。可事实上，无论哪个方向，只要你坚持到底，你都可以到达终点。

四、串（字符串）

1、一首回文诗（李禺《两相思》）

枯眼望遥山隔水，
往来曾见几心知？
壶空怕酌一杯酒，
笔下难成和韵诗。
途路阻人离别久，
讯音无雁寄回迟。
孤灯夜守长寥寂，
夫忆妻兮父忆儿。

更多回文诗可以戳我一下

2、英语单词中的字符串

即使是 lover 也有个 over，即使是 friend 也有个 end，即使是 believe 也有个lie

3、关于字符串的一些概念

空格串：是只包含空格的串，空格串是有内容有长度的，而且可以不止一个空格
子串与主串：串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串
子串在主串中的位置：就是子串的第一个字符在主串中的序号

4、Unicode 和 ASCII 编码

计算机中的常用字符是使用标准的 ASCII 编码，更准确一点，由 7 位二进制数表示一个字符，总共可以表示 128 个字符。后来发现一些特殊符号的出现，128 个不够用，于是扩展 ASCII 码由 8 位二进制数表示一个字符，总共可以表示 256 个字符；可是换做全世界估计要有成百上千种语言与文字，显然这 256 个字符是不够的，因此后来就有了 Unicode 编码，比较常用的是由 16 位的二进制数表示一个字符，这样总共就可以表示 216 个字符，约是 65 万多个字符，足够表示世界上所有语言的所有字符了。当然，为了和 ASCII 码兼容，Unicode 的前 256 个字符与 ASCII 码完全相同

5、两个字符串的比较

给定两个串：s=”a1a2……an”，t=”b1b2……bm”，当满足以下条件之一时，s < t

• n < m，且 ai=bi（i=1，2，……n），例如当 s=”hap”，t=”happy”，就有 s < t。因为 t 比 s 多出了两个字母
• 存在某个 k ≤ min(m,n)，使得 ai = bi（i=1，2，……，,k-1），ak < bk，例如当 s=”happen”，t=”happy”，因为两串的前 4 个字母均相同，而两串第 5 个字母（k 值），字母 e 的 ASCII 码是 101，而字母 y 的 ASCII 码是 121，显然 e < y，所以 s < t

五、树

1、一些概念

• 结点拥有的子树数称为结点的度（Degree）；
• 度为 0 的结点称为叶节点（Leaf）或终端结点；
• 度不为 0 的结点称为非终端结点或分支结点；
• 除根结点之外，分支结点也成为内部结点树的度是树内各结点的度的最大值
• 树中结点的最大层次称为树的深度（Depth）或高度

2、线性表与树的结构

3、双亲表示法

以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置；由于根结点是没有双亲的，所以我们约定根结点的位置域设置为 -1：

这样的存储结构，我们可以根据结点的 parent 指针很容易找到它的双亲结点，知道 parent 为 -1 时，表示找到了树结点的根。可如果我们要知道结点的孩子是什么，需要遍历整个结构。

4、多重链表表示法

由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根节点，我们把这种方法叫做多重链表表示法；不过，树的每个结点的度，也就是孩子个数是不同的，所以可以设计两种方案来解决：

方案一：指针域的个数就等于树的度（树的度是树各个结点度的最大值）

其中 data 是数据域，child1 到 childd 是指针域，用来指向该结点的孩子结点，这种方法对于树中各结点的度相差很大时，显然是很浪费空间的，因为有很多的结点，它的指针域都是空的

方案二：每个结点指针域的个数等于该结点的度，我们专门取一个位置来存储结点指针域的个数

这种方法提升了空间利用率，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗

5、孩子表示法

把每个结点的孩子结点排列起来，以单链表作存储结构，则 n 个结点有 n 个孩子链表，如果是叶子结点则此单链表为空。然后 n 个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中：

6、双亲孩子表示法

7、孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟：

data 是数据域，firstchild 为指针域，存储该结点的第一个孩子结点的存储地址，rightsib 是指针域，存储该结点的右兄弟结点的存储地址，这个表示法的最大好处是它把一棵复杂的树变成了一棵二叉树

8、二叉树特点

• 每个结点最多有两棵子树，所以二叉树中不存在度大于 2 的结点（没有子树或者有一棵子树都是可以的）
• 左子树和右子树是有顺序的，次序不能任意颠倒
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

9、二叉树五种基本形态

1. 空二叉树
2. 只有一个根结点
3. 根结点只有左子树
4. 根结点只有右子树
5. 根结点既有左子树又有右子树

10、特殊二叉树

斜树

所有的结点都只有左子树的二叉树叫左斜树，所有结点都是只有右子树的二叉树叫右斜树，这两者统称为斜树

满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树

完全二叉树

对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i（1≤i≤n）的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树：

完全二叉树的特点：

• 叶子结点只能出现在最下两层
• 最下层的叶子一定集中在左部连续位置
• 倒数二层，若有叶子结点，一定都在右部连续位置
• 如果结点度为 1，则该节点只有左孩子，即不存在只有右子树的情况
• 同样结点数的二叉树，完全二叉树的深度最小

11、二叉树的性质

1. 在二叉树的第 i 层上至多有 2i-1 个结点（i ≥ 1）
2. 深度为 k 的二叉树至多有 2k-1 个结点（k ≥ 1）
3. 对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的节点数为 n2，则 n0 = n2 + 1（解释见下图）
4. 具有 n 个结点的完全二叉树的深度为 ⌊log2n⌋ + 1（⌊x⌋ 表示不大于 x 的最大整数）
5. 如果对一棵有 n 个结点的完全二叉树（其深度为 ⌊log2n⌋+1）的结点按层序编号（从第 1 层到第 ⌊log2n⌋ + 1 层，每层从左到右），对任一结点 i（1≤i≤n）有：

• 如果 i = 1，则结点i是二叉树的根，无双亲；如果 i > 1，则其双亲是结点 ⌊i / 2⌋
• 如果 2i > n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左结点是结点 2i
• 如果 2i + 1 > n，则结点 i 无右孩子；否则其右孩子是结点 2i + 1

12、二叉链表

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表：

其中 data 是数据域，lchild 和 rchild 都是指针域，分别存放指向左孩子和右孩子的指针

13、二叉树遍历方法

前序遍历

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树，遍历的顺序为：ABDGHCEIF

中序遍历

若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树，遍历的顺序为：GDHBAEICF

后序遍历

若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点，遍历的顺序为：GHDBIEFCA

层序遍历

若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序堆结点逐个访问，遍历的顺序为：ABCDEFGHI

14、两个二叉树遍历的性质

• 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树
• 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树
• 但是已知前序和后序遍历，是不能确定一棵二叉树的

15、线索二叉树

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

通过上图（空心箭头实线为前驱，虚线黑箭头为后继），可以看出，其实线索二叉树，等于是把一棵二叉树转变成了一个双向链表；所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化；但是，我们并不知道某一结点的 lchild 是指向它的左孩子还是指向前驱，所以需要一个区分标致；因此，我们在每个结点再增设两个标志域 ltag 和 rtag，这两个 tag 只是存放 0 或 1 数字的布尔型变量，其占用的内存空间要小于像 lchild 和 rchild 的指针变量，结点结构如下：

• ltag 为 0 时指向该结点的左孩子，为 1 时指向该结点的前驱
• rtag 为 0 时指向该结点的右孩子，为 1 时指向该结点的后继

如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择

16、树转换为二叉树

1. 加线，在所有兄弟结点之间加一条连线
2. 去线，对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线
3. 层次调整，以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明，注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子

17、森林转换为二叉树

1. 把每个树转换为二叉树
2. 第一棵二叉树不动，从第二棵二叉树开始，以此把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来，当所有的二叉树连接起来后就得到了由森林转换来的二叉树

18、二叉树转换为树

1. 加线，若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点……哈，反正就是左孩子的 n 个右孩子结点都作为此结点的孩子，将该结点与这些右孩子结点用线连接起来
2. 去线，删除原二叉树中所有结点与其右孩子结点的连线
3. 层次调整，使之结构层次分明

19、二叉树转换为森林

判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树

1. 从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有右孩子连线都删除为止，得到分离的二叉树
2. 再将每棵分离后的二叉树转换为树即可

20、树的遍历

1. 一种是先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树
2. 另一种是后根遍历，即先依次后根遍历每棵子树，然后再访问根结点

21、森林的遍历

1. 前序遍历：先访问森林中第一棵树的根结点，然后再依次先跟遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林
2. 后序遍历：是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林

森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树中的中序遍历结果相同

22、赫夫曼树算法描述

1. 根据给定的n个权值 {w1，w2，···wn} 构成 n 棵二叉树的集合 F={T1，T2，···Tn}，其中每个二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均为空。
2. 在 F 中选择两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
3. 在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。
4. 重复 2 和 3，直到 F 只含一棵树为止。这棵树便是赫夫曼树。

23、赫夫曼编码

一般地，设需要编码的字符集为 {d1，d2，···dn}，各个字符在电文中出现的次数或频率集合为 {w1，w2，···wn}，以 d1，d2，···dn 作为叶子结点，以 w1，w2，···wn 作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表 0，右分支代表 1，则从根结点到叶子结点所经过的路径分支组成的 0 和 1 的序列便为该结点对应字符的编码，这就是赫夫曼编码

六、图

1、图的定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合

2、关于图的一些定义

• 无向边：若顶点 vi 到 vj 之间的边没有方向，则称这条边为无向边（Edge），用无需偶对（vi，vj）来表示

• 有向边：若从顶点 vi 到 vj 的边有方向，则称这条边为有向边，也成为弧（Arc）
  无向边用小括号 “()” 表示，而有向边则是用尖括号 “<>” 表示

• 在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图

• 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图
• 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图
• 有很少条边或弧的图称为稀疏图，反之称为稠密图
• 这里稀疏和稠密是模糊的概念，是相对而言的 有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight）
• 带权的图通常称为网（Network）
• 假设有两个图 G =（V，{E}）和G’ =（V’，{E’}），如果 V’ ⊆ V 且 E’ ⊆ E，则称 G’ 为 G 的子图（Subgraph）
• 图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。
• 若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。
• 图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量 无向图中连通且n个顶点n-1条边叫生成树。
• 有向图中一顶点入度为0其余顶点入度为1的叫有向树。
• 一个有向图由若干棵有向树构成生成森林

由于定义实在太多，就不再叙述了，可以点击这里查看关于图的其他定义

3、图的邻接矩阵

图的邻接矩阵（Adiacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息 n 个顶点和 e 条边的无向网图的创建，时间复杂度为 O（n+n2+e），其中对邻接矩阵的初始化需要耗费 O（n2）的时间

4、邻接表

数组与链表相结合的存储方法称为邻接表 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息 图中每个顶点 vi 的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点 vi 的边表，有向图则称为顶点 vi 作为弧尾的出边表

若是有向图，邻接表结构是类似的，但我们是以顶点为弧尾来存储边表的，这样很容易就可以得到每个顶点的出度，但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表，即对每个顶点 vi 都建立一个链接为 vi 为弧头的表 对于带权值的网图，可以在边表结点定义中再增加一个 weight 的数据域，存储权值信息即可

5、图的遍历

从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）

6、深度优先遍历（DFS）

从图中某个顶点 v 出发，访问此顶点，然后从 v 的未被访问的邻接点出发深度优先遍历图，直至图中所有和 v 有路径相通的顶点都被访问到，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止

7、广度优先遍历（BFS）

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了，如下图所示：

8、图的两种遍历方式的比较

两者在时间复杂度上是一样的，不同之处仅仅在于对顶点访问的顺序不同，可见两者在全图遍历上是没有优劣之分的，只是视不同的情况选择不同的算法。不过，深度优先更适合目标比较明确，以找到目标为主要目的的情况，而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况

9、最小生成树

我们把构造连通网的最小代价生成树称为最小生成树（Minimum Cost Spanning Tree）
找连通网的最小生成树，经典的有两种算法，普利姆算法和克鲁斯卡尔算法

10、普利姆（Prim）算法

算法思路：

以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树

算法步骤：

1. 输入：一个加权连通图，其中顶点集合为 V，边集合为 E；
2. 初始化：Vnew = {x}，其中 x 为集合 V 中的任一节点（起始点），Enew = {}，为空；
3. 重复下列操作，直到 Vnew = V：

• 在集合 E 中选取权值最小的边 <u, v>，其中 u 为集合 Vnew 中的元素，而 v 不在 Vnew 集合当中，并且 v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
• 将 v 加入集合 Vnew 中，将 <u, v> 边加入集合 Enew 中；

4. 输出：使用集合 Vnew 和 Enew 来描述所得到的最小生成树。

书中有非常详尽的解释，但是感觉解释的比较繁琐，建议去看一下百度百科中的讲解

11、克鲁斯卡尔（Kruskal）算法

算法思路：

因为权值是在边上，所以直接去找最小权值的边来构建生成树，只不过构建时要考虑是否会形成环路而已

算法步骤：

先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。关于这个算法，百度百科上的讲解就不是很清楚了，如果感兴趣的话可以自行查阅其他资料

12、Prim 算法和 Kruskal 算法的对比

对比两个算法，克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以堆于稀疏图有很大的优势；而普利姆算法对于稠密图，即边数非常多的情况会更好一些

13、最短路径

对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点 主要有两种求最短路径的算法：迪杰斯特拉算法和

14、迪杰斯特拉（Dijkstra）算法

算法步骤：

G = {V,E}

1. 初始时令 S = {V0}, T = V - S = {其余顶点}，T 中顶点对应的距离值

若存在 <V0,Vi>，d(V0,Vi) 为 <V0,Vi> 弧上的权值

若不存在 <V0,Vi>，d(V0,Vi) 为 ∞

2. 从 T 中选取一个与 S 中顶点有关联边且权值最小的顶点 W，加入到 S 中

3. 对其余 T 中顶点的距离值进行修改：若加进 W 作中间顶点，从 V0 到 Vi 的距离值缩短，则修改此距离值

重复上述步骤 2、3，直到 S 中包含所有顶点，即 W = Vi 为止

15、弗洛伊德（Floyd）算法

算法步骤：

1. 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

2. 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

把图用邻接矩阵 G 表示出来，如果从 Vi 到 Vj 有路可达，则 G[i][j] = d，d 表示该路的长度；否则 G[i][j] = 无穷大。定义一个矩阵D用来记录所插入点的信息，D[i][j] 表示从 Vi 到 Vj 需要经过的点，初始化 D[i][j] = j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i][j] = min( G[i][j], G[i][k]+G[k][j])，如果 G[i][j] 的值变小，则 D[i][j] = k。在 G 中包含有两点之间最短道路的信息，而在 D 中则包含了最短通路径的信息。

比如，要寻找从 V5 到 V1 的路径。根据 D，假如 D(5,1) = 3 则说明从 V5 到 V1 经过 V3，路径为 {V5,V3,V1}，如果 D(5,3)=3，说明 V5 与 V3 直接相连，如果 D(3,1) = 1，说明 V3 与 V1 直接相连。

16、拓扑排序

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为 AOV 网（Activity On Vertex Network）
拓扑序列：设 G = (V,E)是一个具有 n 个顶点的有向图，V 中的顶点序列 V1，V2，……，Vn，满足若从顶点 Vi 到 Vj 有一条路径，则在顶点序列中顶点 Vi 必在顶点 Vj 之前。则我们称这样的顶点序列为一个拓扑序列
拓扑排序：其实就是对一个有向图构造拓扑序列的过程；构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环（回路）的 AOV 网；如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环（回路），不是 AOV 网。

17、拓扑排序算法

对 AOV 网进行拓扑排序的基本思路是：从 AOV 网中选择一个入度为 0 的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者 AOV 网中不存在入度为 0 的顶点为止

18、关键路径

在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为 AOE 网（Activity On Edge Network）；我们把 AOE 网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点；正常情况下，AOE 网只有一个源点一个汇点，我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动

19、关键路径算法

原理：我们只需要找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径。如果不等，则就不是。为此，我们需要定义如下几个参数：

1. 事件的最早发生时间etv（earliest time of vertex）：即顶点 Vk 的最早发生时间
2. 事件的最晚发生时间ltv（latest time of vertex）：即顶点 Vk 的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期
3. 活动的最早开工时间ete（earliest time of edge）：即弧 ak 的最早发生时间
4. 活动的最晚开工时间lte（latest time of edge）：即弧 ak 的最晚发生时间，也就是不推迟工期的最晚开工时间

我们是由 1 和 2 可以求得 3 和 4，然后再根据 ete[k] 是否与 lte[k] 相等来判断 ak 是否是关键活动

20、世界上最遥远的距离……

世界上最遥远的距离，不是从南极到北极，而是我在讲解算法为何如此精妙，你却能够安详在课堂上休息。
世界上最遥远的距离，不是珠峰与马里亚纳海沟的距离，而是我欲把古人的智慧全盘给你，你却不屑一顾毫不怜惜。
世界上最遥远的距离，不是牛 A 与牛 C 之间狭小空隙，而是你们当中，有人在通往牛逼的路上一路狂奔，而有人步入大学校园就学会放弃。

七、查找

1、查找概论

• 查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合
• 关键字（Key）是数据元素中某个数据项的值，又称为键值
• 若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary Key）
• 那些可以识别多个数据元素（或记录）的关键字，我们称为次关键字（Secondary Key）
• 查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值得数据元素（或记录）

2、查找表操作方式

分为两大种：静态查找表和动态查找表 静态查找表（Static Search Table）：只作查找操作的查找表。它的主要操作有：

• 查询某个“特定的”数据元素是否在查找表中
• 检索某个“特定的”数据元素和各种属性

动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。显然动态查找表的操作就是两个：

• 查找时插入数据元素
• 查找时删除数据元素

3、顺序查找

顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是： 从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

4、二分查找

折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是： 在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止

5、插值查找

插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式 (key-a[low])/(a[high]-a[low])，对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多

6、斐波那契查找算法

算法核心：

1. 当 key = a[mid] 时，查找就成功
2. 当 key < a[mid] 时，新范围是第 low 个到第 mid - 1 个，此时范围个数为 F[k-1] - 1 个
3. 当 key > a[mid] 时，新范围是第 m + 1 个到第 high 个，此时范围个数为 F[k-2] - 1 个

7、三种查找算法的比较

折半查找是进行加法与除法运算 (mid = (low + high) / 2)，插值查找进行复杂的四则运算(mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]))，而斐波那契查找只是最简单加减法运算(mid = low + F[k-1] - 1)，在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率

8、线性索引

索引就是把一个关键字与它对应的记录相关联的过程 所谓线性索引就是将索引项集合组织为线性结构，也称为索引表 三种线性索引：稠密索引、分块索引和倒排索引

9、稠密索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项

对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列 索引项有序也就意味着，我们要查找关键字时，可以用到折半、插值、斐波那契等有序查找算法，大大提高了效率

10、分块索引

分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：

• 块内无序：当然如果能够让块内有序对查找来说更理想
• 块间有序：只有块间有序，才有可能在查找时带来效率

分块索引的索引项结构分三个数据项：

• 最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大
• 存储了块中的记录个数，以便于循环时使用
• 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历

分块索引表中查找的步骤：

1. 在分块索引表中查找要查关键字所在的块，可以利用折半、插值等算法
2. 根据块首指针找到响应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找

11、倒排索引

记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字），这样的索引方法就是倒排索引（inverted index） 倒排索引的优点就是查找记录非常快，基本等于生成索引表后，查找时都不用去读取记录，就可以得到结果。但它的缺点是这个记录号不定长

12、二叉排序树

二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树

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

如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树。

13、平衡二叉树

平衡二叉树（Self-Balancing Binary Search Tree或Height-Balanced Binary Search Tree），是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于 1；我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor），那么平衡二叉树上所有结点的平衡因子只可能是 -1，0，1

14、最小不平衡子树

距离插入结点最近的，且平衡因子的绝对值大于 1 的结点为根的子树，我们称为最小不平衡子树

如上图所示，当新插入结点 37 时，距离它最近的平衡因子绝对值超过 1 的结点是 58（即它的左子树高度 2 减去右子树高度 0），所以从 58 开始以下的子树为最小不平衡子树

15、平衡二叉树实现算法

算法原理：

基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应地旋转，使之成为新的平衡子树

右旋操作：

左旋和右旋代码是对称的

16、多路查找树

多路查找树（multi-way search tree），其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素

17、2-3 树

2-3 树是这样的一棵多路查找树：其中的每一个结点都具有两个孩子（我们称它为2结点）或三个孩子（我们称它为 3 结点）。

• 一个 2 结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似
• 一个 3 结点包含一小一大两个元素和三个孩子（或没有孩子），左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素
• 2-3 树中所有的叶子都在同一层次上

18、2-3树的插入实现

可分为三种情况：

1. 对于空树，插入一个 2 结点即可，这很容易理解
2. 插入结点到一个 2 结点的叶子上。由于其本身就只有一个元素，所以只需要将其升级为 3 结点即可
3. 要往 3 结点中插入一个新元素。因为 3 结点本身已经是 2-3 树的结点最大容量（已经有两个元素），因此就需要将其拆分，且将树中两元素或插入元素的三者中选择其一向上移动一层

19、2-3-4树

就是 2-3 树的概念扩展，包括了 4 结点的使用。一个4结点包含小中大三个元素和四个孩子（或没有孩子），一个 4 结点要么没有孩子，要么具有 4 个孩子。如果某个 4 结点有孩子的话，从左到右按照由小到大的顺序排列

20、B树

B树（B-tree）是一种平衡的多路查找树，2-3树和 2-3-4树都是 B树的特例。结点最大的孩子数目称为 B树的阶（order），因此，2-3树是 3 阶 B树，2-3-4树是 4 阶 B树

一个 m 阶的 B 树具有如下属性：

• 如果根结点不是叶节点，则其至少有两棵子树
• 每一个非根的分支结点都有 k-1 个元素和k个孩子，其中 ⌈m/2⌉ ≤ k ≤ m。每一个叶子节点 n 都有 k - 1 个元素，其中 ⌈m/2⌉ ≤ k ≤m
• 所有叶子结点都位于同一层次
• 所有分支结点包含下列信息数据（n,A0,K1,A1,K2,A2,…,Kn,An），其中：Ki(i=1,2,…,n) 为关键字，且 Ki<Ki+1(i=1,2,…,n-1)；Ai(i=0,2,…,n) 为指向子树根结点的指针，且指针 A(i-1) 所指子树中所有结点的关键字均小于 Ki(i=1,2,…,n),An 所指子树中所有结点的关键字均大于 Kn，n·(⌈m/2⌉-1≤n≤m-1) 为关键字的个数（或 n + 1 为子树的个数）

21、B+树

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

一棵 m 阶的 B+树和 m 阶的 B树的差异在于：

• 有 n 棵子树的结点中包含有 n 个关键字
• 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接
• 所有分支结点可以看成是索引，结点中仅含有其子树中的最大（或最小）关键字

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

22、散列表（哈希表）

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f(key)，散列技术既是一种存储方法，也是一种查找方法
散列技术最适合的求解问题是查找与给定值相等的记录 f称为散列函数，又称为哈希（Hash）函数
采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）

散列过程有两步：

1. 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录
2. 当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录

23、散列函数构造方法

直接定址法

取关键字的某个线性函数值为散列地址

数字分析法

如果我们的关键字是位数较多的数字，可以对数字进行翻转、右环位移、左环位移、甚至前两数与后两数叠加等方法，合理地将关键字分配到散列表的各位置

平方取中法

假设关键字是 1234，那么它的平方就是 1522756，再抽取中间的 3 位就是 227，用做散列地址。平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况

折叠法

将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址.折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况 比如我们的关键字是 9876543210，散列表表长为三位，我们将它分为四组，987|654|321|0，然后将它们叠加求和 987 + 654 + 321 + 0 = 1962，再求后 3 位得到散列地址为 962。

除留余数法

对关键字直接取模，也可在折叠、平方取中后再取模，对于散列表长为 m 的散列函数公式为：

f(key)=key mod p(p≤m)

根据前辈们的经验，若散列表表长为 m，通常 p 为小于或等于表长（最好接近 m）的最小质数或不包含小于 20 质因子的合数

随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址

24、采用不同的散列函数应该考虑的因素

• 计算散列地址所需的时间
• 关键字的长度
• 散列表的大小
• 关键字的分布情况
• 记录查找的频率

25、处理散列冲突的方法

开放定址法

一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入，公式是：

fi(key)=（f(key)+di）MOD m(di=1,2,3,……,m-1)

这种解决冲突的开放定址法称为线性探测法
如果 di 改进为正负两类值，等于是可以双向寻找到可能的空位置，可以不让关键字都聚集在某一块区域。我们称这种方法为二次探测法
如果 di 采用随机函数计算得到，我们称之为随机探测法

再散列函数法

我们事先准备多个散列函数，每当发生散列地址冲突时，就换一个散列函数计算，相信总会有一个可以把冲突解决掉

链地址法

将所有关键字为同义词的记录存储在一个单链表红，我们称这种表尾同义词子表，在散列表中只存储所有同义词子表的头指针

公共溢出区法

凡是冲突的都将它们存储到溢出表中

八、排序

关于排序，推荐我的另一篇文章：十大排序算法的Javascript实现，这篇文章里有一些常见排序算法的实现步骤以及演示，是一个比较好的排序算法讲解

九、总结

1、数据结构和算法

数据结构和算法对于程序员的职业人生来说，那就是两个圆圈的交集部分，用心去掌握它，你的编程之路将会是坦途