第4章算法与数据结构摘要.PDF

第4章 算法与数据结构 在编写计算机程序时，需要明确将要处理的数据对象和组织方式，需要理解如何去处 理这些数据才能得到理想的结果，这时就会涉及算法和数据结构的问题。数据结构描述了 数据对象的组织方式，算法描述了处理这些数据的详细过程，甚至有专家提出了程序等于 算法加数据结构的论断。由此可以看出，在计算机软件技术领域中，描述程序的数据和过 程的算法与数据结构是非常重要的内容。理解算法与数据结构的基本思想和方法，对于编 写高性能的程序有着重要的帮助。本章将研究算法和数据结构的基本思想和典型方法。 4.1 算法概述 本节将从以下 5 个方面对算法进行概述。首先，分析几个典型的算法示例情景；然后， 给出算法的定义和基本特征；接下来，讨论算法的表示方法；第四，研究和分析评价算法 优劣的方法；最后，讲述程序设计领域中的典型算法。 4.1.1 算法示例 在编写计算机程序时，研究和选择合理的算法是一项非常重要的工作。无论是数学领 域的科学计算，还是管理领域、工程领域的数据处理，都离不开对算法的研究和应用。下 面，讨论几个典型的算法应用场景示例。 ● 在数学方面，计算一元二次方程的解、计算球体的面积、计算前 N 项整数和等问 题都需要依据相应的算法进行编程。 ● 在管理领域开发软件时，根据制造企业现有的人员、设备、物料等资源进行合理 地制定生产作业计划，需要依据特定的排产算法进行编程。 ● 在数据挖掘领域，为了进行规则挖掘、知识发现、模式匹配，需要按照数据挖掘 的目标选择相应的算法进行运算。 ● 在图像识别领域，为了自动地识别汽车牌号，需要依据车牌定位算法、字符分割 算法、字符识别算法、模板匹配算法等编写相应的应用程序。 ● 在 Internet 领域，为了开发有哪些信誉好的足球投注网站引擎工具，需要研究有哪些信誉好的足球投注网站算法、匹配算法、排名算 法、有哪些信誉好的足球投注网站调度算法等。 对于大多数的应用程序而言，算法的好坏直接影响到这些应用程序能否被用户接收和 能否被广泛地应用。 第 4 章 算法与数据结构 • 55 • 4.1.2 算法的概念 一般地认为，算法(algorithm)是一系列有限的解决问题的指令。也就是说，算法是指 能够对一定的规范的输入，在有限时间内获得所要求的输出。算法也可以理解为是由规定 的运算顺序所构成的完整的解题步骤。还有些专家认为，算法是一个有穷规则的集合，这 些规则规定了解决特定问题的运算序列。 被称为 Pascal 语言之父的瑞士计算机专家 Niklaus Wirth 教授在 1975 出版的图书中， 提出了“算法+数据结构=程序”的著名论断，并且将该论断作为其图书的名称。由此可见， 算法与计算机程序关系的密切程度。 1968 年，年仅 30 岁的美国斯坦福大学计算机系 Donald Knuth 教授出版了他的《计算 机程序设计的艺术》一书，该书在计算机程序设计领域产生了深远的影响。在该书中，Donald Knuth 教授总结了算法的5 个基本特征：有穷性(finiteness)、确定性(definiteness)、输入(input)、 输出(output)和可行性(effectiveness)。目前，Donald Knuth 教授提出的这 5 个特征被广泛地 接受。 ● 有穷性是指任何算法在经过有限的步骤之后总会结束，步骤的数量是一个合理的 数字。实际上，算法的有穷性包含了时间的含义。如果某种算法从理论上可以实 现，但是运行时间过长(例如要运行 200 年)则可能失去了实际的应用价值。 ● 确定性是指算法的每一个步骤都是精确定义的，在任何情况下这些步骤都是严密 的、清晰的。该特征是指算法不允许出现模棱两可的解释、不允许有多种不同的 理解，不同的人、不同的环境下对同一种算法的理解应该是明确的、唯一的。 ● 输入是指算法开始运算时给定的初始数据，这些输入是与特定的运算对象关联的。 ● 输出是指与输入相关的运算结果，反映了对输入数据加工后的情况。 ● 可行性是指算法的每一个步骤都是可以实现的，即使人们用笔和纸进行手工运算， 那么在有限的时间内也是可以完成的。 4.1.3 算法的表示方