计算机二级公共基础教程书稿

1、1 数据结构与算法1.1 算法的复杂度 1.1.1 算法的基本概念 所谓算法是指解决问题的方法和步骤。 利用计算机算法为计算机解题的过程实际上是在实施某种算法。 1.算法的基本特征 算法一般具有4 个基本特征：可行性、确定性、有穷性、拥有足够的情报。 （1）可行性：算法中有待执行的运算和操作必须是相当基本的，换言之，它们都是能够精确地进行的，算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。如在算法中不允许出现分母为0的情况。（2）确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。（3）有穷

2、性：一个算法在执行有穷步之后必须结束。也就是说，一个算法，它所包含的计算步骤是有限的。（4）拥有足够的情报： 一个算法是否有效，还取决于为算法所提供的情报是否足够。通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。一般来说.当算法拥有足够的情报吋，此算法才是有效的，而当提供的情报不够时，算法可能无效。2. 算法的基本要素一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的

3、控制结构。(1)算法中对数据的运算和操作每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。通常计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中，基本的运算和操作有以下四类：算术运算：主要包括加、减、乘、除等运算。逻辑运算：主要包括“与”、“或”、“非”等运算。 关系运算：主要包括“大于”、“小于”、“等于” 、“不等于“等运算。 数据传输：主要包括

4、赋值、输入、输出等操作。算法的设计一般都应从上述的四种操作考虑，通过对已知条件一步一步加工和变换，从而组成解题的操作序列。（2）算法的控制结构一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、NS结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。 (a) 顺序结构 (b) 选择结构 (c)循环 图1.1 三种基本结构3. 算法设计基本方法

5、计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。计算机算法不同于人工处理的方法。算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。 （1）列举法 列举法的基本思是根据提出的问题,列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的，列举法常用于解决“是否否存”，或“有多少种可能”等类型的问题，例如求解不定方程的问题。 列举法的特点是算法比较简单。伹当列举的可能情况较多吋，列举算法的工作量将会很大。因此,在用列举法设计算法时,使方案优化,尽量减少运算工作量，是应该重点注意的。通常，在设计列举算法时，只要对实际问题进行详细的分析，将与问题有关的

6、知识条理化、完备化、系统化，从中找出规律；或对所有可能的情况进行分类，引出-些有用的信息，是可以大大减少列举量的。列举算法虽然是一种比较原始的方法，其运算量比较大，但在有些实际问题中（如寻找路径、査找、搜索等问题）、局部使用列举法却是很有效的，因此，列举算法是计算机算法中的一个基础算法。（2） 归纳法归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。显然,归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。但是，从一个实际问题中总结归纳出一般的关系，并不是一件容易的事情，尤其是要归纳出一个数学模型更为困难。从本质上讲，归纳就是通过观察一些简单而特殊的情况

7、，最后总结出一般性的结论。归纳是一种抽象，即从特殊现象中找出一般关系。但由于在归纳的过程中不可能对所有的情况进行列举，因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。 （3）递推所谓递推，是指初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的，因此，递推关系式往往是归纳的结果。递推算法在数值计算屮是极为常见的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。（4）递归人们在解决一些复

8、杂问题时，为了降低问题的复杂程度（如问题的规模等，一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。由此可以看出，递归的基础也是归纳。在工程实际中，有许多问题就是用递归来定义的，数学中的许多函数也是用递归来定义的。递归在可计算性理论和算法设计中占有很重要的地位。递归分为直接递归与问接递归两种。如果一个算法显式地凋用自己则称为直接递归。如果算法F调用另一个算法P，而算法P又调用算法F，则称为问接递归调用。递归是很重要的算法设计方法之一。实际上，递

9、归过程能将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。有些实际问题，既可以归纳为递推算法，又可以归纳为递归算法。但递推与递归的实现方法是大不一样的。递推是从初始条件出发,逐次推出所需求的结果；而递归则是从算法本身到达递归边界的。通常，递归算法要比递推算法清晰易读，其结构比较简练。特别是在许多比较复杂的问题中，很难找到从初始条件推出所需结果的全过程，此吋，设计递归算法要要比递推算法容易得多。但递归算法的执行效率比较低。（5）减半递推技术实际问题的复杂程度往往与问题的规模有着密切的联系。因此，利用分治法解决这类实

