da07b.htm

数据结构（cc++)1800例题与答案,值得一看

</SPAN><SPAN style="mso-spacerun: yes">&nbsp;</SPAN><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp;</SPAN><B 
style="mso-bidi-font-weight: normal">else</B> <B 
style="mso-bidi-font-weight: normal">if</B> (visited[p-&gt;adjvex]==0) 
{dfs(g,g-&gt;adjvex); top--; p=p-&gt;next;}//<B 
style="mso-bidi-font-weight: normal">else</B> <B 
style="mso-bidi-font-weight: normal">if</B><o:p></o:p></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 51.5pt; TEXT-INDENT: -79.55pt; mso-char-indent-count: -6.98; mso-para-margin-left: -2.46gd"><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
</SPAN>}//<B 
style="mso-bidi-font-weight: normal">while</B><o:p></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;</SPAN><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp; </SPAN>}//</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">结束算法<SPAN 
lang=EN-US>2<o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">算法<SPAN 
lang=EN-US>3</SPAN>：本题用非递归算法求解。<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp; </SPAN><B 
style="mso-bidi-font-weight: normal">int</B><SPAN 
style="mso-spacerun: yes">&nbsp; </SPAN>Connectij (AdjList g , vertype vi , vj 
)<o:p></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;</SPAN>//</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">判断<SPAN 
lang=EN-US>n</SPAN>个顶点以邻接表表示的有向图<SPAN lang=EN-US>g</SPAN>中，顶点<SPAN lang=EN-US> 
Vi </SPAN>各<SPAN lang=EN-US>Vj </SPAN>是否有路径，有则返回<SPAN 
lang=EN-US>1</SPAN>，否则返回<SPAN lang=EN-US>0</SPAN>。<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">{ <B 
style="mso-bidi-font-weight: normal">for</B> (i=1;i&lt;=n;i++)<SPAN 
style="mso-spacerun: yes">&nbsp; </SPAN>visited[i]=0; //</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">访问标记数组初始化。<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp; </SPAN>i=GraphLocateVertex(g,vi); 
//</SPAN><SPAN style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">顶点定位，不考虑 
<SPAN lang=EN-US>vi</SPAN>或 <SPAN lang=EN-US>vj</SPAN>不在图中的情况。<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp; 
</SPAN>j=GraphLocateVertex(g,vj);<o:p></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp; </SPAN><B 
style="mso-bidi-font-weight: normal">int</B> 
stack[],top=0;stack[++top]=i;<o:p></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp; </SPAN><B 
style="mso-bidi-font-weight: normal">while</B>(top&gt;0)<o:p></o:p></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 17.1pt; mso-para-margin-left: 1.5gd"><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">{k=stack[top--]; 
p=g[k].firstarc;<o:p></o:p></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.9pt; mso-char-indent-count: 2.0"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">while</SPAN></B><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">(p!=null 
&amp;&amp; visited[p-&gt;adjvex]==1) p=p-&gt;next; //</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">查第<SPAN 
lang=EN-US>k</SPAN>个链表中第一个未访问的弧结点。<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 17.1pt; TEXT-INDENT: 0.05pt; mso-para-margin-left: 1.5gd"><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;</SPAN><B 
style="mso-bidi-font-weight: normal">if</B>(p==null) 
top--;<o:p></o:p></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 17.1pt; TEXT-INDENT: 0.05pt; mso-para-margin-left: 1.5gd"><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;</SPAN><B 
style="mso-bidi-font-weight: normal">else</B> 
{i=p-&gt;adjvex;<o:p></o:p></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 56.85pt; mso-char-indent-count: 4.97"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">if</SPAN></B><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">(i==j) <B 
style="mso-bidi-font-weight: normal">return</B>(1); //</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">顶点<SPAN 
lang=EN-US>vi</SPAN>和<SPAN lang=EN-US>vj </SPAN>间有路径。<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 17.1pt; TEXT-INDENT: 42.2pt; mso-char-indent-count: 3.69; mso-para-margin-left: 1.5gd"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">else</SPAN></B><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"> {visited[i]=1; 
stack[++top]=i;}//<B 
style="mso-bidi-font-weight: normal">else</B><o:p></o:p></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 17.1pt; TEXT-INDENT: 33.85pt; mso-char-indent-count: 2.97; mso-para-margin-left: 1.5gd"><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">}//<B 
style="mso-bidi-font-weight: normal">else</B><o:p></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </SPAN>}<B 
style="mso-bidi-font-weight: normal">while</B><o:p></o:p></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.9pt; mso-char-indent-count: 2.0"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">return</SPAN></B><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">(0); } 
//</SPAN><SPAN style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">顶点<SPAN 
lang=EN-US>vi</SPAN>和<SPAN lang=EN-US>vj </SPAN>间无通路。<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">9. <B 
style="mso-bidi-font-weight: normal">void</B> DeletEdge(AdjList g,<B 
style="mso-bidi-font-weight: normal">int</B> i,j)<o:p></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp; </SPAN>//</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">在用邻接表方式存储的无向图<SPAN 
lang=EN-US>g</SPAN>中，删除边<SPAN lang=EN-US>(i,j)<o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN 
lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">{p=g[i].firstarc;<SPAN 
style="mso-spacerun: yes">&nbsp; </SPAN>pre=null; //</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">删顶点<SPAN lang=EN-US>i 
</SPAN>的边结点<SPAN lang=EN-US>(i,j),pre</SPAN>是前驱指针<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 34.2pt; mso-char-indent-count: 2.99"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">while</SPAN></B><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"> 
(p)<o:p></o:p></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 11.4pt; mso-char-indent-count: 1.0"><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp; </SPAN><B 
style="mso-bidi-font-weight: normal">if</B> 
(p-&gt;adjvex==j)<o:p></o:p></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 11.4pt; mso-char-indent-count: 1.0"><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </SPAN>{<B 
style="mso-bidi-font-weight: normal">if</B>(pre==null)g[i].firstarc=p-&gt;next;<B 
style="mso-bidi-font-weight: normal">else</B> 
pre-&gt;next=p-&gt;next;free(p);}//</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">释放结点空间。<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 11.4pt; mso-char-indent-count: 1.0"><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp; </SPAN><B 
style="mso-bidi-font-weight: normal">else</B> {pre=p; p=p-&gt;next;}<SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp; </SPAN>//</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">沿链表继续查找<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal 
style="TEXT-INDENT: 34.1pt; mso-char-indent-count: 2.99"><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">p=g[j].firstarc;<SPAN 
style="mso-spacerun: yes">&nbsp; </SPAN>pre=null; //</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">删顶点<SPAN lang=EN-US>j 
</SPAN>的边结点<SPAN lang=EN-US>(j,i)<o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 34.2pt; mso-char-indent-count: 2.99"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">while</SPAN></B><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"> 
(p)<o:p></o:p></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 11.4pt; mso-char-indent-count: 1.0"><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp; </SPAN><B 
style="mso-bidi-font-weight: normal">if</B> 
(p-&gt;adjvex==i)<o:p></o:p></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 11.4pt; mso-char-indent-count: 1.0"><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </SPAN>{<B 
style="mso-bidi-font-weight: normal">if</B>(pre==null)g[j].firstarc=p-&gt;next;<B 
style="mso-bidi-font-weight: normal">else</B> 
pre-&gt;next=p-&gt;next;free(p);}//</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">释放结点空间。<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 11.4pt; mso-char-indent-count: 1.0"><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp; </SPAN><B 
style="mso-bidi-font-weight: normal">else</B> {pre=p; p=p-&gt;next;}<SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp; </SPAN>//</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">沿链表继续查找<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 11.4pt; mso-char-indent-count: 1.0"><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp; </SPAN>}// 
DeletEdge<o:p></o:p></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN 
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">[</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">算法讨论<SPAN lang=EN-US>] 
</SPAN>算法中假定给的<SPAN lang=EN-US>i</SPAN>，<SPAN lang=EN-US>j 
</SPAN>均存在，否则应检查其合法性。若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标<SPAN 
lang=EN-US>i</SPAN>和<SPAN lang=EN-US>j</SPAN>。<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">10. <B 
style="mso-bidi-font-weight: normal">void</B><SPAN 
style="mso-spacerun: yes">&nbsp; </SPAN>DeleteArc</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">（<SPAN lang=EN-US>AdjList 
g,vertype vi,vj</SPAN>）<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN 
style="mso-spacerun: yes">&nbsp;&nbsp; </SPAN>//</SPAN><SPAN 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">删除以邻接表存储的有向图<SPAN 
lang=EN-US>g</SPAN>的一条弧<SPAN lang=EN-US>&lt;vi,vj&gt;</SPAN>，假定顶点<SPAN 
lang=EN-US>vi</SPAN>和<SPAN lang=EN-US>vj</SPAN>存在<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN 
lang=EN-US 
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">{i=GraphLocateVertex(g,vi); 
j=GraphLocateVertex(g,vj);