算法分析与设计[基本检索与周游方法].pptVIP

第五章 基本检索与周游方法 一般方法 许多问题的解法涉及到对二元树、树和图的处理。这种处理往拄要求我们确定满足某一性质的那些给定数据对象中的一个结点或结点子集。 这通常在数据对象中以检索的方式来进行。 当这种检索必须包括对检索的数据对象的每一个结点进行检查时就把它称之为周游。 代码优化 编译程序的作用是,把高级语言程序翻译成一个等效的机器语言程序。 假定有一个模型机A，其只有一个累加器寄存器。 讨论只限于四个双目运算符：+、-、*、/ 相应的汇编语言指令：LOAD X 将内存单元X的内容装入累加器。STORE X 将累加器的内容不得存入内存X单无。OP X OP可以是ADD，SUB，MPY或DIV。 例1 相关定义 定义5.1 表达式E翻译成某给定机器的机器语言或汇编语言是最优的，当且仅当这一翻译有最少的指令条数。 定义5.2 运算符的交换律。 定义5.3 运算符的分配律。 定义5.4 运算符的结合律。 例2 例3 例4 怎样获取最优代码段？ 首先将讨论局限于模型机A。然后，再考察更一般的机器模型。 用二叉树表示算术表达式，非叶子结点表示一个运算符，称为内部结点。叶子结点或者表示一个变量或者表示一个常数。这样的二叉树称为表达式树。 假定所有的运算符既不可交换，也不可分配或结合。 易于证明在任何没有冗余指令的代码段中，除了第一条以外的每条装入指令都必须紧接在一条存放指令之后。因此，装入指令数总比存放指令数多1。所以只要产生使装入指令数或存放指令数为最小值的代码段就是最优的代码。 表达式树 计算L⊙R 生成代码段的算法CODE1 procedure CODE1(T) if T是叶子 then print (“LOAD”,DATA(T)) return endif F=0 //如果RCHILD（T）不是叶子，则将F置成1 if RCHILD(T) 不是叶子 then call CODE1(RCHILD(T)) //生成CR call TEMP(i); print(“STORE”, i); F=1 endif call CODE1(LCHILD(T)) //生成CL if F=1 then print(DATA(T),i) call RETEMP(i) else print(DATA(T),DATA(RCHILD(T))) endif end CODE1 例5 更一般的情况 现将机器A推广到另一种机器B。B有N?1个可以执行算术运算的寄存器。 对于B，有四种类型的机器指令：（1）LOAD M，R（2）STORE R，M（3）OP R1，M，R2（4）OP R1，R2，R3 例 6 如何在机器B上生成最优代码段 给定一个表达式E1、不用任何STORE指令可以算出E的值吗？2、不用任何STORE指令而计算E的值所需要寄存器的最小数量是多少？ 第一个问题答案是肯定的。 下面讨论第二个问题。 函数MR(P)的定义 例 7 机器B的代码生成器 line procedure CODE2(T,i) if T是叶子 then print(‘LOAD’,DATA(T),’R’,i) return endif L=LCHILD(T); R=RCHILD(T) case :MR(R)=0: //R是叶子// call CODE2(L,i) print(DATA(T),’R’,i,’,’,DATA(R),’,R’,i) :MR(L)=N and MR(R)=N: call CODE2(R,i) call TEMP(S) print(‘STORE’,’R’,i,’,’,S) call CODE2(L,i) print(DATA(T),’R’,i,’,’,S,’R’,i) call RETEMP(S) 例 8 定理5.8 对每一棵表达式树T， CODE2都生成正确的代码段。 定义5.5 已知寄存器数目为N，如果一个结点的两个儿子的MR值都至少为N，则称该结点为大结点(major)。 如果一个结点是没有父亲的叶子，或者是它父亲的左儿子叶子，则称该结点为小结点(minor)。 引理5.1 设n是表达式树T中的大结点数。当表达式树T没有可交换的运算符且在运算符和运算量之间不存在任何关系（即