程序设计与算法分析.ppt

第六章 程序设计与 算法分析 本章要点 初步了解程序设计的基础知识 掌握结构化程序设计和面向对象程序设计的基本方 法 掌握数据结构中的基本数据类型及其实现 掌握程序设计算法的基本思想及几种经典的算法 了解编译原理的基本知识 6.1.1 程序的概念 程序 就是能够实现特定功能的一组指令序列的 集合。 程序设计 是程序员编写一系列可存储的指令以 指示计算机完成某些工作的过程。这些指令用 程序设计语言写成。 程序设计语言 是一组专门设计的用来生成一系 列可被计算机处理和执行的指令的符号集合。 程序设计人员用程序设计语言写成的指令称作 代码 。 6.1 程序设计基础 6.1.2 计算机程序设计语言 分类： 低级语言、高级语言。 1）低级语言包括两种类型：机器语言和汇 编语言。 机器语言 机器语言面向机器，可以由 CPU直接识 别和执行。 不同的机器能够识别的机器语言是不相 同的。 机器语言指令都是用一串 0、 1构成的二 进制位串来表示的。 指令系统是机器提供的机器指令的集合。 用二进制编码表示的指令，称为机器指 令，或称为机器码。 用机器指令编写的程序称为机器语言程 序，或称为目标程序，这是计算机能够 直接执行的程序。 机器语言难以阅读和理解，编写和修改 都比较困难，而且通用性较差。 汇编语言 汇编语言也称符号语言。 指令助记符是指令英文名称的缩写，容 易记忆。 所谓汇编语言，就是采用字母、数字和 符号来代替由一个个 0和 1构成的指令操 作码、寄存器、数据和存储地址等，并 在程序中用它们代替二进制编码数，这 样编写出来的程序就称为符号语言程序 或汇编语言程序。 大多数情况下，一条汇编指令直接对应 一条机器指令，少数对应几条机器指令。 汇编语言具有一个本质上与机器语言一 一对应的指令系统。汇编语言的实质和 机器语言是相同的。 低级语言的特点 都与特定的计算机硬件系统紧密相关，来自 于特定系统的指令系统，可移植性差； 专业知识要求高，要求对计算机硬件的结构 和工作原理非常熟悉； 每条指令的功能很单一，程序员编制源程序 时指令比较繁琐； 由于直接针对特定硬件编程，所以，最终的 可执行程序代码精炼，而且执行效率非常高。 两者主要的区别在于：机器语言无需翻 译或编译， CPU能够直接识别和执行。 而汇编语言必须经过汇编才能得到目标 程序。 汇编 虽然汇编语言比机器语言容易阅读理解和便于 检查，所以仍然需要一种特殊的程序，该程序 能够将用汇编语言编写的程序“翻译”成 CPU 能够识别的机器语言。 实现这种翻译功能的特殊程序称为 汇编语言翻 译程序、汇编程序或汇编器 。程序员手工编写 的程序统称为源程序，用汇编语言编写的源程 序称为汇编语言源程序，汇编程序将源程序翻 译得到的机器语言程序称为目标程序，翻译的 过程称为 汇编 。 反汇编程序 用于将目标代码程序转换成相 应的汇编语言源程序，这一过程称为反 汇编。反汇编主要用于识别源程序代码， 常用的调试工具程序 DEBUG就提供了反 汇编功能。 高级语言的产生 一个问题：如何解决程序的可移植性，即：程 序员编写的源程序如何可以从一台计算机很容 易地转到另一台计算机上工作。为了解决这些 问题，人们引入了高级语言来编写程序。 所谓高级语言是一种由表达各种意义的“词” 和“公式”，按照一定的“语法规则”来编写 程序的语言，又称为程序设计语言或算法语言。 高级语言之所以“高级”，就是因为它使程序 员可以完全不用与计算机的硬件打交道，可以 不必了解机器的指令系统。 程序员可以把硬件上复杂的概念比如存储空间 抽象成一个所谓的变量之类的概念，因而程序 员就可以绕开硬件问题而集中精力解决问题本 身，编程效率大大提高。 由于高级语言与具体机器无关，那么在一种机 器上运行的高级语言程序可以几乎不经改动地 移植到另一种机器上运行，大大提高了程序的 通用性。 此外，由于高级语言与自然语言 (尤其是英语 ) 很相似，因此易学、易懂，也易编写。 高级语言的常见类型 目前已经有许多高级语言在流行，并且 新的类型还在不断出现和升级。 用户在实际应用中进行程序设计时，可 根据情况选择适合的高级语言。 (1) BASIC语言 (2) FORTRAN语言 (3) COBOL语言 (4) PASCAL语言 (5) C语言 (6) C+语言 (7) 其他高级语言 基于视窗类操作系统的，如 Visual Basic、 Visual C+、 Delphi、 Power Builder、 Java等 等。 高级语言的优点是语句的功能强，源程序比较 短，容易学习，使用方便，通用性较强，便于 推广和交流。 其缺点是编译程序比汇编程序复杂，而且编译 出来的目标程序往往效率不高，目标程序的长 度比有经验的程序员所编的同样功能的汇编语 言程序要长 半以上，运行时间也要长一些。 因此，在很多对时间要求比较高的系统，如某 些实时控制系统或者大型计算机控制系统中， 低级语言，主要是汇编语言，仍然得到了一定 的应用。 6.1.3 高级语言的基本内容 高级程序设计语言依赖于各自特定的语句和语 法。一条一条的语句是构成源程序的基本单位。 高级语言的一条语句被编译或解释时往往会对 应多条机器指令。 每一种编程语言都包含一组语句和语法。所谓 语法，是指管理语言结构和语句的一组规则。 不论使用何种设计语言，都必须遵循其语法规 则。 以下内容主要描述了大多数高级语言都共同具 备的特性，但不一定是所有高级语言都有的。 1高级语言的基本符号 高级语言都是由所谓的基本符号组成的。基本 符号可以分为单字符和多字符两种情况。单字 符基本符号由单个字符组成，在高级语言中通 常都有下列几种单字符基本符号： (1) 字母 大写英文字母 A Z，小写英文字母 a z，共 52个符号。 (2) 数字 0 9，共 10个数字符号。 (3)特殊字符 (加 )， (减 )， *(乘 )， /(除 )， (乘方 )， (等号 )， (左括号 )， )(右括号 )， (大 于 )， (小于 )， (逗号 )， (空格 )等。 在高级语言中的多字符基本符号由两个 或两个以上的字符组成，例如 GoTo(转 移 )、 (小于或等于 )、 AND(与 )等等。 2高级语言的基本元素 基本元素由基本符号组成，可分为数、 逻辑值、名字、标号和字符串等五大类。 (1) 数 它由 0 9共 10个基本数字和其他一些符 号 (如小数点“ .”、正负号“、”及 指数符号“ E”等所构成。 (2) 逻辑值 由真 (True)和假 (False)两个值表示。 (3) 名字 由字符组成，一般约定名字的开头是字母或者 下划线，其后可为字母或数字，如 XYZ、 A123、 _C等。名字可用来定义常量、变量、 函数、过程或子程序的，也被用来定义成某些 东西，故也称为标识符。在高级语言中，一般 还规定了组成名字的字符的长度，即字符个数。 (4) 标号 是在高级语言中的程序语句前所加的一个名字， 主要用来指示程序可能的转移方向。 (5) 字符串 由一串字符所组成。在不同的高级语言 中，字符串中的多个字符放在一对单引 号或双引号中。 3基本的数据类型 任何一种高级语言都会定义一些基本的 数据类型。基本的数据类型通常包括整 数数据类型、实数数据类型和字符数据 类型等。 在程序中，除了值无需改变的常数外， 大部分数据的值是可以修改的。在程序 中， 变量 是指代表某个具体数值，并且 所代表的数值可改变的一个符号名字。 变量必须先定义，然后才能使用，这是 条基 本原则。 变量实质上代表了一个特定大小的内存单元空 间。 定义变量的实质就是让程序为该变量分配一个 特定的内存空间。 变量的类型实质上反映了该数据占用内存空间 的大小，即分配给该变量代表的数据的所占据 的内存单元的字节数目。 4结构数据类型 是在基本数据类型的基础上构造出来的数据类 型。数组和结构体是大多数高级语言都支持的 两种最基本的结构数据类型。 (1) 数组类型 数组是若干个相同类型的数据的集合。 (2) 用户自定义的结构体类型 结构体是隶属于同一个事物的多个不同类型的 数据的集合，用来表示具有若干个属性的一个 事物。 除了以上两种最基本的结构数据类型外，许多 高级语言还有比如枚举、集合，以及更复杂的 队列、堆栈等多种数据类型。 结构数据类型在使用时也必须定义相应类型的 “变量”名字。 5运算符与表达式 表达式是由基本符号、基本元素和各种数据通 过各种运算符连接而成的。按表达式的运算结 果可以分为 算术表达式、逻辑表达式和字符串 表达式 等几种情况。 高级语言中的运算符大致包括以下几个方面： (1) 逻辑运算： 与、或、非、异或。 (2) 算术运算： 加、减、乘、除、取模。 (3) 数据比较： 大于、小于、等于、不等于。 (4) 数据传送； 输入、输出、赋值。 (5) 算术表达式： 该表达式的运算结果是数， 它非常近似于日常的数学公式。 (6) 关系运算表达式： 该表达式的运算结果是 逻辑值，常用的运算符包含 (大于 )、 (小 于 )、 (等于 )、 (小于等于 )、 (大于等 于 )、不等于。 (7) 字符串表达式： 该表达式的运算结果是字 符串。 6语句 语句是构成高级语言源程序的基本单位， 是由基本元素、运算符、表达式等组成。 任何一种高级语言往往都支持赋值、条 件判断、循环、输入输出等语句。程序 员利用这些语句的结合，能够很方便地 编制出功能强大的程序。 7库函数和用户自定义的函数 为了支持用户编写出功能强大的源程序， 几乎所有的高级语言都为用户提供了丰 富的库函数，这些库函数能够实现某些 特定的功能，比如计算一个比较复杂的 数学函数。 在源程序中，用户也可以自己定义自己 的函数 (子程序或过程 )，以便以后可以 反复调用这些代码集合。 8注释 任何一种程序设计语言都强调注释的重要性。 源程序所包含的代码往往比较冗长，添加必要 的注释不仅有助于阅读程序，更重要的是，在 需要对程序功能进行扩充时，注释可以极大地 帮助程序员对原始程序的理解。 经常会出现这样一种情况，程序员自己编写的 程序，经过一段时间后，可能就是半年或者几 个月以后，程序员自己也读不懂自己的程序了。 况且，程序不仅要自己看得懂，更重要的是也 要让别人能够看懂。 9程序设计风格 (1) 编码格式和编码约定在整个程序中应保持一致。 (2) 程序中应给出必要的注释，尤其在变量定义、调用接口、参 数传递处，在修改程序时应注明修改人、时间、简要的修改原因。 (3) 对变量、函数标识等的命名，采用规范的命名方法，避免含 义不明确的缩写，从命名最好就可以一目了然读出命名标识的含义和数据类型。 (4) 采用缩进格式，突出程序的逻辑层次结构。 (5) 每一行只写一条语句，使用括号间隔表达式或语句的组成部 分，使组成部分清晰； (6) 使用结构化、面向对象的编程技术，提高程序可重用性、可 扩充性。 (7) 除非完全必要，应尽量避免多任务和多重处理。 (8) 尽量避免使用复杂的算术和逻辑表达式。 (9) 提高程序健壮性，预防用户的操作错误，做到废进废出。 10高级语言程序的运行 使用高级语言编制程序的一般过程可以归纳为以下几个步骤： (1) 使用文本编辑工具，逐条编写源程序的语 句。存储源程序文件时文件的后缀名与所用的 高级语言有关。 (2) 编译源程序文件，生成目标文件，文件后 缀名通常为 obj。 (3) 链接目标文件，生成可执行文件，文件后 缀名通常为 exe。 (4) 在计算机上执行可执行程序文件，进 步 调试和维护。 6.2.1 结构化程序设计方法 采用 自顶向下、逐步求精 的设计方 法和单入口单出口的控制结构。 1. 结构化程序设计思想 . . . . . . 二级子问题 二级子问题 二级子问题 需要解决的复杂问题 三级子问题 三级子问题 三级子问题 . . . . . . . . . 最小问题 最小问题 最小问题 结构化程序设计的 原则 是： (1) 使用顺序、选择、循环 3种基本控制 结构表示程序逻辑。 (2)程序语句组织成容易识别的语句模块， 每个模块都是单入口、单出口。 (3)严格控制 GOTO语句的使用。 (a) 顺序结构 (b) 选择结构 (c) while循环 (d) do-while循环 A B 出口 假 真 入口 A B S 假 真 入口 S A 出口 假 真 入口 A S 2模块 一个复杂的问题可以划分为多个简单问题的组 合。 在自顶向下、逐步细化的过程中，把复杂问题 分解成一个个简单问题的最基本方法就是模块 化。 模块化便于问题的分析，模块体现了信息隐藏 的概念。模块常用子程序加以实现。 1面向对象的思想 6.2.2 面向对象的程序设计方法 OO(Object Oriented，面向对象 )的程序 设计把客观事物看作具有属性和行为的 对象，通过抽象找出同一类对象的共同 属性 (静态特征 )和行为 (动态特征 )，形成 类。 2对象和类 对象 是对现实问题的高度概括、分类和 抽象。每个对象都只有自己的数据和相 应的处理函数，整个程序是由一系列相 互作用的对象来构成，不同对象之间是 通过发送消息来实现相互联系、相互作 用。 方法 在对象内的操作通常叫做方法。 类 定义了一组大体上相似的对象。一个类 所包含的方法和数据描述一组对象的共同行 为和属性。 对象则是类的具体化，是类的实例。 类通过派生可以有子类，同样也可以有父类， 形成层次结构。 3抽象 抽象 是对具体事物 (即对象 )进行概括， 即忽略事物的非本质特征，只注意那些 与当前目标有关的本质特征，从而抽象 出一类对象的共性并加以描述。 对一个问题的抽象一般来讲应该包 括两个方面：数据抽象和代码抽象 (或称 为行为抽象 )。 4封装性 封装的两个含义 ： 第一是，将抽象得到的数据成员和代码成 员相结合，形成一个不可分割的整体，即对象， 这种数据及行为的有机结合也就是封装。 第二个含义称为信息隐蔽，即尽可能隐蔽 对象的内部细节。在隐蔽对象内部细节的同时， 对象需要提供与外部世界进行交流的接口，并 实现对数据访问权限的合理控制，把整个程序 中不同部分的相互影响减少到最低限度。 5继承性 继承性 是父类和子类之间共享数据和方法的机制。 在定义一个类的时候，可以以一个已经存在的 类为基础，并把这个已经存在的类所包含的属 性和方法作为自身的一部分，然后加入新的属 性和方法以区别于原来的类。 原有的类称为 基类或父类 ，产生的新类称 为 派生类 。 6多态性 多态性 在收到外部消息时，对象通常要予 以响应。不同的对象收到同一消息可能 产生完全不同的结果。 1数据、数据类型 数据 是对客观事物的符号表示。在计算机系统 内，数据通常是指能够输入到计算机中并被计 算机进行处理的符号的集合。 数据类型 是指具有相同取值范围和可以实施同种操 作的数据的集合的总称。例如，在程序设计中， 通常会有字符型、整型、数组等多种数据类型。 6.3.1 基本概念 6.3 数据结构 2数据元素、数据项、数据对象 能够独立并完整地描述客观世界实体的基本数 据单元称为 数据元素 ，它是组成数据的基本单 位。 数据项 是组成数据元素的不可分割的最小单位。 最简单的数据元素就是由一个数据项构成的。 同类数据元素的集合称为 数据对象 。 3数据结构 数据结构 是指数据元素之间的相互关系的集 合，包括了数据的逻辑结构、物理结构 以及数据的运算。 数据的逻辑结构 数据的逻辑结构是指数据元素之间 的逻辑关系。数据之间可以根据不同的 关系组成不同的数据结构。 线性结构 数据结构中，如果数据元素之间存在着前后顺序的 关系，即除了第一个数据元素和最后一个元素外，其 他每个元素都有惟一的一个前驱和一个后继元素，这 样的数据元素之间的关系被称为线性结构。 树形结构 数据结构中，如果数据元素之间有顺序关系，且 除了一个被称为根节点的元素外，每个元素都有一个 前驱节点，并且可以有多个后继节点，这种逻辑结构 称为树形结构。 图形结构 数据结构中，如果任何一个数据元素都可以有多个 前驱节点和多个后继节点，这种逻辑结构称为图形结 构。 (2) 数据的物理结构 数据的物理结构是指逻辑结构在计 算机存储器中的表示。数据的物理结构 不仅要存储数据本身，还要存储表示数 据间的逻辑关系。 数据的物理结构主要有四种，分别 是顺序结构、链表结构、索引结构及散 列结构。 顺序结构 把所有元素存放在一片连续的存储单元中， 逻辑上相邻的元素存储在物理位置相邻的存储 单元中，由此得到的存储表示称为顺序存储结 构。 顺序存储结构常借助于程序设计语言中的 数组来实现。优点是使用方法简单，缺点是必 须预先分析出所需定义数组的大小。 链表结构 对逻辑上相邻的元素不要求其物理 位置相邻，元素间的逻辑关系通过附设 的指针域来实现，由此得到的存储表示 称为链式存储结构。 链式存储结构通常借助于程序设计 语言中的指针来实现。 索引结构 针对每个数据结构建立一张所谓的 索引表，每个数据元素占用表中的一项， 每个表项包含一个能够惟一识别一个元 素的关键字和用以指示该元素的地址指 针。 散列结构 通过构造相应的散列函数，由散列 函数的值来确定元素存放的地址。 (3) 数据运算 数据操作的集合。常见的数据操作 有数据的插入、删除、查找、遍历等。 数据操作通常由计算机程序加以实 现，通常也叫 算法实现 。 6.3.2 线性表 1定义 线性表 是由有限个相同的数据元素构成的序列， 元素之间是一对一的线性关系，除了第一个元素 只有直接后继、最后一个元素只有直接前驱外， 其余数据元素都有一个直接前驱和一个直接后继， 如图。 元素 1 uansu 元素 2 1 元素 3 1 元素 n 1 ua 2运算和实现 线性表通常采用顺序和链表两种物 理实现。对于经常变化的表，通常采取 链表结构。线性表常用的运算主要有： 插入、删除、查询和遍历。 插入 在保持原有的存储结构的前提下，根据插 入要求，在适当的位置插入一个元素。插入操 作要求线性表要有足够的存放新元素的空间， 如果空间不足，插入操作无法进行，线性表会 溢出。 删除 在线性表中，找到满足条件的数据元素， 并删除。如果线性表为空，删除就会失败。 查询 在线性表中，按照查询条件，定位数据元 素的过程就是查询。查询的条件一般根据数据 元素中的关键字进行。实际上，数据的插入和 删除都需要首先定位数据元素。对于空的线性 表是无法查询的。 遍历 是指按照某种方式，逐一访问线性表中的 每一个数据元素，并执行相同处理的操作。这 里的处理可以是读、写、或查询等。 6.3.3 栈 1定义 对于由 N个数据元素构成的一个线性序列， 如果只允许在其固定的一端位置插入和删除一 个数据元素，那么这种逻辑结构的数据结构称 为 堆栈或栈 (stack)。 允许插入或删除的这一端称为 栈项 ，另一 个固定端称为 栈底 。当表中没有元素时称为 空 栈 。 2运算和实现 栈的基本运算主要有：入栈、出栈和判断。 入栈 入栈也叫压栈，是在栈顶添加新元素的操 作，新的元素入栈后成为新的栈顶元素。 出栈 出栈也叫退栈或弹栈，是将栈顶元素从栈 中退出并传递给用户程序的操作 D C B A 入栈数据元素 E E D C B A D C B A 出栈数据元素 D C B A 判断 判断操作用来检查栈内数据是否为 空，返回结果是一个逻辑值：真或假。 如果栈顶和栈底重合，说明堆栈为空。 6.3.4 队列 1定义 对于由 N个数据元素构成的一个线 性序列，如果在其固定的一端只允许插 入数据元素，且在另一端只允许删除数 据元素，则这种逻辑结构的数据结构称 为 队列 (queue)。 把允许插入的一端叫 队尾 (rear)，把 只允许删除的一端叫 队首 (front)。 2运算 队列的基本运算主要有：入队、出队和判断。 入队 入队是在队列中插入一个新数据元素的过 程，插入在队尾进行，新的元素成为队尾，。 出队 出队是在队列中删除一个数据元素的过程， 删除在队首进行并把出来的数据传递给用户程 序。 A B C D E 头指针 尾指针 A B C D E F G 头指针 尾指针 F ， G 入队 A B C D E 头指针 尾指针 D E F G 头指针 尾指针 A ， B ， C 出队 判断： 判断操作用来检查队列是否为空，返 回结果是一个逻辑值：真或假，如图。 头指针 尾指针 3循环队列的实现 F G A B C D E 头指针 尾指针 内存块第一个存储单元 内存块最后一个存储单元 队 列 移 动 6.3.5 树 1定义 树形数据结构中，每个数据元素称 为是一个节点，除了一个惟一的所谓 根 节点 外，其他每个节点都有且只有一个 父节点，每个元素可以有多个子节点。 树主要用在大型、动态列表的搜索， 人工智能系统和编码算法等问题中。 2运算 树常见的基本运算有：插入、删除和遍历。 插入 在树中合适的位置，添加一个节点，通常插入新 的节点后，仍然应该保持该树本身所具有的性质。 删除 在树中找到满足条件的节点并删除。通常删除节 点后，也要保持该树本身所具有的性质。 遍历 按照某种顺序或规则，对树中的每个节点逐一进 行访问的过程。 3实现 Left A Right Left B Right C Right D E F 6.3.6 图 1定义 在图形结构中，每个数据元素称为一个顶 点，任意两个顶点之间都可能相关，这种相关 性用一条边来表示，顶点之间的邻接关系可以 是任意的。 图可以用来描述计算机网络的拓扑结构， 以及图论中获得最小生成树。除此以外，图在 自然科学、社会科学和人文科学等许多领域也 都有着非常广泛的应用。 2运算 常见的基本运算有：添加顶点、删除顶点、添 加边、删除边和遍历图。 添加顶点 在图中添加新的顶点，新添加的顶点通常 是孤立的节点，还没有边连接。 删除顶点 在图中去掉一个顶点，显然，在去掉一个 顶点的同时还应该删除与该顶点所连接的边。 添加边 根据指定的顶点，添加相应的边。 删除边 根据指定的顶点，删除相应的边。 遍历图 按照一定的规则，对图中的每个数 据顶点逐一进行访问。 3实现 图通常用数组和链表两种结构加以实现。 对于各个顶点和顶点之间的关系分别采 用邻接矩阵和邻接列表来进行描述。 A B C D E A B E B A C E C B D E A B D D C E 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 A B C D E A B C D E ( a ) ( b ) ( c ) 6.4.1 概述 1算法的定义 准确地说，“ 算法 (Algorithm)是一组明确 的、可以执行的步骤的有序集合，它在有限的 时间内终止并产生结果”。 算法和数据结构之间存在密切联系。数据结构 是算法的基础，数据结构的不同，通常的采用 的算法也会不同；当问题的求解算法一旦确定， 也可以选择合适的数据结构加以实现，合理的 数据结构能够简化算法。 6.4 算法分析基础 (1) 有穷性 (可终止性 ) 一个算法必须在有限个操作步骤内以及合 理的时间内执行完成。 (2) 确定性 算法中的每一个操作步骤都必须有明确的 含义，不允许存在二义性。 (3) 有效性 (可执行性 ) 算法中描述的操作步骤都是可执行的，并 能最终得到确定的结果。 (4) 输入及输出 一个算法应该有零个或多个输入数据、有 1 个或多个输出数据。 2算法的特性 3算法的描述 (1) 自然语言表示 自然语言就是人们日常使用的语言，可以 是中文、英文等。 例如，求三个数中最大值的问题，可以描述为： 比较前两个数； 将中较大的数与第三个数进行比较； 步骤中较大的数即为所求。 (2) 流程图表示 流程图是用规定的一组图形符号、流程线 和文字说明来表示算法的一种表示方法。 (3) 伪码 伪码用一种介于自然语言与计算机语言之 间的文字和符号来描述算法。比计算机语言形 式灵活，格式紧凑，没有严格的语法。 (4) 程序设计语言形式 算法也可以用某种具体的计算机程序设计 语言来表示，如， C、 C+、 Java等都可以用 来描述算法。 例如，求两个数的较大者。用伪代码描述算法如下： Input: two number s:a,b 1. if (the first number a is greater than or equal to the second number b) then 1.1 return a else 1.2 return b end if end 6.4.2 常用算法介绍 1递归算法 如果一个过程直接或间接地调用它 本身，则称该过程是递归的。 例如，数学阶乘运算，可以用递归算法 定义函数 f (n)如下： 1 ! ( 1 ) ! n nn 递归的情况包括所谓的递推法和分治法。 递推 是从已知的初始条件出发，逐次推导出最 后所求的值。递推是利用问题本身所具有的一 种递推关系求解问题的一种方法。 分治法 也是一种广泛使用的算法设计方法。其 基本思想是把大问题分解成一些较小的问题。 然后由小问题的解方便地构造出大问题的解。 2迭代算法 所谓迭代是指重复执行一组指令或操作步 骤，在每次执行这组指令时，都从原来的解值 的基础上推出一个新的解值。新的解值比原来 的解值更加接近真实的解。这个过程不断重复， 直到计算得到的解与真实解的误差满足实际要 求。 迭代常常用于科学计算领域对某些无法直接求 解的数值问题。 例如：现欲求解方程 f(x)=0的解。首先用某种 数学方法导出等价的形式 x=g(x)，然后按以下 步骤执行： (1)选一个方程的近似根，赋给变量 x0； (2)将 x0的值保存于变量 x1，然后计算 g(x1)， 并将结果存于变量 x0； (3)若 x0与 x1差的绝对值还不小于指定的精度要 求时，重复步骤 (2)的计算。 如果方程有解，并且按照上述方法计算出来的 近似根序列数学上收敛，则按上述方法求得的 x1就认为是方程的根 。 3穷举算法 亦称枚举法，该算法首先根据问题 的部分条件确定问题解的大致范围，然 后在此范围内对所有可能的情况逐一进 行验证，直到全部情况验证完毕。 4贪婪算法 贪婪算法通常具有 贪婪选择性 和 最 优子结构性 。 贪婪选择性 指的是所求解 问题的整体最优解可以通过一系列局部 最优的选择，即贪婪选择来达到。 最优 子结构性 指的是一个问题的最优解往往 包含着它的子问题的最优解。 现在我们假设顾客同样希望找回总额为 16的硬币。但是银行发行的硬币面额是 分别变成了 1、 5和 12单位的硬币。按照 上述的贪婪法，应该选择 1枚面额 12的硬 币，然后选择 4枚面额为 1的硬币，硬币 总数为 5。而最优解应该是选择 3枚面额 为 5的硬币，然后选择 1枚面额为 1的硬币， 总数为 4。此时，贪婪法的结果就不等于 最优解了。 6.4.3 算法的评价 对于一个算法的评价，通常要从 正确性、可理 解性、健壮性、时间复杂性及空间复杂性 等多 个方面加以衡量。相比而言，人们更关心的是 与计算机系统资源密切相关的时间复杂性和空 间复杂性。 在计算机系统内，求解问题的算法耗费的资源 主要包括时间和空间，可以从分析算法的时间 开销和空间开销入手，来分析算法的时间复杂 性及空间复杂性。 1算法的时间复杂度 时间复杂度 (Time complexity)是度量时间复杂 性、即算法的时间效率的指标。时间复杂度是 与求解问题规模、算法输入相关的函数，该函 数表示算法运行所花费的时间。 为了简化问题，通常，用算法运行某段核心代 码的 次数 来代替准确的执行时间，记为 T(n)， 其中， n代表求解问题的规模，一般是指待处 理的数据量的大 小。 引入符号“ O”，以此简化时间复杂度 T(n) 与求解问题规模 n之间的函数关系，简化后 的关系是一种数量级关系。 时间复杂度最好的算法是常数数量级的算法。 常数数量级的算法表示为 O (c)，其中 c表示 任意常数。 例如，如果某个算法的时间复杂度为 T(n)=n2+2n，那么，当求解规模趋于 n无穷 大时，有 T(n)/n21 ，表示算法的时间复杂 度与 n2成正比，记为 T(n)=O(n2)。 多项式函数的时间复杂度有 O (n)， O (n2)， O (n3)， O (n4)等等，以及数量级介 于上述数量级之间的 O (log2n)， O (n*log2n)， O (n2*log2n)等等。 2算法的空间复杂度 算法的 空间复杂度 (Space complexity) 用 来度量算法的空间复杂性、即执行算法 的程序在计算机中运行时所占用空间的 大小。 简单讲，空间复杂度也是与求解问题规 模、算法输入相关的函数。记为 S(n)， 其中 n代表求解问题的规模。 符号“ O”同样被用来表示空间复杂度 S(n) 与求解问题规模 n之间的数量级关系。 例如，如果 S(n)= O(n2)，表示算法的 空间复杂度与 n2成正比，记为 S(n)=O(n2)。 空间复杂度的分析方法与时间复杂度的分 析也是类似的，往往希望算法有常数数量 级或多项式数量级的空间复杂度。 6.4.4 NP问题 NP(Non-deterministic Polynomial)问题，是非 确定型多项式问题。所谓的非确定型，简单讲 就是指算法无法直接计算出结果，只能通过进 行一些有选择的“猜算”来得到结果。 对于这类问题给出的算法并不能直接计算出结 果，但可以检验某个可能的结果是正确的还是 错误的。这个可以检验“猜算”的答案正确与 否的算法，如果可以在多项式时间内解出，就 是非确定型多项式 (NP)问题。 例如，找一个大的质数的问题。并不存 在一个公式可以用来推算并找到这个大 的质数，但是，如果事先给定一个数， 程序却可以在多项式时间内判断出它是 否满足要求。 检验一个问题是否属于 NP问题，如果在 多项式时间内能够证明该问题的任意 “是”的实例是正确的，则该问题即为 NP问题。 目前关于 NP问题的研究主要集中在 NP-完全问 题的研究上，较为典型的有装箱问题、背包问 题、着色问题等等。 这些问题的研究结果有两种可能，一种是找到 了求解问题的算法；另外一种就是求解问题的 算法是不存在的，那么就要从数学理论上证明 它为什么不存在。 6.5.1 编译程序概述 语言处理的过程如图所示 。 6.5 编译原理 汇编器 绝对机器码 装配连接编辑 编译器 目标汇编程序 可重定位机器代码 预处理器 骨架程序 源程序 可重定位目标文件 库 编译程序的功能如图所示。 编译程序 低级语言程序 高级语言程序 解释程序在处理源程序时，执行方式类 似于日常生活中的“同声翻译”。 解释一句、执行一句，立即产生运行结 果。解释程序不产生目标代码，不能脱 离其语言环境独立执行。 解释程序对源程序的解释执行比编译程 序产生的目标代码程序的执行速度要慢。 编译程序是把高级语言程序 (源程序 )作为一个 整体来处理，首先将程序源代码“翻译”成目 标代码 (机器语言 )，编译后与系统提供的代码 库链接，形成 个完整的可执行的机器语言程 序 (目标程序代码 )。 目标程序可以脱离其语言环境独立执行，使用 比较方便、效率较高。相应地，由于每次执行 之前必须通过编译得到可执行程序，所以，可 执行程序一旦需要修改，必须先修改源代码， 再重新编译生成新的目标文件 (*.obj)才能执行。 词 法 分 析 器 语 法 分 析 器 语 义 分 析 器 中 间 代 码 生 成 优 化 目 标 代 码 生 成 源程序 目标代码 表格管理 出错处理 6.5.2 词法分析 其任务是从左到右一个字符、一个字符 地对源程序进行扫描，读入源程序，对 构成源程序的字符流进行扫描和分解， 通过词法分析从而识别出一个个单词 (也 称单词符号或符号 )。 例 6.1 对表达式： position := initial + rate * 100；进行词法分析。 对其进行词法分析后得到以下结果： 单词类型 单词值 标识符 1(id1) position 算符 (赋值 ) := 标识符 2(id2) initial 算符 (加 ) + 标识符 3(id3) rate 算符 (乘 ) * 整数 100 分号 ； 6.5.3 语法分析 语法分析是编译过程的第二个阶段，任 务是在词法分析的基础上将单词序列分 解成各类语法短语，如“程序”、“语 句”、“表达式”等等。一般这种语法 短语也称为语法单位。 例 6.2 按照例 6.1的结果，对表达式： position := initial + rate * 100；进行语法分析。 语法规则： :=“:=” :=“+” :=“*” :=“(”“)” := := := 依据源程序的语法规则把源程序的单词 序列组成语法短语 (表示成语法树 )，见图。 赋值语句 标识符 表达式 表达式 + 表达式 表达式 标识符 整数 标识符 := 表达式 * 把 id1:=id2+id3*N转换成语法树见图 6.15 所示。 := + N 100 * i d 1 p o s i t i o n i d 2 i n i t i a l i d 3 r a t e 6.5.4 语义处理 在词法分析程序和语法分析程序对源程 序的语法结构进行分析之后，一般要由 语法分析程序调用相应的语义子程序进 行语义处理。 编译过程中的语义处理实现两个功能： (1) 审查每个语法结构的静态语义，即验证语 法结构合法的程序是否真正有意义，有时把这 个工作称为静态语义分析或静态审查。 (2) 如果静态语义正确，则语义处理要执行真 正的翻译，要么生成程序的一种中间表示形式 (中间代码 )，要么生成实际的目标代码。 例 6.3 按照例 6.1和 6.2的结果，对表达式： position := initial + rate * 100；进行语义处理。 Program p(); Var rate:real; Var initial :real; Var position :real ; position := initial + rate * 100； 图 6.16是得到的语义分析树 。 1 0 0 := + * I d 1 p o s i t i o n I d 2 i n i t i a l I d 3 r a t e i n t t o r e a l 词法分析和语义分析本质上都是对源程序的结 构进行分析。但词法分析的任务仅对源程序进 行线性扫描即可完成，比如识别标识符，因为 标识符的结构是字母开头的字母和数字串，这 只要顺序扫描输入流，遇到既不是字母又不是 数字的字符时，将前面所发现的所有字母和数 字组合在一起构成单词标识符。但这种线性扫 描不能用于识别递归定义的语法成分，比如就 不能用此办法去匹配表达式中的括号。 语义分析阶段审查源程序有无语义错误，为代 码生成阶段收集类型信息。比如语义分析的一 个工作是进行类型审查，审查每个算符是否具 有语言规范允许的运算对象，当不符合语言规 范时，编译程序亦报告错误。如有的编译程序 要对实数用作数组下标的情况报告错误。又比 如某些语言规定运算对象可被强制，那么当二 目运算施于整型和实型时，编译程序应将整型 转换成实型而不能认为是源程序的错误。 6.5.5 中间代码生成 所谓“中间代码”是一种结构简单、含义 明确的记号系统，这种记号系统可以设计 为多种多样的形式，重要的设计原则为两 点：一是容易生成；二是容易将它翻译成 目标代码。 常用的中间代码形式有逆波兰式、三元式 和四元式。 6.5.6 中间代码优化 常用的优化技术有删除多余运算、强度 削弱、变换循环控制条件、合并已知量 与复写传播、删除无用赋值等。 6.5.7 目标代码生成 目标代码生成阶段的任务是把中间代码 变换成特定机器上的绝对指令代码或可 重定位的指令代码或汇编指令代码。这 是编译的最后阶段，它的工作与硬件系 统结构和指令含义有关。 1并行编译技术 并行编译技术 交叉编译 硬件描述语言及其编译技术 6.5.8 编译技术的新发展 6.6 本章小结 本章从程序设计的基础开始介绍，阐述 了结构化程序设计和面向对象程序设计， 并对这两种方法进行了比较。在数据结 构中，介绍了常用的数据结构，如线性 表、栈、队列、树、图等。在算法分析 中，讲述了设计算法的思想，评价算法 优劣的标准。在编译原理部分，介绍了 编译原理的词法分析一直到目标代码的 生成，用简单的例子进行阐述。 P167 一、二： 5、 9、 11、 14、 15、 17 6.7 练习与作业