第六章 树

　　树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称根的子树。

　　根是开始结点；结点的子树数称度；度为0的结点称叶子（终端结点）；度不为0的结点称分支结点（非终端结点）；除根外的分支结点称内部结点；

　　有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是m个互不相交的树的集合；

　　树的四种不同表示方法：·树形表示法；·嵌套集合表示法；·凹入表示法·广义表表示法。

　　二叉树的定义：是n≥0个结点的有限集，它是空集（n=0）或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。

　　二叉树不是树的特殊情形，与度数为2的有序树不同。

　　二叉树的4个重要性质： ·。二叉树上第i层上的结点数目更多为2^（i-1）（i≥1）。；

　　·深度为k的二叉树至多有（2^k）-1个结点（k≥1）；

　　·。在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1；

　　·。具有n个结点的完全二叉树的深度为int（log2n）+1.

　　满二叉树是一棵深度为k，结点数为（2^k）-1的二叉树；完全二叉树是满二叉树在更下层自右向左去处部分结点；

　　二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。（存储前先将其画成完全二叉树）

　　树的存储结构多用的是链式存储。BinTNode的结构为lchild|data|rchild，把所有BinTNode类型的结点，加上一个指向根结点的BinTree型头指针就构成了二叉树的链式存储结构，称为二叉链表。它就是由根指针root唯一确定的。共有2n个指针域，n+1个空指针。

　　根据访问结点的次序不同可得三种遍历：先序遍历（前序遍历或先根遍历），中序遍历（或中根遍历）、后序遍历（或后根遍历）。时间复杂度为O（n）。

　　利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为“线索”，加上线索的二叉链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结点的前序前趋和后序后继并没有什么作用。

　　树和森林及二叉树的转换是唯一对应的。

　　转换方法： ·树变二叉树：兄弟相连，保留长子的连线。

　　·二叉树变树：结点的右孩子与其双亲连。

　　·森林变二叉树：树变二叉树，各个树的根相连。

　　树的存储结构：·有双亲链表表示法：结点data | parent，对于求指定结点的双亲或祖先十分方便，但不适于求指定结点的孩子及后代。

　　·孩子链表表示法：为树中每个结点data | next设置一个孩子链表firstchild，并将data | firstchild存放在一个向量中。

　　·双亲孩子链表表示法：将双亲链表和孩子链表结合。

　　·孩子兄弟链表表示法：结点结构leftmostchild |data | rightsibing，附加两个分别指向该结点的更左孩子和右邻兄弟的指针域。

　　树的前序遍历与相对应的二叉树的前序遍历一致；树的后序遍历与相对应的二叉树的中序遍历一致。

　　树的带权路径长度是树中所有叶结点的带权路径长度之和。树的带权路径长度更小的二叉树就称为更优二叉树（即哈夫曼树）。

　　在叶子的权值相同的二叉树中，完全二叉树的路径长度更短。

　　哈夫曼树有n个叶结点，共有2n-1个结点，没有度为1的结点，这类树又称为严格二叉树。

　　变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性。如00、01、0001这三个码无法在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这种码称为前缀码（其实是非前缀码）。

　　哈夫曼树的应用更广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的更优前缀码。哈夫曼编码的构造很容易，只要画好了哈夫曼树，按分支情况在左路径上写代码0，右路径上写代码1，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的更优前缀码。

　　第七章 图

　　图的逻辑结构特征就是其结点（顶点）的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。

　　图GraphG=（V，E），V是顶点的有穷非空集合，E是顶点偶对的有穷集。

　　有向图Digraph：每条边有方向；无向图Undigraph：每条边没有方向。

　　有向完全图：具有n*（n-1）条边的有向图；无向完全图：具有n*（n-1）/2条边的无向图；

　　有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开始和终端重合的简单路径；

　　网络：是带权的图。

　　图的存储结构：

　　·邻接矩阵表示法：用一个n阶方阵来表示图的结构是唯一的，适合稠密图。

　　·无向图：邻接矩阵是对称的。

　　·有向图：行是出度，列是入度。

　　建立邻接矩阵算法的时间是O（n+n^2+e），其时间复杂度为O（n^2）

