《《delphi课程设计》ppt课件》由会员分享，可在线阅读，更多相关《《delphi课程设计》ppt课件（74页珍藏版）》请在金锄头文库上搜索。
1、DelphiDelphi程序设计程序设计 第5章算法与数据结构 本章先概括性地介绍算法的基础知识，然后讲 解Delphi中较复杂的数据类型，并结合数据类 型剖析一些典型算法的程序实现。 5.1算法 5.2集合 5.3数组 5.4抽象数据类型 5.5 本章小结 DelphiDelphi程序设计程序设计 5.1 算法 o5.1.1 算法的描述 o5.1.2 常用算法 o5.1.3 算法复杂性分析* DelphiDelphi程序设计程序设计 5.1 算法 算法的含义：算法是为了求解某一问题在有 限步骤内、定义了具体操作序列的规则集合 。一个算法应该具有以下五个重要的特征： n确切性（No ambig
2、uity） n输入（Input） n输出（Output） n可行性（Feasibility） n有穷性（Finite） DelphiDelphi程序设计程序设计 5.1.1 算法的描述 1. 伪代码描述 伪代码（Pseudo-code）是一种算法描述语言 。使用伪代码的目的是为了使被描述的算法可 以容易地以任何一种编程语言（如Delphi、C 、Java等）实现。因此，伪代码必须结构清晰 ，代码简单，可读性好，并且类似自然语言。 DelphiDelphi程序设计程序设计 5.1.1 算法的描述 2. 图形描述 经验告诉我们画图往往是一种分析和解决问题 的好办法。因为图形直观、易懂，容易说明问
3、题。所以，即使不是几何学的问题，如果我们 能给出适当的几何图形表示，也会使问题变得 容易处理。程序设计中，能够用来表示算法基 本概念的图主要有：PAD图、NS盒图、流程 图。 DelphiDelphi程序设计程序设计 5.1.1 算法的描述 （1）PAD图 问题分析图（Problem Analysis Diagram）， 简称PAD。PAD的目的在于以图表现程序的逻辑结 构，使程序易读、易记、易理解。用以提高程序的 设计、制造、检查、维护等的生产效率。PAD使用 二维树型结构图描述程序的逻辑，它的控制构造主 要是基于Pascal的。 DelphiDelphi程序设计程序设计 5.1.1 算法的
4、描述 PAD表示的控制结构 P1 P2 P1 P2 C （a）顺序结构 （b）选择结构 P1 P2 Pn L1 L2 X= Ln While cP Until cP （c）多选择结构 （d）循环结构 DelphiDelphi程序设计程序设计 5.1.1 算法的描述 （2）N/S盒图 N/S图是I.Nassi和B.Shneiderman提出的一种不 需要有向线段，无需上下左右前后追踪程序流程控 制的程序流程图，该图非常适合描述结构化程序或 者算法的结构化实现，能够较好地反映算法和程序 的层次结构，可读性好，具有自顶向下逐步求精的 特征。 DelphiDelphi程序设计程序设计 5.1.1 算法
5、的描述 N/S盒图表示的控制结构 功能语句1 功能语句2 功能语句n 条 件 满足 不满足 THEN AELSE B （b）选择结构（a）顺序结构 条件 值1 CASE 1 值2 CASE 2. . CASE n 值3 循环条件 循环体 （d）当型循环结 构 （c）多选择结构 循环条件 循环体 （f）调用结构（e）直到型循环结构 DelphiDelphi程序设计程序设计 5.1.1 算法的描述 （3）流程图 流程图是最古老、最广泛使用的程序设计工具，也 是展示程序逻辑流程的有效工具。流程图是最常用 的算法图形表示法。它使用框图的形式掩盖了算法 所有的细节方面，它只显示算法从开始到结束的整 个流
6、程。在程序设计环境下，它能用于设计一个完 整的程序或者部分程序。 DelphiDelphi程序设计程序设计 5.1.1 算法的描述 程序流程图常用图形符号及控制结构图例 处理1 处理2 处理1处理2 处理 条件 否、 是 条件 处理 是 条件 否、 端点符处理判断预定义处理连接符 顺序结构选择结构 (while-do)(repeat-until) 循环结构 DelphiDelphi程序设计程序设计 5.1.2 常用算法 1. 基本算法 基本算法大都比较简单，是其他算法的基础。 这类算法在程序中应用非常普遍，如：累加求 和、累乘求积、求最大和最小值等。 DelphiDelphi程序设计程序设计
7、5.1.2 常用算法 2. 排序算法 n排序算法根据数据的值对它们进行排列。排序 是为了把不规则的信息进行整理，以提高查找 信息的效率。 n常用的排序方法包括：选择排序、冒泡排序、 插入排序等。这三种方法是程序设计中使用的 快速排序的基础。 DelphiDelphi程序设计程序设计 5.1.2 常用算法 3. 查找算法 n查找是一种在列表（list）中确定目标所在位置 的算法。在一个列表中，查找意味给定一个值 ，并在包含该值的列表中找到该值的第一个元 素的位置（索引）。 n对于列表有两种基本的查找方法：顺序查找和 折半查找。顺序查找可以在任何列表中查找， 折半查找则需要列表是有序的。 Delp
8、hiDelphi程序设计程序设计 5.1.2 常用算法 4. 迭代和递归算法 迭代和递归是用于编写解决问题的算法的两种 途径。一种使用迭代，另一种使用递归。 o迭代 “迭”是屡次和反复的意思，“代”是替换的意 思，合起来，“迭代”就是反复替换的意思，也就是 使用一个中间变量保存中间结果，不断反复计算求 解最终值。 o递归 递归是一个算法自我调用的过程，用递归调 用的算法就是递归算法。 DelphiDelphi程序设计程序设计 5.1.3 算法复杂性分析* 算法的复杂性是指：在执行时，算法所需要 计算机资源的量。需要的时间资源的量称作 时间复杂性，需要的空间（即存储器）资源 的量称作空间复杂性。
9、这个量应该集中反映 算法中所采用的方法的效率，而从运行该算 法的实际计算机中抽象出来。 DelphiDelphi程序设计程序设计 5.1.3 算法复杂性分析* 1. 时间复杂性 时间复杂性描述了算法在计算机上执行时，所占用的计 算机时间资源的情况。它是一种抽象的描述方式，并不 是指与算法实现效率有关的算法执行时间，而是指理论 上与问题规模、算法输入及算法本身相关的某些操作次 数的总和，通常记为T(n)。问题规模逐渐增大后时间复 杂度的极限形式称为渐进时间复杂性（Asymptotic Time Complexity），渐进时间复杂性确定了算法所能 解决问题的规模，通常用来分析随着问题规模的加大，
10、 算法对时间需求的增长速度。 DelphiDelphi程序设计程序设计 5.1.3 算法复杂性分析* 2. Fibonacci问题 nFibonacci数列是一个无穷数列，具体构成为： 0，1，2，3，5，8，13，21，34，55， n它可以定义为： F(1) =0, F(2) = 1,F(3) =2 F(i) = F(i-1) + F(i-2) i 3 n即后面的每个Fibonacci值是前两个Fibonacci值之和。 现在的任务是如何求得Fibonacci数列中的第n个 数。下面介绍两种求解方案：递推和递归。 DelphiDelphi程序设计程序设计 （1）Fibonacci问题的递推
11、与迭代解法 program ProjectDiTuiFIB; $APPTYPE CONSOLE Uses SysUtils; function FIB(Num:integer):integer; var F:array of integer; n:integer; begin setlength(F,Num+1); /此时F数组的元素为F0-Fnum F1:=0; F2:=1;F3:=2; For n:=4 to Num do Fn:=Fn-1+Fn-2; result:=FNum; end; var outCome:integer; x:string; begin write(请输入Fibo
12、nacci数列的值： ); readln(x); outCome:=FIB(strtoint(x); writeln(Fibonacci的值为：,outCome); readln; end. DelphiDelphi程序设计程序设计 5.1.3 算法复杂性分析* （2）递归 递归在数学和计算机中经常遇到。利用递归方法可 以用有限的语句来定义无限集合，但在递归定义中 至少有一条是非递归的，即初始定义，否则就会产 生逻辑性错误。 DelphiDelphi程序设计程序设计 （2）Fibonacci问题的递归解法 program FIBDiGui5; $APPTYPE CONSOLE Uses Sys
13、Utils; function FIB(N:integer):integer; begin if N=1 then FIB:=0 else if N=2 then FIB:=1 else if N=3 then FIB:=2 else FIB:=FIB(N-1)+FIB(N-2); end; var x:string; outCome:integer; begin write(请输入Fibonacci数列的值：); readln(x); OutCome:=FIB(strtoint(x); writeln(Fibonacci数列的值为：, outCome); readln; end. Delph
14、iDelphi程序设计程序设计 5.2 集合 o5.2.1 关系运算 o5.2.2 增删元素 o5.2.3 交集运算 DelphiDelphi程序设计程序设计 5.2 集合 集合类型是一群相同类型元素的组合，这些 类型必须是有限的几种类型，如：整形、布 尔型、字符型、枚举型和子界型。在检查一 个值是否属于一个特定集合时，集合类型非 常有用。集合类型的定义方法：set of BaseType DelphiDelphi程序设计程序设计 5.2 集合 例：type Tint=0100; T1=set of Tint; TDate=set of (Mon,Tues,Wed,Thurs,Fri,Sat,
15、Sun) ; TChar= set of (a,b,c); DelphiDelphi程序设计程序设计 5.2.1 关系运算 用in运算符来判断一个给定的元素是否在一个集合 中，下面的代码判断在前面所定义的集合T1中是 否有80： if (80 in T1) then DoSomeThing /继续运行 下面的代码判断在TDate中是否有集合元素Mon ： if not (Mon in TDate) then DoSomeThing /继续运行 DelphiDelphi程序设计程序设计 5.2.2 增删元素 用、运算符或Include和Exclude过程，可以对一 个集合变量增删元素，例如： C
16、harset : TChar; Charset := a; /初始化集合变量 ; Include(T1, 2); /在集合中增加2 ; CharSet := CharSet + b ; /增加b ; Exclude(CharSet, a); /在集合中删除a ; CharSet := CharSet-a, b;/删除a, b ; DelphiDelphi程序设计程序设计 5.2.3 交集运算 Delphi中用*运算符来计算两个集合的交集，表达式 Set1*Set2的运算结果是产生出Set1和Set2这两个集 合中都存在的元素，下面的例子用来判断在一个给定的 集合中是否有a、b、c这几个元素： if a, b, c * CharSet = a, b, c then DoSomeThing /继续程序 DelphiDelphi程序设
