信息学奥赛辅导资料 (3)

niorder(bt^.rchild);] end;

5.3.3 后序遍历

后序遍历运算：即先后序遍历左子树，然后再后序遍历右子树，最后访问根结点。后序

遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。例如：

按后序遍历此二叉树的结果为：Welecome to use it! proc postorder(bt:bitreprtr) if (bt<>null)[

postorder(bt^.lchild); postorder(bt^.rchild);] print(bt^); end;

图?

??? 图的定义和术语

图是一种数据结构，它的形式化定义为 Graph=（v，r）

其中 V={ x|x<

VR={ | P( x,y )^( x,y <

在图中的数据元素通常称作顶点 （vertex），V是顶点的有穷非空集合,VR是两个顶点之间的关系的集合。若< 表示从x 到y 的一条弧(arc),且称x为弧尾(tail)或初始点(initial node)称Y为弧头（head）或终端点（TERMINAL NODE） 此时的图称为有向图（DIGRAPH）。若〈X，Y 〉〈〈VR必有〈Y，X〉〈〈VR，即VR是对称的，则一无序对（X，Y）代替这两个有序对表示X和Y之间的一条边〈EDGE此时的图称为无向图（UNDIGRPAH）。例如图7。1（A）中 G1是有向图,-定义此图的谓词P(X,Y)则表示从X到Y的一条单向通路.例如图7.1(A)中G1是有向图,定义此图的谓词P(X,Y)则表示从X到Y的一条单向通路.

G1=(V1,{A1}) 其中: V1={V1,V2,V3,V4}

A1={(,,,)}

10

图7.1(B)中G2为无向图。

G2=(V2{E2}) 其中V2={V1,V2,V3,V4,V5}

E2={(V1,V2),(V1,V4)(V2,V3),(V2,V5)(V3,V4),(V3,V5)}

我们用N 表示图中顶点数目,用E表示边或弧的数目.在下面的讨论中我们不考顶点到其自身的弧或边,即若<

有时图的边或弧具有与它相关的数,这种与图的边或弧相关的数叫做权(weight).这些全可以表示从一个顶点到另一个顶点的距离或耗费.这种带权的图通常称为网(subgraph)

6.2 图的存储结构 ??????数组表示法

用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。其形式定义如下：

const vtxnum=...，{图的顶点数} type vtxptr=1..vtxnum；bit=0..1 vertex=record

...{和顶点相关的信息} end; arc=record

adj:bit;{表示两个顶点之间是否存在关系} ... {和弧(或边)相关的其它信息} end; graph=record

vexs:array[vtxptr]of vertex; arcs:array[vtxptr,vtxptr]ofarc end;

若图中顶点只有1至vtxnum的编号，弧(或边)上亦无权及其它相关信息,则只要以一个二维数组表示图的邻接矩阵即可,此时的存储结构可简单说明如下: type adjmatrix=arrayvtxptr，vtxptr]of bit；

11

????? 邻接表

邻接表（adhacency）是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。

若无向图中有n个顶点，e条边，则它的邻接表需n个头结点和2e个表结点。

在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数；而在有向图中，第i个链表中的结点个数只是顶点vi的出度。

????? 邻接多重表

邻接多重表是无向图的另一种链式存储结构。

其中，mark为标志域，可用以标记该条边是否被搜索过；ivex和jvex为该条边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点

12

jvex的边。每一个顶点也用一个结点表示，它由如下所示的两个域组成：

其中，data域存储和该顶点相关的信息，firstedge域知识第一条依附于该顶点的边。 邻接多重表的类型说明如下： TYPE edgeptr=↑enode； enode=RECORD

mark：0..1;

ivex,jvex:vtxptr; ilink,jlink:edgeptr; END; vexnode=RECORD

data:vertextype; firstedge:edgeptr; END;

adjmulist=ARRAY[vxtptr] OF vexnode;

动态规划

一、动态规划的基本思想：

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 二、设计动态规划法的步骤：

1、找出最优解的性质，并刻画其结构特征；

13

2、递归地定义最优值（写出动态规划方程）； 3、以自底向上的方式计算出最优值；

4、根据计算最优值时得到的信息，构造一个最优解。

步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。

三、动态规划问题的特征：

动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。

1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。 四、习题： 1、防卫导弹：

问题描述：一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型 防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一： 1、它是该次测试中第一个被防卫导弹截击的导弹； 2、它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。 输入格式：从当前目录下的文本文件\读入数据 。该文 件的第一行是一个整数N（0〈=N〈=4000），表示本次测试中，发射的进攻导弹数，以下N行每行各有一个整数hi（0〈=hi〈=32767），表示第i个进攻导弹的高度。文件中各行的行首、行末无多余空格，输入文件中给出的导弹是按发射顺序排列的。

输出格式：答案输出到当前目录下的文本文件\中，该文件第一行是一个整数max，表示最多能截击的进攻导弹数，以下的max行每行各有一个整数，表示各个被截击的进攻导弹的编号（按被截击的先后顺序排列）。输出的答案可能不唯一，只要输出其中任一解即可。

输入输出举例：

输入文件：CATCHER.DAT 3 25 36 23

输出文件：CATCHER.OUT 2 1 3

14

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新IT计算机信息学奥赛辅导资料 (3)全文阅读和word下载服务。