导引与基本数据结构精选PPT.ppt

关于导引与基本数据结构关于导引与基本数据结构1第1页，讲稿共74张，创作于星期日2教材教材l计算机算法基础（第二版）余祥宣等计算机算法基础（第二版）余祥宣等 华中科技大学出版社华中科技大学出版社l参考书：参考书：1.计算机算法设计与分析：王晓东，电子工业出版计算机算法设计与分析：王晓东，电子工业出版社社2.算法分析与设计算法分析与设计：（美）古德里奇，（美）塔：（美）古德里奇，（美）塔玛西亚，霍红卫译玛西亚，霍红卫译 人民邮电出版社人民邮电出版社 课时安排：课时安排：28+12考试形式：闭卷考试形式：闭卷成绩：成绩：平时平时50%+考试考试50%第2页，讲稿共74张，创作于星期日3序序l计算机算法是计算机科学和计算机应用的核心计算机算法是计算机科学和计算机应用的核心l数据结构数据结构+算法算法=程序程序l算法（算法（algorithm）是一个在有限时间内逐步）是一个在有限时间内逐步执行某种任务的过程执行某种任务的过程l数据结构（数据结构（data structure）是一种系统组织）是一种系统组织和访问数据的方法和访问数据的方法l算法：计算机软件的灵魂算法：计算机软件的灵魂第3页，讲稿共74张，创作于星期日4问题求解问题求解(Problem Solving)设计程序设计程序证明正确性证明正确性分析算法分析算法理解问题理解问题精确解或近似解精确解或近似解选择数据结构选择数据结构算法设计策略算法设计策略设计算法设计算法第4页，讲稿共74张，创作于星期日5章节安排章节安排l第一章第一章 导引与基本数据结构导引与基本数据结构 l第二章第二章 分治法分治法 l第三章第三章 贪心方法贪心方法 l第四章第四章 动态规划动态规划 l第五章第五章 检索与周游检索与周游l第六章第六章 回溯法回溯法l第七章第七章 分枝分枝-限界限界l第八章第八章 NP-问题问题?l算法研讨环节算法研讨环节 第5页，讲稿共74张，创作于星期日6第一章第一章 导引与基本数据结构导引与基本数据结构1.1 算法的定义及特性1.什么是算法？什么是算法？算法如数字、计算一样，是一个算法如数字、计算一样，是一个基本概念基本概念。算法是解一算法是解一类确定问题类确定问题的任意一种的任意一种特殊的方法特殊的方法。在计算机科学中，算法是使用计算机解在计算机科学中，算法是使用计算机解一类问题一类问题的的精确、有效方法的代名词：精确、有效方法的代名词：算法算法是一组是一组有穷的规则有穷的规则，它规定了解决某一，它规定了解决某一特定类型特定类型问题问题的一系列的一系列运算运算。第6页，讲稿共74张，创作于星期日72.2.算法的五个重要特性算法的五个重要特性 确定性确定性、能行性能行性、输入输入、输出输出、有穷性有穷性1）确定性：）确定性：算法的每种运算必须要有确切的定义，算法的每种运算必须要有确切的定义，不能有二义性。不能有二义性。例：不符合确定性的运算例：不符合确定性的运算l 5/0 l 将将6或或7与与x相加相加l 未赋值变量参与运算未赋值变量参与运算第7页，讲稿共74张，创作于星期日82）能行性）能行性 算法中有待实现的运算都是基本的运算，算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间原理上每种运算都能由人用纸和笔在有限的时间内完成。内完成。例：整数的算术运算是例：整数的算术运算是“能行能行”的的 实数实数(无理数无理数)的算术运算是的算术运算是“不能行不能行”的的第8页，讲稿共74张，创作于星期日93）输入）输入 每个算法有每个算法有0个或个或多多个输入。这些输入是在算法开始个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合之前给出的量，取自于特定的对象集合定义域定义域（或值域）（或值域）4）输出）输出 一个算法产生一个算法产生一个一个或或多个多个输出，这些输出是同输入有某种特定输出，这些输出是同输入有某种特定关系的量。关系的量。第9页，讲稿共74张，创作于星期日105）有穷性有穷性 一个算法总是在执行了一个算法总是在执行了有穷步有穷步的运算之后的运算之后终止终止。计算过程计算过程：只满足确定性、能行性、输入、输出：只满足确定性、能行性、输入、输出四个特性但四个特性但不一定能终止不一定能终止的一组规则。的一组规则。l 准确理解算法和计算过程的区别：准确理解算法和计算过程的区别：l 不能终止的计算过程：操作系统。不能终止的计算过程：操作系统。l 算法是算法是“可以终止的计算过程可以终止的计算过程”。l 算法的时效性：只能把在相当有穷步内终止的算法的时效性：只能把在相当有穷步内终止的算法投入到计算机上运行。算法投入到计算机上运行。第10页，讲稿共74张，创作于星期日114.我们的主要任务我们的主要任务 算法学习将涉及算法学习将涉及5个方面的内容：个方面的内容：1）设计算法设计算法：创造性的活动：创造性的活动 2）表示算法表示算法：思想的表示形式：思想的表示形式 3）确认算法确认算法：证明算法的正确性：证明算法的正确性 程序的证明（程序的证明（程序的形式化证明技术程序的形式化证明技术）4）分析算法分析算法：算法时空特性分析：算法时空特性分析 5）测试程序测试程序：“调试只能指出有错误，而不能指出它们调试只能指出有错误，而不能指出它们 不存在错误不存在错误”本课程集中于学习算法的本课程集中于学习算法的设计设计与与分析分析。通过学习，掌握计算机算法。通过学习，掌握计算机算法设计和分析设计和分析基本策略与方法基本策略与方法，为设计更复杂、更有效的算法奠定基础。，为设计更复杂、更有效的算法奠定基础。第11页，讲稿共74张，创作于星期日125.5.课程关系课程关系 数据结构数据结构 程序设计语言：结构化设计程序设计语言：结构化设计 数学基础数学基础 非数值计算领域的基本知识非数值计算领域的基本知识第12页，讲稿共74张，创作于星期日131.2 1.2 分析算法分析算法1.分析算法的目的分析算法的目的 在于：通过对算法的分析，在把算法变成程序在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。无益的人力和物力浪费。算法分析是计算机领域的古老而前沿的课题。算法分析是计算机领域的古老而前沿的课题。进行算法分析的基本技术：抽象进行算法分析的基本技术：抽象第13页，讲稿共74张，创作于星期日142.重要的假设和约定重要的假设和约定1）计算机模型的假设）计算机模型的假设l Turing机模型：计算机形式理论模型机模型：计算机形式理论模型 l 通用计算机模型：通用计算机模型：l 顺序计算机顺序计算机l 有足够的有足够的“内存内存”l 能在固定的时间内存取数据单元能在固定的时间内存取数据单元 第14页，讲稿共74张，创作于星期日152）计算的约定）计算的约定 算法的执行时间算法的执行时间=Fi*ti 其中，其中，Fi是算法中用到的某种运算是算法中用到的某种运算i的次数，的次数，ti是该运算是该运算执行一次所用的时间。执行一次所用的时间。l 确定使用什么样的运算及其执行时间。确定使用什么样的运算及其执行时间。l从计算时间上，运算的分类：从计算时间上，运算的分类：l 时间囿界于常数的运算时间囿界于常数的运算：基本算术运算，如整数、浮点数的加、减、乘、除基本算术运算，如整数、浮点数的加、减、乘、除 字符运算字符运算 赋值赋值运算运算 过程调用等过程调用等 特点：尽管每种运算的执行时间不同，但一般只花特点：尽管每种运算的执行时间不同，但一般只花 一个一个固定量固定量的时间（单位时间）就可完成。的时间（单位时间）就可完成。第15页，讲稿共74张，创作于星期日162）计算的约定（续）计算的约定（续）其他运算其他运算：字符串操作：与字符串中字符的数量成正比字符串操作：与字符串中字符的数量成正比 记录操作：与记录的属性数、属性类型等有关记录操作：与记录的属性数、属性类型等有关 特点：运算时间特点：运算时间无定量无定量 如何分析非时间囿界于常数的运算：分解成若干如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。时间囿界于常数的运算。如：如：Tstring=Length（String）*tchar第16页，讲稿共74张，创作于星期日173）工作数据集的选择）工作数据集的选择l编制能够反映算法在最好、平均、最坏情况下工作的编制能够反映算法在最好、平均、最坏情况下工作的数据数据配置配置。然后使用这些数据配置运行算法，以了解算法。然后使用这些数据配置运行算法，以了解算法的性能。的性能。l测试数据集的生成测试数据集的生成在目前算法证明与程序正确性证明没在目前算法证明与程序正确性证明没有取得理论上的突破性进展的情况下，是程序测试与有取得理论上的突破性进展的情况下，是程序测试与算法分析中的关键技术之一。算法分析中的关键技术之一。作为算法分析的数据集：典型特征作为算法分析的数据集：典型特征 作为程序性能测试的数据集：对执行指标产生影响作为程序性能测试的数据集：对执行指标产生影响的性质的性质第17页，讲稿共74张，创作于星期日183.如何进行算法分析？如何进行算法分析？对算法进行全面分析，可分两个阶段进行：对算法进行全面分析，可分两个阶段进行：l事前分析事前分析：就算法本身，通过对其执行性能的理论分析，：就算法本身，通过对其执行性能的理论分析，得出关于算法特性得出关于算法特性时间和空间时间和空间的一个特征的一个特征 函数（函数（、）与计算机物理软硬件没有与计算机物理软硬件没有 直接关系。直接关系。l事后测试事后测试：将算法编制成程序后实际放到计算机上运行，：将算法编制成程序后实际放到计算机上运行，收集其执行时间和空间占用等统计资料，进行收集其执行时间和空间占用等统计资料，进行 分析判断分析判断直接与物理实现有关。直接与物理实现有关。第18页，讲稿共74张，创作于星期日191）事前分析）事前分析l目的：试图得出关于算法执行特性的一种形式描目的：试图得出关于算法执行特性的一种形式描 述，以述，以“理论上理论上”衡量算法的衡量算法的“好坏好坏”。l如何给出反映算法执行特性的描述如何给出反映算法执行特性的描述？最直接方法：最直接方法：统计算法中各种运算的执行情况，包括：统计算法中各种运算的执行情况，包括：l 引用了哪些运算引用了哪些运算l 每种运算被执行的次数每种运算被执行的次数l 该种运算执行一次所花费的时间等。该种运算执行一次所花费的时间等。算法的执行时间算法的执行时间=Fi*ti第19页，讲稿共74张，创作于星期日20l频率计数频率计数 例：例：xx+y for i 1 to n do for i 1 to n do x x+y for j 1 to n do repeat x x+y repeat repeat (a)(b)(c)分析：分析：(a)：xx+y执行了执行了1次次 (b)：xx+y执行了执行了n次次 (c)：xx+y执行了执行了n2次次 定义：定义：频率计数频率计数：一条：一条语句语句或一种或一种运算运算在算法（或程序）体中的执行在算法（或程序）体中的执行次数。次数。第20页，讲稿共74张，创作于星期日21一条语句在整个程序运行时实际执行时间一条语句在整个程序运行时实际执行时间=频率计数频率计数*每执行一次该语句所需的时间每执行一次该语句所需的时间l 如何刻画算法执行特性的形式描述如何刻画算法执行特性的形式描述l实际执行时间受约于诸多实际因素，如机器类型、编程与实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，没有统一的描述模型。语言、操作系统等，没有统一的描述模型。l在事前分析中，在事前分析中，只限于确定与所使用的机器及其他环只限于确定与所使用的机器及其他环境因素无关的频率计数境因素无关的频率计数，依此建立理论分析模型。，依此建立理论分析模型。第21页，讲稿共74张，创作于星期日22l数量级数量级l 语句的数量级语句的数量级：语句的执行频率：语句的执行频率 例：例：1，n，n2l 算法的数量级算法的数量级：算法所包含的所有语句的执：算法所包含的所有语句的执 行频率之和。行频率之和。算法的数量级从本质上反映了一个算法的执行特性。算法的数量级从本质上反映了一个算法的执行特性。例：假如求解同一个问题的三个算法分别具有例：假如求解同一个问题的三个算法分别具有n，n2，n3数数 量级。量级。若若n=10，则可能的执行时间将分别是，则可能的执行时间将分别是10，100，1000个个 单位时间单位时间与环境因素无关。与环境因素无关。第22页，讲稿共74张，创作于星期日23l 计算时间计算时间/频率计数的表示函数频率计数的表示函数 通过事前分析给出算法计算时间（频率计通过事前分析给出算法计算时间（频率计数）的一个数）的一个函数函数表示形式，一般记为与表示形式，一般记为与输入规模输入规模n有关的函数形式：有关的函数形式：f(n)注：最高次项与函数整体的关系注：最高次项与函数整体的关系l空间特性分析（略）空间特性分析（略）第23页，讲稿共74张，创作于星期日242）事后测试）事后测试l目的：运行程序，确定程序实际耗费的时间与空间，验证目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论先前的分析结论包括正确性、执行性能等，比较、优包括正确性、执行性能等，比较、优化所设计的算法。化所设计的算法。l分析手段：作时、空性能分布图分析手段：作时、空性能分布图第24页，讲稿共74张，创作于星期日254.计算时间的渐近表示计算时间的渐近表示记：记：算法的计算时间为算法的计算时间为f(n)数量级限界函数为数量级限界函数为g(n)其中，其中，l n是输入或输出规模的某种测度。是输入或输出规模的某种测度。l f(n)表示算法的表示算法的“实际实际”执行时间执行时间与机器及语言有关与机器及语言有关。l g(n)是是形式简单形式简单的函数，如的函数，如nm，logn，2n，n!等。是事前分析中等。是事前分析中通过对计算时间或频率计数统计分析所得的、通过对计算时间或频率计数统计分析所得的、与机器及语言无关与机器及语言无关的函数。的函数。以下给出算法执行时间：以下给出算法执行时间：上界（上界（）、下界（下界（）、“平均平均”（）的定义。的定义。第25页，讲稿共74张，创作于星期日261）上界函数）上界函数定义定义1 如果存在两个正常数如果存在两个正常数c和和n0，对于所有的，对于所有的nnn0 0，有，有|f(n)|c|g(n)|f(n)|c|g(n)|则记作则记作f(n)=f(n)=(g(n)(g(n)含义：含义：l如果算法用如果算法用n n值不变的同一类数据在某台机器上运行时，所用的时间总值不变的同一类数据在某台机器上运行时，所用的时间总是小于是小于|g(n)|g(n)|的一个常数倍。所以的一个常数倍。所以g(n)g(n)是计算时间是计算时间f(n)f(n)的一个的一个上界函上界函数数。f(n)f(n)的数量级就是的数量级就是g(n)g(n)。l试图求出试图求出最小最小的的g(n)g(n)，使得，使得f(n)=f(n)=(g(n)(g(n)。第26页，讲稿共74张，创作于星期日27lF(n)=3n+2 可取可取c4，n02，O(n)lF(n)=100n+6 可取可取 c=101，n06，O(n)lF(n)=2n2+11n-10 可取可取c=3，n010，O(n2)lF(n)=62n+n2 可取可取c=7，n0=4，O(2n)第27页，讲稿共74张，创作于星期日28l多项式定理多项式定理:定理定理1 若若A(n)=amnm+a+a1 1n+an+a0 0是一个是一个m m次多项次多项 式，则有式，则有A(n)=A(n)=(nm)即：变量即：变量n n的固定阶数为的固定阶数为m m的任一多项式，与此多的任一多项式，与此多 项式的最高阶项式的最高阶nm同阶。同阶。证明：取证明：取n n0 0=1,=1,当当nnnn0 0时，有时，有|A(n)|am|nm+|a1|n+|a0|(|am|+|am-1|/n+|a0|/nm)nm (|am|+|am-1|+|a0|)nm 令令c=|am|+|am-1|+|a0|则，定理得证。则，定理得证。第28页，讲稿共74张，创作于星期日29l 计算时间的数量级对算法有效性的影响计算时间的数量级对算法有效性的影响 数量级的大小对算法的有效性有决定性的影响数量级的大小对算法的有效性有决定性的影响。例：假设解决同一个问题的两个算法，它们都有例：假设解决同一个问题的两个算法，它们都有n个输入，计个输入，计算时间的数量级分别是算时间的数量级分别是n2和和nlogn。则，。则，n=1024：分别需要：分别需要1048576和和10240次运算。次运算。n=2048：分别需要：分别需要4194304和和22528次运算。次运算。分析：在分析：在n加倍的情况下，一个加倍的情况下，一个(n2)的算法计算时间增长的算法计算时间增长4倍，而一个倍，而一个(nlogn)算法则只用算法则只用2倍多一点的时间即可完成。倍多一点的时间即可完成。第29页，讲稿共74张，创作于星期日30 算法分类（计算时间）算法分类（计算时间）多项式时间算法多项式时间算法：可用多项式（函数）对其计算时间：可用多项式（函数）对其计算时间限界的算法。限界的算法。常见的多项式限界函数有：常见的多项式限界函数有：(1)(1)(logn)(logn)(n)(n)(nlogn)(nlogn)(n(n2 2)(n(n3 3)指数时间算法指数时间算法：计算时间用指数函数限界的算法：计算时间用指数函数限界的算法 常见的指数时间限界函数：常见的指数时间限界函数：(2(2n n)(n(n！)0。第49页，讲稿共74张，创作于星期日50第50页，讲稿共74张，创作于星期日51l 特殊形态的二元树特殊形态的二元树 满二元树：满二元树：深度为深度为k且有且有2k-1个结点的二元树个结点的二元树 第51页，讲稿共74张，创作于星期日52 完全二元树：完全二元树：一棵有一棵有n个结点深度为个结点深度为k的二元的二元树，当它的结点相当于深度为树，当它的结点相当于深度为k的满二元树中的满二元树中编号为编号为1到到n的结点时，称该二元树是完全的。的结点时，称该二元树是完全的。l 完全二元树的叶子结点至多出现在相邻的两级上。完全二元树的叶子结点至多出现在相邻的两级上。l 完全二元树的结点可以紧凑地存放在一个一维数组完全二元树的结点可以紧凑地存放在一个一维数组中（性质见引理中（性质见引理1.2）。）。第52页，讲稿共74张，创作于星期日53 堆：堆：堆是一棵完全二元树，它的每个结点的值至少堆是一棵完全二元树，它的每个结点的值至少和（大于或等于）该结点的儿子们（如果存在的话）的和（大于或等于）该结点的儿子们（如果存在的话）的值一样大（值一样大（max-max-堆）（或小，堆）（或小，min-min-堆）。堆）。二分检索树：二分检索树：二分检索树是一棵二元树，它或二分检索树是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：据元素，且有：的左子树的所有元素比根结点中的元素小；的左子树的所有元素比根结点中的元素小；的右子树的所有元素比根结点中的元素大；的右子树的所有元素比根结点中的元素大；的左子树和右子树也是二分检索树。的左子树和右子树也是二分检索树。注：二分检索树要求树中所有结点的元素值互异注：二分检索树要求树中所有结点的元素值互异第53页，讲稿共74张，创作于星期日543.图图 图图由称之为结点和边的两个集合组成，由称之为结点和边的两个集合组成，记为记为G=（V，E）。其中，是一个有限非空的）。其中，是一个有限非空的结点集合；是结点对偶的集合，的每一对偶结点集合；是结点对偶的集合，的每一对偶表示的一条边。表示的一条边。第54页，讲稿共74张，创作于星期日55有关图的的重要概念有关图的的重要概念l无向图无向图：边的表示（，）：边的表示（，）l有向图有向图：边的表示：边的表示，l成本成本：带有成本的图称为网络：带有成本的图称为网络l邻接邻接：如果存在边（：如果存在边（i，j）则称结点）则称结点i和和j邻接邻接l结点的度（出度入度结点的度（出度入度）l路径路径：由结点：由结点vp到到vq的一条路（的一条路（path）是结点）是结点 vp，vi1，vi2，vim，vq的一个序的一个序 列，它使得列，它使得(vp，vi1)，(vi1，vi2)，(vim，vq)是是E（G）的边。）的边。l路的长度路的长度：组成路的边数。：组成路的边数。第55页，讲稿共74张，创作于星期日56l简单路径简单路径：除了第一和最后一个结点可以相同以外，：除了第一和最后一个结点可以相同以外，其它所有结点都不同。其它所有结点都不同。l环环：第一个和最后一个结点相同的简单路。：第一个和最后一个结点相同的简单路。l连通图连通图：在无向图中，如果每对结点之间都存在一条：在无向图中，如果每对结点之间都存在一条 路，则称该图是连通的。路，则称该图是连通的。l子图子图：是由：是由G的结点集的结点集V的子集（记为的子集（记为VB）和边集）和边集E 中连接中连接VB中结点的边的子集所组成的图。中结点的边的子集所组成的图。l连通分图连通分图：一个图的最大连通子图。：一个图的最大连通子图。l有向图的强连通性有向图的强连通性：在有向图中，如果对于每一对结：在有向图中，如果对于每一对结 点点i和和j，既存在一条从，既存在一条从i到到j的路，又存在一条从的路，又存在一条从j 到到i的路，则称该有向图是强连通的。的路，则称该有向图是强连通的。第56页，讲稿共74张，创作于星期日57图的表示方法图的表示方法l邻接矩阵邻接矩阵 邻接表邻接表第57页，讲稿共74张，创作于星期日581.5 递归和消去递归递归和消去递归1.递归递归 一个算法若其中有调用自身的过程，则一个算法若其中有调用自身的过程，则称该算法是一个递归算法。称该算法是一个递归算法。l 递归是一种强有力的设计方法递归是一种强有力的设计方法l 递归的效率问题递归的效率问题第58页，讲稿共74张，创作于星期日59 例例1.3 斐波那契斐波那契(Fibonacci)序列：序列：F0=F1=1 Fi=Fi-1+Fi-2（i1)算法算法1.7 求斐波那契数求斐波那契数 procedure F(n)/返回第返回第n个斐波那契数个斐波那契数/integer n if n=1 then return(1)else return(F(n-1)+F(n-2)endif end Fl算法效率：对算法效率：对F(n-1)、F(n-2)存在大量的重复计算存在大量的重复计算l改改 进：保存中间结果进：保存中间结果第59页，讲稿共74张，创作于星期日60l练习题练习题18lProcedure F1(n)l If n2 then return(1)l Else return(F2(2,n,1,1)l EndiflEnd F1lProcedure F2(i,n,x,y)l If i=nl Then call F2(i+1,n,y,x+y)l Endifl Return(y)lEnd F2第60页，讲稿共74张，创作于星期日61l练习练习17题题l假设假设t(n)是所给出的是所给出的F(n)的时间函数，证明的时间函数，证明t(n)=O(2n-2)第61页，讲稿共74张，创作于星期日62l练习练习18题题l以下是计算第以下是计算第n个斐波那契数的函数个斐波那契数的函数lProcedure F1(n)If(nb/if b=0 then return(a)else return(GCD(b,a mod b)endif end GCD 例：例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;第63页，讲稿共74张，创作于星期日64例例1.5 递归在递归在非数值算法非数值算法设计中的应用设计中的应用 已知元素已知元素x，判断，判断x是否在是否在A（1：n）中。）中。算法算法1.9 在在A（1：n）中检索）中检索x procedure SEARCH(i)/如果在如果在A（1：n）/中有一元素中有一元素A（k）=x，则将其第一次，则将其第一次出现的下标出现的下标k返回，否则返回返回，否则返回0/global n,x,A(1:n)case :in:return(0):A(i)=x;return(i):else:return(SEARCH(i+1)endcase end SEARCH第一次调用第一次调用ans-SEARCH(1)第64页，讲稿共74张，创作于星期日652.消去递归消去递归直接递归的消去规则：直接递归的消去规则：基本思路基本思路：将递归过程中出现递归调用的地方，用等价的：将递归过程中出现递归调用的地方，用等价的非递归代码非递归代码来代替，并对来代替，并对return语句语句做适当处理。做适当处理。13条规则：条规则：处理直接递归调用中的递归代码和处理直接递归调用中的递归代码和return语句，语句，将之转换成等价的迭代代码。将之转换成等价的迭代代码。l 初始化初始化 在过程的开始部分，插入说明为栈的代码并将其初始在过程的开始部分，插入说明为栈的代码并将其初始化为空。在一般情况下，这个栈用来存放参数、局部变量和化为空。在一般情况下，这个栈用来存放参数、局部变量和函数的值、每次递归调用的返回地址。函数的值、每次递归调用的返回地址。将标号将标号L L1 1附于第一条可执行语句。然后对于每一处递归附于第一条可执行语句。然后对于每一处递归调用都用一组执行下列规则的指令来代替。调用都用一组执行下列规则的指令来代替。第65页，讲稿共74张，创作于星期日66l 处理递归调用语句处理递归调用语句 将所有参数和局部变量的值存入栈。将所有参数和局部变量的值存入栈。栈顶指针栈顶指针可作为一个全程变量来看待。可作为一个全程变量来看待。建立第建立第i i个新标号个新标号L Li i，并将，并将i i存入栈。这个标号的存入栈。这个标号的i i值将值将用来计算返回地址。用来计算返回地址。此标号放在规则此标号放在规则所描述的程序段中。所描述的程序段中。计算这次调用的各实在参数（可能是表达式）的值，并计算这次调用的各实在参数（可能是表达式）的值，并把这些值赋给相应的形式参数。把这些值赋给相应的形式参数。插入一条无条件转向语句转向过程的开始部分：插入一条无条件转向语句转向过程的开始部分：Goto LGoto L1 1第66页，讲稿共74张，创作于星期日67l 对递归嵌套调用的处理对递归嵌套调用的处理 如果这过程是函数，则对递归过程中含有此次函数如果这过程是函数，则对递归过程中含有此次函数调用的那条语句做如下处理：将该语句的此次函数调用部调用的那条语句做如下处理：将该语句的此次函数调用部分用从栈顶取回该函数值的代码来代替，其余部分的代码分用从栈顶取回该函数值的代码来代替，其余部分的代码按原描述方式照抄，并将按原描述方式照抄，并将中建立的标号附于这条语句上。中建立的标号附于这条语句上。如果此过程不是函数，则将如果此过程不是函数，则将中建立的标号附于中建立的标号附于所产生所产生的转移语句后面的那条语句。的转移语句后面的那条语句。以上步骤实现消去过程中的递归调用。下面对过程中出以上步骤实现消去过程中的递归调用。下面对过程中出现现returnreturn语句语句进行处理（纯过程结束处的进行处理（纯过程结束处的endend可看成是一可看成是一条没有值与之联系的条没有值与之联系的returnreturn语句）。语句）。第67页，讲稿共74张，创作于星期日68l 对每个有对每个有returnreturn语句的地方，执行下述规则语句的地方，执行下述规则：如果栈为如果栈为空空，则执行，则执行正常返回正常返回。否则，将所有输出参数（带有返回值的出口参数，否则，将所有输出参数（带有返回值的出口参数，out/inoutout/inout型）的当前值赋给栈顶上的那些对应的变量。型）的当前值赋给栈顶上的那些对应的变量。如果栈中有返回地址标号的下标，就插入一条此下标如果栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。从栈中退出的代码，并把这个下标赋给一个未使用的变量。从栈中退出所有局部变量和参数的值并把它们赋给对应从栈中退出所有局部变量和参数的值并把它们赋给对应的变量。的变量。如果这个过程是函数，则插入以下指令，这些指令如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在用来计算紧接在returnreturn后面的表达式并将结果值存入栈顶。后面的表达式并将结果值存入栈顶。用返回地址标号的下标实现对该标号的转向。用返回地址标号的下标实现对该标号的转向。第68页，讲稿共74张，创作于星期日69例例1.6 递归调用示例递归调用示例 求数组元素中的最大值求数组元素中的最大值算法算法1.10 递归求取数组元素的最大值递归求取数组元素的最大值 procedure MAX1(i)/查找数组查找数组A中最大值元素，并返回该元素的最大下标。中最大值元素，并返回该元素的最大下标。/global integer n,A(1:n),j,k integer i if i A(j)then ki else kj endif else kn endif return(k)/递归调用的返回递归调用的返回/end MAX1 第69页，讲稿共74张，创作于星期日70l消去上例中的递归消去上例中的递归l算法算法1.11 使用上述的规则消去例使用上述的规则消去例1.10中的递归代码中的递归代码 procedure MAX2(i)local integer j,k;global integer n,A(1:n)integer I integer STACK(1:2*n)top0 /规则规则1，声明栈的代码，并初始化为空，声明栈的代码，并初始化为空/L1:if i A(j)then k I else k j endif else k n endif第71页，讲稿共74张，创作于星期日72 if top=0 then return(k)/规则规则8，如果栈空，则正常返回如果栈空，则正常返回/else addr STACK(top);top top-1;/规则规则10，从从 栈中退出返回标号栈中退出返回标号/i STACK(top);top top-1;/规则规则11，从栈中退从栈中退 出局部变量和参数的值出局部变量和参数的值/top top+1;STACK(top)k;/规则规则12，计算返计算返 回值，并将之入栈回值，并将之入栈/if addr=2 then goto L2 endif /规则规则13，用返回用返回 地址标号的下标实现对该标号的转向地址标号的下标实现对该标号的转向/endifend MAX2 第72页，讲稿共74张，创作于星期日73l进一步优化和简化经过消去递归产生的迭代程进一步优化和简化经过消去递归产生的迭代程序。序。第73页，讲稿共74张，创作于星期日感谢大家观看第74页，讲稿共74张，创作于星期日