📄 9.6.5b.htm.bak
字号:
<html>
<head>
<title>编译原理</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>
<BODY>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.4.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.6.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.6.5 流图结点的深度优先次序</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>流图结点的一个有用次序是<font class = "definition2">深度优先</font>次序，它是树的深度优先遍历的推广。深度优先次序可用于查找流图中的循环，可加快本节所讨论的数据流分析迭代算法的速度。深度优先次序从初始结点开始，搜索整个流图，尽可能快地访问远离初始结点的结点，(深度优先)搜索的路线形成树。
<p>
<font class = "example">例9.26</font>如图9.36所示的左侧流图深度优先搜索的一种可能次序显示在其右侧图中。实线边形成树，虚线边是流图的其它边。流图的深度优先搜索对应树的前序遍历，1→3→4→6→7→8→10，然后回到8进入9。再次回到8，后退到7，6和4，然后进入5。从5退到4，回到3和1，从1走到2，最后从2退回1，按前序遍历了整个树。
</p>
<p>结点的<font class = "definition2">深度优先次序</font>是前序遍历的结点序列中最后访问的结点次序的逆。<br>
</td>
</tr>
</table>
<p align=center>
<img src="images/9.36a.gif"></p>
<table>
<tr>
<td>    </td>
<td class="content">
遍历该树时结点访问的完整次序是
<p> l，3，4，6，7，8，10，8，9，8，7，6，4，5，4，3，1，2，1 </p>
<p>在该表中，标记每个数的最后出现，得到 </p>
<p> 1，3，4，6，7，8，<u>10</u>，8，<u>9</u>，<u>8</u>，<u>7</u>，<u>6</u>，4，<u>5</u>，<u>4</u>，<u>3</u>，1，<u>2</u>，<u>1</u>
</p>
<p>深度优先次序是上面序列中被标记数的逆序序列，这里该序列正好是1，2，…，10，即最初这些结点是按深度优先次序编号的。 </p>
<p>现在我们给出计算流图深度优先次序的算法。它构造和遍历初始结点为根的树，试图使树中的路径尽可能长。这样的树叫做<font class = "definition2">深度优先扩展树(dfst)</font>。图9.36右边图所示的深度优先扩展树就是用此算法从左边流图构造出来的。
</p>
<p><font class="definition">算法9.6 深度优先扩展树和深度优先次序 </font></p>
<p>输入: 一个流图G 。</p>
<p>输出: G的dfst T和G的一个深度优先结点次序。 </p>
<p>方法: 下面的算法中search(n)是一个递归过程，该算法先置G的所有结点为“未访问”，然后调用search(n<sub>0</sub>)，其中n<sub>0</sub>是初始结点。当调用search(n)时,首先标记n为“已访问”，以避免把n加入扩展树两次,用i计数，随着逐步前进，i从G的结点个数降到1，把深度优先编号dfn[n]赋给结点n,边的集合T形成G的dfst，称它们为<font class = "definition2">树边</font>。
</p>
<p> <font color="#0000FF">procedure</font> search(n)； </p>
<p> <font color="#0000FF">begin</font> </p>
<p> (1) 标记n为“已访问”； </p>
<p> (2) <font color="#0000FF">for</font> n的每个后续s
<font color="#0000FF">do</font>； </p>
<p> (3) <font color="#0000FF">if</font> s是“未访问”
<font color="#0000FF">then</font><b> </b><font color="#0000FF">begin</font> </p>
<p> (4) 把边n→s加到T； </p>
<p> (5) search(s) </p>
<p> <font color="#0000FF">end</font> </p>
<p> (6) dfn[n]:=i； </p>
<p> (7) i:=i-1 </p>
<p> <font color="#0000FF">end</font> </p>
<p> <font color="#008000">／* 主程序如下 *／
</font> </p>
<p> (8) T：=empty；<font color="#008000">／* 边的集合 *／</font> </p>
<p> (9) <font color="#0000FF">for</font> G的每个结点n
<font color="#0000FF">do</font> 标记n为“未访问”; </p>
<p> (10) i:=G的结点数 ;</p>
<p> (11) search(n<span style="vertical-align: sub"><font face="Courier">0</font></span>); </p>
<p> <b>图9.37 求流图结点的深度优先次序的算法</b></p><br>
<table align=right width=300>
<tr>
<td>
<img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.4.htm'" ></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.6.htm'" ></td>
</tr>
</table>
</BODY>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -