|
|
|
|
|
|
|
算法是问题求解过程的精确描述，它为解决某一特定类型的问题规定了一个运算过程，并且具有下列特性：
|
|
|
|
（1）有穷性。一个算法必须在执行有穷步骤之后结束，且每一步都可在有穷时间内完成。
|
|
|
|
（2）确定性。算法的每一步必须是确切定义的，不能有歧义。
|
|
|
|
（3）可行性。算法应该是可行的，这意味着算法中所有要进行的运算都能够由相应的计算装置所理解和实现，并可通过有穷次运算完成。
|
|
|
|
（4）输入。一个算法有零个或多个输入，它们是算法所需的初始量或被加工的对象的表示。这些输入取自特定的对象集合。
|
|
|
|
（5）输出。一个算法有一个或多个输出，它们是与输入有特定关系的量。
|
|
|
|
因此，算法实质上是特定问题的可行的求解方法、规则和步骤。一个算法的优劣可从以下几个方面考查：
|
|
|
|
（1）正确性。正确性也称为有效性，是指算法能满足具体问题的要求。即对任何合法的输入，算法都能得到正确的结果。
|
|
|
|
（2）可读性。可读性指算法被理解的难易程度。人们常把算法的可读性放在比较重要的位置，因为晦涩难懂的算法不易交流和推广使用，也难以修改和扩展。因此，设计的算法应尽可能简单易懂。
|
|
|
|
（3）健壮性。健壮性也称为鲁棒性，即对非法输入的抵抗能力。对于非法的输入数据，算法应能加以识别和处理，而不会产生误动作或执行过程失控。
|
|
|
|
（4）效率。粗略地讲，就是算法运行时花费的时间和使用的空间。对算法的理想要求是运行时间短、占用空间小。
|
|
|
|
|
|
算法与数据结构密切相关，算法实现时总是建立在一定的数据结构基础之上。
|
|
|
|
计算机程序从根本上看包括两方面的内容：一是对数据的描述，二是对操作（运算）的描述。概括来讲，在程序中需要指定数据的类型和数据的组织形式就是定义数据结构，描述的操作步骤就构成了算法。因此，从某种意义上可以说“数据结构＋算法＝程序”。
|
|
|
|
当然，设计程序时还需选择不同的程序设计方法、程序语言及工具。但是，数据结构和算法仍然是程序中最为核心的内容。用计算机求解问题时，一般应先设计初步的数据结构，然后再考虑相关的算法及其实现。设计数据结构时应当考虑可扩展性，修改数据结构会影响算法的实现方案。
|
|
|
|
|
|
算法的描述方法有很多，若用程序语言描述，就成了计算机程序。常用的算法描述方法有流程图、N/S盒图、伪代码和决策表等。
|
|
|
|
（1）流程图。流程图（flow chart）即程序框图，是历史最久、流行最广的一种算法的图形表示方法。每个算法都可由若干张流程图描述。流程图给出了算法中所进行的操作以及这些操作执行的逻辑顺序。程序流程图包括三种基本成分：加工步骤，用方框表示；逻辑条件，用菱形表示；控制流，用箭头表示。流程图中常用的几种符号如下图所示。
|
|
|
|
|
|
|
|
例如，求正整数m和n的最大公约数流程图如下图（a）所示。
|
|
|
|
|
|
|
若流程图中的循环结构通过控制变量以确定的步长进行计次循环，则可用 和 分别表示“循环开始”和“循环结束”，并在“循环开始”框中标注“循环控制变量：初始值，终止值，增量”，如上图（b）所示。
|
|
|
|
（2）N/S盒图。盒图是结构化程序设计出现之后，为支持这种设计方法而产生的一种描述工具。N/S盒图的基本元素与控制结构如下图所示。在N/S图中，每个处理步骤用一个盒子表示，盒子可以嵌套。对于每个盒子，只能从上面进入，从下面走出，除此之外别无其他出入口，所以盒图限制了随意的控制转移，保证了程序的良好结构。
|
|
|
|
|
|
|
|
用N/S盒图描述求最大公约数的欧几里德算法，如下图所示。
|
|
|
|
|
|
|
|
（3）伪代码。用伪代码描述算法的特点是借助于程序语言的语法结构和自然语言叙述，使算法具有良好的结构又不拘泥于程序语言的限制。这样的算法易读易写，而且容易转换成程序。
|
|
|
|
（4）决策表。决策表是一种图形工具，它将比较复杂的决策问题简洁、明确、一目了然地描述出来。例如，如果订购金额超过500元，以前没有欠账，则发出批准单和提货单；如果订购金额超过500元，但以前的欠账尚未还清，则发不予批准的通知；如果订购金额低于500元，则不论以前的欠账是否还清都发批准单和提货单，在欠账未还清的情况下还要发出“催款单”。处理该问题的决策表如下表所示。
|
|
|
|
|
|
|
|
|
|
解决同一个问题总是存在多种算法，每个算法在计算机上执行时，都要消耗时间（CPU执行指令的时间）和使用存储空间资源。因此，设计算法时需要考虑算法运行时所花费的时间和使用的空间，以时间复杂度和空间复杂度表示。
|
|
|
|
由于算法往往和需要求解的问题规模相关，因此常将问题规模n作为一个参照量，求算法的时间、空间开销和n的关系。详细分析指令的执行时间会涉及计算机运行过程的细节，因此时间消耗情况难以精确表示，所以算法分析时常采用算法的时空开销随n的增长趋势来表示其时空复杂度。
|
|
|
|
对于一个算法的时间开销T（n），从数量级大小考虑，当n增大到一定值后，T（n）计算公式中影响最大的就是n的幂次最高的项，其他的常数项和低幂次项都可以忽略，即釆用渐进分析，表示为T（n）=O（f（n））。其中，n反映问题的规模，T（n）是算法运行所消耗时间或存储空间的总量，O是数学分析中常用的符号“大O”，而f（n）是自变量为n的某个具体的函数表达式。例如，若f（n）=n2+2n+1，则T（n）=O（n2）。
|
|
|
|
|
|
语句频度（frequency count）是指语句被重复执行的次数，即对于某个基本语句，若在算法的执行过程中被执行n次，则其语句频度为n。这里的“语句”是指描述算法的基本语句（基本操作），它的执行是不可分割的，因此，循环语句的整体、函数调用语句不能算作基本语句，因为它们还包括循环体或函数体。
|
|
|
|
算法中各基本语句的语句频度之和表示算法的执行时间。
|
|
|
|
例如，对于下面的三个程序段（1）、（2）、（3），其实现基本操作“x增1”的语句++x的语句频度分别为1、n、n2。
|
|
|
|
|
|
（2）for（i=1；i<=n；i++）｛s+=x；++x；｝
|
|
|
|
|
|
|
|
|
|
因此，程序段（1）、（2）、（3）的时间复杂度分别为O（1）、O（n）、O（n2），分别称为常量阶、线性阶和平方阶。若程序段（1）、（2）、（3）组成一个算法的整体，则该算法的时间复杂度为O（n2）。
|
|
|
|
|
|
假设含n个记录的文件内容为｛R1，R2，…，Rn｝，其相应的关键字为｛k1，k2，…，kn｝。经过排序确定一种排列｛Rj1，Rj2，…，Rjn｝，使得它们的关键字满足如下递增（或递减）关系：kj1≤kj2≤…≤kjn（或kj1≥kj2≥…≥kjn）。
|
|
|
|
|
|
若在待排序的一组序列中，Ri和Rj的关键字相同，即ki=kj，且在排序前Ri领先于Rj，那么当排序后，如果Ri和Rj的相对次序保持不变，Ri仍领先于Rj，则称此类排序方法为稳定的。若在排序后的序列中有可能出现Rj领先于Ri的情形，则称此类排序为不稳定的。
|
|
|
|
|
|
内部排序是指待排序记录全部存放在内存中进行排序的过程。
|
|
|
|
外部排序是指待排序记录的数量很大，以至内存不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
|
|
|
|
|
|
|
|
|
|
|
|
这里的简单排序包括直接插入排序、冒泡排序和简单选择排序。
|
|
|
|
|
|
直接插入排序是一种简单的排序方法，具体做法是：在插入第i个记录时，R1，R2，…，Ri-1己经排好序，这时将记录Ri的关键字ki依次与关键字ki-1，ki-2，…，k1进行比较，从而找到Ri应该插入的位置，插入位置及其后的记录依次向后移动。
|
|
|
|
|
|
|
直接插入排序法在最好情况下（待排序列已按关键码有序），每趟排序只需作1次比较且不需要移动元素，因此n个元素排序时的总比较次数为n-1次，总移动次数为0次。在最坏情况下（元素已经逆序排列），进行第i趟排序时，待插入的记录需要同前面的i个记录都进行1次比较，因此，总比较次数为 。排序过程中，第i趟排序时移动记录的次数为i+1（包括移进、移出temp），总移动次数为 。
|
|
|
|
由此，直接插入排序是一种稳定的排序方法，其时间复杂度为O（n2）。排序过程中仅需要一个元素的辅助空间，空间复杂度为O（1）。
|
|
|
|
|
|
n个记录进行冒泡排序的方法是：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换两个记录的值，然后比较第二个记录和第三个记录的关键字，以此类推，直至第n-1个记录和第n个记录的关键字比较完为止。上述过程称作一趟冒泡排序，其结果是关键字最大的记录被交换到第n个位置。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是关键字次大的记录被交换到第n-1个位置。当进行完第n-1趟时，所有记录有序排列。
|
|
|
|
|
|
|
冒泡排序法在最好情况下（待排序列已按关键码有序）只需作1趟排序，元素的比较次数为n-1且不需要交换元素，因此总比较次数为n-1次，总交换次数为0次。在最坏情况下（元素已经逆序排列），进行第i趟排序时，最大的i-1个元素已经排好序，其余的n-（i-1）个元素需要进行n-i次比较和n-i次交换，因此总比较次数为 ，总交换次数为 。
|
|
|
|
由此，冒泡排序是一种稳定的排序方法，其时间复杂度为O（n2）。排序过程中仅需要一个元素的辅助空间用于元素的交换，空间复杂度为O（1）。
|
|
|
|
|
|
n个记录进行简单选择排序的基本方法是：通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录进行交换，当i等于n时所有记录有序排列。
|
|
|
|
|
|
|
简单选择排序法在最好情况下（待排序列已按关键码有序）不需要移动元素，因此n个元素排序时的总移动次数为0次。在最坏情况下（元素已经逆序排列），每趟排序移动记录的次数都为3次（两个数组元素交换值），共进行n-1趟排序，总移动次数为3（n-1）。无论在哪种情况下，元素的总比较次数为 。
|
|
|
|
由此，简单选择排序是一种不稳定的排序方法，其时间复杂度为O（n2）。排序过程中仅需要一个元素的辅助空间用于数组元素值的交换，空间复杂度为O（1）。
|
|
|
|
|
|
希尔排序又称“缩小增量排序”，是对直接插入排序方法的改进。
|
|
|
|
希尔排序的基本思想是：先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。具体做法是：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1组，将所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2（d2<d1），重复上述的分组和直接插入排序过程，依此类推，直至所取的增量di=1（di<di-1<…d2<d1），即所有记录放在同一组进行直接插入排序为止。
|
|
|
|
增量序列为5，3，1时，希尔插入排序过程如下图所示。
|
|
|
|
|
|
|
|
|
|
|
|
快速排序的基本思想是：通过一趟排序将待排的记录划分为独立的两部分，称为前半区和后半区，其中，前半区中记录的关键字均不大于后半区记录的关键字，然后再分别对这两部分记录继续进行快速排序，从而使整个序列有序。
|
|
|
|
一趟快速排序的过程称为一次划分，具体做法是：附设两个位置指示变量i和j，它们的初值分别指向序列的第一个记录和最后一个记录。设枢轴记录（通常是第一个记录）的关键字为pivot，则首先从j所指位置起向前搜索，找到第一个关键字小于pivot的记录时将该记录向前移到i指示的位置，然后从i所指位置起向后搜索，找到第一个关键字大于pivot的记录时将该记录向后移到j所指位置，重复该过程直至i与j相等为止。
|
|
|
|
|
|
|
|
|
|
|
|
快速排序算法的时间复杂度为O（nlog2n），在所有算法复杂度为此数量级的排序方法中，快速排序被认为是平均性能最好的一种。但是，若初始记录序列按关键字有序或基本有序时，即每次划分都是将序列划分为某一半序列的长度为0的情况，此时快速排序的性能退化为时间复杂度是O（n2）。快速排序是不稳定的排序方法。
|
|
|
|
|
|
对于n个元素的关键字序列｛k1，k2，…，kn｝，当且仅当满足下列关系时称其为堆。
|
|
|
|
|
|
若将此序列对应的一维数组（即以一维数组作为序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。因此，在一个堆中，堆顶元素（即完全二叉树的根结点）必为序列中的最小元素（或最大元素），并且堆中任一棵子树也都是堆。若堆顶为最小元素，则称为小顶堆；若堆顶为最大元素，则称为大顶堆。
|
|
|
|
例如，将序列（48，37，64，96，75，12，26，54，03，33）中的元素依次放入一棵完全二叉树中，如下图（a）所示。显然，它既不是大顶堆（48<64），也不是小顶堆（48>37），调整为大顶堆后如下图（b）所示。
|
|
|
|
|
|
|
|
堆排序的基本思想是：对一组待排序记录的关键字，首先把它们按堆的定义排成一个序列（即建立初始堆），从而输出堆顶的最小关键字（对于小顶堆而言）。然后将剩余的关键字再调整成新堆，便得到次小的关键字，如此反复，直到全部关键字排成有序序列为止。
|
|
|
|
n个元素进行堆排序时，时间复杂度为O（nlog2n），空间复杂度为O（1）。堆排序是不稳定的排序方法。
|
|
|
|
|
所谓“归并”，是将两个或两个以上的有序文件合并成为一个新的有序文件。从线性表的讨论可知，将两个有序表合并成为一个有序表，无论是顺序存储结构还是链式存储结构，都是容易实现的。利用归并的思想可以进行排序。归并排序是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，得到 个长度为2或1的有序文件，再两两归并，如此重复，直至最后形成包含n个记录的有序文件为止。这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。
|
|
|
|
n个元素进行二路归并排序的时间复杂度为O（nlog2n），空间复杂度为O（n）。二路归并排序是稳定的排序方法。
|
|
|
|
|
|
综合比较以上所讨论的各种排序方法，大致结果如下表所示。
|
|
|
|
|
|
|
|
不同的排序方法各有优缺点，可根据需要运用到不同的场合。选取排序方法时需要考虑的主要因素有：待排序的记录个数n，记录本身的大小，关键字的分布情况，对排序稳定性的要求，语言工具的条件，辅助空间的大小等。
|
|
|
|
|
|
（1）若待排序的记录数目n较小时，可采用插入排序和简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因此当记录本身信息量较大时，用简单选择排序方法较好。
|
|
|
|
（2）若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序。
|
|
|
|
（3）若n较大，则应采用时间复杂度为O（nlog2n）的排序方法，例如快速排序、堆排序或归并排序。
|
|
|
|
快速排序在目前内部排序方法中被认为是最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短；堆排序只需一个辅助存储空间，并且不会出现在快速排序中可能出现的最坏情况。这两种排序方法都是不稳定的排序方法，若要求排序稳定，可选择归并排序。通常可将归并排序和直接插入排序结合起来使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并。
|
|
|
|
前面讨论的内部排序算法都是在一维数组上实现的。当记录本身信息量较大时，为避免耗费大量的时间移动记录，可以采用链表作为存储结构。
|
|
|
|
|
|
外部排序就是对大型文件的排序，待排序的记录存放在外存。在排序的过程中，内存只存储文件的一部分记录，整个排序过程需要进行多次内外存间的数据交换。
|
|
|
|
常用的外部排序方法是归并排序，一般分为两个阶段：在第一阶段，把文件中的记录分段读入内存，利用某种内部排序方法对这段记录进行排序并输出到外存的另一个文件中，在新文件中形成许多有序的记录段，称为归并段；在第二阶段，对第一阶段形成的归并段用某种归并方法进行一趟趟地归并，使文件的有序段逐渐加长，直到将整个文件归并为一个有序段时为止。
|
|
|
|
|
|
查找是非数值数据处理中一种常用的基本运算，查找运算的效率与查找表所采用的数据结构和查找方法密切相关。
|
|
|
|
|
|
查找表是指由同一类型的数据元素（或记录）构成的集合。由于“集合”这种数据结构中的数据元素之间存在着完全松散的关系，因此，查找表是一种非常灵活的数据结构，分为静态查找表和动态查找表，哈希表是一种动态查找表。
|
|
|
|
（1）静态查找表。对查找表经常要进行的两种操作如下：
|
|
|
|
|
|
|
|
|
|
（2）动态查找表。对查找表经常要进行的另外两种操作如下：
|
|
|
|
|
|
|
|
若在查找过程中还可能插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称相应的查找表为动态查找表。
|
|
|
|
（3）关键字。关键字是数据元素（或记录）的某个数据项的值，用它来识别（标识）这个数据元素（或记录）。主关键字是指能唯一标识一个数据元素的关键字；次关键字是指能标识多个数据元素的关键字。
|
|
|
|
（4）查找。根据给定的某个值，在查找表中确定是否存在一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找成功，此时或者给出整个记录的信息，或者指出记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时的查找结果用一个“空记录”或“空指针”表示。
|
|
|
|
（5）平均查找长度。对于查找算法来说，其基本操作是“将记录的关键字与给定值进行比较”。因此，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量查找算法好坏的依据。
|
|
|
|
为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。
|
|
|
|
对于含有n个记录的表，查找成功时的平均查找长度定义为：
|
|
|
|
|
其中，Pi为对表中第i个记录进行查找的概率，且 ，一般情况下，均认为查找每个记录的概率是相等的，即Pi=1/n；Ci为找到表中其关键字与给定值相等的记录时（为第i个记录），和给定值已进行过比较的关键字个数。显然，Ci随查找方法的不同而不同。
|
|
|
|
|
|
从表中的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。
|
|
|
|
顺序查找的方法对于顺序存储和链式存储方式的查找表都适用。
|
|
|
|
从顺序查找的过程可见，Ci取决于所查记录在表中的位置。若需查找的记录正好是表中的第一个记录时，仅需比较一次；若查找成功时找到的是表中的最后一个记录，则需比较n次。一般情况下，Ci=n-i+1，因此在等概率情况下，顺序查找成功的平均查找长度为：
|
|
|
|
|
|
也就是说，成功查找的平均比较次数约为表长的一半。若所查记录不在表中，则至少进行n次比较才能确定失败。
|
|
|
|
与其他查找方法相比，顺序查找方法在n值较大时，其平均查找长度较大，查找效率较低。但这种方法也有优点，那就是算法简单且适应面广，对查找表的结构没有要求，无论记录是否按关键字有序排列均可应用。
|
|
|
|
|
|
折半查找也称为二分查找，其基本思想是：先令查找表中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时（表明查找不成功）为止。
|
|
|
|
设查找表的元素存储在一维数组r［1..n］中，那么在表中的元素已经按关键字递增（或递减）排序的情况下，进行折半查找的方法是：首先比较key值与表r中间位置（下标为mid）的记录的关键字，若相等，则查找成功。若key>r［mid］.key，则说明待查记录只可能在后半个子表r［mid+1..n］中，下一步应在后半个子表中再进行折半查找；若keyr的前半个子表中进行折半查找。这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。
|
|
|
|
【函数】设有一个整型数组中的元素是按非递减的方式排列的，在其中进行折半查找的算法如下：
|
|
|
|
|
|
折半查找的过程可以用一棵二叉树描述，方法是：以当前查找区间的中间位置上的记录作为根，左子表和右子表中的记录分别作为根的左子树和右子树上的结点，这样构造的二叉树称为折半查找判定树。例如，具有11个结点的折半查找判定树如下图所示，结点中的数字表示元素的序号。
|
|
|
|
|
|
|
从折半查找判定树可以看出，查找成功时，折半查找的过程恰好走了一条从根结点到被查结点的路径，关键字进行比较的次数即为被查找结点在树中的层数。因此，折半查找在查找成功时进行比较的关键字数最多不超过树的高度，而具有n个结点的判定树的高度为 ，所以折半查找在查找成功时和给定值进行比较的关键字个数至多为 。
|
|
|
给判定树中所有结点的空指针域加上一个指向一个方型结点的指针，称这些方型结点为判定树的外部结点（与之相对，称那些圆形结点为内部结点），如下图所示。那么折半查找不成功的过程就是走了一条从根结点到外部结点的路径。和给定值进行比较的关键字个数等于该路径上内部结点个数。因此，折半查找在查找不成功时和给定值进行比较的关键字个数最多也不会超过 。
|
|
|
|
|
|
|
|
那么折半查找的平均查找长度是多少呢？为了方便起见，不妨设结点总数为n=2h-1，则判定树是深度为h=log2（n+1）的满二叉树。在等概率情况下，折半查找的平均查找长度为：
|
|
|
|
|
|
当n值较大时，ASLbs≈log2（n+1）-1。
|
|
|
|
折半查找比顺序查找的效率要高，但它要求查找表进行顺序存储并且按关键字有序排列。因此，折半查找适用于表不易变动，且又经常进行查找的情况。
|
|
|
|
|
|
索引顺序查找又称分块查找，是对顺序查找方法的一种改进。
|
|
|
|
在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的，即后一块中所有记录的关键字均大于前一个块中最大的关键字。此外，还建立了一个“索引表”，索引表按关键字有序，如下图所示。
|
|
|
|
|
|
|
|
因此，查找过程分为两步：第一步在索引表中确定待查记录所在的块；第二步在块内顺序查找。
|
|
|
|
由于分块查找实际上是两次查找的过程，因此整个分块查找的平均查找长度应该是两次查找的平均查找长度（块内查找与索引查找）之和，所以分块查找的平均查找长度为ASLbs=Lb+Lw，其中Lb为查找索引表的平均查找长度，Lw为块内查找时的平均查找长度。
|
|
|
进行分块查找时可将长度为n的表均匀地分成b块，每块含有s个记录，即 。在等概率的情况下，块内查找的概率为 ，每块的查找概率为 ，若用顺序查找方法确定元素所在的块，则分块查找的平均查找长度为：
|
|
|
|
|
可见，其平均查找长度在这种条件下不仅与表长n有关，而且和每一块中的记录数s有关。可以证明，当s取 时，ASLbs取最小值 ，这时的查找效率较顺序查找要好得多，但远不及折半查找。
|
|
|
|
|
|
二叉查找树、B-树、红黑树等是常见的以树表方式组织的查找表。
|
|
|
|
|
|
二叉查找树是一种动态查找表，其特点是表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。
|
|
|
|
根据定义，非空的二叉查找树中左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字，因此，可将二叉查找树看成是一个有序表，其查找过程与折半查找过程相似。
|
|
|
|
在二叉查找树上进行查找的过程为：若二叉查找树非空，将给定值与根结点的关键字值相比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定值时，到根的左子树中进行查找，否则到根的右子树中进行查找。若找到，则查找过程是走了一条从树根到所找到结点的路径；否则，查找过程终止于一棵空树。
|
|
|
|
设二叉查找树以二叉链表为存储结构，结点的类型定义如下：
|
|
|
|
|
|
|
|
|
|
|
|
二叉查找树是通过依次输入数据元素并把它们插入到二叉树的适当位置上构造起来的，即每读入一个元素，首先在二叉查找树中进行查找，若找到则不再插入，否则根据查找时得到的位置信息进行插入。其过程为：若二叉查找树为空，则为新元素创建结点并作为二叉查找树的根结点；若二叉查找树非空，则将新元素的值与根结点的值相比较，如果小于根结点的值，则继续在左子树中查找，否则在右子树中继续查找，直到某结点的值与新元素的值相等，或者到达空的子树为止，此时创建新元素的结点并替换该空的子树完成插入处理。设关键字序列为｛46，25，54，13，29，91｝，则对应的二叉查找树构造过程如下图（a）~（g）所示。
|
|
|
|
|
|
|
|
从上面的插入过程还可以看到，每次插入的新结点都是二叉查找树上新的叶子结点，因此在进行插入操作时，不必移动其他结点，仅需改动某个结点的指针域，由空变为非空即可。这就相当于在一个有序序列上插入一个记录而不需要移动其他记录。
|
|
|
|
另外，由于一棵二叉查找树的形态完全由输入序列决定，所以在输入序列已经有序的情况下，所构造的二叉查找树是一棵单枝树。从二叉查找树的查找过程可知，这种情况下的查找效率与顺序查找的效率相当。
|
|
|
|
|
|
一棵m阶的B_树，或为空树，或为满足下列特性的m叉树。
|
|
|
|
|
|
|
（3）除根之外的所有非终端结点最少有 棵子树。
|
|
|
|
|
|
（n，A0，K1，A1，K2，A2，…，Kn，An）
|
|
|
其中，Ki（i=1，2，…，n）为关键字，且Ki<Ki+1（i=1，2，…，n-1）；Ai（i=0，1，…，n）为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki（i=1，2，…，n），An所指子树中所有结点的关键字均大于Kn，n为结点中关键字的个数且满足 。
|
|
|
|
（5）所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。
|
|
|
|
|
|
|
|
|
|
由B_树的定义可知，在B_树上进行查找的过程是：首先在根结点所包含的关键字中查找给定的关键字，若找到则成功返回；否则确定待查找的关键字所在的子树并继续进行查找，直到查找成功或查找失败（指针为空）时为止。
|
|
|
B_树上的插入和删除运算较为复杂，因为要保证运算后结点中关键字的个数大于等于 ，因此涉及结点的“分裂”及“合并”问题。
|
|
|
|
在B_树中插入一个关键字时，不是在树中增加一个叶子结点，而是首先在低层的某个非终端结点中添加一个关键字，若该结点中关键字的个数不超过m-1，则完成插入；否则，要进行结点的“分裂”处理。所谓“分裂”，就是把结点中处于中间位置上的关键字取出来插入到其父结点中，并以该关键字为分界线，把原结点分成两个结点。“分裂”过程可能会一直持续到树根。
|
|
|
同样，在B_树中删除一个结点时，首先找到关键字所在的结点，若该结点在含有信息的最后一层，且其中关键字的数目不少于 ，则完成删除；否则需进行结点的“合并”运算。
|
|
|
|
若待删除的关键字所在的结点不在含有信息的最后一层，则将该关键字用其在B_树中的后继替代，然后删除其后继元素，即将需要处理的情况统一转化为在含有信息的最后一层再进行删除运算。
|
|
|
|
|
|
对于前面讨论的几种查找方法，由于记录的存储位置与其关键码之间不存在确定的关系，所以查找时都要通过一系列对关键字的比较，才能确定被查记录在表中的位置，即这类查找方法都建立在对关键字进行比较的基础之上。理想的情况是依据记录的关键码直接得到对应的存储位置，即要求记录的关键码与其存储位置之间存在一一对应关系，通过这个关系，能很快地由关键码找到记录。哈希表就是按这种思想组织的查找表。
|
|
|
|
|
|
根据设定的哈希函数Hash（key）和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表，这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。
|
|
|
|
在构造哈希表时，是以记录的关键字为自变量计算一个函数（称为哈希函数）来得到该记录的存储地址并存入元素，因此在哈希表中进行查找操作时，必须计算同一个哈希函数，首先得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。
|
|
|
|
对于某个哈希函数Hash和两个关键字K1和K2，如果K1≠K2而Hash（K1）=Hash（K2），则称为出现了冲突，对该哈希函数来说，K1和K2则称为同义词。
|
|
|
|
一般情况下，只能尽可能地减少冲突而不能完全避免，所以在建造哈希表时不仅要设定一个“好”的哈希函数，而且要设定一种处理冲突的方法。
|
|
|
|
釆用哈希法主要考虑的两个问题是哈希函数的构造和冲突的解决。
|
|
|
|
|
|
解决冲突就是为出现冲突的关键字找到另一个“空”的哈希地址。常见的处理冲突的方法有开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区法等，在处理冲突的过程中，可能得到一个地址序列，记为Hi（i=1，2，…，k）。下面简要介绍开放定址法和链地址法。
|
|
|
|
|
|
Hi=（Hash（key）+di）%mi=l，2，…，k（k≤m-1）
|
|
|
|
其中，Hash（key）为哈希函数；m为哈希表的表长；di为增量序列。
|
|
|
|
|
|
.di=1，2，3，…，m-1，称为线性探测再散列。
|
|
|
|
.di=12，-12，22，-22，32，…，±k2（k≤m/2），称为二次探测再散列。
|
|
|
|
|
|
最简单的产生探测序列的方法是进行线性探测。也就是发生冲突时，顺序地到存储区的下一个单元进行探测。
|
|
|
|
例如，某记录的关键字为key，哈希函数值H（key）=j。若在哈希地址j发生了冲突（即此位置已存放了其他元素），则对哈希地址j+1进行探测，若仍然有冲突，再对地址j+2进行探测，以此类推，直到将元素存入哈希表。
|
|
|
|
|
|
|
|
|
|
（b）根据哈希函数，计算出关键码47的哈希地址为3，在该单元处无冲突，因此插入47。此后关键码34和19需要插入的哈希地址1和8处也没有冲突，因此在对应位置直接插入后如下所示。
|
|
|
|
|
|
（c）将关键码12存入哈希地址为1的单元时发生冲突，探测下一个单元（即哈希地址为2的单元），不再冲突，因此将12存入哈希地址为2的单元后如下所示。
|
|
|
|
|
|
（d）将关键码52存入哈希地址为8的单元时发生冲突，探测下一个单元（即哈希地址为9的单元），不再冲突，因此将52存入哈希地址为9的单元后如下所示。
|
|
|
|
|
|
（e）在哈希地址为5的单元存入关键码38，没有冲突；在哈希地址为0的单元中存入关键码33，没有冲突。因此将38和33先后存入哈希地址为5和0的单元后如下所示。
|
|
|
|
|
|
（f）在哈希地址为2的单元存入关键码57时发生冲突，探测下一个单元（即哈希地址为3的单元），仍然冲突，再探测哈希地址为4的单元，不再冲突，因此将57存入哈希地址为4的单元后如下所示。
|
|
|
|
|
|
（g）在哈希地址为8的单元存入关键码63时发生冲突，探测下一个单元（即哈希地址为9的单元），仍然冲突，再探测哈希地址为10的单元，不再冲突，因此将63存入哈希地址为10的单元后如下所示。
|
|
|
|
|
|
（h）在哈希地址为10的单元存入关键码21时发生冲突，用线性探测法解决冲突，算出哈希地址11，不再冲突，因此将21存入哈希地址为11的单元后如下所示，此时得到最终的哈希表。
|
|
|
|
|
|
线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“聚集”起来的现象，大大降低了查找效率。为此，可采用二次探测再散列法或随机探测再散列法，以降低“聚集”现象。
|
|
|
|
（2）链地址法。链地址法是一种经常使用且很有效的方法。它将具有相同哈希函数值的记录组织成一个链表，当链域的值为NULL时，表示已没有后继记录。
|
|
|
|
例如，哈希表表长为11、哈希函数为Hash（key）=key mod 11，对于关键码序列47，34，13，12，52，38，33，27，3，使用链地址法构造的哈希表如下图所示。
|
|
|
|
|
|
|
|
|
|
在线性探测法解决冲突的方式下，进行哈希查找有两种可能：第一种情况是在某一位置上查到了关键字等于key的记录，查找成功；第二种情况是按探测序列查不到关键字为key的记录而又遇到了空单元，这时表明元素不在表中，表示查找失败。
|
|
|
|
在用链地址法解决冲突构造的哈希表中查找元素，就是根据哈希函数得到元素所在链表的头指针，然后在链表中进行顺序查找的过程。
|
|
|
|
|
|
递归（recursion）是一种描述和解决问题的基本方法，用来解决可归纳描述的问题，或者是可分解为结构自相似的问题。所谓结构自相似，是指构成问题的部分与问题本身在结构上相似。这类问题具有的特点是：整个问题的解决可以分为两部分，第一部分是一些特殊或基本的情况，可直接解决；第二部分与原问题相似，可用类似的方法解决，但比原问题的规模小。
|
|
|
|
由于第二部分比整个问题的规模小，所以每次递归时第二部分的规模都在缩小，如果最终缩小为第一部分的情况则结束递归。因此，通过递归不断地分解问题，第一部分和第二部分的解密切配合，完成原问题的求解。
|
|
|
|
|
|
|
|
在该式中，f（n-1）的计算与原问题f（n）的计算相似，只是规模更小。
|
|
|
|
【算法】用递归方法求A［k1］~A［k2］中的最大者，并作为函数值返回。
|
|
|
|
|
|
【算法】设有一个整型数组中的元素是按非递减的方式排列的，递归地进行折半查找。
|
|
|
|
|
|
|
|
|
|
|
|
设图G=（V，E）是一个连通图，如果其子图是一棵包含G的所有顶点的树，则该子图称为G的生成树（Spanning Tree）。
|
|
|
|
当从图G中任一顶点出发遍历该图时，会将边集E（G）分为两个集合A（G）和B（G）。其中A（G）是遍历时所经过的边的集合，B（G）是遍历时未经过的边的集合。显然，G1=（V，A）是图G的子图，称子图G1为连通图G的生成树。下图所示的是图及其生成树。
|
|
|
|
|
|
|
|
对于有n个顶点的连通图，至少有n-1条边，而生成树中恰好有n-1条边，所以连通图的生成树是该图的极小连通子图。若在图的生成树中任意加一条边，则必然形成回路。
|
|
|
|
图的生成树不是唯一的。从不同的顶点出发，选择不同的存储方式和遍历方式，可以得到不同的生成树。对于非连通图而言，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，把它们称为非连通图的生成树森林。
|
|
|
|
|
|
对于连通网来说，边是带权值的，生成树的各边也带权值，于是就把生成树各边的权值总和称为生成树的权，把权值最小的生成树称为最小生成树。求解最小生成树有许多实际的应用。普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法是两种常用的求最小生成树的算法。
|
|
|
|
|
|
假设N=（V，E）是连通网，TE是N上最小生成树中边的集合。算法从顶点集合U=｛u0｝（u0∈V）、边的集合TE=｛｝开始，重复执行下述操作：在所有u∈U，ν∈V-U的边（u，ν）∈E中找一条代价最小的边（u0，ν0），把这条边并入集合TE，同时将ν0并入集合U，直至U=V时为止。此时TE中必有n-1条边，则T=（V，｛TE｝）为N的最小生成树。
|
|
|
|
由此可知，普里姆算法构造最小生成树的过程是以一个顶点集合U=｛u0｝作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充U集合直至U=V时为止。
|
|
|
|
|
|
|
|
|
|
|
|
克鲁斯卡尔求最小生成树的算法思想为：假设连通网N=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，｛｝），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。
|
|
|
|
|
|
|
|
|
|
克鲁斯卡尔算法的时间复杂度为O（eloge）（e为网中的边数），与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。
|
|
|
|
|
|
|
|
在工程领域，一个大的工程项目通常被划分为许多较小的子工程（称为活动），当这些子工程都完成时，整个工程也就完成了。若以顶点表示活动，用有向边表示活动之间的优先关系，则称这样的有向图为以顶点表示活动的网（Activity On Vertex network，AOV网）。在有向网中，若从顶点νi到顶点νj有一条有向路径，则顶点νi是νj的前驱，顶点νj是νi的后继。若<νi，νj>是网中的一条弧，则顶点νi是νj的直接前驱，顶点νj是νi的直接后继。AOV网中的弧表示了活动之间的优先关系，也可以说是一种活动进行时的制约关系。
|
|
|
|
在AOV网中不应出现有向环，若存在的话，则意味着某项活动必须以自身任务的完成为先决条件，显然这是荒谬的。因此，若要检测一个工程划分后是否可行，首先就应检查对应的AOV网是否存在回路。检测的方法是对其AOV网进行拓扑排序。
|
|
|
|
|
|
拓扑排序是将AOV网中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点νi到νj有一条路径，则在该线性序列中，顶点νi必然在顶点νj之前。
|
|
|
|
一般情况下，假设AOV网代表一个工程计划，则AOV网的一个拓扑排序就是一个工程顺利完成的可行方案。对AOV网进行拓扑排序的方法如下：
|
|
|
|
（1）在AOV网中选择一个入度为零（没有前驱）的顶点且输出它；
|
|
|
|
|
|
（3）重复上述两步，直至网中不存在入度为零的顶点为止。
|
|
|
|
按照上述步骤进行拓扑排序的过程如下图所示，得到的拓扑序列为6，1，4，3，2，5。显然，对有向图进行拓扑排序所产生的拓扑序列有可能是多种。
|
|
|
|
|
|
|
|
执行的结果会有两种情况：一种是所有顶点已输出，此时整个拓扑排序完成，说明网中不存在回路；另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路，拓扑排序无法进行下去。
|
|
|
|
|
|
所谓单源点最短路径，是指给定带权有向图G和源点ν0，求从ν0到G中其余各顶点的最短路径。迪杰斯特拉（Dijkstra）提出了按路径长度递增的次序产生最短路径的算法，其思想是：把网中所有的顶点分成两个集合S和T，S集合的初态只包含顶点ν0，T集合的初态包含除ν0之外的所有顶点，凡以ν0为源点，已经确定了最短路径的终点并入S集合中，按各顶点与ν0间最短路径长度递增的次序，逐个把T集合中的顶点加入到S集合中去。
|
|
|
|
每次从T集合选出一个顶点u并使之并入集合S后（即ν0至u的最短路径已找出），从ν0到T集合中各顶点的路径有可能变得更短。例如，对于T集合中的某一个顶点νi来说，其已知的最短路径可能变为（ν0，…，u，νi），其中的…仅包含S中的顶点。对T集合中各顶点的路径进行考查并进行必要的修改后，再从中挑选出一个路径长度最小的顶点，从T集合中删除它，同时将其并入S集合。重复该过程，就能求出源点到其余各顶点的最短路径及路径长度。
|
|
|
|
在下图所示的有向网中，用迪杰斯特拉算法求解顶点V0到达其余顶点的最短路径的过程如下表所示。
|
|
|
|
|
|
|
|
|
|
迪杰斯特拉算法求解上图（a）顶点V0到V1、V2、V3、V4、V5最短路径的过程
|
|
|
