ds7.2.2.htm

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

<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF"><b><font size="5">&nbsp; 
EdgeNode<span style="mso-spacerun: yes">&nbsp; </span>* firstedge;<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
</span></font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">边表头指针</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF"><b><font size="5">}VertexNode;<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span></font></b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span lang="EN-US">typedef 
VertexNode AdjList[MaxV];<span style="mso-spacerun:
yes">&nbsp; </span></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*AdjList</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">是邻接表类型</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/</span></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF"><b><font size="5">typedef 
struct{<span style="mso-spacerun: yes">&nbsp;</span></font></b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span lang="EN-US">&nbsp; 
AdjList adjlist;<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><span style="mso-spacerun: yes">&nbsp;</span>/*</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">邻接表</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/</span></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF"><b><font size="5">&nbsp; 
int n,e;<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
</span></font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">顶点数和边数</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF"><b><font size="5">}</font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">ALGraph</span><span lang="EN-US">;<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
</span></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*ALGraph</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">是以邻接表方式存储的图类型</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font color="#FFFFFF"><b><font size="5"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
</o:p>
</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">建立一个有向图的邻接表存储的算法如下：</span></b></font></p>
<p class="MsoPlainText" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;"><font size="5" color="#FFFFFF"><b>void 
CreateALGraph(ALGraph *G)<o:p>
</o:p>
</b></font></span></p>
<p class="MsoPlainText" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;"><font color="#FFFFFF"><b><font size="5">{</font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman">/*</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">建立有向图的邻接表存储</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman">*/</span><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;"><o:p>
</o:p>
</span></font></b></font></p>
<p class="MsoPlainText" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;"><font color="#FFFFFF"><b><font size="5">&nbsp; 
int i,j,k;<o:p>
</o:p>
</font></b></font></span></p>
<p class="MsoPlainText" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;"><font color="#FFFFFF"><b><font size="5">&nbsp; 
EdgeNode * s;<o:p>
</o:p>
</font></b></font></span></p>
<p class="MsoPlainText" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;"><font color="#FFFFFF"><b><font size="5">&nbsp; 
printf(&quot;</font></b></font></span><font color="#FFFFFF"><b><span style="mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;"><font size="4">请输入顶点数和边数</font></span><font size="4"><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;">(</span><span style="mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">输入格式为</span><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;">:</span><span style="mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">顶点数</span><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;">,</span><span style="mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">边数</span></font><font size="5"><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;">)</span><span style="mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">：</span><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;">\n&quot;);<o:p>
</o:p>
</span></font></b></font></p>
<p class="MsoPlainText" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;"><font color="#FFFFFF"><b><font size="5">&nbsp; 
scanf(&quot;%d,%d&quot;,&amp;(G-&gt;n),&amp;(G-&gt;e));<span style="mso-spacerun: yes">&nbsp; 
</span></font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman">/*</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"></span></font><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font size="4">读入顶点数和边数</font></span><font size="5"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman">*/</span><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;"><o:p>
</o:p>
</span></font></b></font></p>
<p class="MsoPlainText" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US" style="font-family:&quot;Times New Roman&quot;"><font color="#FFFFFF"><b><font size="5">&nbsp;