算法与数据结构讲课课件(精）.ppt

第三章算法与数据结构?用计算机解决实际问题时,首先要进行程序设计;而程序设计主要包括两个方面的内容: --行为特性的设计---- 将解决实际问题的每个细节准确地加以定义,并且还应当将全部解题过程完整地描述出来。这就是算法的设计--结构特性的设计---- 确定合适的数据结构?程序设计的步骤: ?,提出适当的计算模型并列出解决问题的方法和步骤?,就要选择合适的算法, 并将解题步骤表述出来?“读懂”的计算机程序,即所谓的“编程”??本章着重讨论解决问题的核心--算法以及算法的处理对象--数据的结构 算法?通常,把解题过程的准确而完整的描述称作解该问题的算法–程序的目的是加工数据,而如何加工数据是算法的问题。程序是数据结构与算法的统一?Niklaus Wirth 教授进一步提出了如下有名公式: ?程序=算法+数据结构–程序就是在数据的某些特定的表示方式和结构基础上对抽象算法的计算机语言具体表述?从算法的角度,可将程序定义为: ?一个算法由一些操作组成,而这些操作又是按一定的控制结构所规定的次序执行的–操作?(1) 逻辑运算: “与”、“或”、“非”?(2) 算术运算: 加、减、乘、除?(3) 数据比较: 大于、小于、等于、不等于?(4) 数据传送: 输入、输出、赋值–算法的控制结构(三种基本控制结构) ?(1) 顺序(a. 顺序结构) ?(2) 选择(b. 选择结构) ?(3) 循环(c. 直到型循环 ) 三种基本控制结构的一般形式 S1 S2 B S1 S2 B S (a) (b) (c) S3 F T B F T (d) S?算法结构化 1966 Bohm Jacopini 顺序选择循环-直到循环-?算法具有以下几个特征: –有效性–确定性,可行性–足够的信息:一个或多个输出;0个或多个输入–有穷性:执行是可终止的?算法是一个过程,这个过程由一套明确的规则组成,这些规则指定了一个操作的顺序, ?自然语言?专用工具?算法描述语言自然语言?用自然语言描述算法通俗易懂,但它存在着难以克服的缺陷: –易产生歧义性–语句比较繁琐冗长,并且很难清楚地表达算法的逻辑流程。如果算法中包含判断、循环处理,尤其是这些处理的嵌套层数增多,自然语言描述其流程既不直观又很难表达清楚–当今的计算机尚不能处理用自然语言表示的算法专用工具?为了形象地描述算法,人们创造了许多专用工具来描述算法。常用的有流程图、 PAD 图和 N-S 图等。除图形工具之外,人们可使用代码符号(如伪代码)描述算法?PAD 是问题分析图( Problem Analysis Diagram )的英文缩写,自 1973 年由日本日立公司发明以来,已经得到一定程度的推广。它用二维数形结构的图表示程序的控制流, 将这种图转换为程序代码比较容易常用流程图符号开始结束(a) 起止框、连接框(b) 输入输出框 AA 输入a,b N>10 (c) 判断框 true false (d) 处理框 i+1→i (e) 注释框(f) 流向线 N为正整数流程图简明直观、便于交流