xtjd5.htm

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

&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;while(B.data[pb]==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"'>B</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=B.data[pb].j;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;C.data[pc].e=B.data[pb].e;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pb++;pc++;<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;}//for<br>
&nbsp;&nbsp;C.tu=pc;<br>
}//TSMatrix_Add <o:p></o:p></span></p>

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

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>typedef
struct{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>&nbsp;int j;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int
e;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
DSElem; <o:p></o:p></span></p>

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>typedef
struct{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;DSElem
data[MAXSIZE];<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int
cpot[MAXROW];//</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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int
mu,nu,tu;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
DSMatrix; //</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><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>Status
DSMatrix_Locate(DSMatrix A,int i,int j,int &amp;e)//</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[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"'>e<br>
{<br>
&nbsp;&nbsp;for(s=cpot[i];s&lt;cpot[i+1]&amp;&amp;A.data[s].j!=j;s++);//</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;if(A.data[s].i==i&amp;&amp;A.data[s].j==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"'>A[i][j]<br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;e=A.data[s];<br>
&nbsp;&nbsp;&nbsp;&nbsp;return OK;<br>
&nbsp;&nbsp;}<br>
&nbsp;&nbsp;return ERROR;<br>
}//DSMatrix_Locate <o:p></o:p></span></p>

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

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>typedef
struct{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>&nbsp;int seq; //</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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>&nbsp;int e;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>&nbsp;} SElem; <o:p></o:p></span></p>

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>typedef
struct{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>SElem data[MAXSIZE];<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span
style="mso-spacerun: yes">&nbsp;&nbsp; </span><span style="mso-spacerun:
yes">&nbsp;</span>&nbsp;&nbsp;&nbsp;int mu,nu,tu;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>&nbsp;} SMatrix; //</span><span