第5章算法与数据结构

1、我们毕业啦其实是答辩的标题地方Taiyuan University of Technology大学计算机基础计算机科学与技术学院 计算机基础教学部2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部数学思维强调数与形的逻辑关系、演算推理能力和严谨态度，计算思维强调问题求解的操作过程和机器实现。问题求解的思路和方法，即为算法。而在确定问题求解的算法之前应先分析问题，从中抽象提取操作对象，并找到这些操作对象之间蕴含的关系，即数据结构。 计算机算法与数据结构都是问题求解过程中两个要素，且二者密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。可以说一个好的算法

2、和数据结构可能使某个原来需要用成年累月才能完成的问题在分秒之中得到解决。在某些特殊的领域，例如图形学、数据库、语法分析、数值分析和模拟等，解决问题的能力几乎完全依赖于最新的算法和数据结构。 算法设计和数据结构是相互依存相互影响的。 数据结构十算法= 程序，可见两者间在计算机科学界与计算机应用界的地位。22022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部35.1 算法基础5.2 数据结构5.3 算法设计本章小结第五章 算法与数据结构2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部45.1 算法基础算法（算法（Algorithm）是计算机学科中最具有方法论性质

3、的核）是计算机学科中最具有方法论性质的核心概念，被誉为计算机学科的灵魂。心概念，被誉为计算机学科的灵魂。广义地说，算法就是为解决某一问题采用的方法和步骤，广义地说，算法就是为解决某一问题采用的方法和步骤，即算法要解决的问题就是即算法要解决的问题就是“做什么做什么”和和“怎么做怎么做”。2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部本节内容55.1.1算法的起源算法的起源5.1.2 算法的定义和特性算法的定义和特性5.1.3 算法的表述算法的表述5.1.4 算法的基本结构算法的基本结构5.1.5 算法的评价算法的评价周髀算经九章算术最早四则运算、最大公约数、最小公倍数、开平

4、方根、开立方根、求素数、线性方程组求解第一个算法欧几里得算法（辗转相除法）：求两个正整数m和n的最大公约数：第一步: 比较两个数大小，将m设置为较大的数，n为较小的数；第二步: m除以n，得到余数r；第三步: 如果r等于0，则最大公约数就是n，否则将n赋值给m，r赋值给n，重复 第二 、第三步。5.1.15.1.1算法的起源算法的起源5.1.2 5.1.2 算法的定义和特性算法的定义和特性2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部广义：为解决问题采用的方法和步骤。计算机算法就是研究适合计算机实现的求解问题的方法和步计算机算法就是研究适合计算机实现的求解问题的方法和步骤

5、。计算机按照算法设计的顺序来执行这些命令，以达到解决某骤。计算机按照算法设计的顺序来执行这些命令，以达到解决某个问题的目的。亦即算法代表着用系统的方法描述解决问题的策个问题的目的。亦即算法代表着用系统的方法描述解决问题的策略机制。略机制。算法的基本特征：2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部（1）有穷性：）有穷性：有穷有穷步骤、步骤、有穷时间。有穷时间。（2）确定性：）确定性：算法中每一条指令必须有确切的含义，不存在二义算法中每一条指令必须有确切的含义，不存在二义性，确保对于同一个算法，相同的输入必然得出相同的执行结果性，确保对于同一个算法，相同的输入必然得出相同

6、的执行结果。且算法只有一个入口和一个出口。且算法只有一个入口和一个出口。（3）可行性：）可行性：可以执行的，并得到确定的结果。即算法中不应该可以执行的，并得到确定的结果。即算法中不应该有永远都执行不到的有永远都执行不到的“死语句死语句”和不可操作的和不可操作的“虚语句虚语句”。（4）输入：）输入：有零个或多个输入（即可以没有输入有零个或多个输入（即可以没有输入）。）。（5）输出：）输出：一个算法至少有一个或多个输出（即必须有输出），一个算法至少有一个或多个输出（即必须有输出），5.1.3 5.1.3 算法的表述算法的表述2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部算法的

7、表述就是用文字或图形把算法表示出来，便于人们阅读和算法的表述就是用文字或图形把算法表示出来，便于人们阅读和理解。好的表述可使程序员清楚地了解其中的逻辑关系，发现和理解。好的表述可使程序员清楚地了解其中的逻辑关系，发现和改正错误，进而提高程序设计的效率。改正错误，进而提高程序设计的效率。一个算法的表述可用多种描述工具，经常使用的有一个算法的表述可用多种描述工具，经常使用的有自然语言、流自然语言、流程图、程图、N-S图、图、PAD图、图、伪代码、伪代码、程序设计语言等方法。程序设计语言等方法。1. 自然语言2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部自然语言（自然语言（Na

