📄 9.6.5b.htm

📁 建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术
💻 HTM
字号:
<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.5.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>
<table>
<tr>
<td>&nbsp&nbsp&nbsp&nbsp</td>
<td class="content">
<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>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">procedure</font> search(n)； </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">begin</font> </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(1)&nbsp;&nbsp;&nbsp;&nbsp;标记n为“已访问”； </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(2)&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">for</font> n的每个后续s
<font color="#0000FF">do</font>； </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(3)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">if</font> s是“未访问”
<font color="#0000FF">then</font><b> </b><font color="#0000FF">begin</font> </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(4)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;把边n→s加到T； </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(5)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;search(s) </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">end</font> </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(6)&nbsp;&nbsp;&nbsp;&nbsp;dfn[n]:=i； </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(7)&nbsp;&nbsp;&nbsp;&nbsp;i:=i-1 </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">end</font> </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000">／* 主程序如下 *／ 
</font> </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(8)&nbsp;T：=empty；<font color="#008000">／* 边的集合 *／</font> </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(9)&nbsp;<font color="#0000FF">for</font> G的每个结点n
<font color="#0000FF">do</font> 标记n为“未访问”; </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(10)&nbsp;i:=G的结点数 ;</p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(11)&nbsp; search(n<span style="vertical-align: sub"><font face="Courier">0</font></span>); </p>
<p>&nbsp;&nbsp;&nbsp;&nbsp;<b>图9.37&nbsp;&nbsp;求流图结点的深度优先次序的算法</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.5.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>

</BODY>
<html><script language="JavaScript">
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -