计算机科学导论-数据结构与算法综述

1、第第5讲讲 数据结构与算法数据结构与算法 理解数据结构的概念，理解数据结构的逻辑和存储结构； 理解算法的概念和算法的基本特性，了解算法复杂度的度量方法； 理解线性数据结构，理解顺序存储和链式存储的存储方法； 描述栈和队列、串和数组这几个线性数据结构的概念； 了解非线性的数据结构，了解树、二叉树以及图的概念和数据结构； 理解排序的概念，描述插入、选择、气泡和快速排序的算法； 理解查找的概念，描述顺序查找和折半查找的算法，并能够比较它们 理解递归的概念，能够在实践中了解递归的应用。 教 学 目目 的的学学 习习 重重 点点 数据结构的基本概念 算法的描述、流程图的使用以及算法的复杂度的衡量 顺序存

2、储和链式存储的方法 栈、队列、串和数组的概念和用法 二叉树数据结构 查询、排序和递归算法第一节第一节 数据结构概述数据结构概述1. 1. 数据结构概述数据结构概述1. 数据结构概述1.2 数据结构相关概念基本概念和术语数据元素、结点、数据项、关键字或主关键字、 次关键字、数据对象、数据结构数据结构 特性相同的数据元素构成的集合中，如果在数据元素之间存在一种或多种特定的关系，则称之为数据结构 。 Data-Structure=(D,R) 其中，D是数据元素的有限集，R是D上关系的有限集。1. 数据结构概述1. 数据结构概述四类基本的数据结构集合结构。在集合结构中，数据元素间的关系是“属于同一个集

3、合”。集合是元素关系极为松散的一种结构，各元素间没有直接的关联。线性结构。该结构的数据元素之间存在着一对一的关系。树型结构。该结构的数据元素之间存在着一对多的关系。图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。 123456 例例5-2 5-2 线性数据结构线性数据结构=(D,S)=(D,S) D=1,2,3,4,5,6,7,8,9,10 D=1,2,3,4,5,6,7,8,9,10 S=,S=, , ,1. 数据结构概述例5-3 图形数据结构=(D,R) D=1, 2, 3, 4, 5, 6, 7, 8, 9 R=, ,1. 数据结构概述 例例5-4 树形结构树形

4、结构 =（D,R） D=a, b, c, d, e, f, g, h, i, j, k, l R=, ,1. 数据结构概述1.3 数据结构的分类按数据结构的性质划分 数据的逻辑结构数据元素之间的逻辑关系 （设计算法 数学模型） 数据的物理结构数据结构在计算机中的映像 （存储结构，算法的实现）按数据结构的操作来划分 静态结构经过操作后，数据的结构特征保持不变（如数组）。 半静态结构经过操作后，数据的结构特性只允许很小变迁（如栈、队列）。 动态结构经过操作后，数据的结构特性变化比较灵活，可随机地重新组织结构（如指针）。1. 数据结构概述1.3 数据结构的分类按数据结构在计算机内的存储方式来划分 顺

5、序存储结构借助元素在存储器的相对位置来表示数据元素之 的逻辑关系。 链式存储结构借助指示元素存储地址的指针表示数据元素之间 的逻辑关系 索引存储结构在存储结点的同时，建立附加 的索引表，索引表 中的每一项称为索引项，形式为：关键字，地址。 散列存储结构根据结点的关键字直接计算出该结点的存储地址。 说明：四种存储方法可结合起来对数据结构进行存储映像。1. 数据结构概述1.4 算法及其描述和算法分析1、算法的概念及特征算法: 对问题求解的描述，为解决问题给出的一个确定的、有限长的操作序列算法具有以下五个重要的特征： 1）有穷性：一个算法必须保证执行有限步之后结束。 2）确切性：算法的每一步骤必须有

6、确切的定义。 3）输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。 4）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。 5）可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。1. 数据结构概述1.4 算法及其描述和算法分析算法的描述: 1）流程图 2）伪代码类程序设计语言算法的基本结构 :1）顺序结构 2）分支结构 3）循环结构1. 数据结构概述1. 数据结构概述 算法基本结构示意图算法基本结构示意图1.4 算法及其描述和算法分析算法效率衡量方法与准则 :时间复杂度：指算法从开