8、tural Language）即人们日常生活中使用的语言。可以是汉语、即人们日常生活中使用的语言。可以是汉语、英语、数学关系式等。使用自然语言描述算法，通俗易懂，初学者容易掌握。英语、数学关系式等。使用自然语言描述算法，通俗易懂，初学者容易掌握。缺点缺点：（1）描述文字显得冗长。（）描述文字显得冗长。（2）容易产生歧义性。（）容易产生歧义性。（3）不易直接转化为程序。）不易直接转化为程序。【例【例5-1】 用计算机实现：比较两个数用计算机实现：比较两个数a、b的值，请按从大到小的顺序输出。用的值，请按从大到小的顺序输出。用自然语言描述的算法如下：自然语言描述的算法如下：S1：输入：输入a和和b

9、的值；的值；S2：比较：比较a，b的大小，如果的大小，如果a=b，则先打印，则先打印a，再打印，再打印b；否则，先打印；否则，先打印b，再，再打印打印a；S3：算法结束。：算法结束。 2. 2. 流程图流程图2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部流程图（流程图（Flow Chart）也称为程序框图，是用各种几何图形、流也称为程序框图，是用各种几何图形、流程线及文字说明来表示各种类型的操作框图。美国国家标准化协程线及文字说明来表示各种类型的操作框图。美国国家标准化协会会ANSI规定了一些常用的流程图符号规定了一些常用的流程图符号：2022-3-7太原理工大学.计算机

10、科学与技术学院.计算机基础教学部优点：优点：流程图方法形象直观，易于理解，流程图方法形象直观，易于理解，并可直观地将算法转化为程序。并可直观地将算法转化为程序。缺点：缺点：流程图占用篇幅较多，尤其是当算流程图占用篇幅较多，尤其是当算法比较复杂时，制作流程图既费时又不方法比较复杂时，制作流程图既费时又不方便。此外，由于流程线没有约束，可以任便。此外，由于流程线没有约束，可以任意转向，从而造成算法阅读和修改上的困意转向，从而造成算法阅读和修改上的困难，不利于结构化程序的设计。难，不利于结构化程序的设计。如例如例5-1用流程图来描述的算法如用流程图来描述的算法如下：下：2022-3-7太原理工大学.

11、计算机科学与技术学院.计算机基础教学部用流程图描述算法时，一般要注意一下几点。用流程图描述算法时，一般要注意一下几点。（1）根据解决问题的步骤从上至下顺序地画流程线，各图框）根据解决问题的步骤从上至下顺序地画流程线，各图框中的文字要尽量简洁。中的文字要尽量简洁。（2）为避免流程图的图形显得过长，图中的流程线要尽量短）为避免流程图的图形显得过长，图中的流程线要尽量短。（3）用流程图描述算法的原则是：根据实际问题的复杂性，）用流程图描述算法的原则是：根据实际问题的复杂性，流程图达到的最终效果应该是：依据此图就能用某种程序设流程图达到的最终效果应该是：依据此图就能用某种程序设计语言实现相应的算法（即

12、完成编程）。计语言实现相应的算法（即完成编程）。3. N-S3. N-S图图2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部N-S图图指将指将流程图中流程线去掉，在框内将算法的每一步都用一个矩流程图中流程线去掉，在框内将算法的每一步都用一个矩形框来描述，把一个个矩形框按执行的次序连接起来组成一个大矩形形框来描述，把一个个矩形框按执行的次序连接起来组成一个大矩形框，就是一个完整的算法描述。这种流程图就称为框，就是一个完整的算法描述。这种流程图就称为N-S结构流程图（结构流程图（简称简称N-S图）或盒图。图）或盒图。特点：特点：N-S图描述的算法在执行时只能从上图描述的算法在执

13、行时只能从上到下顺序执行，从而避免了算法流程的任意到下顺序执行，从而避免了算法流程的任意转向，保证了程序的质量。转向，保证了程序的质量。N-S图的另一个图的另一个优点是形象直观，画图节省篇幅，尤其适合优点是形象直观，画图节省篇幅，尤其适合结构化程序的设计。结构化程序的设计。如如：用用N-S图来描述例图来描述例5-1的算法如图所示。的算法如图所示。4. 4. 伪代码伪代码2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部伪代码（伪代码（Pseudocode）又称程序设计语言又称程序设计语言PDL，是一种近似高级，是一种近似高级语言但又不受语法约束的一种语言描述方式，它用一种介于

14、自然语语言但又不受语法约束的一种语言描述方式，它用一种介于自然语言和程序设计语言之间的文字和符号来描述算法。相比程序语言（言和程序设计语言之间的文字和符号来描述算法。相比程序语言（例如例如Java、C+、C、VB 等等）它更类似自然语言，是计算机代等等）它更类似自然语言，是计算机代码的简略形式。码的简略形式。特点：特点：伪代码可以用英文、汉字、数学表达式等混合表示算法，且伪代码可以用英文、汉字、数学表达式等混合表示算法，且无固定的、严格的语法规则，以便于书写和阅读为原则，故其能更无固定的、严格的语法规则，以便于书写和阅读为原则，故其能更好的转换为高级语言程序。好的转换为高级语言程序。2022-

15、3-7太原理工大学.计算机科学与技术学院.计算机基础教学部如例如例5-1用伪代码描述其算法如下。用伪代码描述其算法如下。 int a,b /*定义两个整型变量a，b*/scanf a、b; /*键盘输入a，b的值*/ if( a=b) /*如果ab */ printf a,b; /*输出a的值*/ else printf b,a; /*否则输出b的值*/#include main() int a,b; scanf(%d,%d,&a,&b); if(ab) printf(%d,%d,a,b); else printf(%d,%d,b,a);将算法转化为将算法转化为C语言程序语言程序：5.1.4

16、5.1.4 算法的基本结构算法的基本结构2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部一个算法具有两个要素：操作和控制结构。一个算法具有两个要素：操作和控制结构。（1）操作：指计算机最基本的功能操作，包括算术运算）操作：指计算机最基本的功能操作，包括算术运算、关系运算、逻辑运算和数据传送等。、关系运算、逻辑运算和数据传送等。（2）控制结构：指各操作之间的执行顺序。算法中的每）控制结构：指各操作之间的执行顺序。算法中的每个步骤必须是定义完好的、执行流畅的结构。个步骤必须是定义完好的、执行流畅的结构。计算机科学家为结构化程序设计或算法定义了三种控制结计算机科学家为结构化程序设

17、计或算法定义了三种控制结构：构：顺序结构顺序结构、分支结构分支结构和和循环结构循环结构。1. 顺序结构2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部（a）流程图（b）N-S图 顺序结构示例流程图顺序结构顺序结构是最简单、最基本的控制结构，其操作步骤是按照设置的先后顺序，是最简单、最基本的控制结构，其操作步骤是按照设置的先后顺序，一步一步地执行。一步一步地执行。设设A、B代表算法的两个不同的步骤，顺序结构的基本形式为代表算法的两个不同的步骤，顺序结构的基本形式为“执行执行A，然后执，然后执行行B”，即按照从上到下依次执行，即按照从上到下依次执行A步骤和步骤和B步骤，执行流程

18、如图所示。步骤，执行流程如图所示。 【例例5-2】表述用计算表述用计算机实现求任意两数之和机实现求任意两数之和的算法。的算法。2. 分支结构2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部分支结构也叫选择结构，它首先需要判断给定条件的真假，然后选择执行方分支结构也叫选择结构，它首先需要判断给定条件的真假，然后选择执行方向。如图向。如图下所示，其基本形式为下所示，其基本形式为“如果如果P成立，则执行成立，则执行A，否则（即条件，否则（即条件P不成不成了）执行了）执行B”。应当注意，无论条件是否成立，只能执行。应当注意，无论条件是否成立，只能执行A或或B之一，不能既执行之一，不

19、能既执行A又执行又执行B。（a）流程图）流程图（b）N-S图图 2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部【例【例5-3】求任意求任意3个正整数个正整数a、b、c中的最大者。中的最大者。用自然语言描述其算法如下：用自然语言描述其算法如下：S1：输入：输入3个正整数个正整数 a，b，c；S2：若：若a大于大于b，则将，则将a放到放到max中，否则将中，否则将b放到放到max中；中；S3：若：若c大于大于max，则将，则将c放到放到max中；中；S4：输出：输出max即为三个数中最大的一个。即为三个数中最大的一个。用流程图描述算法如图所示。用流程图描述算法如图所示。分支结

20、构示例流程图分支结构示例流程图3. 3.循环结构循环结构2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部循环结构也叫重复结构，它在给定条件成立时，需要反复执行同一操作。循环结构也叫重复结构，它在给定条件成立时，需要反复执行同一操作。循环结构有三个要素：循环结构有三个要素：循环变量循环变量、循环体循环体和和循环终止条件循环终止条件。即从某处开始，按照一定条件需要反复执行的某些步骤，就是循环体。循环结即从某处开始，按照一定条件需要反复执行的某些步骤，就是循环体。循环结构中通常都有一个起循环计数作用的变量，这个变量的取值一般都包含在执行构中通常都有一个起循环计数作用的变量，这个变

21、量的取值一般都包含在执行或终止循环的条件中，即为循环变量。循环结构不能无限制的进行下去，否则或终止循环的条件中，即为循环变量。循环结构不能无限制的进行下去，否则就成了死循环，所以一定要在某个条件下终止循环，这个可以用来判定是否继就成了死循环，所以一定要在某个条件下终止循环，这个可以用来判定是否继续执行循环体的条件就称为循环终止条件。续执行循环体的条件就称为循环终止条件。从循环的形成与控制不同来划分，循环结构可分为当型循环结构和直到型循环从循环的形成与控制不同来划分，循环结构可分为当型循环结构和直到型循环结构。结构。2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部当型循环结构

22、当型循环结构：是先判断条件是先判断条件P，若，若P成立，执行循环体成立，执行循环体A，如此反复，如此反复，当当P不成立时，退出循环结构，如图（不成立时，退出循环结构，如图（a）所示。）所示。直到型循环结构直到型循环结构：是先执行一次循环体是先执行一次循环体A后，再对条件后，再对条件P进行判断，若进行判断，若P不成立，执行循环体不成立，执行循环体A，如此反复，直到条件，如此反复，直到条件P成立，退出循环结构，如成立，退出循环结构，如图（图（b）所示。）所示。（a）当型循环结构流程图和）当型循环结构流程图和N-S图图（b）直到型循环结构流程图和）直到型循环结构流程图和N-S图图5.1.5 算法的评