　　·邻接表表示法：用顶点表和邻接表构成不是唯一的，适合稀疏图。·顶点表结构 vertex | firstedge，指针域存放邻接表头指针。

　　·邻接表：用头指针确定。 ·无向图称边表；

　　·有向图又分出边表和逆邻接表；

　　·邻接表结点结构为 adjvex | next，

　　时间复杂度为O（n+e）。，空间复杂度为O（n+e）。。

　　图的遍历： ·深度优先遍历：借助于邻接矩阵的列。使用栈保存已访问结点。

　　·广度优先遍历：借助于邻接矩阵的行。使用队列保存已访问结点。

　　生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图称作该图的生成树。

　　更小生成树：图的生成树不唯一，从不同的顶点出发可得到不同的生成树，把权值更小的生成树称为更小生成树（MST）。

　　构造更小生成树的算法： ·Prim算法的时间复杂度为O（n^2）与边数无关适于稠密图。

　　·Kruskal算法的时间复杂度为O（lge），主要取决于边数，较适合于稀疏图。

　　更短路径的算法：·Dijkstra算法，时间复杂度为O（n^2）。·类似于prim算法。

　　拓扑排序：是将有向无环图G中所有顶点排成一个线性序列，若<u，v>∈E（G），则在线性序列u在v之前，这种线性序列称为拓扑序列。

　　拓扑排序也有两种方法：·无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，更后得到的序列即拓扑序列。

　　·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，更后得到的序列是逆拓扑序列。

　　第八章 排序

　　记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。

　　排序是使文件中的记录按关键字递增（或递减）次序排列起来。

　　·基本操作：比较关键字大小；改变指向记录的指针或移动记录。

　　·存储结构：顺序结构、链表结构、索引结构。

　　经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的，否则排序算法是不稳定的。

　　排序过程中不涉及数据的内、外存交换则称之为“内部排序”（内排序），反之，若存在数据的内外存交换，则称之为外排序。

　　内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。

　　评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。

　　插入排序：·直接插入排序： ·逐个向前插入到合适位置。

　　·哨兵（监视哨）有两个作用： ·作为临变量存放R[i]

　　·是在查找循环中用来监视下标变量j是否越界。

　　·直接插入排序是就地的稳定排序。时间复杂度为O（n^2），比较次数为（n+2）（n-1）/2；移动次数为（n+4）（n-1）/2；

　　·希尔排序： ·等间隔的数据比较并按要求顺序排列，更后间隔为1.

　　·希尔排序是就地的不稳定排序。时间复杂度为O（n^1.25），比较次数为（n^1.25）；移动次数为（1.6n^1.25）；

　　交换排序：·冒泡排序：·自下向上确定更轻的一个。·自上向下确定更重的一个。·自下向上确定更轻的一个，后自上向下确定更重的一个。

　　·冒泡排序是就地的稳定排序。时间复杂度为O（n^2），比较次数为n（n-1）/2；移动次数为3n（n-1）/2；

　　·快速排序：·以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。

　　·快速排序是非就地的不稳定排序。时间复杂度为O（nlog2n），比较次数为n（n-1）/2；

　　选择排序：·直接选择排序： ·选择更小的放在比较区前。

　　·直接选择排序就地的不稳定排序。时间复杂度为O（n^2）。比较次数为n（n-1）/2；

　　·堆排序  ·建堆：按层次将数据填入完全二叉树，从int（n/2）处向前逐个调整位置。

　　·然后将树根与更后一个叶子交换值并断开与树的连接并重建堆，直到全断开。

　　·堆排序是就地不稳定的排序，时间复杂度为O（nlog2n），不适宜于记录数较少的文件。

　　归并排序： ·先两个一组排序，形成（n+1）/2组，再将两组并一组，直到剩下一组为止。

　　·归并排序是非就地稳定排序，时间复杂度是O（nlog2n），

　　分配排序：·箱排序： ·按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。

　　·箱排序的平均时间复杂度是线性的O（n）。

　　·基数排序：·从低位到高位依次对关键字进行箱排序。

　　·基数排序是非就稳定的排序，时间复杂度是O（d*n+d*rd）。

　　各种排序方法的比较和选择： ·。待排序的记录数目n；n较大的要用时间复杂度为O（nlog2n）的排序方法；

