xtjd10.htm

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

QSort_NotRecurve(int SQList &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;low=1;high=L.length;<br>
&nbsp;&nbsp;InitStack(S); //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"'>boundary</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(low&lt;high&amp;&amp;!StackEmpty(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;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;if(high-low&gt;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"'>3</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;pivot=Partition(L,low,high); //</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(high-pivot&gt;pivot-low)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Push(S,{pivot+1,high}); //</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;high=pivot-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;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Push(S,{low,pivot-1});<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;low=pivot+1;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;}//if<br>
&nbsp;&nbsp;&nbsp;&nbsp;else if(low&lt;high&amp;&amp;high-low&lt;3)//</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"'>3</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;Easy_Sort(L,low,high); //</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;low=high; //</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;else //</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;Pop(S,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;&nbsp;&nbsp;&nbsp;&nbsp;low=a.low;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;high=a.high;<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;}//while<br>
}//QSort_NotRecurve <o:p></o:p></span></p>

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>int
Partition(SQList &amp;L,int low,int high)//</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;L.r[0]=L.r[low];<br>
&nbsp;&nbsp;pivotkey=L.r[low].key;<br>
&nbsp;&nbsp;while(low&lt;high)<br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;while(low&lt;high&amp;&amp;L.r[high].key&gt;=pivotkey)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;high--;<br>
&nbsp;&nbsp;&nbsp;&nbsp;L.r[low]=L.r[high];<br>
&nbsp;&nbsp;&nbsp;&nbsp;while(low&lt;high&amp;&amp;L.r[low].key&lt;=pivotkey)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;low++;<br>
&nbsp;&nbsp;&nbsp;&nbsp;L.r[high]=L.r[low];<br>
&nbsp;&nbsp;}//while<br>
&nbsp;&nbsp;L.r[low]=L.r[0];<br>
&nbsp;&nbsp;return low;<br>
}//Partition <o:p></o:p></span></p>

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>void
Easy_Sort(SQList &amp;L,int low,int high)//</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"'>3</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;if(high-low==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;if(L.r[low].key&gt;L.r[high].key)
L.r[low]&lt;-&gt;L.r[high];<br>
&nbsp;&nbsp;else //</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;if(L.r[low].key&gt;L.r[low+1].key)
L.r[low]&lt;-&gt;L.r[low+1];<br>
&nbsp;&nbsp;&nbsp;&nbsp;if(L.r[low+1].key&gt;L.r[high].key)
L.r[low+1]&lt;-&gt;L.r[high];<br>
&nbsp;&nbsp;&nbsp;&nbsp;if(L.r[low].key&gt;L.r[low+1].key)
L.r[low]&lt;-&gt;L.r[low+1];<br>
&nbsp;&nbsp;}<br>
}//Easy_Sort <o:p></o:p></span></p>

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

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>void
Divide(int a[ ],int 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;low=0;high=n-1;<br>
&nbsp;&nbsp;while(low&lt;high)<br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;while(low&lt;high&amp;&amp;a[high]&gt;=0) high--; //</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</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[low]&lt;-&gt;a[high];<br>
&nbsp;&nbsp;&nbsp;&nbsp;while(low&lt;high&amp;&amp;a[low]&lt;0) low++;<br>
&nbsp;&nbsp;&nbsp;&nbsp;a[low]&lt;-&gt;a[high];<br>
&nbsp;&nbsp;}<br>
}//Divide <o:p></o:p></span></p>

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

<p><span lang=EN-US style='mso-bidi-font-size:10.0pt;font-family:"Times New Roman"'>typedef
enum {RED,WHITE,BLUE} color; //</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"'>void
Flag_Arrange(color a[ ],int 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"'>,</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;i=0;j=0;k=n-1;<br>
&nbsp;&nbsp;while(j&lt;=k)<br>
&nbsp;&nbsp;&nbsp;&nbsp;switch(a[j])<br>
&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case RED:<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[i]&lt;-&gt;a[j];<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i++;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j++;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case WHITE:<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j++;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case BLUE:<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[j]&lt;-&gt;a[k];<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;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"'>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[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;}<br>
}//Flag_Arrange<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"'>,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"'>;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"'>;k</span><span