23、价2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部同一个问题可以用许多不同的算法解决，而不同的算法可能耗用系统不同同一个问题可以用许多不同的算法解决，而不同的算法可能耗用系统不同的时间、空间或效率。对算法优劣的评定称为的时间、空间或效率。对算法优劣的评定称为“算法评价算法评价”。算法评价的目的，在于从解决同一问题的不同算法中选择出较为合适的一算法评价的目的，在于从解决同一问题的不同算法中选择出较为合适的一种算法，或者是对原有的算法进行改造、加工，使其更优、更好。种算法，或者是对原有的算法进行改造、加工，使其更优、更好。算法评价的标准算法评价的标准：（1）算法的正确性（2）算

24、法的可读性（3）算法的健壮性（4）算法的时间复杂度 （5）算法的空间复杂度2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部5.2 算法设计5.2.1 计算机基本算法计算机基本算法利用计算机解题的过程实际上是实施某种算法的过程，在这个过程利用计算机解题的过程实际上是实施某种算法的过程，在这个过程中，将具体问题抽象出其数学模型固然重要，但也要充分考虑计算机强中，将具体问题抽象出其数学模型固然重要，但也要充分考虑计算机强大的数据处理能力和其硬件设备的限制问题，在此基础上发现和构造的大的数据处理能力和其硬件设备的限制问题，在此基础上发现和构造的一些常见问题的处理算法一些常见问题的处

25、理算法，已不同于传统的数学思维处理方法。如：两，已不同于传统的数学思维处理方法。如：两个变量值的交换、累加和累乘问题基本求解算法等。个变量值的交换、累加和累乘问题基本求解算法等。1. 交换变量的值2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部交换变量的值：需引入一个中间变量交换变量的值：需引入一个中间变量t，t=a,a=b,b=tabt1232022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部用自然语言描述其算法如下：用自然语言描述其算法如下：S1：输入：输入a，b的值；的值；S2：判断：判断ab是否成立，若成立，则依此执行是否成立，若成立，则依此执行S3

26、、S4、S5、S6；若不成立则执行；若不成立则执行S7；S3：将：将a的值存放到变量的值存放到变量t的存储单元中，即的存储单元中，即t=a； S4：将：将b的值存放到变量的值存放到变量a的存储单元中，即的存储单元中，即a=b；S5：将：将t的值（即原来变量的值（即原来变量a的值）存放到变量的值）存放到变量b的的存储单元中，即存储单元中，即b=t。S6：输出：输出a，b的值；的值；S7：输出：输出ab，则交换二者的值。，则交换二者的值。用流程图表示的算法用流程图表示的算法:2.累加2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部累加就是对若干个数求和。例如累加就是对若干个数求

27、和。例如1100的整数求和，的整数求和，mn之间的奇数或偶数之间的奇数或偶数求和等等。求和等等。计算机由于硬件所限，每次只能处理两个数的相加运算，所以多个数相加必计算机由于硬件所限，每次只能处理两个数的相加运算，所以多个数相加必须通过多次的两两相加来实现。而简单的重复执行某一操作正是计算机的强项。须通过多次的两两相加来实现。而简单的重复执行某一操作正是计算机的强项。因此计算机实现累加求和最基本的思想就是因此计算机实现累加求和最基本的思想就是“反复的做加法反复的做加法”。存储累加结果的变量一般情况下应该赋初值为存储累加结果的变量一般情况下应该赋初值为0。【例5-5】 计算1+2+3+n 的值。自

28、然语言算法描述如下：自然语言算法描述如下：S1S1：变量赋初值：变量赋初值：i=1i=1，sum=0sum=0；S2S2：输入：输入n n的值；的值；S3S3：判断：判断i=ni=n是否成立，若成立则执行是否成立，若成立则执行S4S4，否则就执行，否则就执行S5S5；S4S4：执行：执行sum=sum+i(sum=sum+i(实现累加实现累加) )，i=i+1(i=i+1(实现计数实现计数) )，并返回第三步继续执行，并返回第三步继续执行；S5S5：输出：输出sumsum的值。的值。 【例【例5-55-5】 计算计算1+2+3+1+2+3+ +n n 的值。的值。用流程图描述其算法如图用流程图

29、描述其算法如图5.105.10所示。所示。2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部开 始i= 1 ,su m = 0输 入 n 的 值i = nsu m = su m + 1i= i+ 1输 出 su m 的 值结 束NY3.累乘2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部累乘就是在一个变量的基础上重复乘上一个数。其基本思想和累加相同，最累乘就是在一个变量的基础上重复乘上一个数。其基本思想和累加相同，最典型的应用为阶乘问题。存储累乘结果的变量的初值应置为典型的应用为阶乘问题。存储累乘结果的变量的初值应置为1，不能为，不能为0。【例【例5-6】