7、始执行到处理结束所需要的总时间。 T（n）= O（f(n)）空间复杂度：指算法从开始执行到处理结束所需的存储量空间的总和。 S（n）= O（g(n)）1. 数据结构概述1. 数据结构概述第二节 线性结构2.1 线性表线性表的定义 线性表是n(n=0)个数据元素的有限序列，表中各个元素具有相同的属性，表中相邻元素间存在“序偶”关系。 记做：(a1,a2,.ai-1,ai,ai+1,an-1,an ) 其中，ai-1称为ai 的直接前驱元素，ai+1是ai的直接后继元素 线性表的长度：表中的元素个数 n 位序：i称元素ai在线性表中的位序2. 线性结构2.1 线性表线性表的顺序表示和实现 线性表的

8、顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。 2. 线性结构2.1 线性表线性表的顺序表示和实现 顺序表线性表的顺序存储表示 Const LIST_INIT_SIZE=100; (C+规范) Const LISTINCREMENT=10; #define LIST_INIT_SIZE 100 (C规范) Typedef Struct Elemtype * elem;Int length;Intlistsize;Int incrementsize; SqList;2. 线性结构2. 线性结构2.1 线性表线性表的链式表示和实现 链表

9、是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的关系，对每个数据元素ai，除了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继ai+1所在的存贮单元的地址，这两部分信息组成一个“节点”。 2. 线性结构2.1 线性表线性表的链式表示和实现 单链表线性表的链式存储表示 F 数据域（data）和指针域（next） F 存储表示typedef struct LnodeElemTypedata;Struct Lnode*next;Lnode, *LinkList; 2. 线性结构2. 线性结构2. 线性结构2. 线性结构堆栈结构示意图堆栈结构示意图2. 线性结构2

10、. 线性结构2. 线性结构2. 线性结构2. 线性结构2. 线性结构2. 线性结构第三节 非线性结构3. 非线性结构3. 非线性结构3. 非线性结构典型的树结构典型的树结构3. 非线性结构二叉树的五种基本形态二叉树的五种基本形态 2.2.二叉树二叉树 满二叉树和完全二叉树满二叉树和完全二叉树 满二叉树（满二叉树（full binary treefull binary tree）：所有结点度为）：所有结点度为2 2，叶子结，叶子结点在同一层次。点在同一层次。 完全二叉树（完全二叉树（complete binary treecomplete binary tree）：一棵深度为）：一棵深度为k k

11、的有的有n n个节点的二叉树，对树中的节点按从上至下、从左到右的顺序个节点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，如果编号为进行编号，如果编号为i i（1in1in）的节点与满二叉树中编号）的节点与满二叉树中编号为为i i的节点在二叉树中的位置相同，则这棵二叉树称为完全二叉的节点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。树。 3. 非线性结构3. 非线性结构3. 非线性结构3. 非线性结构3.2 图图图的定义与相关概念图的定义与相关概念 图的相关概念图的相关概念弧弧(arc)(arc)、弧头（终点）、弧尾（起点）：、弧头（终点）、弧尾（起点）：表示从表示从v v到到w

12、 w的弧的弧 有向图有向图(digraph) (digraph) 、无向图、无向图(undigraph) (undigraph) 、边、边: : (v,w)(v,w)代表代表和和 有向网、无向网：有向网、无向网：带权的有向图和无向图带权的有向图和无向图 完全图（完全图（complete graphcomplete graph）：边）：边e e为为n(n-1)/2n(n-1)/2有向完全图：弧有向完全图：弧e e为为n(n-1)n(n-1) 3. 非线性结构3. 非线性结构3 非线性结构一、一、算法概念算法概念二、二、算法结构算法结构三三、算法表示算法表示（流程图、伪代码、（流程图、伪代码、N-

13、SN-S图等）图等）四、四、基本基本算法算法（计数，累加，值交换，求最（计数，累加，值交换，求最大（小）值，穷举、迭代、递推、递归）大（小）值，穷举、迭代、递推、递归） 1.1.算法的定义算法的定义 为解决问题而采取的方法和步骤。（非为解决问题而采取的方法和步骤。（非正式）正式） 算法是一组明确步骤的有序集合，它产算法是一组明确步骤的有序集合，它产生结果并在有限的时间内终止。（正式）生结果并在有限的时间内终止。（正式） 2. 2. 算法的分类算法的分类计算机算法可分为两大类：计算机算法可分为两大类： 数值运算算法：数值运算算法： 求解数值求解数值 非数值运算算法：非数值运算算法： 事务管理事务

