ds7.5.1.htm

这是清华大学所用的数据结构的电子版教材

<p align="center" style="margin-top: 0"><b><font size="5" color="#FFFFFF"><span style="text-shadow: auto; layout-flow: vertical"><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">1</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">2</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">3</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">4</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">5</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">6</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">8</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">9</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">7</span><span lang="EN-US" style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN"><br>
</span><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">&nbsp; 
或</span><span style="mso-spacerun: yes; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">&nbsp; 
</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN">C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">1</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">8</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">9</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">2 
</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN">, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">5</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">3 
</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN">, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">4</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">7</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 2; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">6</span></span></font></b></p>
<p align="center"><img border="0" src="ds7.5.5.gif" width="536" height="295"></p>
<p align="center">　</p>
<p><b><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5" color="#FFFF00">进行拓扑排序的方法</font></b></p>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff">
<p></font><b><font color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">1.输入</font><font SIZE="5">AOV</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">网络。令</font><font SIZE="5"> 
n </font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">为顶点个数。</font></font></b><font FACE="Times New Roman" SIZE="5" COLOR="#0000ff"></p>
<p></font><font color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">2.在</font><font SIZE="5">AOV</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">网络中选一个没有直接前驱的顶点</font><font SIZE="5">, 
</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">并输出之</font><font SIZE="5">;</font></b></font></p>
<p><font color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">3.从图中删去该顶点</font><font SIZE="5">, 
</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">同时删去所有它发出的有向边</font><font SIZE="5">;</font></b></font></p>
<p><font color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">4.重复以上</font><font SIZE="5"> 
</font><font FACE="楷体_GB2312" LANG="ZH-CN" color="#FFFFFF" size="5">2、3</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5"> 
步</font><font SIZE="5">, </font></b><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5"><b>直到</b></font></font><b><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5" color="#FFFFFF">全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或</font></b><font color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时</font><font SIZE="5">AOV</font></b><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5"><b>网络中必定存在有向环。</b></font></font></p>
<p><b><font color="#FFFF00" size="5"><span style="font-family: 楷体_GB2312; mso-ascii-font-family: Arial Narrow; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Arial Narrow; text-shadow: auto; layout-flow: vertical; mso-color-index: 3">拓扑排序的过程</span></font></b></p>
<p align="center"><img border="0" src="ds7.5.6.gif" width="1119" height="400"></p>
<p align="left"><font color="#FFFFFF" size="5"><b><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">&nbsp;&nbsp;