30、计算】计算10！分析：分析：10!=12310，和例，和例5-5不不同的是在循环中运算的是乘法，每一次得同的是在循环中运算的是乘法，每一次得到的是累乘的积，记录累乘的积的变量初到的是累乘的积，记录累乘的积的变量初值应为值应为1。其算法流程图如图所示。其算法流程图如图所示。开 始p = 1i= 1i = 1 0p = p * ii= i+ 1输 出 p 的 值结 束NY5.2.2 经典算法策略2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部算法作为一门古老的学科，随着历史的发展，积累了很多经典算法策算法作为一门古老的学科，随着历史的发展，积累了很多经典算法策略。算法策略和算法

31、是有区别的，他们是算法设计中的两个方面。算法策略。算法策略和算法是有区别的，他们是算法设计中的两个方面。算法策略是面向问题的，算法是面向实现的，但是二者又是不可分的，只有通过略是面向问题的，算法是面向实现的，但是二者又是不可分的，只有通过一定的算法策略才能找出解决问题的具体算法。基本的算法策略主要有穷一定的算法策略才能找出解决问题的具体算法。基本的算法策略主要有穷举策略、递推策略、递归策略、分治策略、贪婪策略、回溯策略、和动态举策略、递推策略、递归策略、分治策略、贪婪策略、回溯策略、和动态规划策略等。规划策略等。1.枚举策略2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部枚

32、举既是一个策略，也是一个算法，还是一种分析问题的手段，所以，枚举既是一个策略，也是一个算法，还是一种分析问题的手段，所以，也称为枚举法、穷举法或试凑法。这种算法策略充分利用计算机高速运算的也称为枚举法、穷举法或试凑法。这种算法策略充分利用计算机高速运算的特点，将可能出现的、有穷的情况一一列举出来，用题目给定的检验条件来特点，将可能出现的、有穷的情况一一列举出来，用题目给定的检验条件来判断其是否符合条件，枚举完所有对象，问题最终得以解决。枚举法常用于判断其是否符合条件，枚举完所有对象，问题最终得以解决。枚举法常用于解决解决“是否存在是否存在”或或“有多少种可能有多少种可能”等类型的问题。等类型的

33、问题。枚举法在具体的程序实现过程中，可以通过循环结构和分支结构来完成枚举法在具体的程序实现过程中，可以通过循环结构和分支结构来完成。【例5-7】我国古代数学家张丘建在张丘建算经一书中提出了“百钱买百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部【分析分析】在本题中可以设鸡翁为在本题中可以设鸡翁为x只，鸡母为只，鸡母为y只，鸡雏为只，鸡雏为z只。由题意给出一只。由题意给出一共要用共要用100钱买一百只鸡，可将问题简化为三元一次方程组：钱买一百只鸡，可将问题简化为三元一次方程组：

34、x+y+z=100 （1） 5x+3y+z/3=100 （2）这里这里x,y,z为正整数，由于鸡和钱的总数都是为正整数，由于鸡和钱的总数都是100，可以确定，可以确定x，y，z的取值范的取值范围：围：0 x20、0y33、0z100。下面用枚举的方法设计本题算法。下面用枚举的方法设计本题算法。2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部算法设计一：根据问题中的约束算法设计一：根据问题中的约束条件，排除一些明显的不可能的条件，排除一些明显的不可能的情况，将可能的情况一一列举出情况，将可能的情况一一列举出来，即遍历来，即遍历x，y，z的所有可能的所有可能组合，最后得到问题的

35、解。流程组合，最后得到问题的解。流程图如图所示。图如图所示。开始0=x=20输出x、y、z的值z=z+10=y=335x+3y+z/3=100结束x=x+1NYYYNN0=z=100 x+y+z=100y=y+1NNYY2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部算法设计二：在假设了鸡翁和鸡母的算法设计二：在假设了鸡翁和鸡母的只数为只数为x和和y之后，鸡雏的数量就可确之后，鸡雏的数量就可确定为定为100 xy，那么此时只对，那么此时只对x，y进行枚举即可，而约束条件就只有一进行枚举即可，而约束条件就只有一个个5x3yz/3100，流程图如图，流程图如图5.13所示。所示

36、。开始0=x=20输出x、y、z的值0=y=335x+3y+z/3=100结束x=x+1NYYYNNz=100-x-yy=y+12.递推策略2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部递推策略在数学上又称为迭代法或辗转法，其基本思想是从给定的初始条递推策略在数学上又称为迭代法或辗转法，其基本思想是从给定的初始条件出发，通过算法（递推公式）推出可求的新值，再由所得新值代替旧值，然件出发，通过算法（递推公式）推出可求的新值，再由所得新值代替旧值，然后按着同样的算法（递推公式）又可求得另一个新值，依此类推，经过有限次后按着同样的算法（递推公式）又可求得另一个新值，依此类推，经

37、过有限次推导，即可求得最终结果。递推的过程就是找出旧值和新值（即相邻两项或几推导，即可求得最终结果。递推的过程就是找出旧值和新值（即相邻两项或几项）之间的关系，即递推公式。然后通过给定的初始条件，再按照这一规律来项）之间的关系，即递推公式。然后通过给定的初始条件，再按照这一规律来计算序列中其余各项。递推策略更多地用于计算，如利用辗转相除法求两个正计算序列中其余各项。递推策略更多地用于计算，如利用辗转相除法求两个正整数的最大公约数，就体现了这一算法思想。整数的最大公约数，就体现了这一算法思想。2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部【例【例5-8】猴子吃桃问题。一只猴

