xtjd10.htm

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

&nbsp;&nbsp;&nbsp;&nbsp;}<br>
}//Merge_Sort <o:p></o:p></span></p>

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>void
Merge(int a[ ],int s1,int e1,int s2,int e2)//</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[s1]</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[e1]</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[s2]</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[e2]</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[s1]</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[e2]<br>
{<br>
&nbsp;&nbsp;int b[MAXSIZE]; //</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<br>
&nbsp;&nbsp;for(i=s1,j=s2,k=s1;i&lt;=e1&amp;&amp;j&lt;=e2;k++)<br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;if(a[i]&lt;a[j]) b[k]=a[i++];<br>
&nbsp;&nbsp;&nbsp;&nbsp;else b[k]=a[j++];<br>
&nbsp;&nbsp;}<br>
&nbsp;&nbsp;while(i&lt;=e1) b[k++]=a[i++];<br>
&nbsp;&nbsp;while(j&lt;=e2) b[k++]=a[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"'>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"'><br>
&nbsp;&nbsp;for(i=s1;i&lt;=e2;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"'><br>
&nbsp;&nbsp;&nbsp;&nbsp;a[i]=b[i];<br>
}//Merge <o:p></o:p></span></p>

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

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>void
LinkedList_Merge_Sort1(LinkedList &amp;L)//</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(l=1;l&lt;L.length;l*=2) //l</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(p=L-&gt;next,e2=p;p-&gt;next;p=e2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i=1,q=p;i&lt;=l&amp;&amp;q-&gt;next;i++,q=q-&gt;next);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e1=q;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i=1;i&lt;=l&amp;&amp;q-&gt;next;i++,q=q-&gt;next);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e2=q; //</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;if(e1!=e2) LinkedList_Merge(L,p,e1,e2); //</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>
}//LinkedList_Merge_Sort1 <o:p></o:p></span></p>

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>void
LinkedList_Merge(LinkedList &amp;L,LNode *p,LNode *e1,LNode *e2)//</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"'>p-&gt;next</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"'>e1,</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"'>e1-&gt;next</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"'>e2<br>
{<br>
&nbsp;&nbsp;q=p-&gt;next;r=e1-&gt;next; //q</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"'>r</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;while(q!=e1-&gt;next&amp;&amp;r!=e2-&gt;next)<br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;if(q-&gt;data&lt;r-&gt;data) //</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"'><br>
&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p-&gt;next=q;p=q;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;q=q-&gt;next;<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;else<br>
&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p-&gt;next=r;p=r;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r=r-&gt;next;<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;}//while<br>
&nbsp;&nbsp;while(q!=e1-&gt;next) //</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;p-&gt;next=q;p=q;<br>
&nbsp;&nbsp;&nbsp;&nbsp;q=q-&gt;next;<br>
&nbsp;&nbsp;}<br>
&nbsp;&nbsp;while(r!=e2-&gt;next)<br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;p-&gt;next=r;p=r;<br>
&nbsp;&nbsp;&nbsp;&nbsp;r=r-&gt;next;<br>
&nbsp;&nbsp;}<br>
}//LinkedList_Merge <o:p></o:p></span></p>

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

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>void
LinkedList_Merge_Sort2(LinkedList &amp;L)//</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>
{<br>
&nbsp;&nbsp;LNode *end[MAXSIZE]; //</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;for(p=L-&gt;next-&gt;next,i=0;p;p=p-&gt;next) //</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;if(!p-&gt;next||p-&gt;data&gt;p-&gt;next-&gt;data)
end[i++]=p;<br>
&nbsp;&nbsp;while(end[0]-&gt;next) //</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;j=0;k=0; //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"'>;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"'><br>
&nbsp;&nbsp;&nbsp;&nbsp;for(p=L-&gt;next,e2=p;p-&gt;next;p=e2) //</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;e1=end[j];e2=end[j+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"'><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(e1-&gt;next)
LinkedList_Merge(L,p,e1,e2); //</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;end[k++]=e2; //</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;j+=2; //</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;}//while<br>
}//LinkedList_Merge_Sort2 <o:p></o:p></span></p>

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>void
LinkedList_Merge(LinkedList &amp;L,LNode *p,LNode *e1,LNode *e2)//</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"'>p-&gt;next</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"'>e1,</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"'>e1-&gt;next</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"'>e2<br>
{<br>
&nbsp;&nbsp;q=p-&gt;next;r=e1-&gt;next;<br>
&nbsp;&nbsp;while(q!=e1-&gt;next&amp;&amp;r!=e2-&gt;next)<br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;if(q-&gt;data&lt;r-&gt;data)<br>
&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p-&gt;next=q;p