《delphi课程设计》PPT课件

《《delphi课程设计》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第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算法算法的含义：算法是为了求解某一问题在有限步骤内、定义了具体操作序列的规则集合。一个算法应该具有以下五个重要的特征：确切性（Noambiguity）输入（Input）输出（Output）可行性（Feasibility）有穷性（Finite）5.1.1算法的描述

2、1.伪代码描述伪代码（Pseudo-code）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（如Delphi、C、Java等）实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。5.1.1算法的描述2.图形描述经验告诉我们画图往往是一种分析和解决问题的好办法。因为图形直观、易懂，容易说明问题。所以，即使不是几何学的问题，如果我们能给出适当的几何图形表示，也会使问题变得容易处理。程序设计中，能够用来表示算法基本概念的图主要有：PAD图、NS盒图、流程图。5.1.1算法的描述（1）

3、PAD图问题分析图（ProblemAnalysisDiagram），简称PAD。PAD的目的在于以图表现程序的逻辑结构，使程序易读、易记、易理解。用以提高程序的设计、制造、检查、维护等的生产效率。PAD使用二维树型结构图描述程序的逻辑，它的控制构造主要是基于Pascal的。5.1.1算法的描述PAD表示的控制结构P1P2P1P2C（a）顺序结构（b）选择结构P1P2PnL1L2X=…LnWhilecPUntilcP（c）多选择结构（d）循环结构…5.1.1算法的描述（2）N/S盒图N/S图是I.Nassi和B.Shneiderman提

4、出的一种不需要有向线段，无需上下左右前后追踪程序流程控制的程序流程图，该图非常适合描述结构化程序或者算法的结构化实现，能够较好地反映算法和程序的层次结构，可读性好，具有自顶向下逐步求精的特征。5.1.1算法的描述N/S盒图表示的控制结构功能语句1功能语句2功能语句n条件满足不满足THENAELSEB（b）选择结构（a）顺序结构条件值1CASE1值2CASE2…….…….CASEn值3循环条件循环体（d）当型循环结构（c）多选择结构循环条件循环体（f）调用结构（e）直到型循环结构5.1.1算法的描述（3）流程图流程图是最古老、最广泛使用

5、的程序设计工具，也是展示程序逻辑流程的有效工具。流程图是最常用的算法图形表示法。它使用框图的形式掩盖了算法所有的细节方面，它只显示算法从开始到结束的整个流程。在程序设计环境下，它能用于设计一个完整的程序或者部分程序。5.1.1算法的描述程序流程图常用图形符号及控制结构图例处理1处理2处理1处理2处理条件否、是条件处理是条件否、端点符处理判断预定义处理连接符顺序结构选择结构(while-do)(repeat-until)循环结构5.1.2常用算法1.基本算法基本算法大都比较简单，是其他算法的基础。这类算法在程序中应用非常普遍，如：累加求

6、和、累乘求积、求最大和最小值等。5.1.2常用算法2.排序算法排序算法根据数据的值对它们进行排列。排序是为了把不规则的信息进行整理，以提高查找信息的效率。常用的排序方法包括：选择排序、冒泡排序、插入排序等。这三种方法是程序设计中使用的快速排序的基础。5.1.2常用算法3.查找算法查找是一种在列表（list）中确定目标所在位置的算法。在一个列表中，查找意味给定一个值，并在包含该值的列表中找到该值的第一个元素的位置（索引）。对于列表有两种基本的查找方法：顺序查找和折半查找。顺序查找可以在任何列表中查找，折半查找则需要列表是有序的。5.1.

7、2常用算法4.迭代和递归算法迭代和递归是用于编写解决问题的算法的两种途径。一种使用迭代，另一种使用递归。迭代“迭”是屡次和反复的意思，“代”是替换的意思，合起来，“迭代”就是反复替换的意思，也就是使用一个中间变量保存中间结果，不断反复计算求解最终值。递归递归是一个算法自我调用的过程，用递归调用的算法就是递归算法。5.1.3算法复杂性分析*算法的复杂性是指：在执行时，算法所需要计算机资源的量。需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率，而从运行该算法的实际计

8、算机中抽象出来。5.1.3算法复杂性分析*1.时间复杂性时间复杂性描述了算法在计算机上执行时，所占用的计算机时间资源的情况。它是一种抽象的描述方式，并不是指与算法实现效率有关的算法执行时间，而是指理论上与问题规模、算法输