38、子第一天摘下若干猴子吃桃问题。一只猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个，第二桃子，当即吃了一半，还不过瘾，又多吃了一个，第二早上又将剩下的桃子吃掉一半，又多吃了一个。以后每早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半再多一个。到第天早上都吃了前一天剩下的一半再多一个。到第10天早天早上想再吃时，见只剩下一个桃子了。求猴子第一天共摘上想再吃时，见只剩下一个桃子了。求猴子第一天共摘了多少个桃子？了多少个桃子？ 【分析分析】这是一个递推问题，因为猴子每次吃掉前一这是一个递推问题，因为猴子每次吃掉前一天的一半又多一个，则若设天的一半又多一个，则若

39、设xn为第为第n天的桃子数，它就天的桃子数，它就是第是第n-1天的桃子数的一半减天的桃子数的一半减1个，即个，即 那么第那么第n-1天的桃子数的递推公式为：天的桃子数的递推公式为：1211nnxx211-）（nnxx3. 递归策略2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部递归策略是利用大问题与其子问题的递推关系来解决问题。它通常把一个大递归策略是利用大问题与其子问题的递推关系来解决问题。它通常把一个大型复杂的问题层层转化为一个与原问题相似的但规模较小的问题来求解。递归型复杂的问题层层转化为一个与原问题相似的但规模较小的问题来求解。递归的能力在于用有限的语句来定义对象的

40、无限集合。递归策略只需少量的程序就的能力在于用有限的语句来定义对象的无限集合。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。在算可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。在算法或程序设计中，具体的处理办法是一个过程或函数在其定义或说明中又直接法或程序设计中，具体的处理办法是一个过程或函数在其定义或说明中又直接或间接地调用自身。或间接地调用自身。2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部【例【例5-9】斐波那契（】斐波那契（Fibonacci）是中世纪意大利数学家，他在算盘书中）是中世纪意大利数学家，他在算

41、盘书中提出了提出了1对兔子的繁殖问题：如果每对兔子成熟后每月能生对兔子的繁殖问题：如果每对兔子成熟后每月能生1对小兔子，而每对对小兔子，而每对小兔子在出生后的第三个月开始，每月再生小兔子在出生后的第三个月开始，每月再生1对小兔子，假定在不发生死亡的对小兔子，假定在不发生死亡的情况下，最初的一对兔子在一年末能繁殖成多少对兔子（假定以上兔子都是雌情况下，最初的一对兔子在一年末能繁殖成多少对兔子（假定以上兔子都是雌雄成对）？雄成对）？ 【分析分析】根据问题描述，可以看出新生兔到第三个月开始生小兔，之后就可根据问题描述，可以看出新生兔到第三个月开始生小兔，之后就可每月生一对小兔，而且不发生死亡情况，每

