📄 9.6.5.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>
<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.5b.htm'" ></td>
</tr>
</table>
</BODY>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -