本帖最后由 miaohangbo 于 2018-12-19 13:46 编辑
第三部分
7、树（tree） 树是n个节点的有限集合。n=0时为空树；在任意的树中有且仅有一个称为根节点的，当n>1时，其余节点分为m个互不相交的有限集合（T1,T2......Tm）;每个树的本身又是一棵树，并且称为根的子树；
7.1结点分类： 根节点、叶节点、度 7.2 结点关系： 双亲、孩子、兄弟
7.3其他概念 层次、深度、有序树、无序树、森林。 从根节点开始为第一层，孩子为第二层等等，从根到叶子层数为深度或高度。（最大）
树中各子树从做右使有序的，有序树。m个（m>=0）个互不相交的树的集合，即森林。
线性结构与树结构
7.4树的存储结构： 顺序存储结构中结点的位置无法反映结点之间的逻辑关系，所有利用顺序存储结构和链式存储结构的特点，可以实现对树的表示。双亲表示法、孩子表示法、孩子兄弟表示法。 7.4.1双亲表示法：除了数据，每个结点设置一个指向双亲节点的位置。 节点结构
找双亲时间复杂度O(1);找孩子需要遍历整个树O(n)。
7.4.2孩子表示法：考虑有多个孩子的情况，用多指针域，指向多个孩子。（多重链表表示法）
方案一：孩子的个数就是树的度。
缺点：度相差大时候浪费空间，因为指针域为空。 优点：度相差小时候节省空间。
方案二： degree度域表示该结点度，存储孩子结点的个数。
空间利用率高，但是也带来维护度的开销。
孩子表示法： 每个节点的孩子节点用单链表，n个结点有n个孩子单链表，n个头节点组成的顺序表采用顺序存储结构，存放在一个一维数组中。
表头数组的头结点：data数据域，firstchild头指针域 表示孩子结点：child数据域、next指针
要找双亲怎么办？改进的 孩子双亲表示法
7.4.3孩子兄弟表示法：当两个指针指向是唯一的。
查找孩子比较容易，查找双亲比较麻烦，可以增加指向双亲指针。
7.5二叉树
7.5.1概念
有一个根节点或者有两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成。（折半查找）某个阶段只有两种结果的情形（开关、上下、大小、0和1、正和反）都适合用树状结构建模。
7.5.2特点 1. 每个结点最多有两个子树，度不大于2； 2. 左右子树是有序的； 3. 即使只有一个子树，也是有序的；
7.5.3形态 三个结点五种形态： 7.5.4特殊的二叉树 4. 斜树：左斜树（只有左子树）、右斜树。 5. 满二叉树：叶子出现在最下一层；非叶子结点度必须为2；与同深度树比较，满二叉树叶子节点最多，结点也最多。 6. 完全二叉树：完全二叉树结点编号位置与满二叉树结点位置相同。 7.5.5二叉树性质
如下：n2 = 4,n0=5 n1=1;n0=n2+1;(推到过程见书p194)
7.5.6存储结构 a、顺序存储结构：用一个一维数组存储二叉树结点。一般只用于完全二叉树。 完全二叉树：
一般二叉树：
极端二叉树：（斜树）
b、链式存储：二叉链表，及一个数据域两个指针域。
7.5.7二叉树遍历 从根节点出发，按照某种次序依次访问二叉树所有结点，每个结点被访问一次且仅访问一次。 访问方法：前序、中序、后续。 a、前序遍历：ABDGHCEIF（先根-左-右） b、中序遍历：GDHBAEICF（先左-根-右） c、后序遍历：GHDBIEFCA（先左-右-根） d、层序遍历：ABCDEFGHI（先根-第一层-......-第n层） 遍历代码算法实现：前序、中序、后序；（递归） 推导遍历： 前序遍历：ABCDEF 中序遍历：CBAEDF 已知前序和中序、中序和后序是能确定一个二叉树的。
7.5.8线索二叉树 指向前驱和后继的指针称为线索。线索链表，线索二叉树。 因为n个结点的二叉树有n+1个空指针
线索化：对二叉树的某种遍历使其变为线索二叉树过程。
7.5.9树、森林与二叉树转换 树转化为二叉树 森林转化为二叉树 二叉树转化为树 二叉树转换为森林
7.6赫夫曼树及其应用 最基本的压缩编码方法-赫夫曼编码。 赫夫曼树（美国数学家赫夫曼1952年发明赫夫曼编码）在赫夫曼编码中用的特殊的二叉树称为赫夫曼树 7.6.1赫夫曼树定义域原理 路径长度：从树中一个结点到另一个结点之间分支构成两个结点之间的路径，路径上分支数目就称为路径长度。 树的路径长度就是从根到每一个结点的路径长度之和。 例子：学生成绩，A表示不及格、B表示及格、C表示中等、D表示良好、E表示优秀。
路径长度： a树：1+1+2+2+3+3+4+4=20 b树：1+2+3+3+2+1+2+2=16
带权路径长度WPL最小的二叉树称为赫夫曼树。 a树WPL=5*1+15*2+40*3+30*4+10*4=315； b树WPL=5*3+15*3+40*2+30*2+10*2=220;
结论：10000名学生做分数统计：a树需要33500次；b树需要22000次。
7.6.2赫夫曼树构造： A5、E10、B15、D30、C40
WPL=40*1+30*2+15*3+10*4+5*4=205;
7.6.3赫夫曼编码 主要是为了解决远距离通信（当年电报）数据传输最优化问题。 例子：ABCDEF;字母使用频率A-27、B-8、C-15、D-15、E-30、F-5; 构建好的赫夫曼树，然后将权值替换为左0右1。 对六个字母从根到叶子编码后，如下图 对BADCADFEED编码： 原编码二进制串：001000011010000011101100100011(共30个字符串) 新编码二进制串：1001010010101001000111100(共25个字符串) 很明显数据压缩了，长度不一容易混淆，前缀编码可解决该问题，即任何一个编码都不其他编码的前缀。同时发送方和接收方需要约定好编码规则。
解码：如1001代表B,01代表A等等。
8、图 8.1概念 由顶点的所有有穷非空集合和顶点之间边的有穷集合组成，通常表示为G(V，E)；G表示图，V表示图中顶点集合，E表示图中边的集合。 注意：线性表、树、图的叫法。 线性表中数据称为数据元素、树中的数据元素称为结点、图中称为顶点。线性表可以为空表、树可以为空树，图的顶点不能为空。线性表中相邻数据元素是线性关系，树中数据元素是层次关系。
概念： 无向边、有向边（弧（弧头、弧尾））、简单图、无向完全图、有向完全图、稀疏图、稠密图、网等等。
8.2图的存储结构 邻接矩阵（二维数组）： 邻接表：缺点对于边和顶点较少的图是浪费；链式存储 无向图的邻接表 逆邻接表
十字链表： 邻接多重表： 边集数组：关注边的集合。应用Kruskal（克鲁斯卡尔）
8.3图的遍历 从图中某个节点触发，访问其他结点，且每个结点纸杯访问一次。深度优先DFS，广度优先BFS。
8.4最小生成树 Prim算法、Kruskal算法
8.5拓扑排序 无环图；拓扑排序算法
8.6关键路径 AOV网、AOE网
9、查找 9.1概念 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。 查找表：同一类型的数据元素构成的集合。 关键字：数据元素中某个数据项的值。 主关键字： 次关键字： 按照操作方式分：静态查找表（只做查找操作）、动态查找表（查找时插入或删除）
9.2顺序表查找 也叫线性表查找。从第一个开始找。 时间复杂度O(n) 9.3有序表查找 折半查找（二分查找）：O(logn) 插入查找（适用于表长大，关键字分布均匀）:O(logn) 斐波那契查找； 9.4线性索引查找 线性索引（稠密索引O(n)、分块索引（快内无序，块间有序）、倒排索引） 树形索引 多级索引 9.5二叉排序树 二叉排序树：（二差查找树），空树或者具有以下性质的树 （1）若左子树不为空则，左子树都小于他根节点的值； （2）若右子树不为空，则右子树都大于他根节点的值； （3）左右子树各为二叉排序树。 二差排序树是以链接发方式存储，保持插入删除不用移动其他数据元素。插入和删除时间性能比较好，查找取决于二叉树的树形。 时间复杂度O(logn) 9.6平衡二叉树 平衡二叉树（AVL）:是一个平衡二叉树，左右子树高度差至多是1。（平衡因子-1、0、1）。 平衡二叉树原理及实现：每插入一个结点都会检查树的平衡性。如不平衡则调整为平衡。
9.7多路查找树（B树） 多路查找树（B树）：每一个节点存储的孩子数可以多以两个，且每一个节点可以存储多个数据元素。 包含2-3树，2-3-4树，B树，B+树 2-3树：是每个节点都有2个孩子或3个孩子。 一个2结点包含一个元素和2个孩子。 一个3结点包含一大一小两个元素和三个孩子。 注意：2-3树所有结点都在一个层次上。新结点插入和已有结点删除复杂。在插入和删除的时候树是要调整的。 2-3-4树：一个4个结点包含小中大三个元素和4个孩子（或没有孩子）。
B树：2-3树、2-3-4树是B树特例。一个平衡查找树，结点最大的孩子数目称为B树的阶；2-3树3阶，2-3-4树是4阶；（为了将大型数据库文件存储在硬盘上 以减少访问硬盘次数为目的在此提出了一种平衡多路查找树——B-树结构 由其性能分析可知它的检索效率是相当高的） B+树：B树的顺序查找需要多次往返于页面和硬盘之间。B+树不知严格意义上的树，在叶子结点上加入下一叶子结点的指针。（目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构， 在 MySQL 中，主要有四种类型的索引，分别为： B-Tree 索引， Hash 索引，Fulltext 索引和 R-Tree 索引。我们主要分析B-Tree索引。 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree； InnoDB索引和MyISAM索引的区别：一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别） B+树与B-树应用可参见：http://blog.csdn.net/hijiankang/article/details/9166451
9.8散列表查找 9.8.1 基础 散列技术：是记录存储的位置和他的关键字存在一个确定的对应关系f,使得每个关键字key都能对应有一个存储位置f（key）。存储方法和查找方法。关系f称为散列函数，采用散列技术将记录存储到一块连续的存储空间，这个连续的存储空间称为散列表。散列技术即使一种存储方法也是一种查找方法。 存储位置=f(关键字) key1与key2不等，但是f(key1)=f(key2)则key1和key2是f的同义词，这种称为冲突。 9.8.2构造方法 好的散列函数应该：计算简单，地址分布均匀。 散列构造方法如下： 直接地址法： 数学分析法： 平方取中法： 折叠法： 除留余数法： 随机数法：
9.8.3处理冲突方法 一： 开发地址法（线性探测法）：如果冲突，则寻找下一个空闲地址。 线性探测法容易产生堆积（本来不私活同义词但是却争夺同一个地址的情况），所以有二次探测法 二次探测法： 随机探测法：di是随机获取的。 二： 再次探测法：准备多个不同的RHi函数，产生冲突时调用下一个。
三： 链地址法：不会出现找不到地址情况，查找需要遍历单链表查询。 四： 公共溢出区法： 9.8.4散列表查找 查找时间复杂度O(1)
10、排序 10.1概念 排序：使序列按关键字有序。排序的稳定性 内排序（内存中）：时间性能、辅助空间，算法复杂性。（分为插入排序、交换排序、选择排序、归并排序） 外排序（内存与外存交互） 按照算法复杂度分两大类： 简单算法：冒泡排序、简单排序、直接插入排序 改进算法：快速排序、堆排序、希尔排序、堆排序、归并排序
10.2简单算法 10.2.1冒泡排序 冒泡排序：一种交换排序，两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止。 例子： 优化：正常冒泡排序，优化方案是只记录最小和当前位置，最后在交换。 时间复杂度：O(n^2)
10.2.2选择排序 简单选择排序：通过n-i次关键字比较，从n-i+1记录中选择最小关键字记录，并与i交换。时间复杂度O(n^2),性能优于冒泡（省去频繁交换）。 例子： 时间复杂度：O(n^2)，性能要好于冒泡
10.2.3直接插入排序 直接插入排序：在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。 例子： 时间复杂度O(n^2);要比冒泡和简单排序好一些。
10.3改进算法 10.3.1希尔排序 希尔排序：算法先将要排序的一组数按某个增量d（n/2,n为要排序数的 个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。 是一种不稳定的排序算法。最后的增量序列值必须是1。 例子： 时间复杂度：O(n^(3/2))
10.3.2堆排序 堆排序（完全二叉树）：每个结点都大于或等于其左右孩子的值，大顶堆；（小顶堆）；时间复杂度O(nlogn);不稳定的排序算法。
例子：46、79、56、38、40、84 第一步建堆 第二步堆中提出最大 第三步
10.3.3归并排序 归并排序：假设初始n个记录有序，每个子序列长度为1，两两归并得到n/2个有序的序列，在两两序列归并，直到长度为n的序列为止。 例子： 时间复杂度O(nlogn);空间复杂度O(n+logn);比较占内存，效率高且稳定的算法。
10.3.4快速排序 快速排序：（不稳定排序）通过一次排序将待排序序列分成独立的两部分，其中一部分记录均比另一部分小，继续对这两部分使用该排序方法。 例子：
时间复杂度O(nlogn);空间复杂度O(logn)
基数排序 基数排序：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。 例子：
11、结尾语
数据结构和算法对于程序员的职业人生来说就是圈的交集部分，用心掌握它，编程之路才会平坦。
| 
收藏
淘帖
踩
牛逼了~~~全是干货