42、月生一对小兔，而且不发生死亡情况，下下表可清楚地分析兔子数的变化规律表可清楚地分析兔子数的变化规律月份月份1月月2月月3月月4月月5月月6月月7月月8月月9月月10月月11月月12月月小兔小兔111235813213455大兔大兔1123581321345589合计合计11235813213455891442022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部假设第假设第n个月的兔子数目是个月的兔子数目是fib(n)，根据上述分析，可得如下关系式：，根据上述分析，可得如下关系式：2)2()1(21)(nnfibnfibnnfib该公式递归地定义了该公式递归地定义了Fibonacc

43、i数列的各项。数列的各项。用用C程序设计语言描述其递归函数为：程序设计语言描述其递归函数为：int fib(int n) int f;if(n=0)printf( n=0，数据错误！，数据错误！);else if (n= =1|n= =2)f=1; else f= fib(n-1)+fib(n-2);return f; 开 始fib(1)=1fib(2)=1i=n输 出 fib(1)、 fib(2)、 、 fib(n)的 值i=3fib(i)=fib(i-1)+fib(i-2)i=i+1结 束NY4.分治策略2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部在计算机科学中，分

44、治策略是一种很重要的算法策略。字面上的解释是在计算机科学中，分治策略是一种很重要的算法策略。字面上的解释是“分分而治之而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。的解即子问题的解的合并。分治策略的一个要点是子问题与原问题结构相同，因此子问题也同样可以利分治策略的一个要点是子问题与原问题结构相同，因此子问题也同样可以利用分治策略进行求解。用分治策略进行求解。如果原

45、问题可分割成如果原问题可分割成k个子问题，个子问题，1max，则，则max=A(2)；S3：取：取A(3)和和max比较，如果比较，如果A(3)max，则，则max=A(3)；S4：取：取A(4)和和max比较，如果比较，如果A(4)max，则，则max=A(4)；依此类推依此类推S10：取：取A(10)和和max比较，如果比较，如果A(10)max，则，则max=A(10)；S11：输出该数列最大值：输出该数列最大值max。开始max=A(1)i=2imax结束NYYN2.排序问题2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部排序是数据处理中最常见的问题之一，它要求将一

46、组数据按递增或递减的排序是数据处理中最常见的问题之一，它要求将一组数据按递增或递减的次序排列，例如对一个班的学生考试成绩排序，公司内多个销售部门月销售次序排列，例如对一个班的学生考试成绩排序，公司内多个销售部门月销售额排序等等。额排序等等。排序算法有很多种，最常用的有选择排序法、冒泡排序法、插入排序法、排序算法有很多种，最常用的有选择排序法、冒泡排序法、插入排序法、合并排序法、希尔排序法等等。不同算法的执行效率不同，因此在处理数据合并排序法、希尔排序法等等。不同算法的执行效率不同，因此在处理数据量很大的排序问题时选择适当的算法就显得很重要了。量很大的排序问题时选择适当的算法就显得很重要了。下面

47、以例下面以例5-11为处理对象，比较冒泡排序法、选择排序法和插入排序法的为处理对象，比较冒泡排序法、选择排序法和插入排序法的算法思想和操作特点。算法思想和操作特点。2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部【例【例5-11】将数列】将数列A中的元素中的元素8，6，9，3，2，7按升序排列。按升序排列。 冒泡排序法冒泡排序法冒泡法排序（升序）的基本思路是：从第一个元素开始，对数列中两两相冒泡法排序（升序）的基本思路是：从第一个元素开始，对数列中两两相邻的元素进行比较，如不符合顺序要求，就立即交换，直到该数列的最后一个邻的元素进行比较，如不符合顺序要求，就立即交换，直到该

48、数列的最后一个元素。按此方法，数列中的数据经过一轮比较移位后，数列中一些较小的数就元素。按此方法，数列中的数据经过一轮比较移位后，数列中一些较小的数就如同气泡一样上浮（前移）一个位置，一些较大的数会下沉（后移）一个位置如同气泡一样上浮（前移）一个位置，一些较大的数会下沉（后移）一个位置，而最大的数会沉底，成为数列中的最后一个元素。这时称第一轮冒泡排序结，而最大的数会沉底，成为数列中的最后一个元素。这时称第一轮冒泡排序结束。第二轮冒泡排序只对前束。第二轮冒泡排序只对前n-1个数列元素进行比较移位即可。依此类推，个数列元素进行比较移位即可。依此类推，n个个数，经过数，经过n-1轮比较移位后完成排序

49、。轮比较移位后完成排序。冒泡排序重复地走访要排序的数列，一次次比较交换，完成排序，这体现冒泡排序重复地走访要排序的数列，一次次比较交换，完成排序，这体现了枚举策略的思想。了枚举策略的思想。2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部选择法排序选择法排序选择法排序（升序）的基本思路是：每一趟从待排序的数据元素中选出最小的选择法排序（升序）的基本思路是：每一趟从待排序的数据元素中选出最小的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。例例5-11用自然语言用自然语言描述算法为：描述算

50、法为：S1：从：从6个数中选出最小的数，与第个数中选出最小的数，与第 1个数交换位置；个数交换位置；S2：在除第：在除第1 个数外的其余个数外的其余5个数中选最小的数，与第个数中选最小的数，与第2个数交换位置；个数交换位置；S3：依此类推，选择了：依此类推，选择了5趟后，这个数列已按升序排列。趟后，这个数列已按升序排列。插入法排序2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部插入排序的基本思想是：把插入排序的基本思想是：把n个待排序的数据分为两部分：个待排序的数据分为两部分：R1，R2，Ri-1为已排好序的有序表，为已排好序的有序表，Ri，Ri+1，Rn为未排序的无序表（

51、初始时，令为未排序的无序表（初始时，令i=2）。把未排序的无序表中的第）。把未排序的无序表中的第1个数据个数据Ri依次与依次与R，Ri-1比较，并插比较，并插入到有序表的适当位置上，使得入到有序表的适当位置上，使得R1，R2，Ri-1变为一个新的有序表，直变为一个新的有序表，直到未排序表中的数据元素全部插入到有序表中。图到未排序表中的数据元素全部插入到有序表中。图5.21说明了例说明了例5-11的数据的数据按插入排序法进行排序的全过程。按插入排序法进行排序的全过程。3.查找问题2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部查找是数据处理中经常使用的一种重要算法。查找过程就

52、是在给定的一列数查找是数据处理中经常使用的一种重要算法。查找过程就是在给定的一列数据中寻找指定的数据及该数据在数列中的位置。常见的查找算法有：顺序查据中寻找指定的数据及该数据在数列中的位置。常见的查找算法有：顺序查找法和二分法查找法。找法和二分法查找法。（1）顺序查找法）顺序查找法顺序查找，是最原始的要求最低的查找办法，指的是从数列的第一个元素开顺序查找，是最原始的要求最低的查找办法，指的是从数列的第一个元素开始，将要查找的数据与数列中的每个元素，依次进行比较，如果二者相等，始，将要查找的数据与数列中的每个元素，依次进行比较，如果二者相等，则查找成功，结束查找并记录位置；否则，查找失败。则查找

53、成功，结束查找并记录位置；否则，查找失败。2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部（2）二分查找）二分查找二分查找又称折半查找，是一种查找效率较高的查找方法。但该方二分查找又称折半查找，是一种查找效率较高的查找方法。但该方法要求待查数据列必须是有序的，即数据是由小到大或由大到小排列的。法要求待查数据列必须是有序的，即数据是由小到大或由大到小排列的。二分查找二分查找的的基本的思想基本的思想为（为（假设数列中元素按升序排列假设数列中元素按升序排列）：）：首先，将查找的数与待查数列中处于中间位置的数据（中点数据）首先，将查找的数与待查数列中处于中间位置的数据（中点数据）进

54、行比较，如果两者相等，则查找成功；否则利用中间位置将数列分成前进行比较，如果两者相等，则查找成功；否则利用中间位置将数列分成前、后两个子数列，若待查数据小于中点数据，则进一步查找前一子数列，、后两个子数列，若待查数据小于中点数据，则进一步查找前一子数列，否则进一步查找后一子数列。其次，在子数列中重复以上过程，直到找到否则进一步查找后一子数列。其次，在子数列中重复以上过程，直到找到满足条件的数据，使查找成功，或直到再分解的子数列不存在为止，此时满足条件的数据，使查找成功，或直到再分解的子数列不存在为止，此时查找不成功。查找不成功。2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学

55、部【例【例5-12】 假设有一组从小到大排列的数列假设有一组从小到大排列的数列A：A(1)、A(2)、A(3)、A(4)、A(5)、A(6)、A(7)、A(8)、A(9)、A(10)，用二分法查找此数列中是否含有数据值为，用二分法查找此数列中是否含有数据值为x的数。若有，则输出这个数在数列中的下标。若不在，则显示该数不存在。的数。若有，则输出这个数在数列中的下标。若不在，则显示该数不存在。【分析分析】假设假设Low为查找区间下界的数列元素下标，初值为为查找区间下界的数列元素下标，初值为0；High为查找区间为查找区间上界的数列元素上标，初值为上界的数列元素上标，初值为10，即，即Low=0，H

56、igh=10；需要查找的数为；需要查找的数为x。二分查找的算法描述如下二分查找的算法描述如下：S1：求出查找区间的中间位置元素下标：求出查找区间的中间位置元素下标Mid=(int)(High +Low)/2) ；S2：若：若A(Mid)）=x成立，则找到，否则进行下面的判断；成立，则找到，否则进行下面的判断；S3：若：若A(Mid)x），则表明），则表明x在在A(Low)到到A(Mid-1)区间内，则设置区间内，则设置High=Mid-1，使查找区间上界移动到新位置；，使查找区间上界移动到新位置；S5：重复执行以上操作；：重复执行以上操作；S6：结束查找的条件有两个：已经找到或找不到（：结束查