10、际问题是有效的。所谓分治法,就是对问题分而治之。工程上常用的分治法是减半递推技术。所谓”减半”，是指将问题的规模减半，而问题的性质不变；所谓”递推”，是指重复”减半”的过程. (6) 回溯法 有些问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能进行无限的穷举。对于这类问题，一种有效的方法是试探，通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解，若试探失败，则逐步回退，换别的线路再进行试探。这种方法叫回溯法。1.1.2 算法复杂性分析求解同一个问题可以有许多不同的算法，那么如何来评价这些算法质量的优劣呢?正确性是设计和评价一个算法的首要条件。

11、如果一个算法不正确，其他方面就无从谈起。此外主要考虑如下三点：(1)执行算法所耗费的时间; (2)执行算法所占用的存储空间，其中主要考虑辅助存储空间; (3)算法应易于阅读，易于编码，易于调试等。 1算法的时间复杂度时间复杂度是度量时间的复杂性，即算法的时间效率的指标。算法时间复杂度是指算法中有关操作次数的多少，它用T(n)表示，T为英文单词Time的第一个字母，T(n)中的n表示问题规模的大小。如在累加求和中，n表示待加数的个数。同一个算法用不同语言进行描述，不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不相同。这表明用绝对的时间单位来衡量算法的效率是不合适的。 一个算法是由控制

12、结构(顺序、分支、循环)和一些基本操作所组成的，算法所耗费的时间取决于两者的综合效果，即基本语句的执行次数(也称频度)与该语句执行一次所需时间的乘积。但当算法转换为程序之后，每条语句执行的时间取决于机器的硬件速度、指令类型以及编译所产生的代码质量，这是很难确定的。因此我们假定每条语句执行一次所需的时间均为一个单位时间。这样一个算法的时间耗费就是该算法中所有语句的执行频度之和，从而避开了计算机硬、软件有关的因素，独立地评价算法所耗费的时间。一般情况厂，算法中基本操作的频度是问题规模n的某个函数f(n)，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度，记作：T

