第二章 数据结构与算法
1、线性表的定义及特点
线性表是若干数据元素组成的有限集合；
线性表的特点是，有惟一的起始结点和惟一的终端结点，其它元素都有惟一的直接前驱和惟一的直接后继。
线性表的抽像数据类型定义包括2方面，
数据对象、关系的定义；
线性表有关操作的定义；
线性表的数据对象是具有相同性质数据元素的集合。
线性表的有关操作有：
基本操作：初始化线性表、撤消线性表、判/置空表、取表长、取前驱元素、取后继元素、取第i个元素、遍历等。
插删操作：在顺序结构下，结点的插入(n/2)和删除[(n-1)/2]主要是进行元素的移动；在链式结构下，结点的插删是调整指针的指向。
查找操作：在顺序表中可以进行折半查找，在链表中只能进行顺序查找。
2、线性表的基本存储结构及特点，线性表有顺序和链式两种存储结构。
顺序存储结构是：用一组地址连续的存储单元依次存储线性表中的数据元素；
链式存储结构是：用一组地址任意的存储单元存储线性表中的数据元素。（存储单元节点可以是连续的，也可以是不连续的）
链式存储结构包括，
单链表（又称线性链表），结点的结构体有两个域，分别存储数据元素和当前元素有关系的其它元素所在结点的指针
双向链表，每个结点包含两个指针，分别指明直接前驱和直接后继元素，可以在两个方向上遍历其后及其前的元素；
循环链表，链表中最后一个结点的指针指向第一个结点，开成环状结构，可以在任意位置上方向不变地遍历全表；
静态链表，借助数组描述线性表的链式存储结构。
3、栈的定义：是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。
栈的特点：是先进后出(FILO)。在线结构中，允许进行插、删操作的一端称为栈顶，相应另一端称为栈底。不含数据的栈称为空栈。
栈的基本运算有：置空栈、判空栈、元素入栈、出栈和读取栈顶元素的值。
栈的存储结构：顺序栈和链栈。
顺序栈指，用一组连续的存储单元依次存储自栈顶到栈底的元素，同时设置指针top指示栈顶元素的位置。顺序栈的空间容量是有限的，要预先定义。顺序栈的入栈和出栈操作是通过修改数组下标来完成。假设栈底对应于数组下标较大的一端，那么在元素入栈时就是下标减1，而元素出栈时就是下标加1。
链栈，类似于线性链表，栈顶指针就是链表首结点的位置，元素的插删操作限定在首结点处进行。
栈的应用：表达式计算，数制转换，括号匹配，迷宫问题，递归问题
4、队列的定义：是一种先进先出(FIFO)的线性表。
队列的特点：它只允许在表的一端插入元素而在表的另一端删除元素。在队列中允许插的一端叫队尾(rear)，允许删的一端叫队头(front)。
队列的基本运算：置队空、判队空、入队、出队、读队头元素等。
队列的存储结构：顺序队列和链队列。
顺序队列，又被叫作循环队列，设顺序队列Q，Q.front表示队头指针，Q.rear表示队尾指针，则Q.front和Q.rear相等且为0时为空队列；元素入队时Q.rear加1，元素出队时Q.front加1。因为顺序队列的空间容量是提前设定的，所以当Q.rear达到了上限时表示队列满。 为区别队列空和队列满两种情况下可能出现的Q.front == Q.rear，有两种方法。一个是设置一个标识位，以区别头尾指针相同时队列是空还是满；另一个方法是牺牲一个元素空间，约定以Q.rear所指的下一个位置是Q.front时表示队列满。
链队列，链队列为空的判定条件是头尾指针相同且均指向头结点。
队列的应用：常用于需要排队的场合，如操作系统中的打印队列，离散事件的复读机模拟等。
5、串的定义：是仅由字符构成的有限序列。是取值范围受限的线性表。一般记为S = 'a1a2..an'。
串的几个概念：空串、空格串、子串、串相等、串比较。
串的几个操作：赋值操作StrAssign(s,t)、联接操作Concat(s,t)、求串长StrLength(s)、串比较StrCompare(s,t)、求子串SubString(s,start,len)。
串的存储：静态存储(顺序存储)，是定长的存储结构。当串超长时，超过部分将被截断。
堆存储，通过程序语言提供的字符数组定义串的存储空间，事先不限定串的长度，在程序执行过程中动态地申请地址连续的串值的空间。
块链存储，使用链表存储串值，每个结点可以存储一个或多个字符，同时每个结点设置一个指针指向后继结点。
串的模式匹配：朴素的模式匹配法、KMP算法。
6、数组：是定长线性表在维数上的扩张，即线性表中的每个元素又是一个线性表。N维数组是一种同构的数据结构，其每个数据元素类型相同，结构一致。
数组的特点： 数组元素数目固定。一旦定义了一个数组结构就不再有元素的增减变化；
数据元素具有相同的类型；
数据元素的下标关系受上下界的约束且下标有序。
数组的基本运算：
给定一组下标，存取相应的数据元素；
给定一组下标，修改相应的数据元素中的某个数据项的值。
数组的存储： 数组的固定结构适于使用顺序存储。对于数组，只要知道它的维数和长度，就可以为它分配存储空间。反之，只要给出一组下标就可以求出该数组元素的存储位置。就是说，在数组的顺序存储结构中，数据元素的位置是其下标的线性函数。
以行为主序； Loc(Aij) = Loc(Aij) + ((i-1)*n + (j-1))*L
以列为主序； Loc(Aij) = Loc(Aij) + ((j-1)*m + (i-1))*L
多维数组的顺序存储计算：例如3维数组A[1..10, 5..8, -3..6]，数组空间的起始位置是a，每个元素占4个存储单元，试以行为主存储和以列为主存储时给出数组元素A[i,j,k]的存储地址。
解：理解上面给出的以行为主序和以列为主序的两个线性函数公式。把3维数组拆开计算，例如以行为主序时先将3维数组看成是有一个行和2个列的数组，算出此时以行为主占用了多少空间。然后再单独看两个列的组合B[j,k]又会占用多少空间。前后结果相加就是这个3维数组元素在以行为主序存储时的地址。如下，
以行为主序时，A[i,j,k]前面的元素个数是： (i-1)(8-5+1)(6-(-3)+1) + (j-5)(6-(-3)+1) + k-(-3) = 40i-40 + 10j-50 + k+3 = 40i + 10j + k -87
因此A[i,j,k]的地址为a + (40i+10j+k-87)*4
以列为主序时，A[i,j,k]的地址为a + (40k+10j+i+69)*4
7、特殊矩阵与稀疏矩阵，稀疏矩阵就是非零元素很少的矩阵，而特殊矩阵是非零元素分布有规律的一类矩阵。为节省空间，在存储它们时都使用压缩存储，特殊矩阵有压缩算法，稀疏矩阵使用三元组顺序表或使用十字链表存储矩阵元素。
8、广义表的定义：是由零个或多个单元素或子表所组成的有限序列。广义表的长度是指广义表中元素的个数，深度是指广义表展开后所含的括号的最大层数。
广义表的基本运算：取表头head(LS)，非空广义表的第一个元素称为表头；
取表尾tail(LS)，非空广义表中除第一个元素之外，由其余元素构成的表称为表尾。表尾必定是一个表。
Head(LS)=a1, Tail(LS)=(a2,a3,...,an)
9、树的定义：树是n(n>=0)个结点的有限集合。当n=0时称为空树。在任一非空树中，有且仅有一个称为根的结点；其余m个结点可分为m(m>=0)个互不相交的有限集，其中每个子集合又都是一棵树，称为根结点的子树。
树的定义是递归的，树形结构具有明显的层次结构。
树的术语：双亲和孩子，兄弟，结点的度，叶子结点，内部结点，结点的层次，树的高度，有序树和无序树，森林。
树的基本操作是：先根遍历和后根遍历。
10、二叉树的定义：二叉树是另一种树形结构，它的特点是每个结点至多有两棵子树并且有左右之分，且左、右子树的次序不能颠倒。
满二叉树，若二叉树上每一层的结点数目都达到最大值，则称为满二叉树；
完全二叉树，若二叉树的除第H层以外，其余各层的结点数目达到了最大值，而第H层上的结点集中存放在左侧，则称为完全二叉树；
非完全二叉树，就是完全二叉树的相反情况。
二叉树的性质： 1）二叉树第i层(i>=1)上至多有2^(i-1)个结点；
2）深度为K的二叉树至多有2^k -1 个结点(k>=1)；
3）对任何一棵二叉树，若其终端结点个数为N0，度为2的结点个数为N2，则N0 = N2 + 1 ；
4）具有n个结点的完全二叉树的深度为log(2,n)+1;
5）对一棵有n个结点的完全二叉树的结点按层次自左至右进行编号，则对任一结点i (1<=i<=n)有：
若i=1，则i是根结点；若i>1则其双亲为i/2;
若2i>n,，则结点i无左孩子，否则其左孩子为2i;
若2i+1>n,则结点i无右孩子，否则其右孩子为2i+1;
例：一棵有124个叶结点的完全二叉树，最多有多少结点？
N0=N2+1
N=N0+N1+N2
N1=1
综合上面3个表达式可以求解。
例2：具有N个结点的满二叉树，其叶子结点个数为多少？
设其深度为h，则: N0=2^(h-1)
N = 2^h - 1
所以N0 = (n+1)/2
二叉树的存储结构：
二叉树的顺序存储结构，若采用二叉树的性质5对树中的结点进行编号，即树根结点的编号为1，若编号为i的结点存在左孩子，则其左孩子的编号为2i；若编号为i的结点存在右孩子，则其右孩子的编号为2i+1，这样利用数组元素的下标作为结点的编号，表示出结点间的关系。
二叉树的链式存储结构，二叉链表（有单向性）和三叉链表（有双向性）。
遍历二叉树，有4种方式：先序、中序、后序和层序遍历。
先序遍历二叉树的操作定义为：访问根结点；先序遍历根的左子树；先序遍历根的右子树。（若二叉树为空，则进行空操作）
中序遍历二叉树的操作定义为：中序遍历根的左子树；访问根结点；中序遍历根的右子树.（若二叉树为空，则进行空操作）
后序遍历二叉树的操作定义为：后序遍历根的左子树；后序遍历根的右子树；访问根结点。
层序遍历二叉树的操作定义为：从根结点开始，从或到右依次访问每层上的结点。
二叉树遍历思想的关键：首先在想象中把二叉树补齐为满二叉树，叶子结点也要被想象为有2个子结点。然后，画一条路线，从根出发，逆时针沿着二叉树的外缘移动，全程对每个结点均途经三次。若第一次经过时即访问，则是先序遍历；若是第二次经过结点时访问结点，则是中序遍历；若是第3次经过时访问则是后序遍历。这3种方法的路径相同，但结果不同。
遍历二叉树的基本操作就是，访问结点。--遍历二叉树实质上是按一定规则，将树中的结点排成一个线性序列。
11、线索二叉树：对于有N个结点的二叉树的二叉链表存储表示，其中必有N+1个空指针。遍历时使结点中原本为空的左孩子指针或（和）右孩子指针指向结点的前驱或（和）后继，这样的处理称为对二叉树的线索化，指向前驱或后继的指针称为线索。加上线索的二叉树称为线索二叉树。
为了区分结点中的指针是孩子还是线索，在结点结构中增加标志域ltag, rtag。两个标志取值0，则lchild,rchild域分别指向左孩子和右孩子；两个标志取值1，则lchild,rchild域分别指向直接前驱和直接后继。
访问线索二叉树时，如何查找结点的前驱和后继？以中序线索二叉树为例，令P指向树中的某个结点，
当p->ltag = 0时，P的中序直接前驱一定是其左子树进行中序遍历得到的最后一个结点，也可以沿P的左子树根结点出发沿右孩子指针向下查找，直到找到一个没有右孩子的结点时为止，该结点就是P的直接前驱结点，也称为P的左子树中“最右下”的结点。
当P->rtag = 0时，P的中序直接后继一定是其右子树进行中序遍历得到的第一个结点， 也可以沿P的右子树根结点出发沿左孩子指针向上查找，直到找到一个没有右孩子的结点时为止，该结点就是P的直接后继结点，也称为P的右子树中“最左下”的结点。
12、二叉树的应用：最优二叉树（又称霍夫曼树），是一种带权路径长度最短的树。
路径，是从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。
树的路径长度，是从根到每一个叶子结点之间的路径长度之和。
结点的带权路径长度，是从该结点到树根之间的路径长度与该结点权的乘积。
树的带权路径长度，是树的所有叶子结点的带权路径长度之和，记为 WPL 。
如何构造最优二叉树？使用霍夫曼算法如下：
1）将给定的N个结点的权值构成N棵二叉树的集合F，其中每棵树Ti只有一个权为Wi的根结点，其左右子树为空；
2）在F中选取两棵根结点的权值最小的树作为左右子树，并新生成一个根结点，根结点的权值为左右子树的权值和；
3）从F中删除被取出的两棵树并将新生成的树放入F；
4）重复2，3步骤到只剩一棵树为止，这棵树就是最优二叉树。最优二叉树的形式不唯一，但其WPL值却是唯一确定的。
霍夫曼编码：若要设计长度不等的编码，则任一字符的编码都不是其他字符编码的前缀，这种编码称为“前缀编码”。要设计总长最短的二进制前缀编码，应以N种字符出现的频率作为权来构造一棵霍夫曼树，由此得到的二进制前缀编码称为霍夫曼编码。树的左右分枝分别标上0和1（或相反）。从根到叶子路径上的0，1组成的串就是每个字符的二进制编码。
13、树的存储结构
1）树的双亲表示法，用一组连续的存储单元存储树的结点，并在每个结点中附设一个指示器，指示其双亲结点在该存储结构中的位置；
2）树的孩子表示法，是在存储结构中用指针指出结点的每个孩子。要为树的每个结点的孩子建立一个链表，则N个结点的树具有N个单链表，这N个单链表的头指针又排成了一个线性表（头指针即树的存储结构中每个结点的指示器）。
将上两种方法结合起来可以形成树的双亲孩子表示法。
3）树的孩子兄弟表示法，是指用二叉链表表示树。在链表的结点中设置两个指针域，分别指向该结点的第一个孩子和下一个兄弟。 |firstchild| data |nextbrother| 若将树的孩子指针解释为左孩子、兄弟指针解释为右孩子，则可以得到这棵树的二叉树结构。
14、树的遍历：
先根遍历；
后根遍历。
树进行先根遍历也就是对转换得到的二叉树进行先序遍历；对树进行后根遍历也就是对转换得到的二叉树进行中序遍历。
（先根遍历的顺序是：由根出发从左至右遍历每棵子树。后根遍历的顺序是从左至右从每棵子树的叶子结点向根的方向访问子树，最后访问根结点。）
15、森林的遍历：
先序遍历森林；
中序遍历森林。
先序遍历森林，若森林非空，访问森林中第一棵树的根结点，先序遍历第一棵子树根结点的子树森林，再先序遍历除第一棵树之外的树所构成的森林。
中序遍历森林，若森林非空，中序遍历森林中第一棵树的子树森林，再访问第一棵树的根结点，再中序遍历除第一棵树以外的树所构成的森林。
16、树、森林和二叉树的转换
利用树的孩子兄弟表示法可以由一棵树转成唯一的一棵二叉树。
森林如何转换成二叉树呢？因为树根没有兄弟，所以树转换成二叉树后一定没有右子树，所以森林转换成二叉树的方法是：
1）先将森林中的每棵树全转成二叉树；
2）用第一棵树的根做新二叉树的根，第一棵树转为二叉树后得到的左子树做为新二叉树的左子树，第二棵树作为新二叉树的右子树，第三棵树作为新二叉树的右子树的右子树，依此类推，森林便转为了一棵二叉树。
17、图的定义：在数据结构中，图是一个由顶点集合和边集合构成的二元组，其中边表示顶点之间的关系。
图的主要术语：
有向图，图中每条边都是有方向的，弧、弧尾、弧头；
无向图，图中的边是没有方向的，边；
无向完全图，图中的N个结点之间每两个结点间都有边，共有n(n-1)/2条边；
有向完全图，图中的N个结点之间每两个结点间都有方向相反的两条弧，共有n(n-1)条弧；
度、入度、出度，顶点v的度是指关联于该顶点的边的数目，记作D(v)。若是有向图则以该顶点为终点的有向边数目称为入度，从该顶点出发的有向边的数目称为出度，有向图的度是入库和出度的和。
路径，两个顶点之间由边组成的一条通路。若是有向图则路径也有方向。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路。若首尾顶点以外的顶点均不相同则是简单路径，若只有首尾顶点相同则称为简单回路。
子图，一个图的顶点集合与边集合都从属于另一个图，则称之为另一个图的子图；
连通图与连通分量，在无向图中若两个顶点之间有路径则称为这两个顶点是连通的。若无向图中任两个顶点间都是连通的则称其为连通图。该无向图的最大连通子图称为它的连通分量。
强连通图与强连通分量，是有向图的连通概念；
网，边（弧）带权值的图称为网；
生成树，是一个极小的连通子图，它包括图中的全部顶点，但只有构成一棵树的n-1条边；
有向树和生成森林，一个有向图恰有一个顶点的入度为0其它顶点的入度均为1，则这是一棵有向树。生成森林是一个有向图中的若干棵有向树组成，特点是含有全部顶点但只有足以构成若干棵不相交的有向树的弧。
图的存储结构：
邻接矩阵表示法，用于表示图有顶点之间的关系。对于个有n个顶点的图G＝（V，E）来说，其邻接矩阵就是一个n阶方阵。依靠判断图的两顶点间是否存在边或弧来决定Aij=1或Aij=0；网的邻接矩阵，当两顶点间存在边或弧时Aij等于权值否则Aij等于无穷。
邻接链表表示法，为图的每个顶点建立一个单链表，单链表中的结点表示依附于相应顶点的边或弧，有表头结点和表结点两种结构类型。
图的遍历：深度优先搜索；广度优先搜索。一个类似于先根遍历，一个类似于层序遍历。
生成树的概念：生成树是连通图的一个子图，它由全部顶点和一次遍历图所经过的边组成。图的生成树不惟一，按深度优先搜索得到深度优先生成树，按广度优先搜索得到广度优先生成树。一个非连通图，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，称为非连通图的生成树森林。
18、最小生成树：连通网的边是带有权值的，将生成树的各边权值和称为生成树的权。其中权值最小的生成树称为最小生成树。
构造最小生成树的两种算法：
普里母算法：以一个顶点集合U作为初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充U至U＝V时为止。例如初始只给U一个顶点且边的集合TE＝｛｝；这种算法的时间复杂度为O（n^2），因为它由顶点推算出的，所以适合于边稠密的网的最小生成树。
克鲁斯卡尔算法：假设连通网N＝（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T＝（V，｛｝），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。信此类推，直至T中所有顶点都在一个连通分量上为止。这种算法与顶点数无关，所以适合计算顶点多而边稀疏的网的最小生成树。
19、AOV网(active on vertex)：在有向图中，以顶点表示活动，用有向边表示活动之间的优先关系，这样的网称为AOV网。在AOV网中不应出现有向环。
拓朴排序：是将AOV网中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点Vi到Vj有一条路径，则在该线性序列中，顶点Vi必然在Vj之前。
拓朴排序的方法：在AOV网中选一个入度为0的顶点并输出它；从网中删除该顶点及与其有关的边；重复前两步至网中不存在入度为0的顶点为止。这样操作会有两种结果：一个是所有顶点已输出，也就是拓朴排序完成，说明网中不存在回路；另一个可能结果是尚有未输出的结点，剩余顶点均有前驱顶点，表明网中存在回路！
也可以进行逆拓朴排序，即计算出度为0的顶点。拓朴算法的时间复杂度为O(n+e)。
AOE网(active on edge)：，在带权有向图中，以事件表示顶点，以边表示活动，以边上的权值表示活动持续的时间，则这种网称为用边表示活动的网，简称AOE网。
AOE网特点：
1）顶点所表示的事件是指该顶点的所有进入边所表示的活动已完成，所有发出边表示的活动可以开始的一种状态。
2）对一个工程来说，要有一个开始状态和一个结束状态，所以在AOE网中有一个入度为0的开始顶点，称为源点；有一个出度为0的结束顶点，称为汇点。AOE网中也不允许存在回路。
3）完成整个工程的时间是从开始顶点到结束顶点间的最长路径的长度（指该路径上的权值和）。
活动的松驰时间：用活动的持续时间和该活动两侧的两个事件的关键路径时间，二者取差。
关键路径：从源点到汇点的路径长度最长路径称为关键路径。关键路径上的所有活动均是关键活动。
最短路径？？？
20、查找的基本概念
1）查找是一种常用的基本运算。查找表是由同一类型数据元素构成的集合；
2）静态查找表，指在进行查找运算时不再修改的已经构造好的查找表。静态查找表只进行两种操作：查询某个特定的数据元素是否在查找表中；检索某个特定的数据元素的各种属性。
3）动态查找表，是可以进行另两种操作的查找表，即在查找表中插入一个数据元素；从查找表中删除一个数据元素。
4）关键字，是数据元素的某个数据项的值，用它来识别这个数据元素；
5）主关键字，指能唯一标识一个数据元素的关键字；
6）次关键字，指能标识多个数据元素的关键字；
7）查找，根据给定的某个值，在查找表中确定是否存在一个其关键字等于给定值的记录，并返回结果。
顺序查找，从表的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字和给定值相等则查找成功；若整个表均比较过仍未找到则查找失败。若要查找的记录不在表中则需进行n+1次查找。
平均查找长度为(n+1)/2。
折半查找（二分查找），可以用二叉树进行分析，以中间记录为根，左子表为左子树，右子表为右子树，依此类推。关键字的比较次数即为被查找结点在树中的层数。查找成功或失败时所比较的关键字数不超过树的层数。折半查找只适用于有序顺序表（以数组方式存储的有序表）。 n=2^k - 1, k=log(n+1)
分块查找，又称为索引顺序查找，综合使用上面两种方法。
将长度为n的表均匀分为b块，每块含有s个记录，按顺序查找确定元素所在的块，则ASL = Lb + Lw , 即块内查找与索引查找之和。
ASL=(b+1)/2 + (s+1)/2 , 当s取n的平方根时，ASL取得最小值“n的平方根加1"。
21、二叉排序树（又称二叉查找树）：二叉查找树或者是一棵空树，或者具有这样的特性，
1）若二叉查找树的左子树非空，则左子树上的结点值均小于根结点的值；
2）若它的右子树非空，则右子树上的结点值均大于根结点的值；
3）左、右子树的子身就是一棵二叉查找树。
二叉查找树的查找过程从根结点开始，过程类似于折半查找（二分查找）。二叉查找树的插入操作按它的特性法则进行插入，若是空树则作根结点，否则会成为一个新的叶子结点。在二叉查找树中删除一个结点时不能把该结点的子树也删掉，只能删除这个结点但仍要保持二叉查找树的特性，相当于是从一个有序序列中删除一个元素，不能破坏其它元素的有序性。一种方法是，如果删除结点＊P，则可以用＊P的直接前驱或直接后继代替＊P，同时删除它的直接前驱（或直接后继）。
二叉排序树顺序存储在一地址连续的空间内，则序列按中序递增存储。
22、平衡二叉树：它或者是一棵空树，或者具有这样的性质：它的左右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。
平衡因子： 某结点的平衡因子定义为该结点的左子树深度减去它的右子树深度。平衡二叉树上的所有结点的平衡因子只可能是－1、0和1。
为了得到树形均匀的二叉排序树，在构造二叉排序树的过程中可以使用几种办法让它保持为一棵平衡二叉树。每插入一个新结点时，就检查是否打破了平衡。若是，则找出最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡二叉树中结点间关系，达到新的平衡。
最小不平衡二叉树是指离插入结点最近且以平衡因子的绝对值大于1的结点作为根的子树。
平衡二叉树上的插入操作引起不平衡的解决方法：
1）单向右旋平衡处理 －－用于在根的左子树根结点的左子树上插入新结点情况
2）单向左旋平衡处理 －－用于在根的右子树根结点的右子树上插入新结点情况
3）双向旋转（先左旋后右旋）操作 －－用于在根的左子树根结点的右子树上插入新结点的情况
4）双向旋转（先右旋后左旋）操作 －－用于在根的右子树根结点的左子树上插入新结点的情况
B树，有几个比较鲜明的特点。如：一棵m阶的B树中每个结点至多有m棵子树；非终结点（根除外）至少有m/2棵树；根至少有两棵子树（当根不是叶子时）；所有叶子结点出现在同一层次上。
23、哈希表的定义：根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关健字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表。这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。哈希函数是从关键字集合到地址集合的映像。
对于哈希表主要考虑两个问题：一是如何构造哈希函数；一是如何解决冲突。
构造哈希函数要解决好两个问题：首先哈希函数是一个压缩映像函数；其次哈希函数应具有较好的散列性。前者为节省空间，后者为减少冲突。常用的哈希函数构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法。
处理冲突的方法：
1）开放地址法 Hi = (H(key) + Di)%m i=1,2,...,k (k<=m-1)
H(key)为哈希函数；m为哈希表的表长；Di为增量序列。
Di=1,2,3,...,m-1 称为线性探测再散列；
Di=1^2,-1^2,2^2,-2^2...,k^2 (k<=m/2) 称为二次探测再散列；
Di＝伪随机序列，称为随机探测再散列。
最简单的产生探测序列的方法是线性探测，即当冲突时顺序对下一单元进行探测并存储。在用线性探测法解决冲突构造的哈希表中进行查找时有3种可能结果：一是在某一位置上找到关键字等于key的记录，查找成功；一是按探测序列查找不到而又遇到了空单元，查找失败，此时可进行插入操作；一是查遍全表，未查到指定关键字且存储区已满，要进行溢出处理。
线性探测法的缺点是“溢出处理需别编程序”，“很容易产生聚集现象”。
2）链地址法 ，它在符号表的每一个记录增加一个链域，链域中存放下一个有相同哈希函数值的记录的的存储地址。
3）再哈希法 ，Hi = RHi(key) i= 1,2,..,k RHi均是不同的哈希函数，即在同义词发生地址冲突时计算另一个哈希函数地址，直到解决。
4）建立一个公共溢出区，一溢出全放这里去；
哈希表的装填因子， a = (表中添入的记录数/哈希表长度） －－a越小，发生冲突的可能越小
虽然哈希表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得哈希表的查找过程仍是一个给定值和关键字进行比较的过程。仍须以平均查找长度衡量哈希表的查找效率。
在查找过程中须与给定值进行比较的关键字的个数取决于3个因素：哈希函数、处理冲突方法、哈希表的装填因子。
24、排序：稳定的排序、不稳定的排序。
内部排序、外部排序。
简单排序法：包括直接插入排序、冒泡排序和简单选择排序。它们的算法复杂度为O（n＾2），在元素已经基本有序的情况下，使用直接排序方法可获得较高的效率O(n)。直接插入排序和冒泡排序是稳定的排序方法，简单选择排序是不稳定的排序方法。
直接插入排序适用于”在文件局部有序或文件长度较小的情况下的一种最佳内部排序方法“。直接插入排序的时间复杂度为O(n*n)，若记录序列为正序时其时间复杂度可提高到O(n)。正序？？
冒泡排序算法： void bubblesort(int data[], int n){
int i,j,tag,temp;
for(i=0,tag=1;tag==1&&i<n-1;i++){
tag = 0;
for(j=0;j<n-i-1;j++)
if(data[j]>data[j+1]){
temp=data[j];data[j]=data[j+1];data[j+1]=temp;
tag=1;
}
}
}
简单选择排序算法：void selectsort(int data[], int n){
int i,j,k,temp;
for(i=0;i<n-1;i++){
k=i;
for(j=i+1;j<n;j++)
if(data[j]<data[k])k=j;
if(k!=j){
temp=data[i];data[i]=data[k];data[k]=temp;
}
}
}
希尔排序，又称为缩小增量排序。它是在直接插入排序的基础上加以改进得到的排序方法。基本思想就是：设定一个初始间隔d,d<n，按间隔d将元素分组，在每一组内进行直接插入排序，可以使得最小元素跳跃式向前移动。然后缩小增量d的值，重复上述操作到d=1时为止。
快速排序，基本思想是通过一趟排序将待排序的记录分割为独立的两部分，其中一部分的关键字均比另一部分小，然后再分别对这两部分记录继续进行排序。具体做法：在头尾设两个指针low,high，分别指向第一个元素和最后一个元素。设枢轴记录为正向（返向）的第一个记录。当初始序列有序时，快速排序蜕变为冒泡排序，此时算法的时间复杂度为n*n。
例如，对50个整数进行快速排序时，因为初始序列有序，所以排序过程退化为冒泡排序，总过程中的比较次数为49+48+...+1 = 49*50/2
堆排序，基本思想是对一组待排序记录的关键字，首选把它们按堆的定义排成一个序列，从而输出堆顶的最小关键字。然后将剩余关键字再调整成堆，便得到次小关键字，反复进行，直至全部关键字排成有序序列。
归并排序，是将两个或多个有序表合并成一个新的有序表。是一种稳定的排序。
基数排序，是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。它不是基于关键字比较的排序方法，其平均时间复杂度为O(d*n)，适合于n值很大而关键字较少的序列。
基于关键字比较的内部排序方法的时间复杂度的下限为O(nlogn)，简单排序、希尔排序、快速排序、堆排序和归并排序是要熟练掌握的排序方法。（重要）
排序方法好坏的两条因素：执行算法的时间；执行算法所需要的附加空间。
常用的外部排序方法是归并排序。
25、分治法，将一个规模为n的问题逐步分解为k个规模更小的子问题，这些子问题互相独立且与原问题性质相同，逐个解决分解出的子问题，由这些子问题的解构造出原问题的解，当k=2时称为二分法。如解决棋盘覆盖问题。
分治法适用的问题一般具有这些特征：
原问题可以分解成多个子问题，这些子问题与原问题相比只是规模的下降而其结构和求解方法与原问题相同；
若子问题的规模足够小，则直接求解，否则递归地求解子问题；
在得到各子问题的解后，能采用某种方法构造出原问题的解。
动态规划法，与分治法类似也是先将待求解的问题分解成若个个子问题，先求解子问题，然后从子问题的解得到原问题的解。不同的是适合于动态规划法求解的问题所分解得到的子问题之间往往不是独立的。动态规划法常用来求解具有最优性质的问题。即问题的最优解包含了其子问题的最优解。如求解多边形游戏问题。
设计动态规划法的步骤为：
1）找出最优解的性质，并刻画其结构特征；
2）递归地定义最优值；
3）以向前或向后处理方式计算出最优值；
4）根据计算最优值得到的信息，构造最优解。
贪心法，通过一系列的选择来得到一个问题的解，它所做的每一次选择都是当前情况下某种意义的最好选择，即贪心选择。如果待求解的问题具有最优子结构特征，也就是原问题的最优解包含子问题的最优解，并且可以通过局部的贪心选择来达到问题的全局最优解时，可通过贪心法进行求解。贪心标准的选择和问题的结构决定是否可以使用贪心法。如用于二分最小覆盖问题。
回溯法，又被称为通用解题法，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间中按深度优先策略，从根结点出发搜索解空间树。算法搜索到解空间树的任意结点时，首先判断该结点是否包含问题的解。如果不包含则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则进入这棵子树继续按深度优先搜索。如收费公路重建问题。
分支限界法，它类似于回溯法，也是在解空间中搜索问题解的算法，但分支限界法求解的目标是找出满足条件的一个解，如有多个解则要找出某种意义下的最优解。分支限界法以广度优先或以最小耗费优先的方式搜索解空间树。如最大完备子图问题。
26、算法的几个基本特征
有穷性，确定性，能行性，输入，输出。
程序 ＝ 数据结构 ＋ 算法
内容关键字：
线性表、栈、队、串、数组
树、二叉树、森林、线索二叉树、霍夫曼树
图、有向图、无向图、最小生成树、拓朴排序、关键路径
查找、静态查找（顺序、折半、分块）、动态查找（二叉排序树、平衡二叉树、哈希表）
排序、直接插入、简单选择、冒泡、希尔、快速、堆、归并、基数