计算机二级--公共基础知识(第1章).doc

14 - 第1章 数据结构与算法 1.1 算法 1.1.1 算法的基本概念 所谓算法是指解题方案的准确而完整的描述。包括解题的方法、问题描述步骤、计算机程序实现等。 1. 算法的基本特征 （1） 算法的可行性（effectiveness） 为获得满意的结果，必须根据实际问题的特点设计可行的算法。 （2） 算法的确定性（definiteness） 算法的确定性是指算法中的每个步骤必须有明确定义，不允许有摸棱两可的解释，不允许有多义性。 （3） 算法的有穷性（finiteness） 算法的有穷性是指算法必须能在执行有限个步骤之后做完。 （4） 算法应拥有足够的情报 一个算法是否有效，还取决于为算法所提供的情报（如输入）是否足够。 2. 算法的基本要素 （1）算法中对数据的运算和操作 算法运算包括： 算术运算（+ - * /等运算）、 逻辑运算（与、或、非运算）、 关系运算（大于、小于、等于、不等于）、 数据传输（赋值、输入与输出） （2） 算法的控制结构 算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构包括顺序结构、选择结构和循环结构。 3. 算法设计基本方法 （1） 列举法 根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。主要用于解决问题“有多少种可能”或“是否存在”。 （2） 归纳法 通过列举少量的特殊情况，经过分析，最后找出一般关系。归纳得到的结论只是一种猜测，还要对猜测进行必要的证明。 （3） 递推 从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。 （4） 递归 将问题逐层分解，最后归结为一个最简单的问题。即将一个复杂问题归结为若干个简单问题，然后将简单问题再归结为更简单的问题，这个过程一直下去，直到问题解决为止。递归分为直接递归和间接递归两种。 （5） 减半递推技术 将问题的规模减半，逐步重复，直到问题解决 （6） 回溯法 处理复杂问题用上面的归纳法无法解决时，可用回溯法，回溯法就是“试”，找出解决问题的一个线索，沿着线索进行试探，如果试探失败，再逐步回退，从另一个线路试探。 1.1.2 算法复杂度 1. 算法的时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量可用算法在执行过程中所需要基本运算的执行次数来度量。 分析算法的工作量有下面两种方法： （1） 平均性态（Average Behavior） 平均性态是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。平均性态A(n)定义为： A(n) = ∑ p(x)t(x) X∈Dn 其中p(x)：输入为x的概率，t(x)：输入为x所执行的运算次数。Dn当规模为n（如n阶矩阵）时，算法算法执行时所有可能的输入集合。 （2） 最坏情况复杂性（Worst-Case Complexity） 最坏情况分析是指在规模为n时，算法所执行的基本运算的最大次数。它定义为： W(n) = max {t(x)} X∈Dn 2. 算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间。包括：算法程序所占用的空间、输入的初始数据所占的空间、算法执行过程中所需要的额外空间。 1.2 数据结构的基本概念 数据处理是计算机应用的一个重要领域。在进行数据处理时，处理的数据元素量很多，大量的数据元素存放在计算机中，如何组织这些数据以提高数据处理的效率，并节省计算机存储空间，这是数据处理的关键问题。而数据结构就是研究数据存储和数据处理的一门学科。 数据结构是计算机的一门科学，主要研究和讨论如下三个方法问题： (1)数据集合中数据元素之间所固有的逻辑关系，即数据的逻辑结构 (2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构 (3)对各种数据结构进行的运算 1.2.1 什么是数据结构 数据结构是指相互有关联的数据元素的集合。如： 一组数据： 一个学生登记表 编号 姓名 性别 年龄 籍贯 专业 入学成绩 简历 00101 李海 男 20 辽宁 管理 580 00102 赵晓军 男 19 山东 管理 575 00103 刘方 女 18 上海 会计 600 00104 王忆飞 女 19 北京 会计 605 00105 于江 男 19 辽宁 法律 590 表示家庭成员数据元素：父亲、儿子、女儿 一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在