数据结构与算法 第3版 教学课件 作者 张小莉第8章 扩展应用举例

第8章扩展应用举例2023/2/201.教学内容求最大子段和、表达式树的构造、由等价关系求划分2.教学目的

理解穷举的思想，能够应用穷举思想设计算法以及进行算法分析的。理解分治策略的思想，以及分治与递归的关系；并能举出在数据结构课程中应用分治策略的算法。理解动态规划策略的思想，以及其求解过程与分治策略的不同之处。理解表达式与二叉树的对应关系；巩固对字符串、栈和二叉树存储和遍历知识的掌握。掌握用树表示集合的方法，理解其便利之处和存在的问题与解决思路。3.教学重点

穷举法、分治策略和动态规划策略在算法设计中的应用。表达式与二叉树的对应关系。采用树结构表达集合的应用。4.教学难点

动态规划的策略思想2023/2/208.1求最大子段和问题的描述

给定有n个整数(可能为负整数)组成的序列a1,a2,...,an，求该序列连续的子段和的最大值；如果这个最大值是负整数，则定义其最大子段和为0。即根据下面的公式进行求解。

例如：

(a1,a2,a3,a4,a5)=(-5,11,-4,13,-4-2)

最大子段和为11+(-4)+13=20。2023/2/20问题分析与解决1．数据的存储

这个应用要处理的数据是线性结构，由于要对不确定长度的数据进行求和，因此采用顺序存储比较方便，这里用一维数组List存放数据，每个数据元素为整型。

2．简单穷举法【算法8-1】简单穷举法求解最大子段和2023/2/203．改进的穷举法

通过分析，可以看到，从位置i到位置j的子列和等于从位置i到位置j－1的子列和加上List[j]，即

2023/2/204．分治法

所谓分治法就是将一个难以解决的问题拆分成若干小问题或规模较小的相同问题，分别解决后原问题便得到解决，即所谓各个击破分而治之。本问题采用的是类似归并排序的递归算法的拆分方法，简要描述如下。步骤1：将所给序列List[0]~List[n-1]分为两段List[0]~List[n/2-1]和List[n/2]~List[n-1]；步骤2：分别递归求得两段的最大子列和MaxLeftSum和MaxRightSum；步骤3：从中分点分别向左、右两边扫描，找出中间跨分界线的最大子列和MaxMidSum；步骤4：MaxSum＝max{MaxLeftSum，MaxMidSum，MaxRightSum}。2023/2/202023/2/205．动态规划法

动态规划方法是一种自底向上的求解方法，即根据得到的递归式，按照递归返回的顺序计算所要求的值。从上述基于分治思想的求解分析中可看出，若记则所求的最大子段和为：由b[j]的定义知，当b[j－1]>0时，b[j]=b[j－1]＋a[j]，否则b[j]=a[j]。由此可得计算b[j]的动态规划递归式：2023/2/202023/2/20问题描述可以用二叉树的形式表示表达式，这样就可以通过对二叉树的遍历完成表达式的计算，那么如何将一串字符构成的算术表达式转换为二叉树形式的存储就是首先要解决的问题。假设一串字符构成的算术表达式是仅含有二目运算的前缀、中缀和后缀表达式，考虑如何将它们转换成二叉树的表示形式。

8.2表达式树的构造2023/2/20问题分析与解决

本问题的输入数据是一串字符，在转换过程中，该串字符不需要改变，只需要顺次读取，因此可采用一维字符数组存储。本问题的输出是棵二叉树，二叉树中每个结点的数据域为一个运算对象或运算符。将顺序存储的前缀表达式转换为表达式的二叉树存储时，需要借助一个栈空间帮助实现，用于暂存构造二叉树存储过程中形成的子树的根结点。2023/2/201．顺序存储的前缀表达式转换为表达式的二叉树存储

步骤1：读取表达式串的第一个字符。

步骤2：如果当前读入的字符是运算符，则将其作为单个结点构造一棵二叉树，并将这棵二叉树结点压入堆栈。步骤3：如果当前读入的字符是运算对象，则将其作为单个结点构造一棵二叉树，然后读取栈顶元素，根据如下判断进行处理：

如果当前栈顶元素为运算符结点，则将构造的运算对象结点二叉树入栈；

如果当前栈顶元素为运算对象结点，则弹出栈顶的前两个元素，第二个弹出的结点必为运算符结点，将弹出的第一个结点和构造的结点分别作为运算符结点的左子树和右子树，此时形成了一棵以运算符结点为根的二叉树，再准备将该二叉树的根结点作为运算对象入栈，回到步骤3开始处继续。

步骤4：若表达式串未读完，读取表达式串的下一个字符，回到步骤2继续处理；若表达式串已读完，则当前栈顶元素的值为二叉树存储表达式的根结点，弹出并返回之即可。

2023/2/20例如，将前缀表达式串－*3^2－＋4*22*135构造成表达式的二叉树存储过程如图8-1所示，图中在的堆栈中画出的标记“1”的子树，是指当前得到的子树，它还没有入栈，需要根据情况执行入栈或从栈中弹出元素，构成新的子树。

