第9章 算法与数据结构.doc

第9章 算法与数据结构 算法和数据结构是程序设计过程中密切相关的两个方面，是程序设计的技术基础。本章主要介绍算法与数据结构的重要概念。 9.1 算 法 9.1.1 算法的基本概念所谓算法是指解题方案的准确而完整的描述作为一个算法，一般应具有以下几个基本特征 可行性确定性确定性是指算法中的每一个步骤必须有明确的义，不。有穷性有穷性是指算法必须在有限的时间内做完，即算法必须在执行有限个步骤之后终止。算法算法在执行个步骤之后性性性算法。性计算机解题的过程实际上是在实施某种算法过程，这种算法称为计算机算法。计算机算法不同于人工处理的方法。本节介绍常用的几种算法设计方法 列举法列举法是根据提出的问题，列举所有可能的情况，并问题中给定的条件检验哪些是需要的，哪些是不需要的。因此，列举法常用于解决是否存在或有多少种可能等类型的问题，例如求解不定方程的问题。 归纳法归纳法是通过列举少量的特殊情况，经过分析，最后一般的关系。显然，归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。但是，从一个实际问题中总结归纳出一般的关系，并不是一件容易的事情，尤其是要归纳出一个数学模型更为困难。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。 递推递推是从已知的初始条件出发，推出各中间结果和最后结果。递推本质上也属于归纳法，许多递推关系式实际上是通过对实际问题的分析与归纳而得到的，因此，递推关系式往往是归纳的结果。 递归人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。由此可以看出，递归的基础也是归纳。递归分为直接递归与间接递归两种。如果一个算法P调用自己则称为直接递归。如果算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归调用。递归是很重要的算法设计方法之一。实际上，递归过程能将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。减半递推技术实际问题的复杂程度往往与问题的规模有着密切的联系。因此，利用分治法解决这类实际问题是有效的。所谓分治法，就是对问题分而治之。工程上常用的分治法是减半递推技术。所谓减半，是指将问题的规模减半，而问题的性质不变；所谓递推，是指重复减半的过程。 回溯法实际问题很难归纳出一组简单的递推公式或直观的求解步骤，且也不能进行无限的列举。对于这类问题，一种有效的方法就是试。通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法为回溯法。回溯法在处理复杂数据结构方面有着广泛的应用。算法的算法的复杂度主要包括时间复杂度和空间复杂度。算法的时间复杂度所谓算法的时间复杂度，是指执行算法所需要的计算工作量。在度量一个算法的工作量时，与所使用的计算机、程序设计语言程序者算法实现过程中的许多细节无关。可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。基本运算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题的几种算法的优劣。例如，在考虑两个矩阵相乘时，可以将两个实数之间的乘法运算作为基本运算，而对于所用的加法（或减法）运算忽略不计。又如，当需要在一个表中进行查找时，可以将两个元素之间的比较作为基本运算。算法的空间复杂度一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间（例如，在链式结构中 ，除了要存储数据本身外，还需要存储链接信息）。如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。利用计算机进行数据处理是计算机应用的一个重要领域。在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题： 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； 在对数据进行处理时，各数据元素在计算机中的存储关系，