导图社区 408数据结构总结
- 501
- 80
- 19
- 举报
408数据结构总结
数据结构是计算机的基础学科，也是考研408科目中难度较大的一科。21考研时自己一路总结了考研数据结构的知识体系，希望对后来人有所帮助。
编辑于2021-04-06 16:18:44- 相似推荐
- 大纲
数据结构
第一章 绪论
第二章线性表
线性表是具有相同数据类型的n 个数据元素的有限序列，它具有线性有序的逻辑结构。注意线性表是逻辑结构，而顺序表和链表是存储结构，它们是不同层面上的概念
线性表的顺序表示
顺序表
用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻
特点
逻辑顺序与其物理顺序相同
可实现随机访问
存储密度高，每个结点只存储数据元素
插入和删除需要移动大量元素
基本操作
插入、删除的平均时间复杂度均为o(n)
按值查找的最好情况：查找的元素就在表头，时间复杂度为o(1) ；最差情况，查找的元素在表尾或者不存在，时间复杂度为o(n)
链表
通过一组任意的存储单元来存储线性表中的数据元素
特点
不要求逻辑上相邻则物理上也相邻，插入删除无需移动元素，只需修改指针
失去顺序表随机存取的优点，只能顺序存取
结点分为数据域和指针域
通常用头指针来标识一个单链表
单链表上基本操作
第三章栈和队列
栈
栈是一种操作受限，即只能在某一端进行插入和删除操作的线性表，操作特性是后进先出LIFO
顺序存储结构
顺序栈
利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，附设一个指针top 指示当前栈顶元素的位置
共享栈
利用栈底位置相对不变的特性，可让两个顺序栈共享一个一位数组空间
有效利用了存储空间，降低了发生上溢的可能（只有在整个存储空间被占满时才发生上溢）
链式存储结构
便于多个栈共享存储空间和提高其效率，不存在栈满上溢的情况
规定链栈没有头结点，Lhead 指向栈顶元素
采用链式存储便于结点的插入和删除，其操作与链表类似，入栈和出栈都在链表的表头进行
重要
栈的卡特兰数公式：n 个不同元素进栈，出栈元素不同排列的个数为2n 中选n 的组合数除以n+1 分之1
队列
队列也是一种操作受限的线性表，只允许在表的一端进行插入，另一端进行删除，其操作特性是FIFO
顺序存储结构
顺序存储
分配一块连续的存储单元存放队列中的元素，并附设队头指针和队尾指针
循环队列
把存储队列元素的表从逻辑上视为一个环
队空和队满时都将有：Q.front==Q.rear
区分队满/ 队空的方法
牺牲一个单元来区分队空和队满，约定以“队头指针在队尾指针的下一位置作为队满的标志”
队满条件：（Q.rear+1 ）%MaxSize==Q.front
队空条件：Q.front==Q.rear
队列长度：(Q.rear-Q.front+maxsize)%maxsize
类型中增设表示元素个数的数据成员
类型中增设tag 数据成员，以区分是队满还是队空。tag 为0 时若因删除导致上述条件则为队空，tag 为1 时若因插入导致上述条件则为队满
链式存储结构
实际上是一个同时带有队头指针和队尾指针的单链表，头指针指向队头结点，尾指针指向队尾结点即单链表的最后一个结点
通常将链式队列设计成带头结点的单链表
双端队列
允许两端都可以进行入队和出队操作的队列
输出受限的双端队列
允许在一段进行插入和删除，但在另一端只允许插入的双端队列
输入受限的双端队列
允许在一端进行插入和删除，但在另一端只允许删除的双端队列
栈和队列的应用
栈的应用
括号匹配
用栈实现原理：设置空栈，顺序读入括号，若为左括号直接进栈，若为右括号则要么匹配栈顶括号要么是非法情况。算法结束时如果栈为空则说明该括号序列是正确的。
中缀表达式转后缀表达式
手工做法
依次根据优先级为每一次运算加括号，并全部采用同样的操作，即操作数的顺序不变但把操作符放到括号外，将处理完的这一步运算当作一个新的操作数去与其前面的操作数和操作符进行同样的操作，直到转化完成
算法实现
从左到右扫描中缀表达式，分为以下几种情况：1 、若为操作数，则直接加入后缀表达式；2 、若为( 则直接入栈；3 、若为) ，则依次把栈中的运算符加入后缀表达式，直到出现( ，从栈中删除( ；4 、若为其他操作符，需跟栈顶操作符进行比较，如果栈顶是( 则直接入栈，否则依次弹出栈顶优先级大于等于当前所扫描到的操作符的元素，直到出现一个优先级比它低的或遇到一个左括号为止
后缀表达式值的计算
从左至右依次扫描后缀表达式，如果是操作数则直接入栈，如果是操作符则依次弹出栈顶两个元素，先弹出的是右操作数后弹出的是左操作数进行运算，并将此步的运算结果压入栈中，依次重复此步骤直到栈中只有一个操作数则该操作数就是最终的运算结果
在递归中的应用
在递归调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储
队列的应用
二叉树的层次遍历
队列在计算机系统中的应用
比如打印缓冲区
特殊矩阵的压缩存储
数组的存储结构
二维数组可视为其元素也是定长线性表的线性表
两种映射方法
行优先
列优先
矩阵的压缩存储
概念
压缩存储指为多个相同元素分配一个存储空间，对零元素不分配存储空间
特殊矩阵指具有许多相同矩阵元素或者零元素并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵，例如对称矩阵、上/ 下三角矩阵、对角矩阵等
特殊矩阵的压缩存储方法
找规律，把呈现规律分布的，值相同的多个矩阵元素压缩存储到一个存储空间中
对称矩阵
只存放下三角部分（含主对角）的元素
三角矩阵
其存储思想与对称矩阵类似，不同之处在于存储完下三角区和主对角线上的元素之后紧接着要存放对角线上方的常量一次
公式不必死记硬背，现场推也是可以的
三对角矩阵
所有非零元素都集中在以对角线为中心的3 条对角线的区域，其它区域的元素都为零
按行优先方式存放在一个一位数组中，且将a11 存放在B [ 0 ] 中
重要公式
已知某元素aij ，它在一维数组中的下标k=2i+j-3
反之若已知k ，则i=(k+1)/3+1 向下取整，j=k-2i+3
稀疏矩阵
矩阵中非零元素的个数相对矩阵元素的个数来说非常少
既可以采用数组存储，也可以采用十字链表法存储
适用于压缩存储稀疏矩阵的两种存储结构是三元组表和十字链表
第四章串
KMP模式匹配算法
几个重要概念
前缀：除最后一个字符外，字符串的所有头部子串
后缀：除第一个字符外，字符串的所有尾部子串
部分匹配值：字符串的前缀和后缀的最长相等前后缀长度
练习：ababa的部分匹配值为00123
next数组
含义：在子串的第j个字符与主串发生失配时，则跳到子串的next[j]位置重新与主串当前位置进行比较
求解方法
1、求出子串（模式）的部分匹配值
这一步在手算时可以直接看当前子串的首尾重合的最大个数，而无需将所有的前缀和后缀全部写出再找部分匹配值
2、整体右移，左边高位补-1，右边多余的直接移出
3、全部加1
KMP 算法的改进之nextval 数组
当next 数组中出现Pj=Pnext [ j ] 时，相当于拿一个和Pj 相等的字符跟Sj 比较，这必然导致继续失配，则此时应当对next [ j ] 进行修正
修正方法
首先考察Pj 与Pnext [ j ] 是否相等，如果不相等，则nextval [ j ] =next [ j ] ；如果相等，则令nextval [ j ] =nextval [ next [ j ]] ，直至两者不相等为止
注意
对于给定主串和模式串的情况下，求next 数组是求的模式串的，这一点不要搞混了
第五章树和二叉树
树的基本概念与性质
树是一种递归的数据结构，是一种分层次的逻辑结构
特点
根结点没有前驱，除根结点外的所有结点有且只有一个前驱
树中的所有结点可以有零个或者多个后继
基本术语
树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度
分支结点：度大于0；叶结点：度为0
树的高度（或深度）是树中结点的最大层数
路径和路径长度
树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上经过的边的个数
注意
树中的分支是有向的，所以树中的路径只能是从上向下的，同一双亲的两个孩子之间不存在路径
森林
森林是m棵不相交的树的集合
性质
树中的结点数等于所有结点的度数加1 ，这是选择题中最为常用的一条性质
度为m的树中第i层上至多有m的i-1次方个结点
高度为h 的m 叉数至多有(m^h-1)/(m-1) 个结点（推导是利用了上条结论以及等比数列前n 项和公式），至少有h 个结点
注意
m叉树中任意结点的最大度数为m，可能都小于m，而m叉树中至少有一个结点的度为m
有n 个结点的m 叉树的最小高度为logm [ n(m-1)+1 ]，即当它是一棵完全m叉树时高度最小
这条性质的推导思路：设m 叉树的高度为h ，则第h 层至少有1 个结点，至多有m^(h-1) 个结点，可得不等式：1+m^2+m^3+...+m^h-2<n<=1+m^2+m^3+...+m^h-1 ，即可解得最小和最大的高度h
二叉树的基本概念
每个结点的度数至多为2 的有序树
二叉树与度为2 的树的区别
度为2 的树至少有一个结点的度为2 ，也即最少要有3 个结点；而二叉树只要求所有结点的度数小于等于2 ，它甚至可以是一棵空树
二叉树的结点次序不是相对于另一结点而言，即它是确定次序的，左孩子就是左孩子，而无论是否有右孩子
几个特殊的二叉树
满二叉树
每层都含有最多的结点个数，高度为h 的满二叉树的结点数为2^h-1
可以对满二叉树按层序进行编号，约定编号方式为从根结点起（根结点为1 ），自上而下自左向右，则在这种编号方式下，i 结点的左孩子为2i ，右孩子为2i+1 ；i 结点的双亲为i/2 向下取整
完全二叉树
高度为h ，有n 个结点的二叉树，当且仅当其每个结点都与高度为h 的满二叉树中编号1 ～ n 的结点一一对应时称为完全二叉树
特点
若i<=n/2 向下取整，则i 为分支结点，否则为叶子结点
叶子结点只可能出现在层次最大的两层上，最大层次上的叶子结点都依次排列在该层最左边的位置上
若有度为1 的结点则只可能有一个，且该结点只有左孩子而无右孩子
层序编号下，一旦出现某结点为叶子结点或者只有左孩子，则编号大于i 的结点均为叶子结点
n 为奇数则每个分支结点都既有左孩子又有右孩子，n 为偶数则编号最大的分支结点只有左孩子而无右孩子
二叉排序树
左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字，且左右子树又各自是一棵二叉排序树
二叉平衡树
树上任意一结点的左子树和右子树的深度之差不超过1
二叉树的性质
n0=n2+1
非空二叉树的第k 层上至多有2^(k-1) 个结点
高度为h 的二叉树至多有2^h-1 个结点
对完全二叉树进行从1 开始的层序编号之后
对于一个结点i，若i是偶数，则它的双亲编号为i/2且它是双亲的左孩子，若i是奇数，则它的双亲编号为(I-1)/2，且它是双亲的右孩子
若2i<=n ，则i 的左孩子为2i ，否则没有左孩子
若2i+1<=n ，则i 的右孩子为2i+1 ，否则没有右孩子
对于编号为i 的结点，它所在的深度为log2i 向下取整+1
具有n 个结点的完全二叉树的高度为log2n 向下取整+1 或log2(n+1) 向上取整（这条性质和上一条其实类似），推导思想：由上述性质有2^(h-1)-1<n<=2^h-1 ，解不等式即得此结论
注意
完全二叉树是一种比较特殊的二叉树，不能将完全二叉树的性质与一般二叉树的性质弄混淆
二叉树的存储结构
顺序存储
用一组地址连续的存储空间来存储二叉树，建议从数组下标1 开始存储树中的结点以便满足上述在层序编号条件下的性质
适用于满二叉树或者完全二叉树，对于一般的二叉树，为了满足性质可能会有一些存储空间的浪费
链式存储
一般情况下二叉树都采用链式存储方式，结点node 结构体中定义左孩子指针、数据域、右孩子指针
在含有n 个结点的二叉链表中，空指针的个数为n+1
注意
将一棵树转化成二叉树的方法：对某个特定的结点，左孩子依然是左孩子，兄弟变右孩子
将一棵树转换成对应的二叉树，二叉树中无右孩子的结点实际上就是原来的树中没有右兄弟的结点
m 叉树层序编号条件下，编号为i 的结点的第一个孩子的编号为j=(i-1)*m+2
二叉树的遍历和线索二叉树
二叉树的遍历是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次且仅被访问一次
遍历方式
先序遍历
根-> 左-> 右
递归方式
void preorder （BiTree t ） { if(t!=null) { visit(t); preorder(t->lchild); preorder(t->child); } }
非递归方式
void preorder2(bitree t) { initstack(s); bitree p=t; while(p||!isempty(s)) { if(p) { visit(p); push(s,p); p=p->lchild; } else { pop(s,p); p=p->rchild; } } }
中序遍历
左-> 根-> 右
递归和非递归遍历方式的实现过程和先序遍历的实现过程基本是一致的
后序遍历
左-> 右-> 根
二叉树在线索化后，后序线索二叉树中求后序后继也无法得到有效解决，因此后序线索树的遍历仍然需要栈的支持。p148 t29,t31
层次遍历
也即按照层序编号递增的方式来遍历每一个结点
具体遍历算法要借助队列来实现
void levelorder(bitree t) { initqueue(q); bitree p; enqueue(q,t); while(!isempty(q)) { dequeue(q,p); visit(p); if(p->lchild!=null) enqueue(p->lchild); if(p->rchild!=null) enqueue(p->rchild); } }
由遍历序列构造二叉树
先序+ 中序可以唯一确定一棵二叉树
原因：先序序列的第一个结点一定是整棵二叉树的根结点，而在中序序列中，根结点左边的是它的左子树的中序，它右边的是它的右子树的中序。而在先序序列中，左子树的先序序列的第一个结点又是它的根结点，右子树的第一个结点又是它的根结点，如此递归下去，便可唯一确定一棵二叉树。
后序+ 中序也可以唯一确定一棵二叉树
原因：和上述先序+ 中序唯一确定二叉树的原理是一致的，只是在后序序列中最后一个结点才是根结点，剩下的分析过程相同
先序+ 后序无法唯一确定一棵二叉树
线索二叉树
线索二叉树产生的背景：在前面二叉树的链式存储中知道，含有n 个结点的二叉链表中，空指针的个数为n+1 个，因而想到利用这n+1 个空指针来存储指向结点的直接前驱或后继的指针，这样便可以加快查找结点前驱和后继的速度。
规定：对某结点来说，若无左孩子则令lchild 指向其前驱结点，若无右孩子则令rchild 指向其后继结点，同时设置ltag 和rtag 两个标志位来表明该指针是指向子树还是指向前驱或者后继
线索二叉树的构造
二叉树线索化就是将空指针改为指向前驱或者后继的线索，实质上就是遍历二叉树的过程
手工构造线索二叉树：对某一结点，如果它没有左孩子，就将lchild 指针指向它的前驱；如果它没有右孩子，就将rchild 指针指向它的后继
注意
已知前序，判断某中序序列是否可能得到：以前序序列为入栈顺序，分析是否能够得到该中序序列的出栈顺序
由上条结论可知，已知一棵二叉树的前序序列，则满足该前序序列的不同二叉树的个数，可以理解成在该前序序列的入栈次序下，可能得到的出栈序列有多少种（因为没种出栈序列对应一个中序序列，而一旦前序和中序序列确定了，该二叉树也就唯一确定了），则这里可以用栈中的卡特兰数来解题，p149 t34
已知前序和后序，不能唯一确定一棵二叉树，但可以确定结点之间的关系：对任意两个结点，它们在前序后序中的前后关系不同则证明二者是父子关系；如果它们在前序后序中的前后关系相同，则二者应该是兄弟关系
树、森林
树的存储结构
双亲表示法
用一组连续空间来存储每个结点，同时在每个结点中添加一个伪指针，用于指示其双亲结点在数组中的位置
注意区别树的顺序存储结构与二叉树的顺序存储结构：树的存储结构中数组下标代表结点编号，下标中所存的内容指示了结点之间的关系，而在二叉树的存储结构中，结点下标既代表结点的编号，同时也指明了二叉树中各结点之间的关系
孩子表示法
将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n 个结点就有n 个孩子链表
孩子兄弟表示法
又称二叉树表示法，即以二叉链表作为树的存储结构
每个结点包括三部分内容：指向第一个孩子的指针、结点值、指向结点下一个兄弟的指针
树、森林、二叉树的转换
树转化为二叉树
遵循“左孩子右兄弟”原则，即左边的大孩子依然是孩子，而右边的兄弟结点在转换成二叉树后将成为本结点的右孩子
森林转化为二叉树
先将森林中的每棵树转化成二叉树，把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当作第一棵二叉树根的右子树，将第三棵树对应的二叉树当作第二棵二叉树根的右子树，依此类推
二叉树转化为森林
若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，故将根的右链断开，二叉树的右子树又可以视为除第一棵树外的森林转化成的二叉树，依此类推
树的遍历
先根遍历
其遍历序列与这棵树相应二叉树的先序序列相同
后根遍历
其遍历序列与这棵树相应二叉树的中序序列相同
森林的遍历
先序遍历
中序遍历
分别与其对应二叉树的的先序和中序遍历序列相同
注意
含有n 个非叶结点的森林转化成对应的二叉树后，右指针域为空的结点个数为n+1
树与二叉树的应用
二叉排序树
定义
要么是一棵空树，要么是一棵具有以下性质的二叉树：左子树非空则左子树上所有结点的值均小于根结点的值；右子树非空则右子树上所有结点的值均大于根结点的值
根据此定义，对一棵二叉排序树进行中序遍历，可以得到一个递增的有序序列
查找过程
和二分查找的过程很类似，先将给定值与根结点的关键字进行比较，如果相等则查找成功；若不等，如果小于根结点关键字则在左子树继续查找，如果大于根结点关键字则在右子树继续查找，显然这是一个递归的过程
插入过程
其实就是一次查找过程，在原二叉树不空的情况下，插入的结点一定是一个新添加的结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或者右孩子
删除过程
若被删除结点是叶子结点则直接删除
若只有一棵左子树或者一棵右子树，则让z 的子树成为z 的父结点的子树，代替z 的位置
若被删除的结点z有两棵子树，则让z 的中序直接后继（或直接前驱）代替z，然后从二叉排序树中删除这个直接后继（或直接前驱）
查找性能分析
查找效率主要取决于树的高度
若左右子树的深度之差不超过1 ，这样的二叉排序树称为平衡二叉树，平均查找长度为O(log2n) ，若是一个只有左孩子/ 右孩子的单支树，此时的平均查找长度为O(n)
注意
在二叉排序树中删除并插入某结点，得到的二叉树与原来的二叉树不一定相同
二叉排序树便于维护表的有序性，因而适用于有序表的动态查找表，静态的则更适合用二分查找
平衡二叉树
定义
左右子树高度差的绝对值不超过1 的二叉排序树称为平衡二叉树，简称平衡树
平衡二叉树或是一棵空树，或是具有以下性质的二叉树：它的左右子树都是平衡二叉树，且左右子树高度差值不超过1
平衡二叉树的插入
插入过程的前半部分与二叉排序树相同，但在插入新结点后，如果造成查找路径上的某个结点的不平衡，先找到插入路径上离插入结点最近的平衡因子的绝对值大于1 的结点A ，再对以A 为根的子树在保持二叉排序树特性的情况下进行调整，可能的调整情况有以下4 种：
LL 平衡旋转（右单旋转）
由于在A 的左孩子的左子树上插入了新结点而导致以A 为根的子树失去平衡，需要一次向右的旋转操作
将A 的左孩子B 向右上旋转代替A 成为根结点，将A 结点向右下旋转成为B 的右子树的根结点，而B 的原右子树则作为A 结点的左子树
RR 平衡旋转（左单旋转）
由于在A 的右孩子的右子树上插入了新结点而导致以A 为根结点的子树失去平衡，需要一次向左的旋转操作
将A 的右孩子B 向左上旋转代替A 成为根结点，将A 结点向左下旋转成为B 的左子树的根结点，而B 的原左子树则作为A 结点的右子树
LR 平衡旋转（先左后右双旋转）
由于在A 的左孩子的右子树上插入了新结点而导致以A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转
先将A 的左孩子B 的右子树的根结点C 向左上旋转（RR ）提升到B 结点的位置，然后再将该C 结点向右上旋转（LL ）提升到A 结点的位置
RL 平衡旋转（先右后左双旋转）
由于在A 的右孩子的左子树上插入新结点而导致的失衡，需要进行两次旋转操作，先右旋转后左旋转
先将A 的右孩子B 的左子树的根结点C 向右上旋转（LL ）提升到B 的位置，再将该C 向左上旋转（RR ）提升到A 的位置
平衡二叉树的查找
平衡二叉树的查找过程和普通二叉排序树的查找过程是相同的
假设以nh 表示深度为h 的平衡二叉树的最少结点数，则有如下递推公式：n0=0,n1=1,n2=2, nh=n(h-1)+n(h-2)+1
平衡二叉树的平均查找长度为o(log2n)
哈夫曼树和哈夫曼编码
带权路径长度：从树的根结点到任意结点的路径长度（经过的边数）与该结点上权值的乘积，称为该结点的带权路径长度
哈夫曼树是含有n 个带权结点的二叉树中带权路径长度最小的
构造过程
每次都选两棵根结点权值最小的树作为左右子树构造一棵新树，并将新构造的树的根结点的权值置为左右子树根结点的权值之和，直到只剩下一棵树为止
特点
在最终构造出的哈夫曼树中，权值越小的结点距离根结点的路径长度越大
构造过程中一共新增了n-1 个结点，故哈夫曼树的总结点树为2n-1
哈夫曼树中不存在度为1 的结点
哈夫曼编码
前缀编码：没有一个编码是另一个编码的前缀
由哈夫曼编码可以很自然地得到前缀编码，哈夫曼树构造好后，连接左孩子的边上标记0 ，连接右孩子的边上标记1 ，则从根结点到某结点的路径上的标记序列即为该结点的哈夫曼编码
哈夫曼编码可以不唯一，但最终得到的带权路径长度一定唯一
注意
哈夫曼树的最重要特征就是根的权值等于左右子树权值之和，利用这一点可以判断两个从根到叶结点的路径的权值序列是否属于同一棵二叉树，p194 ，t29
如果题目给出某一棵树的各个结点的权值，并让求最小路径长度，要看题目要求是几叉树，不要惯性思维觉得肯定就是哈夫曼树，当然如果题目说明了是哈夫曼树，那么必然就是二叉的了
基础必掌握算法
栈、队列（思想）
括号匹配
中缀表达式转后缀
后缀表达式值的计算
线性表（要求手写代码）
顺序表中链表的定义、插入删除等操作
串（思想）
KMP 模式匹配算法中next 数组的求法
树和二叉树（要求手写代码）
先序、中序、后序遍历的递归和非递归方式
借助队列实现的层次遍历
二叉树的线索化（先序、中序、后序）
图（要求手写代码）
深度优先搜索，p227
广度优先搜索，p229
第八章排序
插入排序
希尔排序是不稳定的。
直接插入排序
核心思想
每次将一个待排序的记录按关键字大小插入到前面已经排好序的序列当中
代码结构：两层循环，外层循环从前往后遍历待排元素，内层循环从后往前找当前待排元素的插入位置，每次用A [ 0 ] 当哨兵
特点
稳定
空间复杂度
常数个辅助单元，o(1)
时间复杂度
最好情况下时间复杂度可达o(n)
平均情况下时间复杂度为o(n^2)
排序次数、趟数与初始序列的关系
排序趟数与初始序列状态无关，固定为n-1
但比较次数和移动次数则取决于待排序表的初始状态
当表中元素顺序正好为逆序时，总的比较次数达到最大，为2+3+4+...+n （因为哨兵的存在，所以第二个元素的比较次数为2 而不是1 ）；总的移动次数也达到最大，树上写的是i+1 从i=2 到n 求和，但我认为是i-1 ，因为第二个元素只需移动一次，即将第一个元素移动到第二个位置即可，再将哨兵赋值给第一个元素
适用于顺序存储和链式存储的线性表
算法
void InsertSort(Elemtypt A[],int n) { int i,j; for(i=2;i<n;i++) if(A[i]<A[i-1]) { A[0]=A[i]; // 这里的A[0]是哨兵 for(j=i-1;A[j]>A[0];j--) A[j+1]=A[j]; A[j+1]=A[0]; } }
折半插入排序
稳定
在插入排序的基础上将查找一个元素插入位置这一部分做了改进，采用折半查找方法
时间复杂度没什么变化，依然为o(n^2)
希尔排序
核心思想
又叫缩小增量排序，从部分有序不断逼近全局有序
代码结构：三层循环，最外层循环依次除2 向下取整确定步长直到步长为1 ，中层循环的作用类似于直接插排里的外层循环的作用，从前往后依次遍历当前按步长的分组中待排元素，内层循环作用类似于直接插排里内层循环的作用，从后往前寻找当前待排元素应该插入的位置
特点
不稳定
空间复杂度
o(1)
时间复杂度
目前没有准确值，平均时间复杂度约为o(n^1.3) 最差为o(n^2)
仅适用于线性表为顺序存储的情况
算法
void ShellSort(ElemType A[],int n) { for(int dk=n/2;dk>=1;dk=dk/2) for(int i=dk+1;i<n;i++) if(A[i]<A[i-dk]) { A[0]=A[i]; // 注意这里的A[0]只是一个暂存单元，而不是哨兵 for(int j=i-dk;j>0&&A[0]<A[j];j-=dk) A[j+dk]=A[j]; A[j+dk]=A[0]; } }
交换排序
交换类的排序其趟数和原始序列状态有关。 冒泡和快排每一趟都有一个元素到达它的最终位置。
冒泡排序
核心思想
从后往前两两比较相邻元素的值，若为逆序则需要进行交换
代码结构：两层循环，外层循环的循环变量i 可以理解成是冒泡的趟数（从0 开始），内层循环从最后一个元素开始向前遍历，如果当前元素比其前一个元素小就进行交换。设置一个flag 表示此趟有没有发生交换，如果没有则说明排序完成，结束排序
特点
稳定
空间复杂度为o(1)
时间复杂度
最好情况下即当初始序列有序时，时间复杂度可达o(n) ，即线性时间
平均时间复杂度为o(n^2)
排序趟数与初始序列状态有关
冒泡排序中所产生的有序子序列一定是全局有序的，即每一趟排序都会有一个元素被放到最终的位置上
算法
void BubbleSort(ElemType A[],int n) { for(int i=0;i<n-1;i++) { bool flag=false; for(j=n-1;j>i;j--) if(A[j-1]>A[j]) { swap(A[j-1],A[j]); flag=true; } if(flag==false) return; } }
快速排序
核心思想
分治思想，每一趟将待排序表分成比枢轴元素小和比枢轴元素大的左右两个部分，再递归对两个子序列快排
关键在于划分操作，同时快速排序算法的性能也主要取决于划分操作的好坏
代码结构：主函数QuickSort() 首先调用Partition 函数返回划分好之后pivot 的位置，再递归地对pivot 左边以及右边的序列进行快速排序；Partition() 函数是快排最核心的部分，完成的主要功能是根据选取的pivot （一般以序列的第一个元素A[low] 为pivot ），将序列划分成左边子序列全部比pivot 小而右边子序列全部比pivot 大的情况，设两个while 循环，第一个循环利用high 指针从high 开始找到第一个比pivot 小的并将其放到A[low] 的位置，第二个循环利用low 指针从low 开始找到第一个比pivot 大的元素并将其放到A[high] 的位置。如此往复直到low=high
特点
不稳定
平均表现性能最好的排序算法
空间复杂度
借助递归工作栈
最好情况递归最大深度：o(log2n)
最坏情况下是o(n)
平均o(log2n)
时间复杂度
最好情况下，子问题划分均匀，时间复杂度为o(nlog2n)
基本有序或者逆序时，左右序列的划分极不对称，是最差情况，时间复杂度为o(n^2)
快排中并不产生有序子序列，但每趟排序后会将枢轴元素放到其最终位置上
算法
Void QuickSort(ElemType A[],int low,int high) { int pivotpos=Partition(A,low,high) QuickSort(A,low,pivotpos-1); QuickSort(A,pivotpos+1,high); } int Partition(ElemType A[],int low,int high) { ElemType pivot=A[low]; while(low<high) { while(low<high&&A[high]>=pivot) high--; A[low]=A[high]; while(low<high&&A[low]<=pivot) low++; A[high]=A[low]; } A[low]=pivot; return low; }
课后习题扩展
双向冒泡排序
奇数趟把关键字最大的放在最后，偶数趟把关键字最小的放在最前
算法
顺序表把所有奇数移动到所有偶数前
利用快速排序算法的划分思想，对线性表进行一次划分
算法
找到数组中第k小的元素
利用快速排序的划分思想，m=partition(A,low,high)，若m=k则结束，否则分情况在左右两边进行递归
算法
选择排序
简单选择排序
核心思想
每一趟在后面若干个元素中找到最小元素，作为前面有序子序列的最后一个元素
代码结构：两层循环，外层循环的作用类似于冒泡排序外层循环的作用，循环变量可以理解为排序进行的趟数（从0 开始），内层循环完成的功能是选择最小的元素并将其更新到min 所指的位置
特点
不稳定
空间复杂度
o(1)
时间复杂度
始终是o(n^2)
比较次数与排序趟数均与初始序列状态无关
算法
Void SelectSort(ElemType A[],int n) { for(int i=0;i<n-1;i++) { int min=i; for(int j=i+1;j<n;j++) if(A[j]<A[min]) min=j; if(min!=i) swap(A[i],A[min]); } }
堆排序
堆的定义
根结点元素比左右孩子结点元素都小的是小顶堆；根结点元素比左右孩子结点元素都大的是大顶堆。注意区分堆与排序二叉树定义上的不同
核心思想
将一维数组视为一棵完全二叉树，构建初始大( 小) 顶堆，输出堆顶元素后交换堆顶与最后一个元素再调整成大( 小顶堆)
构造初始堆的方法
从第ceil(n/2) 各结点开始调整其子树为堆（以大根堆为例），具体的调整方法是：若根结点的关键字小于左右孩子中关键字较大者则进行交换，之后依次向前对以之前各结点为根的子树进行同样的调整，期间可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆直到以该结点为根的子树构成堆为止。
输出堆顶元素后，将堆的最后一个元素与堆顶元素进行交换，此时堆的性质被破坏，需要向下进行筛选调整成新的堆，筛选的过程依然是将根结点与左右孩子中关键字较大者进行交换
代码结构：BuildMaxHeap() 函数从第ceil(n/2) 个结点开始到第一个结点为止，依次调用HeadAdjust() 函数将以该结点为根的子树调整成大根堆；HeadAdjust() 函数首先找到左右孩子中较大的一个，若根结点比较大者还大，则此次筛选结束，否则交换根结点与较大者；主函数HeapSort() 首先调用BuildMaxHeap() 函数创建初始大根堆，再在一层循环内进行n-1 趟的交换和建堆过程，每趟输出堆顶后将堆的最后一个元素进行交换，再调整成新的大根堆
堆的操作
插入
插入时先将新结点放在堆的末端，再对这个新结点向上执行调整操作，调整过程中比较次数最多为树高减1 ，而树高最大为ceil(log2n)+1 ，故比较次数最多为ceil(log2n) ，每次只与自己的父结点进行对比，即每次上调只需对比一次
删除
删除操作时用堆底元素代替被删元素，然后让该元素不断下坠直到无法下坠为止。下坠时每次先在左右孩子中比较找到最小/ 大的，再将待下坠元素与其被选出的孩子进行比较
特点
不稳定
空间复杂度
o(1)
时间复杂度
任何情况下都是o(nlog2n)
算法
Void HeadAdjust(ElemType A[],int k,int len) { A[0]=A[k]; for(int i=2*k;i<len-1;i*=2) { if(i<len&&A[i]<A[i+1]) i++; if(A[0]>=A[i]) break; else { A[k]=A[i]; k=i; } A[k]=A[0]; } } Void BuildMaxHeap(ElemType A[],int len) { for(int i=len/2;i>0;i--) HeadAdjust(A,i,len); } Void HeapSort(ElemType A[],int len) { BuildMaxHeap(A,len); for(int i=len;i>1;i--) { swap(A[i],A[1]); HeapAdjust(A,1,i-1); } }
堆操作
插入
将新结点放在堆的末端，再对新结点不断执行向上调整
每次只需与其父结点进行比较，比较次数最多为树高减1
删除
用堆底元素代替被删除元素，让处于被删除元素位置的堆底元素不断下坠
若有两个孩子，则需要首先比较两个孩子的大小，再比较待下坠元素与两孩子中被选出的；若只有一个孩子，则只需要一次比较
课后习题扩展
单链表的选择排序
每次从待排序单链表中摘下最大的结点插入到结果链表的最前端
算法
归并排序
核心思想
分治，将两个或两个以上的有序子表合成一个新的有序表
代码结构：主函数MergeSort() 每次从中间划分两个子序列，并分别对两个子序列进行归并排序，最后调用Merge 函数将排好序的两个子序列合并成一个有序序列。MergeSort 函数是最重要的函数，它先申请一个和A 数组大小相等的B 数组，并将A 数组的所有元素都复制到B 数组中，然后进行一个带有三个形式指针的for 循环，i ，j ，k 分别指向第一个子序列当前待比较元素、第二个子序列当前待比较元素和B 数组当前的第一个空位，每次选比较结果中较小者放到A [ k++ ] 中。这层for 循环结束后，两个while 循环中只执行一个，表示当一个子序列的所有元素都已经放入A 中并跳出上个for 循环时，可直接将另一段中的所有元素直接依次复制到A
特点
稳定
空间复杂度
需要一个辅助数组，故空间复杂度为o(n)
时间复杂度
o(nlog2n)
算法
void MergeSort(ElemType A[],int low,int high) { while(low<high){ int mid=(low+high)/2; MergeSort(A,low,mid); MergeSort(A,mid+1,high); Merge(A,low,mid,high); } } void Merge(ElemType A[],int low,int mid,int high) { ElempType* B=(ElemType*)malloc((high-low+2)*sizeof(ElemType)); for(int p=low;p<=high;i++) B[p]=A[p]; int k; for(int i=low,j=mid+1;i<=mid&&j<=high;k++) { k=i; if(A[i]<A[j]) A[k]=B[i++]; else A[k]=B[j++]; } while(i<=mid) A[k++]=B[i++]; while(j<=high) A[k++]=B[j++]; }
注意归并排序代码逻辑和手算模拟每一趟结果可能有出入
基数排序
核心思想
不基于比较和移动，基于关键字各位的大小进行排序
过程
分配
依次按关键字某一位的不同将关键字加入到对应的队列中
回收
把各个队列的结点依次首尾相接形成新的线性表
再依次按照更高位重复上述过程，直到有序
特点
稳定
空间复杂度
需要的辅助空间为r 个队列，空间复杂度为o(r)
时间复杂度
共需d 趟分配和收集，一趟分配需要o(n) ，一趟收集需要o(r) ，故时间复杂度为o(d(n+r))
手动模拟基数排序（以升序为例）：第一趟：从前往后扫描待排序列，并以个位数字为分组标准将每个元素分别链入各个分组队列，之后从左往右依次度取这些队列形成一个新的序列；第二趟：对上步中所形成的新队列采用相同的方法进行操作，循环直到最终形成的新序列是有序的
内部排序需要关注的几个问题
算法思想
是否稳定
直接插排
稳定
二分插排
稳定
希尔排序
不稳定
冒泡
稳定
快排
不稳定：记住3 2 ’2 这个例子，经过一趟排序后将变成2 2 ‘3 ，且最终的排序结果也是2 2 ’3
简单选择
不稳定：记住2 2 ’1 这个例子，一趟选择排序后变成了1 2 ’2 ，且最终的排序结果也为1 2 ’2
堆排
不稳定：记住1 2 ’2 这个例子，构造成大顶堆后是2 ’1 2 最终排序得到的结果是1 2 2 ’
归并
稳定
基排序
稳定
每一趟排序能否确定某个元素的最终位置
直接插排
不一定能确定某元素最终位置，但一定会出现部分有序序列（但这些元素不一定在最终位置上）
二分插排
同直接插排
希尔排序
一趟排序不能确定某个元素到最终位置
冒泡排序
可以
快速排序
可以，每趟排序结束后，该趟的pivot 元素的最终位置会被确定
简单选择排序
可以
堆排
可以
归并
不可以，但每趟排序结束后应该能得到若干个元素的有序子序列
基排序
不一定可以
空间复杂度
直接插排/ 二分插排
o(1)
希尔排序
o(1)
冒泡
o(1)
快排
o(log2n)
简单选择
o(1)
堆排
o(1)
归并
o(n)
基排序
o(r)
最好情况、最坏情况、平均情况下的时间复杂度
直接插排
最好o(n) ，即在元素有序情况下；最差o(n^2)
二分插排
在直接插排的基础上基本不改变时间复杂度
希尔排序
目前为止，希尔排序的时间复杂度还没有一个定论，当n 在某个特定范围内时，希尔排序的时间复杂度为o(n^1.3) ，最坏情况下可达o(n^2)
冒泡
最好o(n) ，即当元素有序时；最差o(n^2)
快排
最差o(n^2) ，发生在元素有序或者逆序的情况下；平均o(nlog2n) ，平均表现最好
直接选择
不分好坏，一律都是o(n^2)
堆排
不分好坏，一律都是o(nlog2n)
归并
不分好坏，一律都是o(nlog2n)
基数排序
不分好坏，一律都是o(d(n+r))
排序趟数、比较次数等与初始序列的关系
排序趟数
趟数与初始序列无关的
直接插排
选择排序
快速排序
与初始序列有关的
冒泡排序
比较次数
直接插入排序
o(n)~o(n^2)
二分插入排序
比较次数与初始序列状态无关，始终为o(nlog2n)
外部排序
两个阶段
1 、分割子文件，读入内存进行内部排序后写回外存，生成初始归并段
2 、对这些归并段进行逐趟归并
减少归并趟数可减少磁盘i/O 时间，两个方法
1 、增大归并路数
出现的问题：会导致内部归并比较次数变多
2 、减少初始归并段数
用置换- 选择排序算法生成更长的初始归并段
出现的问题：将产生长度不等的初始归并段
解决问题的方案
败者树用于减少内部归并的比较次数
k 路归并不用败者树，用简单选择排序，每次选最小的要比较k-1 次，每次归并n 个元素，需比较(n-1)(k-1) 次
用败者树，每次选最小的，需要比较log2(k) 向上取整次
哈夫曼树在m 叉树的推广构造最佳归并树
核心思想是让记录少的初始归并段最先归并，让记录数多的最晚参加归并
(n0-1)%(k-1)=u 不为0 ，则需要补充k-u-1 个空归并段
第七章 查找
基本概念
对查找表的操作
查询某特定元素是否在查找表中
检索满足条件的某个特定的数据原素的各种属性
在查找表中插入一个数据元素
从查找表中删除某个数据元素
静态查找表
一个查找表的操作只涉及上述操作的前两个，无须动态修改查找表，则此类查找表称为静态查找表
适用的查找方法：顺序查找、折半查找、散列查找
动态查找表
需要动态地插入或删除的查找表称为动态查找表
适用的查找方法：二叉树的查找、散列查找
平均查找长度
所有查找过程中进行关键字的比较次数的平均值，是衡量查找算法效率的最主要指标
顺序查找和折半查找
顺序查找
一般线性表的顺序查找
采用最直观的查找方法，从线性表的一端开始，逐个检查关键字是否满足给定的条件
平均查找长度：成功时为(n+1)/2 , 不成功时为n+1 ，不成功时为n+1 的原因是“哨兵”的存在
若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由小至大重新排列
对线性的链表只能进行顺序查找
有序表的顺序查找
如果在查找之前已经知道待查找表是有序的，则查找失败可以不用再比较到表的另一端即可判断查找失败
可以用判定树来描述顺序表的查找过程，若表中有n 个元素，则判定树上实际表示表中元素的结点就有n 个，而失败结点就有n+1 个，代表n+1 种查找失败的情况
平均查找长度：成功时与一般线性表的顺序查找一样；失败时在相等查找概率的条件下的平均查找长度为n/2+n/(n+1) ，到达失败结点时所查找的长度等于它上面的一个圆形结点的所在层数
有序表的顺序查找中的线性表可以是链式存储结构，优化的方法是将被查概率大的元素放在靠前位置
折半查找（二分查找）
核心思想：每次比较待查元素和表中一个元素，若相等则查找完毕，若待查元素比该元素小，则在该元素的左半部分继续查找，若比该元素大，则在该元素的右半部分继续查找
平均查找长度的计算方法，根据元素个数画出判定树并直接计算出平均查找长度
判定树
用于描述折半查找过程的一棵二叉树
树中的每个圆形结点表示一个记录，结点中的值为该记录的关键字值，方形结点表示查找不成功的情况
查找成功时的查找长度为从根结点到目的结点的路径上的结点数，查找失败时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数
判定树显然是一棵平衡二叉树
构造
如果low 和high 之间有奇数个元素，则mid 分隔后左右两端的元素个数相等，如果有偶数个元素，则mid 分隔后左半部分比右半部分少一个元素
注意
在判断一棵二叉树是否可能是折半查找判定树时采用的思想：由于折半查找判定树实际上是一棵平衡二叉树，因此该二叉树的中序遍历序列实际上是一个有序序列，可在二叉树结点上填上数字来进行判断
查找次数最多不会超过树高，故时间复杂度为o(log2n) ；只适用于有序排列的顺序存储的线性表
分块查找
吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找
核心思想：将查找表分为若干子块，块内元素可以无序，但块间有序（第一块中最大元素小于第二块中所有元素，第二块中最大元素小于第三块中所有元素，以此类推）。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列
查找过程
1 、在索引表中确定待查元素所在的块
2 、在块内顺序查找
平均查找长度：索引查找和块内查找之和
注意
当每块中的记录个数为n 开方时，分块查找具有最小的平均查找长度根号n+1
分为b 块，每块s 个记录时，若对索引表和块都进行折半查找，则查找效率最高，平均查找长度为log2(b+1)+log2(s+1) ，均向上取整
B 树和B+ 树
B 树（多路平衡查找树）及其基本操作
所有结点的孩子个数的最大值称为B 树的阶
或为空树，或为满足如下特征的m 叉树
每个结点至多含有m 棵子树，即至多含有m-1 个关键字
若根结点不是终端结点，则至少有两棵子树
除根结点外，每个非终端结点都至少有m/2 向上取整棵子树，即至少有m/2 向上取整-1 个关键字
非叶结点的结构，由结点关键字和指针交错构成，对于某一关键字，左边指针所指的子树的所有关键字均小于它，右边指针所指子树的所有关键字均大于它
所有的叶子结点都出现在同一层次上并且不带任何信息，实际上这些结点不存在，指向它们的指针为空
对任一结点，其所有子树的高度相同
结点中的关键字从左向右递增有序
总结
根结点的子树数：[ 2 ，m ] ，关键字数：[ 1 ，m-1 ] ，其它非终端结点的子树数：[ m/2 向上取整，m ] ，关键字数：[ m/2 向上取整-1 ，m-1 ]
对任意结点，其所有子树的高度都相同，因此B 树实际上就是任意子树平衡因子均为0 的多路平衡查找树
关键字的值：子树0< 子树1< 子树2<....
B 树的高度
当B 树中每个结点都有m-1 棵子树时，此时得到的树高是最小的，是logm(n+1)
当根结点只有两棵子树，且其它所有非终端结点都只有m/2 向上取整棵子树时，此时得到的树高是最大的，是以m/2 向上取整为底，(n+1)/2 的对数，再+1
推导思想：根结点最少一个关键字，两棵子树，则第二层最少2 个结点，第三层至少有2ceil(m/2) 个结点... 则第h+1 层至少有2 ceil(m-2)^(h-1) 个结点，由于第h+1 层全是不包含任何信息的叶结点（实际上也是不存在的），而又已知具有n 个关键字的B 树必有n+1 个叶子结点，所以有n+1>=2 ceil(m/2)^(h-1)
n 个关键字的B 树必有n+1 个叶子结点
B 树的查找
不支持顺序查找，只支持多路查找
查找过程分两步进行：1 、在B 树中找结点；2 、在结点内找关键字
B 树的插入
1 、定位，利用B 树查找算法，找出插入该关键字的最低层中的某个非叶结点，要注意的是，插入位置一定是最低层中的某个非叶结点
2 、若插入后的结点的关键字数小于m ，可以直接插入；插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于m-1 时必须对结点进行分裂
分裂的方法：取一个新结点，在插入key 后的原结点，从中间位置m/2 向上取整将其中的关键字分为两部分，左边部分留在原结点中，右边部分的关键字放到新结点中，中间位置的结点插入原结点的父结点中，如果此操作导致父结点的关键字个数也超过了上限，则继续分裂直到这个过程传递到根结点为止，最终将导致B 树的高度增加1
B 树的删除
被删关键字不在终端结点中
用k的前驱或者后继来代替k，然后在相应的结点中删除该前驱/后继，即就转换成了被删关键字在终端结点中的情形
被删关键字在终端结点中
当被删除关键字所在结点的关键字个数>=m/2 向上取整时，可直接删除
兄弟够借
当兄弟结点数还很宽裕时，用当前待删除结点的后继、后继的后继（或者前驱、前驱的前驱）依次顶替空缺
兄弟不够借
将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并
合并过程中双亲结点中的关键字个数会减1，若其双亲结点是根结点且关键字个数减少至0 ，则将该根结点直接删除，合并后的新结点成为根，即每当出现兄弟不够借的情况，都是从双亲结点借一个过来合并
若双亲结点不是根结点，且关键字个数减少到m/2 向上取整-2 ，则又要与它自己的兄弟结点进行调整或者合并操作，并重复上述操作直到符合B 树的要求为止
B+ 树的基本概念
m 阶B+ 树与m 阶B 树的主要差异
B+ 树中具有n 个关键字的结点只含有n 棵子树，即每个关键字对应一棵子树；而在B 树中，具有n 个关键字的结点含有n+1 棵子树，即B+ 树中结点的子树数与关键字个数相等
在B+ 树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，即B+ 树的叶子结点包含了全部关键字，在非叶结点中出现的关键字也会出现在叶结点中
B 树的叶子结点包含了所有的关键字信息，且叶结点本身依关键字从小到大链接，因而支持顺序查找
散列表
基本概念
散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash （key ）=Addr ，这里的地址可以是数组下标、索引或者内存地址等
散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词
散列表：根据关键字直接进行访问的数据结构，也就是说，散列表建立了关键字和存储地址之间的直接映射关系
散列函数的构造方法
直接定址法
直接取关键字的某个线性函数值作为散列地址，H(key)=a*key+b
计算最简单并且不会产生冲突，适合关键字的分布基本连续的情况，若关键字分布不连续且空位较多，则会造成存储空间的浪费
除留余数法
假定散列表表长为m ，取一个不大于m 但最接近或等于m 的质数p ，则有H(key)=key%m
最简单也是最常用的方法，关键是选好p ，使得每个关键字通过该函数的转换后等概率地映射到散列空间上的任一地址
数字分析法
设关键字是r 进制数，而r 个数码在各位上出现的概率不一定相同，选取数码分布较为均匀的若干位作为散列地址
适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数
平方取中法
取关键字的平方的中间几位作为散列地址
处理冲突的方法
开放定址法
可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放
递推公式为：Hi=(H(key)+di)%m ，其中m 为散列表表长，di 为增量序列
取定增量序列后，对应的处理方法就是确定的
线性探测法
当di=0 ，1 ，2...m-1 冲突发生时，顺序查看表中下一单元直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表
这种方法可能造成大量元素在相邻的散列地址上“聚集”起来，大大降低了查找效率
平方探测法
当di=0^2,1^2,(-1)^2....k^2,-k^2 时，称为平方探测法，其中k<=2 ，散列表长度m 必须是一个可以表示成4k+3 的素数
可以避免“堆积”问题，缺点是不能探测到散列表上所有单元，但至少能探测到一半的单元
再散列法
需要两个散列函数，即当通过第一个散列函数H(key) 得到的地址发生冲突时，则利用第二个散列函数H2(key) 形成再探测的地址增量
散列函数：Hi=(H(key)+i*Hash2(key))%m
初次探测位置H0=H(key)%m ，i 是冲突的次数，初始为0 ，最多经过m-1 次探测就会遍历表中的所有位置，回到H0 位置
伪随机序列法
当di= 伪随机数序列时，称为伪随机序列法
拉链法
把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识
适用于经常进行插入和删除的情况，查找、插入和删除操作主要在同义词链中进行
散列查找及性能分析
散列表的查找过程和构造散列表的过程实际上是一致的，对于一个给定的关键字key ，查找的过程为
1 、根据散列函数Addr=Hash(key) ，检查Addr 的位置上是否有记录，若无记录则返回失败；若有记录且等于key 则返回查找成功，否则转2
2 、根据给定的冲突处理方法计算“下一个散列地址”，并把Addr 置为此地址，转入1
散列表的查找效率取决于散列函数、处理冲突的方法和装填因子
装填因子= 表中记录数n/ 散列表长度m
注意
按线性探测法处理冲突时，查找失败的平均查找长度的计算方法：1、根据散列函数确定最后要除的分母，比如Hash(key)=key%m，则最后除的分母应该等于这个m，而不是散列表的表长；2、从第一次计算散列地址开始，到按线性探测法直到找到第一个表中的空元素为止，一共经历的查找次数就是这个元素查找失败时的查找长度，计算出所有元素查找失败时的长度之和，再除以1中的分母即可
第六章图
图的基本概念
图G 由顶点集V 和边集E 组成，其中V(G) 表示图中顶点的有限非空集，E(G) 表示图中各顶点之间的关系( 边) 集合，注意线性表可以是空表、树可以是空树、图不可以是空图，顶点集一定非空而边集可以为空，即图中可以只有顶点而没有边
有向图
边都是有向边（称为弧），用<v1,v2> 表示
无向图
边都是无向边（简称边），用(v1,v2) 表示
简单图
不存在重复边
不存在顶点到自身的边
完全图（简单完全图）
对于无向图，边数的取值为0 ～ n(n-1)/2 ，当边数为n(n-1)/2 时称该无向图为完全图
无向完全图中任意两个顶点之间都存在边
对于有向图，边数的取值为0 ～ n(n-1) ，当边数为n(n-1) 时称该有向图为有向完全图
有向完全图中任意两顶点之间都存在方向相反的两条弧
子图
对于两个图G(V,E) 和G’(V’,E’) ，如果有v’是v 的子集并且e‘是e 的子集，则称G’是G 的子图，并且当VG‘=VG 时，称G’为G 的生成子图
注意
并非V 和E 的任何子集都能够构成G 的子图，因为这样的子集可能不是图，即E 的子集中的某些边关联的顶点可能不在这个V 的子集中
连通、连通图、连通分量
连通：若从顶点v 到顶点w 有路径存在，则称v 和w 是连通的
连通图：在无向图G 中，若图G 中任意两个顶点都是连通的则称图G 为连通图，否则称为非连通图；无向图中极大连通子图称为该图的连通分量
强连通图：在有向图中，如果对任何一对顶点，双向都有路径，则称此有向图是一个强连通图；有向图中的极大连通子图称为有向图的强连通分量
一般在无向图中讨论连通性，而在有向图中讨论强连通
生成树、生成森林
连通图的生成树是包含了图中所有顶点的一个极小连通子图，非连通图中连通分量的生成树构成了该非连通图的生成森林
顶点的度、入度和出度
对无向图，顶点的度是指依附于该顶点的边的条数
无向图中全部结点的度的和等于边数的2 倍
对有向图，结点的度分为入度和出度，所有结点的入度和出度相等，并且就等于边数
注意
若一个图有n 个顶点，并且边数小于n-1 ，则它一定是一个非连通图
若一个图有n 个顶点，并且有大于n-1 条边，则此图一定有环
环是一种较为特殊的图，在某些特殊的情况下，常会考虑用环来举特例或者反例
图的存储及基本操作
图的存储
邻接矩阵法
无向图的邻接矩阵一定是一个对称矩阵（并且唯一），拿到一个邻接矩阵，如果发现是非对称阵，那么该邻接矩阵一定是有向图的邻接矩阵
对于无向图，第i 行或第i 列的非零（或非∞）元素个数正好是第i 个顶点的度
对于有向图，邻接矩阵第i 行的非零（或非∞）元素的个数正好是第i 个元素的出度，而第i 列非零（或非∞）元素的个数正好是第i 个元素的入度
稠密图适合用邻接矩阵进行存储
设图G 的邻接矩阵为A ，则A^n 的第i 行j 列的元素等于在图中顶点i 到顶点j 的长度为n 的路径的条数
邻接表法
邻接表：对图G 中的每个顶点vi 建立一个单链表，第i 个单链表中的结点表示依附于顶点i 的边（对于有向图则是以顶点i 为弧尾的弧），这个单链表就称为顶点i 的边表（对于有向图则称为出边表）
边表的头指针和顶点的数据信息采用顺序存储结构，所以在邻接表中存在两种结点：顶点表结点和边表结点
特点
无向图所需的存储空间为o(|v|+2|e|) ，有向图所需的存储空间为o(|v|+|e|)
稀疏图采用邻接表表示能够极大节省存储空间
图的邻接表表示不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序
十字链表
是有向图的一种链式存储结构
暂时搁置，如果做套卷遇到了再说
邻接多重表
邻接多重表是无向图的另一种链式存储结构
图的基本操作
FirstNeighbor （G ，x ，y ）：求图G 中顶点x 的第一个邻接点，若有则返回顶点号。若x 没有邻接点或图中不存在x ，则返回-1
NextNeighbor （G ，x ，y ）：假设图G 中顶点y 是顶点x 的一个邻接点，返回除y 外顶点x 的下一个邻接点的顶点号，若y 是x 的最后一个邻接点，则返回-1
图的遍历
图的遍历是指从某一个顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点进行访问并且只访问一次。图的遍历算法通常用来求解图的连通性问题、拓扑排序和求解关键路径。
广度优先搜索BFS
类似于二叉树的层序遍历
主要思想
广度优先搜索的思想总结起来就是，从顶点v 开始，由远至近依次访问和v 有路径相通并且路径长度为1 、2... 的顶点，它是一种分层的查找过程，因此每次向前走一步可能访问一批顶点，而不像深度优先搜索需要有回退过程，它不是一个递归过程，需要借助一个辅助队列
图的广度优先搜索的过程与二叉树的层序遍历时完全一致的，说明广度优先搜索遍历算法实际上是二叉树的层序遍历算法的扩展
性能分析
空间复杂度
无论采用邻接矩阵还是邻接表存储，BFS都需要一个辅助队列，n个元素均需入队一次，在最差情况下的空间复杂度可以达到O(|v|)
时间复杂度
邻接表存储
每个顶点均需搜索一次（或入队一次），故时间复杂度为o(|v|) ，在搜索任一顶点的邻接顶点时，每条边至少访问一次，故时间复杂度为o(|e|) ，所以算法总的时间复杂度为o(|v|+|e|)
邻接矩阵存储
查找每个顶点的邻接点所需的时间为o(|v|) ，故算法总的时间复杂度为o(|v|^2)
BFS 算法求解单源最短路径问题
广度优先生成树
在广度优先遍历的过程中我们可以得到一棵遍历树，称之为广度优先生成树
一给定图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的，但由于邻接表存储不唯一，故其广度优先生成树也不是唯一的
深度优先搜索DFS
类似于二叉树的先序遍历
主要思想
与广度优先所不同的是，深度优先的搜索策略是尽可能“深”地搜索一个图
性能分析
空间复杂度
是一个递归算法，需要借助一个递归工作栈，因而空间复杂度为o(|v|)
时间复杂度
邻接表存储
o(|v|+|e|)
邻接矩阵存储
o(|v|^2)
深度优先的生成树和生成森林
对连通图调用DFS 才能产生深度优先树，否则产生的是深度优先森林
注意
对于一个无环有向图进行DFS ，并在推出递归时出栈，得到的一个序列应该是逆拓扑有序的
一个无向图是一棵树的条件是：G 必须是一个无回路的连通图或者n-1 条边的连通图
图的遍历与图的连通性
对于无向图来说，若无向图是连通的，则从任一结点出发仅需遍历一次就能够访问图中的所有顶点；对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点
注意
在无向图的广度/ 深度优先遍历算法中，两个主体函数调用BFS/DFS 函数的次数等于该图的连通分量数，因为对于非连通无向图来说，一次遍历只能遍历完一个连通分量
在有向图中调用次数则不一定，因为有向图的连通分为强连通和非强连通，它的连通分量也分为强连通分量和非强连通分量，而对非强连通分量调用一次BFS/DFS 是不能够遍历完所有结点的
图的应用
最小生成树
一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。对于一棵带权无向图，所有生成树中边的权值之和最小的那棵生成树称为该图的最小生成树
特点
最小生成树不是唯一的，即最小生成树的树形不唯一。当图G 中的各边权值互不相等时，G 的最小生成树是唯一的。
当G 本身就是一棵树时，它的最小生成树就是它本身
虽然最小生成树不唯一，但其对应的边的权值之和总是唯一的，而且是最小的
算法
Prim 算法
核心思想：每次选到当前顶点集合距离最近（权值最小）的顶点加入生成树，直到包含所有顶点
性能分析：时间复杂度为o(|v|^2) ，不依赖于|e| ，因此它适用于求解边稠密的图的最小生成树
Kruskal 算法
核心思想：按边的权值大小排序，若依附于该边的顶点在不同的连通分量中则将其加入边集，否则舍弃此边而选择下一条权值最小的边
性能分析：时间复杂度为o(|e|log|e|) ，因此Kruskal 算法适合于边稀疏而顶点较多的图
最短路径
当图是带权图时，把从一个顶点v0 到图中其余任意一个顶点vi 的一条路径所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条路径称为最短路径
Dijkstra 算法求解单源最短路径
核心思想：初始时集合S 中只包含源点，每次选取当前从源点能够到达的所有结点中最短路径长度最小的那个顶点加入集合S ，加入后更新从源点到其它所有顶点的最短路径长度，更新的原则是看经过新加入的点的路径长度是否小于原来的最短路径长度，如果小则更新，直到S 中包含所有的顶点
性能分析：无论用邻接表还是邻接矩阵表示，Dijistra 算法的时间复杂度均为o(|v|^2)
注意
当边上带有负权值时本算法可能得不到正确的结果
Floyd 算法求图中每对顶点间的最短路径
核心思想：用一个n 阶方阵序列来依次表示绕行第k 个顶点的情况下，从顶点i 到j 的路径长度，从最初的邻接矩阵开始迭代n 次，也即最终所有的顶点都被当作中介点绕行过一次，最终得到的A^n-1 即包含了任意一对顶点i ，j 之间的最短路径长度
迭代更新的标准是，考察以当前顶点为中介进行绕行，则绕行得到的路径长度是否小于原来的路径长度，即Ak [ i ][ j ] =min{A(k-1) [ i ][ j ] ，A(k-1) [ i ][ k ] +A(k-1) [ k ][ j ] }
性能分析：总共迭代n 轮，每轮n^2 次，则总的时间复杂度为o(|v|^3)
该算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路
有向无环图描述表达式
1 、先画出该表达式的二叉树表示形式
2 、对于重复出现的子树以及叶子结点（操作数）可以共享，修改指针即可，最终得到的就是有向无环图的表示方式（有向无环图DAG ：Directed Acyclic Graph ）
拓扑排序
AOV 网（Activity on vertex network ）
用DAG 表示一项工程，顶点表示活动，并用<Vi,Vj> 表示活动Vi 必须先于Vj 发生这样一种关系，则将这种有向图成为顶点表示活动的网络
拓扑排序
一个有向无环图的顶点组成的序列
每个顶点出现且仅出现一次
若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径
对AOV 网进行拓扑排序的算法
从AOV 网中找出一个没有前驱的顶点（入度为0 ）并输出
从网中删除该顶点和所有以它为起点的有向边
重复上述过程直到AOV 网为空网或者当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环
若是要求逆拓扑排序，则上述过程中第一步该成选出度为0 ，第二步中改成以该顶点为终点即可
注意
有环的图不存在拓扑排序序列
在AOV 网中如果一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前后关系，则此时的拓扑排序是唯一的。
拓扑排序唯一也不能确定该图
关键路径
AOE 网（Activity on edge network ）
在带权有向无环图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销，称为用边表示活动的网络，简称AOE 网
性质
只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
只有在进入某顶点的各有向边所代表的活动都已经结束时，该顶点所代表的事件才能发生
AOE 网中仅有一个入度为0 的顶点，成为开始顶点（源点），它表示正个工程的开始；网中也仅存在一个出度为0 的顶点，称为结束顶点（汇点），它表示整个工程的结束
从源点到汇点的有向路径可能有多条，只有所有路径上的活动都已经完成整个工程才算结束。从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，把关键路径上的活动称为关键活动，完成整个工程的最短时间就是关键路径的长度。
求解过程
从源点出发，令Ve （源点）=0 ，按拓扑有序求其余顶点的最早发生时间Ve （），过程中确定某顶点的最早发生时间的标准是比较从源点到该顶点各条路径长度，取最大值
从汇点出发，令Vl （汇点）=Ve （汇点），按逆拓扑有序求其余顶点的最迟发生时间Vl （），过程中确定顶点的最迟发生时间的标准是，用汇点的Vl 减去从汇点到该顶点路径长度最长的
根据各顶点的ve 值求所有弧的最早开始时间e
活动的最早开始时间：该活动弧的起点所表示的事件的最早发生时间
根据各顶点的vl 值求所有弧的最迟开始时间l
活动的最迟开始时间：该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差
求AOE 网中所有活动的差额d ，找出所有d=0 的顶点构成关键路径
某活动的最迟开始时间和其最早开始时间的差额
注意
关键路径上的活动都是关键活动，可以通过加快关键活动来缩短整个工程的工期，但也不能任意缩短关键活动，因为一旦缩短到一定程度，关键活动可能变成非关键活动
网中的关键路径并不唯一，对于有几条关键路径的网，只提高一条关键路径上的关键活动并不能缩短整个工程的工期，只有关键路径上的活动时间同时减少时才能够缩短工期，包含两种情况：1 、缩短某个包含在所有关键路径中的活动的时间；2 、缩短某几个关键活动的时间，要求任意一条关键路径的所有关键活动中至少有一个在这几个关键活动中
实际上，在求解过程中前两步完成后就已经求得了关键路径：最早发生时间= 最迟发生时间的结点一定是在关键路径上的