delphi课程的设计2.ppt

第5章 算法与数据结构 本章先概括性地介绍算法的基础知识，然后讲解Delphi中较复杂的数据类型，并结合数据类型剖析一些典型算法的程序实现。 5.1 算法 5.2 集合 5.3 数组 5.4 抽象数据类型 5.5 本章小结 5.1 算法 5.1.1 算法的描述 5.1.2 常用算法 5.1.3 算法复杂性分析* 5.1 算法 算法的含义：算法是为了求解某一问题在有限步骤内、定义了具体操作序列的规则集合。一个算法应该具有以下五个重要的特征： 确切性（No ambiguity） 输入（Input） 输出（Output） 可行性（Feasibility） 有穷性（Finite） 5.1.1 算法的描述 1. 伪代码描述 伪代码（Pseudo-code）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（如Delphi、C、Java等）实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。 5.1.1 算法的描述 2. 图形描述 经验告诉我们画图往往是一种分析和解决问题的好办法。因为图形直观、易懂，容易说明问题。所以，即使不是几何学的问题，如果我们能给出适当的几何图形表示，也会使问题变得容易处理。程序设计中，能够用来表示算法基本概念的图主要有：PAD图、N\S盒图、流程图。 5.1.1 算法的描述 （1） PAD图 问题分析图（Problem Analysis Diagram），简称PAD。PAD的目的在于以图表现程序的逻辑结构，使程序易读、易记、易理解。用以提高程序的设计、制造、检查、维护等的生产效率。PAD使用二维树型结构图描述程序的逻辑，它的控制构造主要是基于Pascal的。 5.1.1 算法的描述 PAD表示的控制结构 5.1.1 算法的描述 （2） N/S盒图 N/S图是I.Nassi和B.Shneiderman提出的一种不需要有向线段，无需上下左右前后追踪程序流程控制的程序流程图，该图非常适合描述结构化程序或者算法的结构化实现，能够较好地反映算法和程序的层次结构，可读性好，具有自顶向下逐步求精的特征。 5.1.1 算法的描述 N/S盒图表示的控制结构 5.1.1 算法的描述 （3） 流程图 流程图是最古老、最广泛使用的程序设计工具，也是展示程序逻辑流程的有效工具。流程图是最常用的算法图形表示法。它使用框图的形式掩盖了算法所有的细节方面，它只显示算法从开始到结束的整个流程。在程序设计环境下，它能用于设计一个完整的程序或者部分程序。 5.1.1 算法的描述 程序流程图常用图形符号及控制结构图例 5.1.2 常用算法 1. 基本算法 基本算法大都比较简单，是其他算法的基础。这类算法在程序中应用非常普遍，如：累加求和、累乘求积、求最大和最小值等。 5.1.2 常用算法 2. 排序算法 排序算法根据数据的值对它们进行排列。排序是为了把不规则的信息进行整理，以提高查找信息的效率。 常用的排序方法包括：选择排序、冒泡排序、插入排序等。这三种方法是程序设计中使用的快速排序的基础。 5.1.2 常用算法 3. 查找算法 查找是一种在列表（list）中确定目标所在位置的算法。在一个列表中，查找意味给定一个值，并在包含该值的列表中找到该值的第一个元素的位置（索引）。 对于列表有两种基本的查找方法：顺序查找和折半查找。顺序查找可以在任何列表中查找，折半查找则需要列表是有序的。 5.1.2 常用算法 4. 迭代和递归算法 迭代和递归是用于编写解决问题的算法的两种途径。一种使用迭代，另一种使用递归。 迭代 “迭”是屡次和反复的意思，“代”是替换的意思，合起来，“迭代”就是反复替换的意思，也就是使用一个中间变量保存中间结果，不断反复计算求解最终值。 递归 递归是一个算法自我调用的过程，用递归调用的算法就是递归算法。 5.1.3 算法复杂性分析* 算法的复杂性是指：在执行时，算法所需要计算机资源的量。需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率，而从运行该算法的实际计算机中抽象出来。 5.1.3 算法复杂性分析* 1. 时间复杂性 时间复杂性描述了算法在计算机上执行时，所占用的计算机时间资源的情况。它是一种抽象的描述方式，并不是指与算法实现效率有关的算法执行时间，而是指理论上与问题规模、算法输入及算法本身相关的某些操作次数的总和，通常记为T(n)。问题规模逐渐增大后时间复杂度的极限形式称为渐进时间复杂性（Asym