xtjd5.htm

严蔚民版的数据结构的完整课件

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"'>n</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"'>k</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"'>p</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
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"'>A[0],A[1],...A[p-1]</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
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
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
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"'>,A</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"'>p</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"'>&quot;</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"'>&quot;</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
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"'>:<br>
n=15,k=6,</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"'>p=3.<br>
</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"'>:A[0]-&gt;A[6],A[6]-&gt;A[12],A[12]-&gt;A[3],A[3]-&gt;A[9],A[9]-&gt;A[0].<br>
</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"'>:A[1]-&gt;A[7],A[7]-&gt;A[13],A[13]-&gt;A[4],A[4]-&gt;A[10],A[10]-&gt;A[1].<br>
</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"'>:A[2]-&gt;A[8],A[8]-&gt;A[14],A[14]-&gt;A[5],A[5]-&gt;A[11],A[11]-&gt;A[2].<br>
</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"'>.<br>
</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
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"'>. <o:p></o:p></span></p>

<p style='mso-outline-level:1'><span lang=EN-US style='mso-bidi-font-size:10.0pt;
font-family:"Times New Roman"'>5.19 <o:p></o:p></span></p>

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>void
Get_Saddle(int A[m][n])//</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"'>A</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"'><br>
{<br>
&nbsp;&nbsp;for(i=0;i&lt;m;i++)<br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;for(min=A[i][0],j=0;j&lt;n;j++)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(A[i][j]&lt;min) min=A[i][j]; //</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"'><br>
&nbsp;&nbsp;&nbsp;&nbsp;for(j=0;j&lt;n;j++)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(A[i][j]==min) //</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
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
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"'><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(flag=1,k=0;k&lt;m;k++)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(min&lt;A[k][j])
flag=0;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(flag)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;Found
a saddle element!\nA[%d][%d]=%d&quot;,i,j,A[i][j]);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;}//for<br>
}//Get_Saddle <o:p></o:p></span></p>

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>5.20<br>
</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
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
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
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"'>m</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
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
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
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
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
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
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"'>visited</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"'>. <o:p></o:p></span></p>

<p style='mso-outline-level:1'><span lang=EN-US style='mso-bidi-font-size:10.0pt;
font-family:"Times New Roman"'>5.21 <o:p></o:p></span></p>

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>void
TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &amp;C)//</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"'><br>
{<br>
&nbsp;&nbsp;C.mu=A.mu;C.nu=A.nu;C.tu=0;<br>
&nbsp;&nbsp;pa=1;pb=1;pc=1;<br>
&nbsp;&nbsp;for(x=1;x&lt;=A.mu;x++) //</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"'><br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;while(A.data[pa].i&lt;x) pa++;<br>
&nbsp;&nbsp;&nbsp;&nbsp;while(B.data[pb].i&lt;x) pb++;<br>
&nbsp;&nbsp;&nbsp;&nbsp;while(A.data[pa].i==x&amp;&amp;B.data[pb].i==x)//</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"'><br>
&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(A.data[pa].j==B.data[pb].j)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ce=A.data[pa].e+B.data[pb].e;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(ce) //</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"'>0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].i=x;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].j=A.data[pa].j;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].e=ce;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pa++;pb++;pc++;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}//if<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else if(A.data[pa].j&gt;B.data[pb].j) <br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].i=x;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].j=B.data[pb].j;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].e=B.data[pb].e;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pb++;pc++;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].i=x;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].j=A.data[pa].j;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].e=A.data[pa].e<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pa++;pc++;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;}//while<br>
&nbsp;&nbsp;&nbsp;&nbsp;while(A.data[pa]==x) //</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"'>A</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
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"'>x</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"'>)<br>
&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].i=x;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].j=A.data[pa].j;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].e=A.data[pa].e<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pa++;pc++;<br>