2023/2/20

2023/2/202．顺序存储的中缀表达式转换为表达式的二叉树存储

步骤1：读取表达式串的第一个字符。

步骤2：如果当前读入的字符是运算对象，则将其作为单个结点构造一棵二叉树，并将这棵二叉树结点压入子树栈。

步骤3：如果当前读入的字符是运算符，则将其作为单个结点构造一棵二叉树，然后读取运算符栈顶元素，根据如下判断进行处理：

如果当前运算符栈的栈顶结点存储的运算符优先级低于当前构造结点的运算符，则将构造的运算符结点二叉树入运算符栈；

如果当前运算符栈的栈顶结点存储的运算符优先级高于当前构造结点的运算符，则从运算符栈出栈一个结点，以该结点为根构造二叉子树，从子树栈中弹出前两棵子树，分别作为根结点的左孩子和右孩子，然后将新构成的子树入子树栈，回到步骤3开始处，继续处理。

步骤4：若表达式串未读完，读取表达式串的下一个字符，回到步骤2继续处理；若表达式串已读完，则当前栈顶元素的值为二叉树存储表达式的根结点，弹出并返回之即可。2023/2/203．顺序存储的后缀表达式转换为表达式的二叉树存储

步骤1：读取表达式串的第一个字符。

步骤2：如果当前读入的字符是运算对象，则将其作为单个结点构造一棵二叉树，并将这棵二叉树结点压入堆栈。

步骤3：如果当前读入的字符是运算符，则将其作为单个结点构造一棵二叉树，然后弹出栈中的前两个元素，将它们分别作为所构造二叉树运算符结点的左子树和右子树，并将这个运算符结点入栈。

步骤4：若表达式串未读完，读取表达式串的下一个字符，回到步骤2继续处理；若表达式串已读完，则当前栈顶元素的值为二叉树存储表达式的根结点，弹出并返回之即可。2023/2/20问题描述

已知集合S及其上的等价关系R，求R在S上的一个划分{S1,S2,…,Sn}，其中，S1,S2,…,Sn分别为R的等价类，它们满足：

设集合S中有n个元素，关系R中有m个序偶对。

8.3由等价关系求划分2023/2/20问题分析与解决

集合S上的等价关系R是指由集合S中的元素构成的序偶的集合，且该序偶的集合在S上满足自反的、对称的和可传递的。该问题的输入是m个序偶，输出是若干个子集，处理思路如下。（1）令S中每个元素各自形成一个单元素的子集，记作S1，S2，…，Sn；（2）重复读入m个序偶对，对每个读入的序偶对<x,y>，判定x和y所属子集。不失一般性，假设x∈Si，y∈Sj，若Si≠Sj，则将Si并入Sj，并置Si为空（或将Sj并入Si，并置Sj为空）；若Si＝Sj，则不做什么操作，接着读入下一对序偶。直到m个序偶对都被处理过后，S1，S2，…，Sn中所有非空子集即为S的R等价类，这些等价类的集合即为集合S的一个划分。

2023/2/20

通过前面的分析可知，本算法在实现过程中所用到的基本操作有以下两个。（1）Find(S，x)查找函数。确定集合S中的单元素x所属子集Si，函数的返回值为该子集树根结点在双亲表示法数组中的序号；（2）Union(S，i，j)集合合并函数。将集合S的两个互不相交的子集合并，i和j分别为两个子集用树表示的根结点在双亲表示法数组中的序号。合并时，将一个子集的根结点的双亲域的值由没有双亲改为指向另一个子集的根结点。2023/2/20

下面就本问题的解决算法步骤给出描述：

步骤1：k=1；

步骤2：若k>m则转步骤7，否则转步骤3；

步骤3：读入一序偶对<x,y>；

步骤4：i=Find(S,x)，j=Find(S,y)；

步骤5：若i≠j，则Union(S,i,j)；

步骤6：++k;转步骤2

步骤7：输出结果,结束。2023/2/20算法的时间复杂度：

集合元素的查找算法和不相交集合的合并算法的时间复杂度分别为O(d)和O(1)，其中d是树的深度。这种表示集合的树的深度和树的形成过程有关。

在极端的情况下，每读入一个序偶对，就需要合并一次，即最多进行m次合并，若假设每次合并都是将含成员多的根结点指向含成员少的根结点，则最后得到的集合树的深度为n，而树的深度与查找有关。这样全部操作的时间复杂性可估计为O(mn)。

一般有下述四种策略。2023/2/20第一种策略：

按照输入序偶对的顺序顺次合并。即将序偶对的第一个元素所在的树作为序偶第二个元素所在树的根结点的一棵子树，或将序偶对的第二个元素所在的树作为序偶第一个元素所在树的根结点的一棵子树。

2023/2/20第二种策略：

按照规模合并。即根据树中元素的个数确定合并的方式，如果序偶对的第一个元素所在的树的元素个数不小于序偶第二个元素所在树的元素个数，则将序偶对的第二个元素所在的树作为序偶第一个元素所在树的根结点的一棵子树；否则将序偶对的第一个元素所在的树作为序偶第二个元素所在树的根