　　·记录的大小（规模）；记录大更好用链表作为存储结构，而快速排序和堆排序在链表上难于实现；

　　·关键字的结构及其初始状态；

　　·对稳定性的要求；

　　·语言工具的条件；

　　·存储结构；

　　·时间和辅助空间复杂度。

　　第九章 查找

　　查找的同时对表做修改操作（如插入或删除）则相应的表称之为动态查找表，否则称之为静态查找表。

　　衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数（即平均查找长度ASL）。

　　线性表查找的方法： ·顺序查找：逐个查找，ASL=（n+1）/2；

　　·二分查找：取中点int（n/2）比较，若小就比左区间，大就比右区间。用二叉判定树表示。ASL=（∑（每层结点数*层数））/N.

　　·分块查找。要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的更大关键字及其位置建立有序索引表。

　　二叉排序树（BST）定义是：二叉排序树是空树或者满足如下性质的二叉树： ·若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

　　·若它的右子树非空，则右子树上所有结点的值均大于根结点的值；

　　·左、右子树本身又是一棵二叉排序树。

　　二叉排序树的插入、建立、删除的算法平均时间性能是O（nlog2n）。

　　二叉排序树的删除操作可分三种情况进行处理： ·*P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。

　　·*P只有一个孩子*child，此时只需将*child和*p的双亲直接连接就可删去*p.

　　·*p有两个孩子，则先将*p结点的中序后继结点的数据到*p，删除中序后继结点。

　　关于B-树（多路平衡查找树）。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。建立的方式是从下向上拱起。

　　散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。散列函数的选择有两条标准：简单和均匀。

　　常见的散列函数构的造方法：

　　·。平方取中法：hash=int（（x^2）%100）

　　·。除余法：表长为m，hash=x%m

　　·。相乘取整法：hash=int（m*（x*A-int（x*A））；A=0.618

　　·。随机数法：hash=random（x）。

　　处理冲突的方法：·开放定址法： ·一般形式为hi=（h（key）+di）%m1≤i≤m-1，开放定址法要求散列表的装填因子α≤1.

　　·开放定址法类型： ·线性探查法：address=（hash（x）+i）%m；

　　·二次探查法：address=（hash（x）+i^2）%m；

　　·双重散列法：address=（hash（x）+i*hash（y））%m；

　　·拉链法： ·是将所有关键字为同义词的结点链接在同一个单链表中。

　　·拉链法的优点： ·拉链法处理冲突简单，且无堆积现象；

　　·链表上的结点空间是动态申请的适于无法确定表长的情况；

　　·拉链法中α可以大于1，结点较大时其指针域可忽略，因此节省空间；

　　·拉链法构造的散列表删除结点易实现。

　　·拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。

　　第十章 文件

　　文件是性质相同的记录的集合。记录是文件中存取的基本单位，数据项是文件可使用的更小单位，数据项有时称字段或者属性。

　　文件　·逻辑结构是一种线性结构。

　　·操作有：检索和维护。并有实时和批量处理两种处理方式。

　　文件　·存储结构是指文件在外存上的组织方式。

　　·基本的组织方式有：顺序组织、索引组织、散列组织和链组织。

　　·常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。

　　评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。

　　检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。

　　顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。主关键字有序称顺序有序文件，否则称顺序无序文件。

　　一切存储在顺序存储器（如磁带）上的文件都只能顺序文件，只能按顺序查找法存取。

　　顺序文件的插入、删除和修改只能通过复制整个文件实现。

　　索引文件的组织方式：通常是在主文件之外建立一张索引表指明逻辑记录和物理记录之间一一对应的关系，它和主文件一起构成索引文件。

　　索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。

　　若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。是一种静态索引。

　　索引顺序文件常用的有两种：

　　·ISAM索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引结构。

　　·VSAM虚拟存储存取方法：采用B+树作为动态索引结构，由索引集、顺序集、数据集组成。

　　散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。

　　散列文件

　　·优点是：文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区，节省存储空间。

　　·缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。

　　多重表文件：对需要查询的次关键字建立相应的索引，对相同次关键字的记录建一个链表并将链表头指针、长度、次关键字作为索引表的索引项。

　　倒排表：次关键字索引表称倒排表，主文件和倒排表构成倒排文件。