Delphi程序设计大学教程 Delphi程序设计大学教程
第5章 算法与过程控制
本章先概括性地介绍算法的基础知识,然后讲 解Delphi中较复杂的数据类型,并结合数据类 型剖析一些典型算法的程序实现。 5.1 5.2 5.3 5.4 5.5 算法 集合 数组 抽象数据类型 本章小结
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1 算法
5.1.1 算法的描述 5.1.2 常用算法 5.1.3 算法复杂性分析*
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1 算法
算法的含义:算法是为了求解某一问题在有 限步骤内、定义了具体操作序列的规则集合。 一个算法应该具有以下五个重要的特征:
确切性(No ambiguity) 输入(Input) 输出(Output) 可行性(Feasibility) 有穷性(Finite)
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.1
1.
算法的描述
伪代码描述
伪代码(Pseudo-code)是一种算法描述语言。 使用伪代码的目的是为了使被描述的算法可以 容易地以任何一种编程语言(如Delphi、C、
Java等)实现。因此,伪代码必须结构清晰, 代码简单,可读性好,并且类似自然语言。
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.1
2.
算法的描述
图形描述
经验告诉我们画图往往是一种分析和解决问题 的好办法。因为图形直观、易懂,容易说明问 题。所以,即使不是几何学的问题,如果我们 能给出适当的几何图形表示,也会使问题变得 容易处理。程序设计中,能够用来表示算法基 本概念的图主要有:PAD图、N\S盒图、流程 图。
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.1
(1)
算法的描述
PAD图
问题分析图(Problem Analysis Diagram),简 称PAD。PAD的目的在于以图表现程序的逻辑结构, 使程序易读、易记、易理解。用以提高程序的设计、 制造、检查、维护等的生产效率。PAD使用二维树 型结构图描述程序的逻辑,它的控制构造主要是基 于Pascal的。
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.1
P1
算法的描述
P1 C P2 P2
(a)顺序结构 )
P1 L1 L2 X=… Ln P2 … Pn
(b)选择结构 )
While c P
Until c
P
( c) 多选择结构 )
( d) 循环结构 )
PAD表示的控制结构
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.1
(2)
算法的描述
N/S盒图
N/S图是I.Nassi和B.Shneiderman提出的一种不 需要有向线段,无需上下左右前后追踪程序流程控 制的程序流程图,该图非常适合描述结构化程序或 者算法的结构化实现,能够较好地反映算法和程序 的层次结构,可读性好,具有自顶向下逐步求精的 特征。
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.1
功能语句1 功能语句 功能语句2 功能语句
算法
的描述
条件 满足 THEN A 不满足 ELSE B
功能语句n 功能语句 (a)顺序结构 ) 条件 值1 CASE 1 值2 CASE 2 ……. ……. 值3 CASE n (b)选择结构 ) 循环条件 循环体
(c)多选择结构 循环体
(d)当型循环结 构
循环条件
( e ) 直到型循环结构
(f)调用结构 )
N/S盒图表示的控制结构
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.1
(3)
算法的描述
流程图
流程图是最古老、最广泛使用的程序设计工具,也 是展示程序逻辑流程的有效工具。流程图是最常用 的算法图形表示法。它使用框图的形式掩盖了算法 所有的细节方面,它只显示算法从开始到结束的整 个流程。在程序设计环境下,它能用于设计一个完 整的程序或者部分程序。
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.1
算法的描述
端点符
处理
判断
预定义处理
连接符
处理1 处理 处理1 处理 处理2 处理
条件 处理2 处理 处理 是 条件 否、 (while-do) 否、
处理
条件 是 (repeat-until) 循环结构
顺序结构
选择结构
程序流程图常用图形符号及控制结构图例
Delphi程序设计大学教程 Delphi程序设计大学教程
5.1.2
1.
常用算法
基本算法
基本算法大都比较简单