📄 9.4.1_2.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.4.1.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.4.2.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.4.1 必经节点（续）</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
三、寻找必经结点的算法
<p><font class = "definition">算法9.1 寻找必经结点 </font></p>
<p>输入: 一个流图，其结点集合N，边集合E，初始结点n<sub>0</sub> </p>
<p>输出: 关系 dom </p>
<p>方法: 用下面的过程迭代计算n的必经结点集合D(n)，最终，d在D(n)中当且仅当d dom n。
</p>
<p> (1) D(n<sub>0</sub>) ：={n<sub>0</sub>}； </p>
<p> (2) <font color="#0000FF">for</font> n in (N 一{n<sub>0</sub>})
<font color="#0000FF">do</font> D(n)：=N； </p>
<p> <font color="#008000"> ／*初始化结束*／ </font> </p>
<p> (3) <font color="#0000FF">while</font> 任何D(n)出现变化
<font color="#0000FF">do</font> </p>
<p> (4) <font color="#0000FF">for</font> n in (N一{n<sub>0</sub>})
<font color="#0000FF">do</font> </p>
<p> (5) D(n):={n}∪ ∩ D(p);<br>
<font size="2">p是n的前驱</font> </p>
<p> <b>图9.17 求控制必经结点集D(n)的算法</b></p>
<p><font class = "example">例9.7</font> 使用算法9.1求图9.16（见本页上部）的流图的控制必经结点集D(n)，并假定第(4)行的for循环按结点的数值次序访问。结点2只有结点1作为前驱，所以D(2):={2}U
D(1)。因为1是初始结点，D(1)在第(1)行置为{1}，所以D(2)在第(5)行是集合{1，2}。 </p>
<p>然后考虑结点3，它的前驱有1，2，4和8。第(5)行给出D(3)={3}U({1}∩{1，2}∩{1，2，…，10})={1，3}。剩余的计算是
</p>
<p> D(4)={4}U(D(3)∩D(7))={4}U({1，3}∩{1，2，…，10})<br>
={1，3，4} </p>
<p> D(5)={5}UD(4)={5}U{1，3，4}={1，3，4，5} </p>
<p> D(6)={6}UD(4)={6}U{1，3，4}={1，3，4，6} </p>
<p> D(7)={7}U(D(5)∩D(6)∩D(10))<br>
={7}U({1，3，4，5}∩{1，3，4，6}∩{1，2，…，10}）<br>
={1，3，4，7} </p>
<p> D(8)={8}UD(7)={8}U{1，3，4，7}={1，3，4，7，8} </p>
<p> D(9)={9}UD(8)={9}U{l，3,4，7，8}={1，3，4，7，8，9} </p>
<p> D(10)={10}UD(8)={10}U{1，3，4，7，8}<br>
={1，3，4，7，8，10} </p>
<p>通过while循环的第二遍扫描没有产生改变，所以上面的值就是关系dom。 </td>
</p>
</td>
</tr>
</table>
<br>
<table align=right width=300>
<tr>
<td>
<img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.4.1.htm'" ></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.4.2.htm'" ></td>
</tr>
</table>
</BODY>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -