計(jì)算機(jī)軟件技術(shù)基礎(chǔ)徐士良第3章ppt課件

1、第3章 查找與排序技術(shù),3.1 基本的查找技術(shù) 3.2 哈希表技術(shù) 3.3 基本的排序技術(shù) 3.4 二叉排序樹及其查找 3.5 多層索引樹及其查找 3.6 拓?fù)浞诸?3.1 基本的查找技術(shù),3.1.1 順序查找 3.1.2 有序表的對分查找 3.1.3 分塊查找,3.1.1 順序查找 (1)如果線性表為無序表（即表中元素的排列是無 序的），則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯?結(jié)構(gòu)，都只能用順序查找。 (2)即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)， 也只能用順序查找。,線性表在順序存儲結(jié)構(gòu)下的順序查找 輸入：線性表長度n以及線性表的存儲空間V； 被查找的元素x。 輸出：被查找元素x在線性表中的序號

2、k。 如果在線性表中不存在元素x，則輸出k1。 PROCEDURE SERCH(V，n，x，k) k1 WHILE (kn)and(V(k)x) DO kk1 IF (kn1) THEN k1 RETURN,/*函數(shù)返回被查找元素x在線性表中的序號， 如果在線性表中不存在元素值x，則返回1 */ int serch(v，n，x) int n； ET v，x； /*ET為線性表數(shù)據(jù)類型*/ int k； k0； while (kn)&(vkx) kk1； if (kn) k1； return(k)； ,線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的順序查找 輸入：線性鏈表頭指針HEAD以及存儲空間V、NEXT； 被查

3、找的元素x。 輸出：被查找元素x的結(jié)點(diǎn)在線性鏈表中的存儲序號k。 如果在線性鏈表中不存在元素值為x的結(jié)點(diǎn)， 則輸出k1。 PROCEDURE LSERCH(V，NEXT，HEAD，x，k) kHEAD WHILE (k0)and(V(k)x) DO kNEXT(k) IF (k0) THEN k1 RETURN,struct node ET d； struct node *next； ； /*函數(shù)返回被查找元素x所在結(jié)點(diǎn)的存儲地址， 如果在線性鏈表中不存在元素值為x的結(jié)點(diǎn)，則返回NULL*/ struct node *lserch(head，x) struct node *head； ET x

4、； /*ET為線性鏈表中值域的數(shù)據(jù)類型*/ struct node k； khead； while (kNULL)&(kdx) kknext； return(k)； ,3.1.2 有序表的對分查找 設(shè)有序線性表的長度為n，被查元素為x。 將x與線性表的中間項(xiàng)進(jìn)行比較： 若中間項(xiàng)的值等于x，則說明查到，查找結(jié)束； 若x小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分） 以相同的方法進(jìn)行查找； 若x大于中間項(xiàng)的值，則在線性表的后半部分（即中間項(xiàng)以后的部分） 以相同的方法進(jìn)行查找。 這個(gè)過程一直進(jìn)行到查找成功或子表長度為0(說明線性表中沒有這 個(gè)元素)為止。 在最壞情況下，對分查找只需比較l

5、og2n次，而順序查找需比較n次。,有序線性表在順序存儲結(jié)構(gòu)下的對分查找 輸入：有序線性表長度n以及線性表的存儲空間V；被查找的元素x。 輸出：被查找元素x在有序線性表中的序號k。如果在線性表中不存 在元素x，則輸出k1。 PROCEDURE BSERCH(V，n，x，k) i1； jn WHILE (ij) DO k(ij)/2 IF (V(k)x) THEN RETURN IF (V(k)x) THEN jk1； ELSE ik1； IF (ij) THEN k1 RETURN,int bserch(v，n，x) /*函數(shù)返回被查找元素x在線性表中的序號 如果在線性表中不存在元素值x，則返

6、回1 */ int n； ET x，v； int i，j，k； i1； jn； while (ij) k(ij)/2； if (vk1x) return(k1)； if (vk1x) jk1； else ik1； return(1)； ,3.1.3 分塊查找 分塊有序表 將長度為n線性表分成m個(gè)子表，各子表的長度可以相等，也可以互相不 等，但要求后一個(gè)子表中的每一個(gè)元素均大于前一個(gè)子表中的所有元素。 分塊有序表的結(jié)構(gòu)可以分為兩部分： (1)線性表本身采用順序存儲結(jié)構(gòu)。 (2)再建立一個(gè)索引表。在索引表中，對線性表的每個(gè)子表建立一個(gè)索引結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)包括兩個(gè)域：一是數(shù)據(jù)域，用于存放對應(yīng)子表中的最

7、大元素值；二是指針域，用于指示對應(yīng)子表的第一個(gè)元素在整個(gè)線性表中的序號。,struct indnode ET key；/*數(shù)據(jù)域，存放子表中的最大值， 其類型與線性表中元素的數(shù)據(jù)類 型相同*/ int k； /*指針域，指示子表中第一個(gè)元素 在線性表中的序號*/ ；,(1)首先查找索引表，以便確定被查元素所在的子表。由于索引表數(shù)據(jù)域中的數(shù)據(jù)是有序的，因此可以采用對分查找。 (2)然后在相應(yīng)的子表中用順序查找法進(jìn)行具體的查找。 分塊查找 輸入：長度為n的線性表L的存儲空間V(1：n)；索引表中 的數(shù)據(jù)域存儲空間KEY(1：m)與指針域存儲空間 K(1：m)；被查元素x。 輸出：被查元素x在線性表

8、L中的序號j（即使L(j) x的j）。如果x不在線性表L中，則置j1。,PROCEDURE INSERCH(V，n，KEY，K，m，x，j) i1； jm WHILE (ji1) DO 對分查找索引表 t(ij)/2 IF (xKEY(t) THEN jt ELSE it IF (ij)and(xKEY(i) THEN ij jK(i)； tn IF (im) THEN tK(i1)1 確定順序查找的終點(diǎn) WHILE (jt)and(V(j)x) DO jj1 順序查找子表 IF (jt) THEN j1 RETURN,在分塊查找中，為了找到被查元素x所在的子表，需要對分查找索引 表，在最壞情

9、況下需要查找log2(m1)次。 在相應(yīng)子表中用順序查找法查找元素x，在最壞情況下需要查找n/m （假設(shè)各子表長度相等）次；而在平均情況下需要查找n/(2m)次。 因此，分塊查找的工作量為： 在最壞情況下需要查找log2(m1)n/m次， 平均情況下大約需要查找log2(m1)n/(2m)次。 當(dāng)mn時(shí)，線性表L即為有序表，分塊查找即為對分查找 當(dāng)m1時(shí)，線性表L為一般的無序表，分塊查找即為順序查找。 分塊查找的效率介于對分查找和順序查找之間。,struct indnode ET key；/*數(shù)據(jù)域，存放子表中的最大值， 其類型與線性表中元素的數(shù)據(jù)類型相同*/ int k； /*指針域，指示子

10、表中第一個(gè)元素在線性表中的序號*/ ； /*函數(shù)返回被查找元素x在線性表中的序號， 如果在線性表中不存在元素值x，則返回1 */ int inserch(v，n，s，m，x) int n，m； ET x，v； struct indnode s ；, int i，j，t； i1； jm； while (ji1) /*對分查找索引表*/ t(ij)/2； if (xst.key) jt； else it； if (i!j)&(xsi.key) ij； jsi.k； tn； if (i!m) tsi1.k1；/*確定順序查找的終點(diǎn)*/ while(jt)&(Vj!x) jj1；/*順序查找子表*/

11、if (jt) j1； return(j)； ,3.2 哈希表技術(shù),3.2.1 Hash表的基本概念 3.2.2 幾種常用的Hash表,3.2.1 Hash表的基本概念 1. 接查找技術(shù) 設(shè)表的長度為n。如果存在一個(gè)函數(shù)ii(k)，對于表中的任 意一個(gè)元素的關(guān)鍵字k，滿足以下條件：(1)1in；(2)對于任意的元素關(guān)鍵字k1k2，恒存在i(k1)i(k2)。 則稱此表為直接查找表。 其中函數(shù)ii(k)稱為關(guān)鍵字k的映象函數(shù)。,(1)直接查找表的填入要將關(guān)鍵字為k的元素填入到直接查找表，只需做以下兩步：1)計(jì)算關(guān)鍵字k的映象函數(shù)ii(k)；2)將關(guān)鍵字k及有關(guān)元素信息填入到表的第i項(xiàng)。,(2)

12、直接查找表的取出要在直接查找表中取出關(guān)鍵字k的元素，也只需做以下兩步：1)計(jì)算關(guān)鍵字k的映象函數(shù)ii(k)；2)檢查表中第i項(xiàng)：若第i項(xiàng)為空，則說明表中沒有關(guān)鍵字為k的元素； 否則取出第i項(xiàng)中的元素即可。,2. Hash表 例 將關(guān)鍵字序列 (09，31，26，19，01，13，02，11，27，16，05，21) 依次填入長度為n12的表中。 映象函數(shù)為iINT(k/3)1。,設(shè)表的長度為n。如果存在一個(gè)函數(shù)ii(k)，對于表中的任 意一個(gè)元素的關(guān)鍵字k，滿足1in，則稱此表為Hash表。 其中函數(shù)ii(k)稱為關(guān)鍵字k的Hash碼。(1)構(gòu)造合適的Hash碼，以便盡量減少表中元素沖突的次

13、數(shù)。即Hash碼的均勻性要比較好。(2)當(dāng)表中元素發(fā)生沖突時(shí)，要進(jìn)行適當(dāng)?shù)奶幚怼?3. Hash碼的構(gòu)造 (1)使各關(guān)鍵字盡可能均勻地分布在Hash表中，即 Hash碼的均勻性要好，以便減少沖突發(fā)生的機(jī) 會。 (2)Hash碼的計(jì)算要盡量簡單。,(1) 截段法 (2) 分段疊加法 (3) 除法 imod(k，n) (4) 乘法 imod(k*，n)一般取0.618033988747，或0.6125423371， 或0.6161616161。,3.2.2 幾種常用的Hash表1. 線性Hash表開放法,(1)線性Hash表的填入 將關(guān)鍵字k及有關(guān)信息填入線性Hash表的步驟如下： 1)計(jì)算關(guān)鍵字

14、k的Hash碼ii(k)。 2)檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)為空，則將關(guān)鍵字k及有關(guān)信息填入該項(xiàng)；若第i項(xiàng)不空，則令imod(i1，n)，轉(zhuǎn)2)繼續(xù)檢查。 只要Hash表尚未填滿，最終總可以找到一個(gè)空項(xiàng)，將關(guān)鍵字 k及有關(guān)信息填入到Hash表中。,(2) 線性Hash表的取出 要在線性Hash表中取出關(guān)鍵字k的元素，其步驟如下： 1)計(jì)算關(guān)鍵字k的Hash碼ii(k)。 2)檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可；若第i項(xiàng)為空，則表示在Hash表中沒有該關(guān)鍵字的信息；若第i項(xiàng)不空，且登記的不是關(guān)鍵字k，則令 imod(i1，n) 轉(zhuǎn)2)繼續(xù)檢查。,例 將關(guān)鍵字序列

15、(09，31，26，19，01，13，02，11，27，16，05，21) 依次填入長度為n12的線性Hash表中。 設(shè)Hash碼為iINT(k/3)1。,缺點(diǎn)： 1)在線性Hash表填入的過程中，當(dāng)發(fā)生沖突時(shí)，首先考慮 的是下一項(xiàng)，因此，當(dāng)Hash碼的沖突較多時(shí)，在線性 Hash表中會存在“堆聚”現(xiàn)象，即許多關(guān)鍵字被連續(xù)登記 在一起，從而會降低查找效率。 2)在線性Hash表的填入過程中，處理沖突時(shí)會帶來新的沖突。,2. 隨機(jī)Hash表,(1) 隨機(jī)Hash表的填入 將關(guān)鍵字k及有關(guān)信息填入隨機(jī)Hash表的步驟如下： 1)計(jì)算關(guān)鍵字k的Hash碼i0i(k)。且令ii0。 2)偽隨機(jī)數(shù)序列初

16、始化，令j1（即將取隨機(jī)數(shù)指針指向偽 隨機(jī)數(shù)序列中的第1個(gè)隨機(jī)數(shù)）。 3)檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)為空，則將關(guān)鍵字k及有關(guān)信息填入該項(xiàng)；若第i項(xiàng)不空，則令imod(i0RN(j)，n)，并令jj1 （即將取隨機(jī)數(shù)指針指向下一個(gè)隨機(jī)數(shù)），轉(zhuǎn)3)繼續(xù)檢查。 其中RN(j)表示偽隨機(jī)數(shù)序列RN中的第j個(gè)隨機(jī)數(shù)。,偽隨機(jī)數(shù)序列RN按下列方法產(chǎn)生： R1 FOR j1 TO n DO Rmod(5*R，4n) RN(j)INT(R/4) ,例 將關(guān)鍵字序列 (09，31，26，19，01，13，02，11，27，16，05，21) 依次填入長度為n2416的隨機(jī)Hash表中。 設(shè)Hash碼為iIN

17、T(k/3)1。 偽隨機(jī)數(shù)序列為： 1，6，15，12，13，2，11，8，9，14，7，4，5，10，3，0。,(2) 隨機(jī)Hash表的取出 要在隨機(jī)Hash表中取出關(guān)鍵字k的元素，其步驟如下： 1)計(jì)算關(guān)鍵字k的Hash碼i0i(k)。且令ii0。 2)偽隨機(jī)數(shù)序列初始化，令j1（即將取隨機(jī)數(shù)指針指向偽 隨機(jī)數(shù)序列中的第1個(gè)隨機(jī)數(shù)）。 3)檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可；若第i項(xiàng)空，則表示在Hash表中沒有該關(guān)鍵字信息；若第i項(xiàng)不空，且登記的不是關(guān)鍵字k，則令imod(i0RN(j)，n)，并令jj1（即將取隨機(jī)數(shù)指 針指向下一個(gè)隨機(jī)數(shù)），轉(zhuǎn)3)繼續(xù)檢查。

18、 其中RN(j)表示偽隨機(jī)數(shù)序列RN中的第j個(gè)隨機(jī)數(shù)。,3. 溢出Hash表溢出Hash表包括Hash表和溢出表兩部分。在Hash表的填入過程中，將沖突的元素順序填入溢出表，而當(dāng)查找過程中發(fā)現(xiàn)沖突時(shí)，就在溢出表中進(jìn)行順序查找。溢出表是一個(gè)順序查找表。,(1) 溢出Hash表的填入 將關(guān)鍵字k及有關(guān)信息填入溢出Hash表的步驟如下： 1)計(jì)算關(guān)鍵字k的Hash碼ii(k)。 2)檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)為空，則將關(guān)鍵字k及有關(guān)信息填入該項(xiàng)；若第i項(xiàng)不空，則將關(guān)鍵字k及有關(guān)信息依次填入 溢出表中的自由項(xiàng)。,(2) 溢出Hash表的取出 要在溢出Hash表中取出關(guān)鍵字k的元素，其步驟如 下：

19、1)計(jì)算關(guān)鍵字k的Hash碼ii(k)。 2)檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可；若第i項(xiàng)為空，則表示在Hash表中沒有該關(guān)鍵字信息；若第i項(xiàng)不空，且登記的不是關(guān)鍵字k，則轉(zhuǎn)入在 溢出表中進(jìn)行順序查找。,例 將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21) 依次填入長度為n12的溢出Hash表中。 設(shè)Hash碼為iINT(k/3)1。,4. 拉鏈Hash表拉鏈Hash表又分為外鏈Hash表與內(nèi)鏈Hash表。,(1) 外鏈Hash表的填入 將關(guān)鍵字k及有關(guān)信息填入外鏈Hash表的步驟如下： 1)計(jì)算關(guān)鍵字k的Hash碼ii(k)

20、。 2)取得一個(gè)新結(jié)點(diǎn)p，并將關(guān)鍵字k及有關(guān)信息填入結(jié)點(diǎn)p。 3)將結(jié)點(diǎn)p鏈入以H(i)為頭指針的鏈表的鏈頭。,例 將關(guān)鍵字序列(09，31，26，19， 01，13，02，11，27，16，05，21) 依次填入長度為n12的外鏈Hash表 中。 設(shè)Hash碼為iINT(k/3)1。,(2) 外鏈Hash表的取出 要在外鏈Hash表中取出關(guān)鍵字k的元素，其步驟如 下： 1)計(jì)算關(guān)鍵字k的Hash碼ii(k)。 2)在以H(i)為頭指針的鏈表中順序查找關(guān)鍵字為k 的結(jié)點(diǎn)。若找到，則從結(jié)點(diǎn)中取出該元素。,5. 指標(biāo)Hash表指標(biāo)Hash表包括指標(biāo)表與內(nèi)容表兩部分。,3.3 基本的排序技術(shù),3.3

21、.1 冒泡排序與快速排序 3.3.2 簡單插入排序與希爾排序 3.3.3 簡單選擇排序與堆排序 3.3.4 其他排序方法簡介,3.3.1 冒泡排序與快速排序 1. 冒泡排序首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個(gè)逆序。顯然，在掃描過程中，不斷地將兩相鄰元素中的大者往后移動，最后就將線性表中的最大者換到了表的最后。然后從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，后面的元素小于前面的元素，則將它們互換，這樣就又消去了一個(gè)逆序。顯然，在掃描過程中，不

22、斷地將兩相鄰元素中的小者往前移動，最后就將剩下線性表中的最小者換到了表的最懊妗對剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時(shí)的線性表已經(jīng)變?yōu)橛行颉?輸入：無序序列P(1：n)。 輸出：有序序列P(1：n)。PROCEDURE BUBSORT(P，n)k1； mnWHILE (km) DO 子表未空 jm1； m0 FOR ik TO j DO 從前往后掃描子表 IF (p(i)p(i1) THEN 發(fā)現(xiàn)逆序進(jìn)行交換 dp(i)；p(i)p(i1)；p(i1)d；mi jk1； k0 FOR im TO j BY 1 DO 從后往前掃描子表 IF (p(i1) p(i) THEN發(fā)現(xiàn)

23、逆序進(jìn)行交換 dp(i)；p(i)p(i1)；p(i1)d；ki RETURN,bubsort(p，n)int n； ET p； int m，k，j，i； ET d； k0； mn1； while (km) /*子表未空*/ jm1； m0； for(ik；ij；i) /*從前往后掃描*/ if (pipi1) /*發(fā)現(xiàn)逆序進(jìn)行交換*/ dpi；pipi+1；pi+1d；mi；,jk1； k0； for (im；ij；i) /*從后往前掃描*/ if (pi1 pi) /*發(fā)現(xiàn)逆序進(jìn)行交換*/ dpi；pipi-1；pi-1d；ki； return；,2. 快速排序,首先，在表的第一個(gè)、中間一

24、個(gè)與最后一個(gè)元素中選取中項(xiàng)， 設(shè)為P(k)，并將P(k)賦給T，再將表中的第一個(gè)元素移到 P(k)的位置上。 然后設(shè)置兩個(gè)指針i和j分別指向表的起始與最后的位置。反 復(fù)作以下兩步： (1)將j逐漸減小，并逐次比較P(j)與T，直到發(fā)現(xiàn)一個(gè) P(j)T為止，將P(j)移到P(i)的位置上。 (2)將i逐漸增大，并逐次比較P(i)與T，直到發(fā)現(xiàn)一個(gè) P(i)T為止，將P(i)移到P(j)的位置上。 上述兩個(gè)操作交替進(jìn)行，直到指針i與j指向同一個(gè)位置 （即ij）為止，此時(shí)將T移到P(i)的位置上。,線性表的分割 輸入：待分割的子表P(m：n)。 輸出：分割后的分界線位置i。 PROCEDURE SP

25、LIT(P，m，n，i) 選取P(k) 其中mkn TP(k)；P(k)P(m) im；jn,WHILE (ij) DO WHILE (P(j)T)and(ij) DO jj1 IF (ij) THEN P(i)P(j)；ii1 WHILE (P(i)T)and(ij) DO ii1 IF (ij) THEN P(j)P(i)；jj1 P(i)T RETURN,快速排序的遞歸算法輸入：待排序的子表P(m：n)。輸出：有序子表P(m：n)。PROCEDURE QKSORT1(P，m，n)IF (nm) THEN 子表不空 SPLIT(P，m，n，i)； 分割 QKSORT1(P，m，i1)；對前

26、面子表進(jìn)行快速排序 QKSORT1(p，i1，n)；對后面子表進(jìn)行快速排序 RETURN,qksort1(p，m，n)int m，n； ET p； int i； if (nm) /*子表不空*/ isplit(p，m，n)； /*分割*/ qksort1(p，m，i1)；/*對前子表進(jìn)行快速排序*/qksort1(p，i1，n)；/*對后子表進(jìn)行快速排序*/ return；,static int split(p，m，n) /*返回分界線位置*/int m，n； ET p； int i，j，k，u； ET t； im1； jn1； k(ij)/2； if (pipj)&(pjpk) uj； /*

27、選取一個(gè)元素*/ else if (pipk)&(pkpj) uk； else ui； tpu； pupi；,while (i!j) while (ij)&(pjt) jj1； if (ij) pipj； ii1； while (ij)&(pit) ii1； if (ij) pjpi； jj1； pit；return(i)；,快速排序的非遞歸算法 輸入：待排序的子表P(m：n)。 輸出：有序子表P(m：n)。PROCEDURE QKSORT2(P，m，n)建立一個(gè)棧，并初始化棧中每一個(gè)元素有兩個(gè)數(shù)據(jù)項(xiàng)：子表第一個(gè)元素下標(biāo)與最后一個(gè)元素下標(biāo)將下標(biāo)m與n進(jìn)棧 子表進(jìn)棧WHILE 棧非空 DO 還有

28、子表需要分割 從棧中退出兩個(gè)下標(biāo)m與n 從棧中退出一個(gè)子表進(jìn)行分割 WHILE (nm) DO 子表不空 SPLIT(P，m，n，i) 進(jìn)行分割 將下標(biāo)i1與n進(jìn)棧 將分割出的后一個(gè)子表進(jìn)棧 ni1 對分割出前一個(gè)子表繼續(xù)進(jìn)行分割 RETURN,3.3.2 簡單插入排序與希爾排序1. 簡單插入排序 輸入：待排序序列P(1：n)。 輸出：有序序列P(1：n)。 PROCEDURE INSORT(P，n) FOR j2 TO n DO TP(j)；kj1 WHILE (k0)and(P(k)T) DO P(k1)P(k)；kk1 P(k1)T RETURN,5 1 7 3 1 6 9 4 2 8

29、6 j2 1 5 7 3 1 6 9 4 2 8 6 j3 1 5 7 3 1 6 9 4 2 8 6 j4 1 3 5 7 1 6 9 4 2 8 6 j5 1 1 3 5 7 6 9 4 2 8 6 j6,1 1 3 5 6 7 9 4 2 8 6 j7 1 1 3 5 6 7 9 4 2 8 6 j8 1 1 3 4 5 6 7 9 2 8 6 j9 1 1 2 3 4 5 6 7 9 8 6 j10 1 1 2 3 4 5 6 7 8 9 6 j11 1 1 2 3 4 5 6 6 7 8 9,insort(p，n) int n； ET p； int j，k； ET t； for (j

30、1； jn； j) tpj； kj1； while (k0)&(pkt) pk1pk； kk1； pk1t； return； ,2. 希爾排序 將整個(gè)無序序列分割成若干小子序列分別進(jìn)行插入 排序 子序列的分割方法如下： 將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列。在排序 過程中，逐次減小這個(gè)增量，最后當(dāng)h減到1時(shí)，進(jìn) 行一次插入排序，排序就完成。 增量序列一般取 htn/2k(k1，2，log2n)， 其中n為待排序序列的長度。,輸入：待排序序列P(1：n)。 輸出：有序序列P(1：n)。 PROCEDURE SHLSORT(P，n) hn/2 WHILE (h0) DO FOR jh1 TO n

31、DO tP(j)； ijh WHILE (i0)and(P(i)t) DO P(ih)P(i)； iih P(ih)t hh/2 RETURN,shlsort(p，n)int n； ET p； int h，j，i； ET t； hn/2； while (h0) for (jh； jn1； j) tpj； ijh； while (i0)&(pit) pihpi； iih； piht； hh/2； return；,3.3.3 簡單選擇排序與堆排序 1. 簡單選擇排序,輸入：無序序列P(1：n)。 輸出：有序序列P(1：n)。 PROCEDUDE SELESORT(P，n) FOR i0 TO n2

32、 DO ki FOR ji1 TO n1 DO IF P(j)P(k) THEN kj IF (ki) THEN dP(i)； P(i)P(k)； P(k)d RETURN,selesort(p，n)int n； ET p； int i，j，k； ET d； for (i0； in2； ii1) ki； for (ji1； jn1； jj1) if (pjpk) kj； if (k!i) dpi；pipk；kd； return；,2. 堆排序堆的定義：具有n個(gè)元素的序列(h1，h2，hn)，當(dāng)且僅當(dāng)滿足(i1，2，n/2)時(shí)稱之為堆。由堆的定義可以看出，堆頂元素(即第一個(gè)元素)必為最大項(xiàng)。,或

33、具有n個(gè)元素的序列(h1，h2，hn)，當(dāng)且僅當(dāng)滿足(i1，2，n/2)時(shí)稱之為堆。,序列(91，85，53，36，47，30，24，12)是一個(gè)堆,調(diào)整建堆 在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹（用一維數(shù)組 H(1：n)表示）中，假設(shè)結(jié)點(diǎn)H(m)的左右子樹均 為堆，現(xiàn)要將以H(m)為根結(jié)點(diǎn)的子樹也調(diào)整為堆。,調(diào)整建堆輸入：完全二叉樹數(shù)組H(1：n)。其中結(jié)點(diǎn)H(m)的左右子樹均為堆。輸出：以H(m)為根結(jié)點(diǎn)的子樹為堆。 PROCEDURE SIFT(H，n，m) tH(m)； j2m WHILE (jn) DO IF (jn)and(H(j)H(j1) THEN jj1 IF (tH(j) THE

34、N H(m)H(j)； mj； j2m else jn1 H(m)t RETURN,(1)首先將一個(gè)無序序列建成堆。 (2)然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后 一個(gè)元素交換（最大項(xiàng)應(yīng)該在序列的最后）。 不考慮已經(jīng)換到最后的那個(gè)元素，只考慮前 n1個(gè)元素構(gòu)成的子序列，顯然，該子序列已 不是堆，但左、右子樹仍為堆，可以將該子序列 調(diào)整為堆。 反復(fù)做第(2)步，直到剩下的子序列為空為止。,堆排序輸入：無序序列H(1：n)。輸出：無序序列H(1：n)。PROCEDURE HEAPSORT(H，n)kn/2FOR ik TO 1 BY 1 DO SIFT(H，n，i) 無序序列建堆FOR in

35、TO 2 BY 1 DO tH(1)；H(1)H(i)；H(i)t堆頂元素?fù)Q到最后 SIFT(H，i1，1) 調(diào)整建堆 RETURN,heapsort(p，n)int n； ET p； int i，k； ET t； kn/2； for (ik1； i0； i) sift(p，n1，i)； /*無序序列建堆*/ for (in1； i1； i) tp0； p0pi； pit； /*堆頂元素?fù)Q到最后*/ sift(p，i1，0)； /*調(diào)整建堆*/ return；,static sift(h，n，m)int n，m； ET h； int j； ET t； thm； j2*(m1)1； while

36、(jn) if (jn)&(hjhj1) jj1； if (thj) hmhj； mj； j2*(m1)1； else jn1； hmt； return；,3.3.4 其他排序方法簡介1. 歸并排序設(shè)線性表L(1：n)中的某段L(low：high)已經(jīng)部分有序，即它的兩個(gè)子表L(low：mid)與L(mid1：high)（其中l(wèi)owmidhigh）已經(jīng)有序，現(xiàn)要將這兩個(gè)有序子表歸并成一個(gè)有序子表L(low：high)。,實(shí)現(xiàn)上述兩個(gè)子表歸并的基本做法如下： (1)開辟一個(gè)與線性表L同樣大小的表空間A。 (2)設(shè)置三個(gè)指針i，j，k，其初始狀態(tài)分別指向兩個(gè)有序子 表的首部及表空間A中與L中需要進(jìn)

37、行排序段相對應(yīng)空間 的首部。即ilow，jmid1，klow。 (3)沿兩個(gè)有序子表掃描： 若L(i)L(j)，則A(k)L(i)，且i與k指針均加1； 否則A(k)L(j)，且j與k指針均加1。 如此反復(fù)，直到有一個(gè)子表的指針已經(jīng)指到末端（即子 表內(nèi)的元素已經(jīng)取空）為止。 (4)將未取空的子表中的剩余元素依次放入表空間A中。 (5)將A中的對應(yīng)段復(fù)制到L中。,兩個(gè)相鄰有序子表的合并輸入：兩個(gè)相鄰有序子表L(low：mid)與L(mid1：high) （其中l(wèi)owmidhigh）；工作數(shù)組A(low：high)。輸出：有序子表L(low：high)。PROCEDURE MERGE(L，low，

38、mid，high，A)ilow，jmid1，klowWHILE (imid)and(jhigh) DO IF L(i)L(j) THEN A(k)L(i)；ii1 ELSE A(k)L(j)；jj1 kk1 ,IF (imid) THEN FOR ji TO mid DO A(k)L(j)；kk1 ELSE IF (jhigh) THEN FOR ij TO high DO A(k)L(i)；kk1 FOR ilow TO high DO L(i)A(i)RETURN,歸并排序的非遞歸算法輸入：無序序列P(1：n)。輸出：有序序列P(1：n)。PROCEDURE MERGSORT(P，n)定義

39、工作數(shù)組A(1：n)m1,WHILE (mn) DO k2m FOR j1 TO n BY k DO lowj；highjk1；midjm1 IF (highn) THEN highn IF (highmid) THEN MERGE(P，low，mid，high，A) mk RETURN,#include stdlib.hmergsort(p，n)int n；ET p； int m，k，j，low，high，mid； ET *a； amalloc(n*sizeof(ET)； m1； while (mn) k2*m；,for(j1； jn； jjk) lowj； highjk1； midjm1；

40、 if (highn) highn； if (highmid) merge(p,low,mid,high,a)； mk； free(a)； return；,static merge(p，low，mid，high，a)int low，mid，high；ET p，a； int I，j，k； ilow； jmid1； klow； while (imid)&(jhigh) if (pi1pj1) ak1pi1； ii1； else ak1pj1； jj1； kk1； ,if (imid) for(ji； jmid； j) ak1pj1； kk1； else if (jhigh) for(ij； ihi

41、gh； i) ak1pi1； kk1； for(ilow；ihigh；i) pi1ai1； return；,2. 基數(shù)排序設(shè)線性表中各元素的關(guān)鍵字具有k位有效數(shù)字，則基數(shù)排序的基本思想是：從有效數(shù)字的最低位開始直到最高位，對于每一位有效數(shù)字對線性表進(jìn)行重新排列，其調(diào)整的原則為：(1)將線性表依當(dāng)前位的有效數(shù)字為序排列；(2)當(dāng)前位的有效數(shù)字相同時(shí)，按原次序排列。這種基數(shù)排序法稱為最低位優(yōu)先法（LSDLeast Significant Digit first）,基數(shù)排序的最高位優(yōu)先法（MSDMost Significant Digit first）。在這種方法中，是從有效數(shù)字的最高位開始直到最低

42、位進(jìn)行調(diào)整。在這種情況下，必須將線性表按有效位從高到低逐層分割成若干子表，然后對各子表獨(dú)立進(jìn)行排序。,冒泡排序 n(n1)/2快速排序 n(n1)/2簡單插入排序 n(n1)/2希爾排序 O(n1.5)簡單選擇排序 n(n1)/2堆排序 O(nlog2n)歸并排序 O(nlog2n),3.4 二叉排序樹及其查找,3.4.1 二叉排序樹及其構(gòu)造 3.4.2 二叉排序樹查找,3.4.1 二叉排序樹及其構(gòu)造 (1)左子樹上的所有結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值； (2)右子樹上的所有結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值； (3)左、右子樹也滿足上述兩個(gè)條件。,依次讀入給定序列中的每一個(gè)元素： (1)若當(dāng)前的二叉排序樹為空，則

43、讀入的元素為根結(jié)點(diǎn)； (2)若讀入的元素值小于根結(jié)點(diǎn)值，則將元素插入到左子樹中； (3)若讀入的元素值不小于根結(jié)點(diǎn)值，則將元素插入到右子樹中。 無論是插入到左子樹還是右子樹，同樣按照上述方法處理。,插入元素68,插入元素71,插入元素77,插入元素88,二叉排序樹的另一種形態(tài),由無序序列構(gòu)造二叉排序樹 輸入：長度為n的無序序列A(1：n)。 輸出：二叉排序樹的頭指針BT。 PROCEDURE INBSORT(A，n，BT) BT0 FOR k1 TO n DO NEW(p) 取得一個(gè)新結(jié)點(diǎn) V(p)A(k)； L(p)0； R(p)0 jBT IF (j0) THEN BTp 若二叉排序樹為空

44、 ELSE 二叉排序樹不空, WHILE (L(j)p)and(R(j)p) DO 未到葉子結(jié)點(diǎn) IF (A(k)V(j) THEN 插入到左子樹 IF (L(j)0) THEN jL(j) ELSE L(j)p ELSE 插入到右子樹 IF (R(j)0) THEN jR(j) ELSE R(j)p RETURN,#include stdlib.h /* malloc 函數(shù)需要包含頭文件stdlib.h*/ struct btnode /*定義結(jié)點(diǎn)類型*/ ET d； /*數(shù)據(jù)域*/ struct btnode *lchild； /*左指針域*/ struct btnode *rchild；

45、 /*右指針域*/ ； struct btnode *inbsort(a，n) /*函數(shù)返回二叉排序樹頭指針*/ int n； ET a； struct btnode *p， *q， *bt； int k； btNULL；,for (k0； kn； k) p(struct btnode *)malloc(sizeof(struct btnode)； pdak； plchildNULL； prchildNULL； /*置新結(jié)點(diǎn)的數(shù)據(jù)域與左、右指針域*/ qbt； if (qNULL) btp； /*二叉排序樹為空*/ else /*二叉排序樹不空*/ while (qlchild!p)&(qrc

46、hild!p) if (akqd) /*插入到左子樹*/ if (qlchild!NULL) qqlchild； else qlchildp； ,else /*插入到右子樹*/ if (qrchild!NULL) qqrchild； else qrchildp； return(bt)； /*返回二叉排序樹頭指針*/ ,3.4.2 二叉排序樹查找 從二叉排序樹的根結(jié)點(diǎn)開始與被查值進(jìn)行比較： (1)若被查值等于根結(jié)點(diǎn)值，查找成功，查找過程結(jié)束。 (2)若被查值小于根結(jié)點(diǎn)值，則到左子樹中去查找。 (3)若被查值大于根結(jié)點(diǎn)值，則到右子樹中去查找。 在左、右子樹中查找時(shí)也采用上述方法。 查找過程直到查找

47、成功或所考慮的子樹已空為止。,二叉排序樹查找 輸入：二叉排序樹頭指針BT以及存儲空間；被查元素x。 輸出：被查元素x在二叉排序樹空間中的存儲結(jié)點(diǎn)序號p PROCEDURE BSTSERCH(BT，x，p) PBT WHILE (p0)and(V(p)x) DO IF (xV(p) THEN pL(p) 沿左子樹查找 ELSE pR(p) 沿右子樹查找 RETURN,struct btnode /*定義結(jié)點(diǎn)類型*/ ET d； /*數(shù)據(jù)域*/ struct btnode *lchild； /*左指針域*/ struct btnode *rchild； /*右指針域*/ ；,/*函數(shù)返回被查值x所

48、在結(jié)點(diǎn)的存儲地址*/ struct btnode *bstserch(bt，x) struct btnode *bt； ET x； struct btnode *p； pbt； while (p!NULL)&(pd!x) if (xpd) pplchild；/*沿左子樹查找*/ else pprchild； /*沿右子樹查找*/ return(p)； ,3.5.1 B樹 3.5.2 B樹,3.5 多層索引樹及其查找,3.5.1 B樹,一棵2m1階的B樹，或?yàn)榭眨驗(yàn)闈M足下列特性的度為2m1的樹： (1)樹中每個(gè)結(jié)點(diǎn)最多有2m1棵子樹，且除根結(jié)點(diǎn)外的所有非葉子結(jié) 點(diǎn)至少有m1棵子樹，而根結(jié)點(diǎn)至少

49、有兩棵子樹（除非根結(jié)點(diǎn)又 是葉子結(jié)點(diǎn)）。 (2)所有葉子結(jié)點(diǎn)均在最后一層上。 (3)除葉子結(jié)點(diǎn)外的每個(gè)結(jié)點(diǎn)結(jié)構(gòu)中： KEYi(1i2m)為關(guān)鍵字域，用于存放關(guān)鍵字及有關(guān)數(shù)據(jù)信息； LINKi(1i2m1)為指針域，指向各子樹的根結(jié)點(diǎn)。 對于度為n1(1n2m)的結(jié)點(diǎn)，前n個(gè)關(guān)鍵字域內(nèi)容按關(guān)鍵字有 序，即KEYiKEYi1(1in1)，并且，LINKi(1in)所指子 樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于KEYn，而LINKn1所指子樹中所有結(jié) 點(diǎn)的關(guān)鍵字均大于KEYn。 (4)所有葉子結(jié)點(diǎn)中的指針域?yàn)榭铡?5階（即m2）B樹例,數(shù)組N，PRT，KEY，LINK模擬B樹的存儲空間。其中： N(i)表示結(jié)點(diǎn)

50、i中的關(guān)鍵字個(gè)數(shù)n。 如果結(jié)點(diǎn)i為非葉子結(jié)點(diǎn)，則此結(jié)點(diǎn)有N(i)1棵子樹。 PRT(i)指向結(jié)點(diǎn)i的父結(jié)點(diǎn)。 KEY(i，j)結(jié)點(diǎn)i的第j(1j2m)個(gè)關(guān)鍵字域。 LINK(i，j)結(jié)點(diǎn)i的第j(1j2m1)個(gè)指針域。,struct mbnode int n； /*記錄結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)*/ struct mbnode *prt； /*指向父結(jié)點(diǎn)*/ ET key2*m； /*2m個(gè)關(guān)鍵字域*/ struct mbnode *link2*m+1；/*2m1個(gè)指針域*/ ；,1. B樹的查找 從根結(jié)點(diǎn)BTH開始，將關(guān)鍵字x與結(jié)點(diǎn)q中的各關(guān)鍵字 KEY(q，i)(1in)進(jìn)行比較： 若xKEY(q

51、，i)，則查找成功，結(jié)束； 若xKEY(q，1)，則沿指針LINK(q，1)向下搜索； 若xKEY(q，n)，則沿指針LINK(q，n1)向下搜索； 若KEY(q，i)xKEY(q，i1)，則沿指針LINK(q，i1)向下搜 索。 這個(gè)過程一直進(jìn)行到查找成功或進(jìn)行到葉子結(jié)點(diǎn)而查找失敗為止。,B樹的查找 輸入：2m1階B樹的根結(jié)點(diǎn)指針（即頭指針）BTH； B樹的存儲空間N、PRT、KEY、LINK； 被查關(guān)鍵字x。 輸出：若標(biāo)志flag1，則表示查找成功，返回被查關(guān)鍵 字x所在的結(jié)點(diǎn)序號q以及x在該結(jié)點(diǎn)中的關(guān)鍵字序 號k；若標(biāo)志flag0，則表示查找失敗，輸出的 q與k指示了關(guān)鍵字x在B樹中應(yīng)插

52、入的位置（該信 息供插入用），即應(yīng)插入在KEY(q，k)與KEY(q，k 1)之間，其中q必為葉子結(jié)點(diǎn)。,PROCEDURE MBSEARCH(BTH，N，PRT，KEY，LINK，x，q，k，flag) pBTH； flag0； qp WHILE (p0)and(flag0) DO k1； qp WHILE (kN(q)and(KEY(q，k)x) DO kk1 IF (KEY(q，k)x) THEN flag1 /*查找成功*/ ELSE IF (kN(q)and(KEY(q，k)x) THEN pLINK(q，k1) ELSE pLINK(q，k)； kk1 RETURN,struct

53、mbnode int n； /*記錄結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)*/ struct mbnode *prt； /*指向父結(jié)點(diǎn)*/ ET key2*m； /*2m個(gè)關(guān)鍵字域*/ struct mbnode *link2*m+1；/*2m1個(gè)指針域*/ ； /*函數(shù)返回包含元素x的結(jié)點(diǎn)存儲地址；指針變量k指向的變量中存 放元素x在存儲結(jié)點(diǎn)中的序號；指針變量flag指向的變量值為0 時(shí)，表示查找失敗，值為1時(shí)表示查找成功。*/,struct mbnode *mbsearch(bth，x，k，flag) struct mbnode *bth； int *k， *flag； ET x； struct mbnode

54、 *p， *q； pbth； *flag0； qp；,while (p!NULL)&(*flag0) *k1； qp； while (*kqn)&(qkey*k1x) *k*k1； if (qkey*k1x) *flag1； /*查找成功*/ else if (*kqn)&(qkey*k1x) pqlink*k； else pqlink*k1； *k*k1； return(q)； ,2. B樹的插入 (1)如果在找到插入位置的葉子結(jié)點(diǎn)中的元素個(gè)數(shù)不足2m個(gè)，則直接 進(jìn)行插入。 (2)如果在找到插入位置的葉子結(jié)點(diǎn)中的元素已經(jīng)有2m個(gè)，則需要進(jìn) 行分裂，即將原結(jié)點(diǎn)中的2m個(gè)元素與要插入的元素一起按

55、序排列 后再對分，其中前半部分的元素仍然按序放在原來的結(jié)點(diǎn)中，而 后半部分的元素將放在一個(gè)新申請的結(jié)點(diǎn)中，并將中間的一個(gè)元 素放到其父結(jié)點(diǎn)中。如果父結(jié)點(diǎn)中的元素個(gè)數(shù)也已滿（即元素個(gè) 數(shù)等于2m），則又要進(jìn)行分裂。這種分裂過程有可能一直進(jìn)行到 根結(jié)點(diǎn)。 但必須注意，在每一次的分裂過程中，對于放在新申請結(jié)點(diǎn)中的所有元素的下一層結(jié)點(diǎn)，以及放到父結(jié)點(diǎn)中的元素的下一層結(jié)點(diǎn)，它們的父結(jié)點(diǎn)也變了，因此，需要改變它們中指向父結(jié)點(diǎn)的指針。,m2的B樹,插入元素12，結(jié)點(diǎn)數(shù)未變,又插入元素46后，增加了一個(gè)結(jié)點(diǎn),B樹的插入 輸入：2m1階B樹的根結(jié)點(diǎn)指針（即頭指針）BTH；B樹的存儲空間N、PRT、KEY、LIN

56、K；插入元素x。 輸出：插入后的2m1階B樹的根結(jié)點(diǎn)指針（即頭指針）BTH。 PROCEDURE MBINSERT(BTH，N，PRT，KEY，LINK，m，x) IF (BTH0) THEN /*B樹為空*/ NEW(p) 取存儲結(jié)點(diǎn) N(p)1； KEY(p，1)x； PRT(p)0 FOR j1 TO 2*m1 DO LINK(p，j)0 所有指針為空 BTHp 返回頭指針 RETURN ,MBSEARCH(BTH,N,PRT,KEY,LINK，x，q，k，flag)尋找插入位置 IF (flag1) THEN B樹中已有該元素，出錯(cuò)并返回 OUTPUT ERR!； RETURN p0；

57、 t0 WHILE (t0) DO IF (kN(q) THEN yx； up 插入到該結(jié)點(diǎn)最后 ELSE 在該結(jié)點(diǎn)的中間某個(gè)位置插入 yKEY(q，N(q)； uLINK(q，N(q)1) FOR jN(q)1 TO k1 BY 1 DO KEY(q，j1)KEY(q，j)； LINK(q，j2)LINK（q，j1） KEY(q，k1)x； LINK(q，k2)p IF (p0) THEN PRT(p)q 改變指向父結(jié)點(diǎn)的指針 ,IF N(q)2*m) THEN 該結(jié)點(diǎn)中關(guān)鍵字未滿，則進(jìn)行插入 N(q)N(q)1； t1 置分裂插入結(jié)束標(biāo)志 KYE(q，N(q)y； LINK(q，N(q)1)u IF (u0) THEN PRT(u)q 改變指向父結(jié)點(diǎn)的指針 ELSE 該結(jié)點(diǎn)中關(guān)鍵字已滿，應(yīng)進(jìn)行分裂 NEW(p) 取結(jié)點(diǎn) N(p)m； N(q)m； PRT(p)PRT(q) xKEY(q，m1) 中間的元素應(yīng)插入到父結(jié)點(diǎn),FOR j1 TO m1 DO 將