57、找的条件有两个：已经找到或找不到（Low High）。）。5.3 数据结构2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部数据结构是主要研究组织大量数据的方法，即计算机存储、组织数据的数据结构是主要研究组织大量数据的方法，即计算机存储、组织数据的方式及其相互关系。它用来反映一个数据的内部构成，即一个数据由哪些成方式及其相互关系。它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。分数据构成，以什么方式构成，呈什么结构。5.3.1 数据结构的基本概念数据结构的基本概念数据结构是相互之间存在某种特定关系的数据元素的集合。因此，数据结构是相互之

58、间存在某种特定关系的数据元素的集合。因此，也可以把数据结构看成是带结构的数据元素的集合。也可以把数据结构看成是带结构的数据元素的集合。2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部数据结构研究的内容可以包含以下几个方面：数据结构研究的内容可以包含以下几个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；存储结构；（3）对各种数据结构进行的运算。）对各种

59、数据结构进行的运算。5.3.2 5.3.2 数据的逻辑结构数据的逻辑结构2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部数据结构是指相互之间具有一定关系的数据元素的集合。数据元素之间的关数据结构是指相互之间具有一定关系的数据元素的集合。数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的定义的关系，这种自然或人为定义的“关系关系”称为数据元素之间的逻辑关系，称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。相应的结构称为逻辑结构。数据元素之间

60、的逻辑结构有四种基本类型数据元素之间的逻辑结构有四种基本类型： 集合集合、线性结构线性结构、树型结构树型结构、图状结构图状结构集合 线性结构 树形结构 图形结构5.3.3 5.3.3 数据的物理结构数据的物理结构2022-3-7太原理工大学.计算机科学与技术学院.计算机基础教学部数据元素在计算机存储空间的存放形式就是数据的物理结构，也称为数据的存储数据元素在计算机存储空间的存放形式就是数据的物理结构，也称为数据的存储结构。它是数据的逻辑结构在存储器里的实现，包括数据元素的存储和元素之间结构。它是数据的逻辑结构在存储器里的实现，包括数据元素的存储和元素之间关系的表示。关系的表示。元素之间的关系在