14、管理例例 1:1: 数值计算问题：数值计算问题：结构静力分析计算结构静力分析计算需要解需要解线性线性代数方程组代数方程组。例例 2:2: 非数值计算问题：非数值计算问题：计算机对弈计算机对弈 算法算法对弈的规则和策略对弈的规则和策略 模型模型棋盘及棋盘的格局棋盘及棋盘的格局 3. 3.算法的基本特征算法的基本特征有穷性有穷性：任何算法都会在有限步后终止；：任何算法都会在有限步后终止；确定性确定性：算法的每一步都有唯一的含义；：算法的每一步都有唯一的含义；有效性有效性：算法的每一步都可以被执行；：算法的每一步都可以被执行；有输入有输入：可以有多个输入，也可能没有输：可以有多个输入，也可能没有输入

15、；入；有输出有输出：算法至少有一个输出结果。：算法至少有一个输出结果。 4.4.算法设计的原则算法设计的原则正确性：正确性：对于一切合法的输入数据都能得对于一切合法的输入数据都能得出满足要求的结果。出满足要求的结果。可读性：可读性：算法应该易理解，便于交流。算法应该易理解，便于交流。健壮性：健壮性：当输入非法数据时，算法应恰当当输入非法数据时，算法应恰当地作出反应或进行相应处理。地作出反应或进行相应处理。高效率与低存储量需求：高效率与低存储量需求：算法执行时间较算法执行时间较少，算法执行所需存储空间较小。少，算法执行所需存储空间较小。 定义动作定义动作 确定一系列的步骤，每一步都只完成一确定一

16、系列的步骤，每一步都只完成一个动作。个动作。 精化精化 剔除重复的步骤；剔除重复的步骤； 不同的步骤完成的动作可能相同，但它不同的步骤完成的动作可能相同，但它 们产生的结果不能相同。们产生的结果不能相同。 泛化泛化使算法对尽可能多的具体问题具有适应性。使算法对尽可能多的具体问题具有适应性。5.5.如何设计一个算法如何设计一个算法例例1 1：从一组正整数中找到最大的数。从一组正整数中找到最大的数。 （正整数个数（正整数个数2 2，3 3， N N）例如, 12, 8; 12, 8, 13; 12, 8, 13, 9; 12, 8, 13, 9, 11, . 方法方法1 1：第一步第一步: : 比

17、较第一个数和第二个数比较第一个数和第二个数; ;第二步第二步: : 比较第一个数和第三个数比较第一个数和第三个数; ;第三步第三步: : 比较第二个数和第三个数比较第二个数和第三个数; ;方法方法2：第一步：第一步：将最大值置为第一个数；将最大值置为第一个数；第二步：第二步：将第二个数和最大值进行比较，如果第将第二个数和最大值进行比较，如果第二个数大于最大值，将最大值置为第二个数，二个数大于最大值，将最大值置为第二个数，反之保持最大值不变。反之保持最大值不变。第三步：第三步：将第三个数和最大值进行比较，如果第将第三个数和最大值进行比较，如果第三个数大于最大值，将最大值置为第三个数，三个数大于最

18、大值，将最大值置为第三个数，反之保持最大值原值不变。反之保持最大值原值不变。第二、第二、三步程三步程序功能序功能相同，相同，程序描程序描述语言述语言相似相似和第二、三步不同和第二、三步不同方法方法3：第零步：第零步：将最大值置为零；将最大值置为零；第一步：第一步：如果当前数大于最大值，那么将最如果当前数大于最大值，那么将最大值置为当前数，否则保留原最大值；大值置为当前数，否则保留原最大值；第二步：第二步：重复第一步直至所有数全比较完。重复第一步直至所有数全比较完。 任何算法（或程序）都由三种基本结构组成任何算法（或程序）都由三种基本结构组成： 顺序结构顺序结构 判断（选择）结构判断（选择）结构

19、 循环结构循环结构 任何算法都是上述三种结构的组合。任何算法都是上述三种结构的组合。1. 1. 顺序结构顺序结构S1S22. 2. 选择结构选择结构60N条件条件S1S2Y 双选择结构双选择结构N条件条件S1Y单选择结构单选择结构3. 3. 循环结构循环结构61 条件条件A 块块NY直到型循环结构直到型循环结构条件条件A 块块YN 当型循环结构当型循环结构三种基本结构的特点：三种基本结构的特点： 一个入口一个入口 一个出口一个出口 不出现死循环和死语句不出现死循环和死语句6263T+I TI10YN1I，0 K, 0 TK10YNT+K T64T+I TI10YN1I，0 K, 0 TK10Y

20、NT+K T死死循循环环死死语语句句65用顺序结构描述将华氏温用顺序结构描述将华氏温度度F F转换成摄氏温度转换成摄氏温度C C的流的流程。程。算法：算法：C=5/9*（F-32）4. 4. 顺序结构设计顺序结构设计顺序结构中，按语句的自顺序结构中，按语句的自然顺序依次执行。然顺序依次执行。开始开始5/9 bb*(F-32)C输出输出F F，C C结束结束输入输入F F66已知三角形的已知三角形的3 3条边边长，求条边边长，求三角形面积。用顺序结构描三角形面积。用顺序结构描述求三角形面积的流程。述求三角形面积的流程。开始开始(a+b+c)/2 ss*(s-a)*(s-b)*(s-c) t输出输

21、出areaarea结束结束输入输入a,b,ca,b,careat 用顺序结构描述两个值用顺序结构描述两个值（a=1, b=2a=1, b=2）交换的流程）交换的流程 12bca1开始开始1 1a a，2 2b ba bb a 输出输出a a，b b结束结束a cb ac b2112ab21选择结构（分支选择结构（分支结构），根据选结构），根据选择结构中判断的择结构中判断的结果，选择执行结果，选择执行相应的语句。相应的语句。5. 5. 选择结构及其程序设计选择结构及其程序设计开始开始输出输出 MAXMAX结束结束输入输入R,HR MAXH MAXRHYN例例 用选择用选择结构结构描述求描述求两个

22、数中两个数中的最大值的流程的最大值的流程例例 用选择结构描用选择结构描述检查某年是否闰述检查某年是否闰年的流程。年的流程。X X年为闰年满足下年为闰年满足下列条件之一：列条件之一：1.N1.N能被能被400400整除整除2.N2.N能被能被4 4整除，但整除，但不能被不能被100100整除整除开始开始输出输出 X X YESYES结束结束输入输入XX被被400整除整除YNX被被4整除整除YNX被被100整除整除YN输出输出 X X NONO用选择结构描述用选择结构描述检查某成绩级别检查某成绩级别的流程。的流程。成绩成绩N N的级别：的级别：A A级级-X90-X90B B级级90X8090X8

23、0C C级级80X6080X60D D级级X60X60开始开始输出输出 X-X-A A结束结束输入输入XX 9090YNX 80YNYNX 60输出输出 X-X-B B 输出输出 X-X-C C输出输出 X-X-D D循环结构：当循环控制条循环结构：当循环控制条件为真时反复执行循环体件为真时反复执行循环体中的语句，直到循环控制中的语句，直到循环控制条件为假时为止。条件为假时为止。开始开始输出输出 T T 的值的值结束结束输入输入KT+K TI+1 II10YN1I，0 T累加器累加器计数器计数器用循环结构描述求用循环结构描述求1010个个学生成绩之和的流程学生成绩之和的流程用用T T累计累计1

24、010个学生的成绩（个学生的成绩（K K），），用用I I记录累加的次数记录累加的次数（I=1,2,I=1,2,10,10）6.6.循环结构及其程序设计循环结构及其程序设计例例 用循环结构描述用循环结构描述求求1010到到100100之间所之间所有不能被有不能被3 3整除的整整除的整数的流程数的流程开始开始结束结束I+1 II100YN10II不能被不能被3整除整除输出输出 IYN对对1010到到100100之间所之间所有数逐一验证，凡有数逐一验证，凡满足满足“不能被不能被3 3整除整除”的整数即可输出。的整数即可输出。循环嵌套结构循环嵌套结构：一个循环结构一个循环结构的循环体中又的循环体中又

25、出现另一个循出现另一个循环结构。环结构。 外循环外循环 内循环内循环J+1 JI3YN1I输出IJ21J输出JI+1 IYNI=1，输出1 J=1，输出1 J=2，输出2I=2，输出2 J=1，输出1 J=2，输出2I=3，输出3 J=1，输出1 J=2，输出274例例 打印边长为打印边长为 m m 的正方型的正方型要求：从键盘输入要求：从键盘输入 m m 值，输出值，输出 m m 行每行行每行 m m 个个* *号。号。例：输入例：输入 m=4m=4，输出的图形如下：，输出的图形如下：* * * * * * * * * * * * * * * * * * * * * * * * * * *

26、* *算法：算法：1. 1. 输入输入 m m 2. 2. 重复重复打印打印 m m 行，每行打印行，每行打印 m m 个个 * *开始开始结束结束输入输入MI+1 IIMYN1I 对行循环对行循环(I=1,2,，M) 对对I行的各列循行的各列循环环(J=1,2,，M)输出输出 * * J+1 JJMYN1 J换行换行输出输出I行的行的M个个* *I=1，J=1 输出 * * J=2 输出 * * J=3 输出 * * J=4 输出 * * 换行I=2 J=1，2，3，4 * *I=4 J=1，2，3，4 * * * *77例例 从键盘输入从键盘输入n n值，输出值，输出n n行用行用* *号

27、组成等腰三角号组成等腰三角形。例：输入形。例：输入 n=4n=4，输出的图形如下：，输出的图形如下：* * * * * * * * * * * * * * k=1,n-1=3个空，2*1-1=1个* * * * k=2,n-2=2个空，2*2-1=3个* * * * * * k=3,n-3=1个空，2*3-1=5个* * * * * * * k=4,n-4=0个空，2*4-1=7个*共共n n行，其中第行，其中第K K行由行由n-kn-k个空格个空格和和2k-12k-1个个* *组成组成 分析：分析： 1 1、输出、输出 n n 行。行。 2 2、图形的第、图形的第 k k 行行(1=(1=k

28、 k=n n) )由由 n n- -k k个个 空格空格 和和 2 2k k-1 -1 个个 * * 组成。组成。算法设计：算法设计：1.1.输入输入 n n; ;2.2.重复重复输出输出n n行。对于第行。对于第 k k 行，行，每行输出每行输出n n- -k k 个空格个空格和和 2 2k k-1 -1 个个* * 开始开始结束结束输入输入nk+1 kknYN1k 对行循环对行循环(k=1,2,，n)输出空输出空J+1 JJn-kYN1 J输出输出 * * J+1 JJ2k-1YN1 J换行换行 对每个对每个k行行各列循环，各列循环，输出输出n-k个空个空格和格和2k-1个个* 自然语言自

29、然语言 流程图流程图 伪代码伪代码 结构图结构图 N-SN-S结构图结构图 PADPAD结构图结构图 计算机语言计算机语言 用规定的一系列图形、流程线和文用规定的一系列图形、流程线和文字说明算法中的基本操作和控制流程。字说明算法中的基本操作和控制流程。流程图包括：流程图包括： 表示相应操作的框；表示相应操作的框； 带箭头的流程线；带箭头的流程线； 框内外必要的文字说明。框内外必要的文字说明。1. 1. 流程图流程图（1 1）图形符号）图形符号起止框起止框判断框判断框处理框处理框输入输入/输出框输出框注释框注释框流向线流向线连接点连接点例：求给定半径例：求给定半径R R的的圆面积和圆周长。圆面积

30、和圆周长。算法：算法：圆面积圆面积 S=S=* R2 2圆周长圆周长 L=2L=2* *R开始开始输出输出 S S、L L的值的值结束结束输入半径输入半径R*R*R S2*R L顺序顺序（2 2）用流程图表示算法）用流程图表示算法例：例：求给定数求给定数R R的绝对值。的绝对值。算法算法：|R|= R R|R|= R R0 -R R0-R R0开始开始输出输出 S S的值的值结束结束输入输入RR S-R SR0YN选择选择求求 S=1+2+3+.+1000s;s+1ss+2 s.s+100 s0ss+i s(循环体循环体)(i=1,2,.,100)例例: : 给定给定K K值，求值，求T=1+