13、(n)O(f(n)。读作“大O”,f(n)可能是一个复杂的表达式，我们不关心表达式的具体描述，而关心的往往是它的上界。例如，假设某算法中基本操作的频度为f(n)2n 2 +5n+3，则该算法的时间复杂度为：T(n)O(n2)。 常见的大O表示形式有：n O(1)称为常数级；n O(logn)称为对数级；n O(n)称为线性级；n O(nc )称为多项式级；n O(cn)称为指数级；n O(n!)称为阶乘级2算法的空间复杂度 算法的空间复杂度是度量空间的复杂性，即执行算法的程序在计算机中运行时所占用空间的大小。1.2 数据结构 1.2.1 逻辑结构和存储结构 1. 数据结构的基本概念 （1）数据

14、结构 指相互有关联的数据元素的集合。 （2）数据结构研究的3 个方面 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； 在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； 对各种数据结构进行的运算。 2. 逻辑结构 数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一 是数据元素的集合，通常记为 D；二是 D 上的关系，它反映了数据元素之间的 前后件关系，通常记为R。一个数据结构可以表示成：B=(D,R) 其中，B 表示数据结构。为了反映D 中各数据元素之间的前后件关系，一般用二

15、元组来表示。 例如，如果把一年四季看作一个数据结构，则可表示成：B =(D,R) D =春季,夏季,秋季,冬季 R =(春季,夏季),(夏季,秋季),(秋季,冬季) 3. 存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。 由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。 一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接等存储结构。顺序存储方

16、式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。 链式存储结构就是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系。 1.2.2 线性结构和非线性结构 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。 线性结构满足：有且仅有一个根结点；每一个结点最多有一个直接前趋结点，也最多有一个直接后继结点；在一个线性结构中插入或删除任何一个结点后，还是线性结构。线性结构元素之间是一对一的联系。典型的线性结构有线性表、栈、队列、字符串等。如果一个数据结构不是线性结

17、构，则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。 1 线性表线性表是由n（n=0）个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个（首元素）外，有且只有一个前趋，除了最后一个（尾元素）外，有且仅有一个后继。即线性表或是一个空表，或可表示为：（a1,a2,ai,an）其中ai是性质相同的数据元素，也称为线性表中的一个结点。线性表的长度，即表中的元素个数n，当n=0时称为空表。2、线性表的顺序存储结构（顺序表）线性表的顺序存储结构的基本特点：线性表中所有元素所占的存储空间是连续的（一般用数组实现）；线性表中每个元素在存储空间中是按逻辑顺序存放的，即用物理上的相邻

18、关系来体现逻辑上的相邻关系。线性表的随机存取地址计算公式为：ADD(ai)=ADD(a1)+(i-1)*k这里ADD(ai)是第i元素的地址，k是每个元素占用空间字节数。线性表上的主要运算：线性表的插入；线性表的删除；线性表的查找；线性表的排序；线性表的分解；线性表的合并；线性表的复制；线性表的逆转。3、线性表的插入运算在长度为n的线性表(a1,a2,ai,an)的第i 元素ai之前插入一个新元素x后得到的长度为n+1的线性表为(a1,a2,x,ai,an)。实现方法：要在第i（ 1=i.n）元素之前插入一个新元素x，首先要从最后一个（即第n 个）元素开始，直到第i 元素之间的n-i+1个元素

19、依次向后移动一个位置，移动结束后，在第i 位置写入新元素x。插入结束后，表长度就增加了1。插入操作算法的时间复杂度分析：如果插入的位置在第n个元素之前，则只需将第n 元素后移，这是最好情况；如果插入的位置在第1个元素之前，则n个元素都要后移，这是最坏情况；在等概情况下（即在任何位置插入的机率相同）平均移动元素个数为n/2。4、线性表的删除运算在长度为n的线性表(a1,a2,ai,an)中删除第i 元素ai后，变为长度为n-1的线性表(a1,a2, ai-1, ai+1,an)。实现方法：要删除第i （1=i1，则该结点的父结点,编号为INT （k/2 ）； 若 2kn，则编号为k 的结点的左子

20、结点编号为2k；否则该结点无左子结点（显然也没有右子结点）； 若2k+1n，则编号为k 的结点的右子结点编号为2k+1；否则该结点无右子结点。 图1.8 满二叉树 图1.9 完全二叉树1.6.2 二叉树的遍历 在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历。 （1）前序遍历 先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左、右子树时，仍需先访问根结点，然后遍历左子树，最后遍历右子树。例如，对图1.7 中的二叉树进行前序遍历的结果（或称为该二叉树的前序序列）为：A，B，D，E， C，F。

21、 （2）中序遍历 先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。例如，对图1.7 中的二叉树进行中序遍历的结果（或称为该二叉树的中序序列）为： D，B，E，A，C，F。 （3）后序遍历 先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。例如，对图1.7 中的二叉树进行后序遍历的结果（或称为该二叉树的后序序列）为： D， E，B，F，C，A 。 1.7 查找 1.7.1 顺序查找 查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素

22、开始，依次将线性表中的元素与被查找的元素相比较，若相等则表示查找成功；若线性表中所有的元素都与被查找元素进行了比较但都不相等，则表示查找失败。 例如，在一维数组21，46，24，99，57，77，86中，查找数据元素99，首先从第 1 个元素 21 开始进行比较，比较结果与要查找的数据不相等，接着与第2 个元素 46 进行比较，以此类推，当进行到与第 4 个元素比较时，它们相等，所以查找成功。如果查找数据元素 100，则整个线性表扫描完毕，仍未找到与 100 相等的元素，表示线性表中没有要查找的元素。 在下列两种情况下也只能采用顺序查找： 如果线性表为无序表，则不管是顺序存储结构还是链式存储结

23、构，只能用顺序查找； 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 1.7.2 二分法查找 二分法查找，也称拆半查找，是一种高效的查找方法。能使用二分法查找的 线性表必须满足用顺序存储结构和线性表是有序表两个条件。 “有序”是特指元素按非递减排列，即从小到大排列，但允许相邻元素相等。 对于长度为n 的有序线性表，利用二分法查找元素X 的过程如下： 步骤 1：将X 与线性表的中间项比较； 步骤2：如果X 的值与中间项的值相等，则查找成功，结束查找； 步骤 3：如果 X 小于中间项的值，则在线性表的前半部分以二分法继续查找； 步骤 4 ：如果 X 大于中间项的值，则在线性表的后半部分

24、以二分法继续查找。 例如，长度为 8 的线性表关键码序列为：6，13，27，30，38，46，47，70， 被查元素为38，首先将与线性表的中间项比较，即与第4 个数据元素30 相比较，38 大于中间项 30 的值，则在线性表38，46，47，70中继续查找；接着与中间项比较，即与第2 个元素46 相比较，38 小于46，则在线性表38中继续查找， 最后一次比较相等，查找成功。 顺序查找法每一次比较，只将查找范围减少 1，而二分法查找，每比较一次，可将查找范围减少为原来的一半，效率大大提高。 对于长度为n 的有序线性表，在最坏情况下，二分法查找只需比较log2n 次， 而顺序查找需要比较n 次

25、。 1.8 排序 1.8.1 交换类排序法 （1）冒泡排序法 首先，从表头开始往后扫描线性表，逐次比较相邻两个元素的大小，若前面 的元素大于后面的元素，则将它们互换，不断地将两个相邻元素中的大者往后移动，最后最大者到了线性表的最后。 然后，从后到前扫描剩下的线性表，逐次比较相邻两个元素的大小，若后面的元素小于前面的元素，则将它们互换，不断地将两个相邻元素中的小者往前移动，最后最小者到了线性表的最前面。 对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时已经排好序。 例 数据 9,6,8,4,5第一趟冒泡排序之后为： 6 8 4 5 9第二趟冒泡排序之后为： 4 6 8 5 9第三趟冒泡

26、排序之后为： 4 5 6 8 9 第四趟冒泡排序之后为： 4 5 6 8 9在最坏的情况下，N 个数冒泡排序需要比较次数为n(n-1)/2 。时间复杂度为O(n2 )。 （2）快速排序法 基本思想是：选定一个元素作为中间元素，然后将表中所有元素与该元素进行比较，小者调到其前面，大者调到其后面，这样中间元素在表中的位置在两部分之间作为分界点，完成一轮次的排序，再对两个子表进行相同的划分和排序。具体实现时，一般用第一个元素作为中间元素，在表的两端进行比较，一轮完成时确定了中间元素的最终位置，并划分开两个子表，左边子表中任一元素都不大于右边子表中任一元素。例 数据( 52, 45, 80, 36,

27、14, 75, 58, 96, 23, 61 )第1趟快速排序之后为 ( 23, 45, 12, 36) 52 (75, 58, 96 80, 61 ) 第2趟快速排序之后为 ( 14) 23 (45, 36) 52 (61, 58) 75 (80, 96 )第3趟快速排序之后为 ( 14, 23, 36, 45, 52, 58, 61, 75, 80, 96 在快速排序过程中，随着对各子表不断地进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行再分割处理,需要将暂时不分割的子表记忆起来，这就要用一个桟来实现。在对某个子表进行分割后，可以将分割出的后一个子表的第一个元素与最后一个元素

28、的位置压入栈中，而继续对前一个子表进行再分割；当分割出的子表为空吋，可以从找中退出一个子表实际上只是该子表的第一个元素与最后一个元素的位置）进行分割。这个过程直到栈空为止，此时说明所有子表为空，没有子表再需要分割，排序就完成了。1.8.2 插入类排序法 （1）直接插入排序基本思想是：将待排序表看做是左、右两部分，其中左边是有序区，右边是无序区，整个排序过程就是将右边无序区中的元素逐个插入到左边的有序区中，以构成新的有序区。每一趟的算法是将一个待排序数插入到已排序数中。例 数据( 52, 45, 80, 36, 14, 75, 58, 96, 23, 61 )第一趟插入排序时已排序区为 52,

29、待排序区数据45,80,36,14,75,58,96,23,61 第一趟插入排序之后为 45 52 80 36 14 75 58 96 23 61 第二趟插入排序之后为 45 52 80 36 14 75 58 96 23 61第三趟插入排序之后为 36 45 52 80 14 75 58 96 23 61第四趟插入排序之后为 14 36 45 52 80 75 58 96 23 61第五趟插入排序之后为 14 36 45 52 75 80 58 96 23 61第六趟插入排序之后为 14 36 45 52 58 75 80 96 23 61 第七趟插入排序之后为 14 36 45 52 58

30、 75 80 96 23 61第八趟插入排序之后为 14 23 36 45 52 58 75 80, 96 61第九趟插入排序之后为 14 23 36 45 52 58 61 75 80 96 简单插入排序法，最坏情况需要n(n-1)/2 次比较,时间复杂度为O(n2 )。（2）希尔排序法基本思想是：将待排序列分为若干组，在每组内进行直接插入排序，以使整个序列基本有序，然后现对整个序列进行直接插入排序。关键在于如何分组，常用办法是第一轮取步长为初始长度n的一半，即间隔为n/2的元素为一组，以后每轮的步长为上次的一半（缩小增量法）。例 数据( 52, 45, 80, 36, 14, 75, 58

31、, 96 ) 初始的关键字 (a) d1=4 第一趟排序后结果 14 45 58 36 51 75 80 96 (b) d1=2 第二趟排序后结果 14 36 51 45 58 75 80 96 (C) d1=1 第三趟排序后结果 14 36 45 51 58 75 80 96在希尔排序过程中，每组中数据采用的是插入排序，随着增量逐步缩小，每组内记录数增多，但己基本有序，所以效率较高。希尔排序算法的速度比一般直接插入排序要快，但具体分析比较复杂。它涉及到增量序列。希尔排序的效率与所选的增量序列有关，如果选取上述的增量序列，则在最坏情况需要的比较次数是O(n 1.5 )1.8.3 选择类排序法

32、选择排序的基本思想是：每一步在待排序记录中选取关键字最小(或最大)的记录作为有序序列中的第i个记录，直到全部记录排序完成。 1直接选择排序直接选择排序是一种简单的排序方法，它的具体做法是：首先在所有的记录中选出关键字最小的记录，把它与第 个记录进行位置交换。然后在其余的记录中再选出关键字次小的记录与第二个记录进行位置交换。依次类推，直到所有记录排序完成。例如 数据 ( 52, 45, 80, 36, 14, 75, 58, 96 )第一趟选择排序后的结果为 14 45 80 36 52 75 58 96第二趟选择排序后的结果为 14 36 80 45 52 75 58 96第三趟选择排序后的结

33、果为 14 36 45 80 52 75 58 96第四趟选择排序后的结果为 14 36 45 52 80 75 58 96第五趟选择排序后的结果为 14 36 45 52 58 75 80 96第六趟选择排序后的结果为 14 36 45 52 58 75 80 96第七趟选择排序后的结果为 14 36 45 52 58 75 80 962、堆排序堆的定义：一个有n个记录的线性序列（R1,R2,Rn），其关键字序列（K1,K2,Kn）满足：KiK2i 2in 或KiK2i 2in KiK2i+1 2i+1nKiK2i+1 2i+1n时，称之为堆。为便于描述，将根为最小值的堆称为小根堆，类似地有

34、大根堆的概念。堆排序的基本思想是：对一组待排序的数，首先把它们按堆的定义排列成一个序列(称为初始建堆)，同时也就找到了最小关键字，然后将最小关键字输出。对剩余的关键字再建堆，便得到次小的关键字，如此反复进行，直到全部关键字有序为止，即完成了堆排序过程。 堆排序的方法如下：（1）首先将一个无序序列建成堆；即把不符合定义的待排序数据排列成符合堆定义的数字序列。从概念上讲，首先把待排序数据分别放到一棵完全二叉树的各个结点中，这时的完全二叉树结点之间的关系不一定具备堆的定义，从完全二叉树的最后一个非叶子结点（即第n/2个元素）开始，直到根结点（第一个元素）为止，对每个结点调整建堆，得到与数据序列的堆。

35、例如：待排序记录的关键字为(51，38，49，27，62，05，16，40)完全二叉树及其建堆过程如图所示。 图 1.10 初始建堆（2） 然后将堆顶元素（序列中最小的数据）与堆中最后一个数据交换，显然该子序列已不是堆，但左右子树仍然是堆，将此子序列调整为堆。重复这一步，直至剩下的子序列为空为止。 图1.11 调整堆 由上述算法可见，堆排序仅需一个记录大小的辅助存储空间供交换使用。堆排序的运行时间主要消耗在初始建堆和调整时的反复筛选重新建堆上，对于n个关键字集合进行堆排序的时间复杂度为O(nlog2n)。堆排序法对于数据规模较大的线性表比较适合。 相比以上几种（除希尔排序法外），堆排序法的时间

36、复杂度最小。 2 程序设计基础 2.1程序设计的方法与风格 所谓编码风格即书写源程序的习惯、程序代码的逻辑结构与习惯的编程技术。人们曾经认为程序是给机器执行的，所以只要逻辑正确就足够了，至于如何书写无关紧要。随着软件规模的增大和复杂性提高，在软件开发和维护过程中，程序代码的可读性是程序可维护性的前提。因此，从软件工程要求出发，养成良好的程序设计风格，主要考虑下述因素： 1 .源程序文档化 符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解； 程序注释：在源程序中添加正确的注释可帮助人们理解程序。程序注释可分为序言性注释和功能性注释。语句结构清晰第一、效率第二； 视觉组织：通

37、过在程序中添加一些空格、空行和缩进等，使人们在视觉上对程序的结构一目了然。 2.数据说明的方法在设计阶段确定了数据结构的组织和复杂程度，编写程序时则要建立数据说明，使数据更容易理解，更容易维护。一般而言，数据说明应遵循3 个原则：(1) 数据说明的次序应当规范化，使数据属性容易查找，有利于测试、排错和维护；(2) 当多个变量名用一个语句说明时，应当对这些变量按字母的顺序排列；(3) 如果设计了一个复杂的数据结构，应当使用注释，说明这个数据结构的固有特点。3. 语句的结构程序 语句的结构程序应该简单易懂，语句构造应该简单直接。语句结构应遵从如下规则：(1) 在一行内只写一条语句，并且采用适当的缩

38、进格式，使程序的逻辑和功能变得更加明确；(2) 程序编写首先应当考虑清晰性，不要刻意追求技巧性，使程序编写得过于紧凑；(3) 程序编写要简单、清楚，能直截了当地说明程序员的用意；(4) 除非对效率有特殊的要求，程序编写要做到清晰第一，效率第二；(5) 首先保证程序正确，然后才要求提高速度；(6) 让编译程序作简单的优化；(7) 尽可能使用库函数；(8) 避免使用临时变量而使可读性下降；(9) 尽量用公共过程或子程序去代替重复的功能代码段；(10) 使用括号清晰地表达算术表达式和逻辑表达式的运算顺序；(11) 避免不必要的转移；(12) 避免采用过于复杂的条件语句；(13) 尽量减少使用“否定”

39、条件的条件语句；(14) 避免过多使用循环嵌套和条件嵌套；(15) 不要使GOTO 语句相互交叉；(16) 要模块化，使模块功能近可能单一化。4 . 输入和输出 输入/输出的实现方法，决定了用户对系统性质的可接受程度。输入/输出的方式和格式应当尽可能方便用户的使用，一定要避免因设计不当给用户带来的麻烦。在设计和程序编码时都应考虑下列原则：(1) 对所有的输入数据进行检验，从而识别错误的输入，以保证每个数据的有效性；(2) 检查输入项的各种重要组合的合理性，必要时报告输入状态信息；(3) 使得输入的步骤和操作尽可能简单，并保持简单的输入报告；(4) 输入数据时，允许使用自由格式输入；(5) 应允

40、许缺省值；(6) 输入一批数据时，最好使用输入结束标志，而不要由用户指定的输入数据数目；(7) 在以交叉式输入/输出方式进行输入时，要在屏幕上使用提示符，明确提示交互输入的请求，指明可使用选择项的种类和取值范围；(8) 当程序设计语言对输入/输出格式有严格要求时，应保持输入格式与输入语句要求的一致性；2.2 结构化程序设计 采用先进的程序设计技术既可以提高软件开发与维护的效率，又可以提高软件的质量。多年来，人们一直致力于研究新的“程序设计技术”。例如，20 世纪70 年代提出的结构化程序设计技术，结构化程序设计方法引入了工程思想和结构化思想，使大型软件的开发和编程得到了极大的改善。 1. 结构

41、化程序设计的原则 结构化程序设计方法的主要原则为：自顶向下、逐步求精、 模块化和限制使用goto 语句。 (1) 自顶向上：先考虑整体，再考虑细节；先考虑全局目标，再考虑局部目标； (2) 逐步求精：对复杂问题应设计一些子目标作为过渡，逐步细化；(3) 模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。(4) 限制使用goto 语句：在程序开发过程中要限制使用goto 语句。2. 结构化程序的基本结构 结构化程序的基本结构有三种类型：顺序结构、选择结构和循环结构。 顺序结构：是最基本、最普通的结构形式，按照程序中的语句行的先后顺序逐条执行； 选择结构：又称为分支结构，它包括简单选择和多分支选择结构； 循环结构：根据给定的条件，判断是否要重复执行某一相同的或类似的程序段。循环结构对应两类循环语句,先判断后执行的循环体称为当型循环结构,先执行循环体后判