31、2+3+T=1+2+3+K+K。K=5，T=0I=1：T=0+1=1，I=1+1=2I=2：T=1+2=3，I=2+1=3I=3：T=3+3=6，I=3+1=4I=4：T=6+4=10，I=4+1=5I=5：T=10+5=15，I=5+1=60 0 T TT+IT+I T(I=1,2,3,T(I=1,2,3,K)K)开始开始输出输出 T T 的值的值结束结束输入输入KT+I TI+1 IIKYN1I，0 T循循环环 由于流程线的任意转向性，传统流程图由于流程线的任意转向性，传统流程图无法保证自顶向下的程序设计，使模块之间无法保证自顶向下的程序设计，使模块之间的调用关系难以表达。故两位美国学者的

32、调用关系难以表达。故两位美国学者NassiNassi和和ShneidermanShneiderman于于19731973年提出了无流程线的年提出了无流程线的N-N-S S流程图流程图。 2. 2. N NS S流程图流程图S1S2流程图流程图S1S2N-S流程图流程图（1 1）图形符号）图形符号YNS1 S2 条件条件流程图流程图条件条件YNS1 S2N-S流程图流程图YN循环体循环体 条件条件流程图流程图循环体循环体循环条件循环条件N-S流程图流程图流程图流程图NY循环体循环体 条件条件循环体循环体循环条件循环条件N NS S流程图流程图（2 2）用）用N-SN-S流程图表示算法流程图表示算

33、法输入半径输入半径R输出输出 S S、L L的值的值*R*R S2*R L例：求给定半径例：求给定半径R R的圆面积和圆周长的圆面积和圆周长开始开始输出输出 S S、L L的值的值结束结束输入半径输入半径R*R*R S2*R L顺序顺序开始开始输出输出 S S的值的值结束结束输入输入RR S-R SR0YN选择选择输入输入R输出输出 S S的值的值R S - R S Y R 0 N例：求给定数例：求给定数R R的绝对值的绝对值例例: : 给定给定K K值，求值，求T=1+2+3+T=1+2+3+K+K开始开始输出输出 T T 的值的值结束结束输入输入KT+I TI+1 IIKYN1I，0 T循

34、循环环输入输入K输出输出 T T 的值的值IK 1 1I，0 TT+I TI+1 I 伪代码是算法的一种类似英语的表示法。伪代码是算法的一种类似英语的表示法。它是部分英语和部分结构化代码的组合。它是部分英语和部分结构化代码的组合。英文代码部分采用不严格的语法，很容英文代码部分采用不严格的语法，很容易看懂；易看懂；代码部分包含基本算法结构（顺序、选代码部分包含基本算法结构（顺序、选择和循环）的扩展形式。择和循环）的扩展形式。 目前还没有伪代码的标准。目前还没有伪代码的标准。3. 3. 伪代码伪代码伪代码描述算法的一般组成：伪代码描述算法的一般组成：算法头：算法头：算法的名字。算法的名字。目的、条

35、件和返回值：目的、条件和返回值： 目的目的：有关算法要做什么的简短说明：有关算法要做什么的简短说明 前置条件前置条件：列出算法所有前驱条件：列出算法所有前驱条件 后置条件后置条件：指出算法产生的影响：指出算法产生的影响 返回值返回值：算法返回的结果或无返回值：算法返回的结果或无返回值语句序号：语句序号：表示语句之间的附属关系。表示语句之间的附属关系。例：用伪代码描述在一例：用伪代码描述在一数列中找最小值的算法数列中找最小值的算法Algorithm Algorithm （算法）：（算法）：Finding SmallestFinding SmallestPurposePurpose（目的）：（目的

36、）：在一数列中找最小值在一数列中找最小值PrePre（前置条件）：（前置条件）：List of numbersList of numbers（数列）（数列）PostPost（后置条件）：（后置条件）：NoneNoneReturnReturn（返回值）：（返回值）：The smallestThe smallest32416a:S3 2 1算法：算法：设数列中第一个数为最设数列中第一个数为最小值小值S S，然后用后续数依次与，然后用后续数依次与S S比较，若比比较，若比S S小，则用该数替换小，则用该数替换原原S S的值，全部比较完成后的值，全部比较完成后S S即即最小值。最小值。1.Set sm

37、allest to the first number1.Set smallest to the first number2.Loop(not end of list)2.Loop(not end of list) 2.1 if(next number smallest)2.1 if(next number smallest) 2.1.1 set smallest to next2.1.1 set smallest to next number number 2.2 end if2.2 end if3. end loop3. end loop4. return smallest4. return

38、 smallestEnd Finding SmallestEnd Finding Smallest数列数列ai(i=1,5)a1 S, 2 ii 5Y aiS Nai S i+1i返回最小值返回最小值S1. 1. 数列数列ai ( i=1,5 )2.2. a1 S, 2 i3. while(i3. while(i5) ) 3.1 if if( (aiS ) then ai S endif 3.2 i+1i end while end while 4.4. return Sreturn S伪代码不一定按上述严格的格式，且可以伪代码不一定按上述严格的格式，且可以使用汉字，只要把算法表达清楚即可。使

39、用汉字，只要把算法表达清楚即可。数列数列ai(i=1,5)a1 S, 2 ii 5Y aiS Nai S i+1i返回最小值返回最小值Ss=a1; i=2;while(iwhile(i=5) ) if( if(ais ) s = ai; i= i+1; return s;return s;数列数列ai(i=1,5)a1 S, 2 ii 5Y aiS Nai S i+1i返回最小值返回最小值S4. 4. 计算机语言计算机语言 计数计数 累加累加 值交换值交换 求最大（小）值求最大（小）值 穷举穷举 迭代迭代 递推递推 递归递归基本思想基本思想首先根据问题的部分条件预估计出答案的范围首先根据问题的

40、部分条件预估计出答案的范围在预估计的答案范围内，对所有可能的情况逐在预估计的答案范围内，对所有可能的情况逐一验证。一验证。若某个情况使验证符合题目的全部条件，则该若某个情况使验证符合题目的全部条件，则该情况是本题目的一个答案。情况是本题目的一个答案。分析：分析： 假设假设a,ba,b分别代表父亲和儿子的年龄，分别代表父亲和儿子的年龄，x x年后年后a=2ba=2b。根据人的寿命，根据人的寿命，x x取值为：取值为：1,2,1,2,150,150 问题问题：父亲今年：父亲今年3030岁，儿子今年岁，儿子今年6 6岁，在父亲有生之岁，在父亲有生之年中，多少年后父亲的年龄是儿子的年中，多少年后父亲的

41、年龄是儿子的2 2倍？倍？算法：算法：1. 1. 考察考察x x可能的范围：可能的范围：x=1x=1，2 2，150150；2. 30+x2. 30+xa a, 6+x, 6+xb b3. 3. 若若a=2ba=2b，则输出，则输出x x。开始开始结束结束输出输出a,b,xa,b,xx+1 xx150YN0 xa =2bYN30+x a6+x bX X年后，父亲年后，父亲和儿子的年龄和儿子的年龄105分析：分析： 对对5 5本书从本书从1 1至至5 5编号，假设编号，假设a,ba,b两个人分别借这两个人分别借这5 5本本书中的书中的1 1本。当本。当a=ia=i时，表示时，表示a a借了编号为

42、借了编号为i i的书。的书。则则a a、b b的取值范围为：的取值范围为：1 = 1 = a a、b= 5b= 5 当当2 2个人所借的书的编号不相同时（个人所借的书的编号不相同时（a!=ba!=b） ，就是满足题意的一种借阅方法。就是满足题意的一种借阅方法。问题问题：小明有：小明有5 5本新书，要借给、两位小朋友，本新书，要借给、两位小朋友，若每人每次只能借一本，则可有多少种不同的借法？若每人每次只能借一本，则可有多少种不同的借法？算法：算法：1.1.考察考察a a可能的范围：可能的范围：a=1a=1，2 2，3 3，4 4，5 5；2.2.考察考察b b可能的范围：可能的范围：b=1b=1，2 2，3 3，4 4，5;5;3.3.验证验证a,ba,b的所有取值，若的所有取值，若a!=ba!=b，则输出，则输出a,ba,b。开始开始结束结束a+1 aa5YN1a输出输出a,ba,bb+1 bb5YN1 ba bYN