c與數(shù)據(jù)結(jié)構(gòu)課件.ppt

1、,第十四章 查找和排序,本章課件制作：吳虎統(tǒng),第三部分 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ),本章內(nèi)容, 查找 排序,14.1 查找,1. 查找的基本概念, 查找：在數(shù)據(jù)元素集合(查找表)中查找關(guān)鍵字與給定值相等的數(shù)據(jù)元素。 關(guān)鍵字：數(shù)據(jù)元素中的一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)值，它可以惟一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。 平均查找長(zhǎng)度(ASL)：,式中，n為查找表的長(zhǎng)度；pi為查找第i個(gè)元素的概率，在等概率情況下pi等于1/n； Ci為找到第i個(gè)元素時(shí)的比較次數(shù),2. 順序查找, 基本思想：用給定值依次與線性表中每個(gè)元素的關(guān)鍵字進(jìn)行比較。如果某個(gè)元素的關(guān)鍵字與給定值相同，則查找成功；如果找遍全表也沒有發(fā)現(xiàn)滿足條件的元素，則查找失敗。, 要求：

2、查找表必須采用線性表。, 實(shí)現(xiàn)一：順序表類中實(shí)現(xiàn)順序查找的成員函數(shù), 實(shí)現(xiàn)二：?jiǎn)捂湵眍愔袑?shí)現(xiàn)順序查找的成員函數(shù), 順序查找的平均查找長(zhǎng)度, 評(píng)價(jià)：在用順序查找方法完成查找時(shí)，每進(jìn)行一次成功查找需要的平均比較次數(shù)約為表長(zhǎng)度的一半，因此，它的效率較低。適用于在查找表較小的情況下進(jìn)行查找。,3. 二分查找,要求： 查找表必須采用線性表； 必須以順序方式存儲(chǔ)線性表； 線性表中所有數(shù)據(jù)元素必須按照關(guān)鍵字有序排列, 基本思想：將給定值與處于順序表“中間位置”上的元素的關(guān)鍵字進(jìn)行比較，若相等則查找成功，若給定值大于關(guān)鍵字則在表的后半部分繼續(xù)進(jìn)行二分查找，否則在表的前半部分繼續(xù)進(jìn)行二分查找。如此進(jìn)行下去直至找

3、到滿足條件的元素，或當(dāng)前查找區(qū)為空，此時(shí)查找失敗。,演示：,例子：二分查找函數(shù)模板及其測(cè)試程序,優(yōu)點(diǎn)： 查找效率高 平均查找長(zhǎng)度,缺點(diǎn)： 查找前要將表中元素按關(guān)鍵字有序排列 只適用于線性表的順序存儲(chǔ)。適用于那種一經(jīng)建立就很少改動(dòng)而又經(jīng)常需要查找的線性表。,4. 分塊查找,要求： 查找表必須采用線性表； 待查找的線性表分成若干塊。在每一塊內(nèi)，元素的存放是任意的，但在塊與塊之間元素的存放是有序的，即前一塊中任意一個(gè)元素的關(guān)鍵字值都必須小于（或大于）后一塊中所有元素的關(guān)鍵字值； 建立一個(gè)索引表，索引表中的每個(gè)索引項(xiàng)對(duì)應(yīng)于一塊。一個(gè)索引項(xiàng)至少應(yīng)含有兩部分信息：一是對(duì)應(yīng)塊中最大的關(guān)鍵字值；二是指向?qū)?yīng)塊

4、中第一個(gè)元素的指針, 基本思想：首先在索引表中查找，確定出要查找的元素應(yīng)該在哪一塊中；然后在已確定的那一塊內(nèi)進(jìn)行順序查找。, 演示：, 優(yōu)點(diǎn)：塊內(nèi)元素是任意存放的，插入或刪除運(yùn)算不會(huì)造成元素的大量移動(dòng)。, 缺點(diǎn)： 增加了存放索引表的輔助空間及初始時(shí)對(duì)線性表分塊排序的運(yùn)算 大量的插入和刪除運(yùn)算可能會(huì)導(dǎo)致各塊中元素的數(shù)目很不均勻，這會(huì)降低查找速度, 平均查找長(zhǎng)度：將長(zhǎng)度為n的線性表均勻地劃分成塊，每塊中有個(gè)結(jié)點(diǎn)，即。假定對(duì)表中每個(gè)元素的查找概率相等，則查找某一塊的概率為，查找塊中某個(gè)結(jié)點(diǎn)的概率為, 索引表使用順序查找：, 索引表使用二分查找：,5. 二叉排序樹查找, 二叉排序樹的定義： 二叉排序樹

5、或者是一棵空二叉樹，或者是具有以下性質(zhì)的二叉樹： 1、若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； 2、若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均不小于根結(jié)點(diǎn)的值； 3、左、右子樹本身又各是一棵二叉排序樹。, 插入操作：,若二叉排序樹為空，則新結(jié)點(diǎn)為二叉排序樹的根結(jié)點(diǎn)；否則將新結(jié)點(diǎn)的關(guān)鍵字值和根結(jié)點(diǎn)的關(guān)鍵字值進(jìn)行比較，若小于根結(jié)點(diǎn)的值，則將新結(jié)點(diǎn)插入到左子樹中去，否則，插入到右子樹中去。此插入過程是遞歸進(jìn)行的。, 設(shè)有整數(shù)序列47,23,56,15,26,89,將其中的值依次插入二叉排序樹,56,89,47,23,15,26, 刪除操作：,一個(gè)結(jié)點(diǎn)被刪除后，必須保證余下的結(jié)點(diǎn)仍然

6、構(gòu)成一棵二叉排序樹。下面分兩種情況討論：,情況一：被刪除的結(jié)點(diǎn)至少有一棵空子樹,方法：使被刪結(jié)點(diǎn)的那棵非空子樹的根成為其雙親結(jié)點(diǎn)的相應(yīng)子女,情況二：被刪除的結(jié)點(diǎn)有兩棵非空的子樹,方法一：找到被刪除結(jié)點(diǎn)在中序遍歷序列中的直接后繼結(jié)點(diǎn)（它一定在被刪除結(jié)點(diǎn)的右子樹中），用此后繼結(jié)點(diǎn)的值取代被刪除結(jié)點(diǎn)的值，然后刪除此后繼結(jié)點(diǎn)，由于被刪除的后繼結(jié)點(diǎn)的左子樹一定是空子樹，所以刪除后繼結(jié)點(diǎn)的過程同情況一。,方法二：用被刪除結(jié)點(diǎn)在中序遍歷序列中的直接前驅(qū)結(jié)點(diǎn)（該結(jié)點(diǎn)的右子樹也一定為空）代替被刪除的結(jié)點(diǎn)，然后刪除這個(gè)前驅(qū)結(jié)點(diǎn)。,后繼結(jié)點(diǎn),前驅(qū)結(jié)點(diǎn), 將結(jié)點(diǎn)50刪除, 中序遍歷：,10,15,30,33,35,3

7、7,50,53,55,62, 查找操作：,對(duì)二叉排序樹進(jìn)行中序遍歷可以得到一個(gè)數(shù)據(jù)元素由小到大的有序序列。構(gòu)造二叉排序樹的過程即為對(duì)無序序列進(jìn)行排序的過程。,查找思路：,當(dāng)二叉排序樹不為空時(shí)，將給定值與根結(jié)點(diǎn)的值進(jìn)行比較，若相等則查找成功。如果給定值小于根結(jié)點(diǎn)的值，則在根結(jié)點(diǎn)的左子樹中繼續(xù)查找，否則在根結(jié)點(diǎn)的右子樹中繼續(xù)查找。當(dāng)待查找的二叉排序樹為空時(shí)，查找失敗。,平均查找長(zhǎng)度：,在二叉排序樹中查找成功時(shí)走過的是一條從根結(jié)點(diǎn)到所尋找結(jié)點(diǎn)的一條路徑，因此，二叉排序樹查找的平均查找長(zhǎng)度取決于二叉排序樹的深度。, 二叉排序樹的蛻變：,二叉排序樹是動(dòng)態(tài)生成的，它的形態(tài)與各結(jié)點(diǎn)插入二叉排序樹時(shí)的先后順序

8、有關(guān)。當(dāng)把一組有序值依次插入到一棵二叉排序樹時(shí)，生成的二叉排序樹將蛻變成一棵單支樹。例如，由整數(shù)序列15,23,26,47,56,89 生成的二叉排序樹就是一棵單支樹。在單支樹中查找時(shí)，平均查找長(zhǎng)度與順序查找相同。,6. 哈希查找, 哈希存儲(chǔ)(哈希表)：,以數(shù)據(jù)元素的關(guān)鍵字k為自變量，通過一定的函數(shù)關(guān)系h(稱為哈希函數(shù)或散列函數(shù))計(jì)算出對(duì)應(yīng)的函數(shù)值h(k)，把這個(gè)值解釋為數(shù)據(jù)元素的存儲(chǔ)地址并把數(shù)據(jù)元素存儲(chǔ)到相應(yīng)的存儲(chǔ)單元內(nèi)。h(k)稱為哈希地址。, 沖突：,若有兩個(gè)不同的關(guān)鍵字ki和kj，即ki kj(i j)。但h(ki)=h(kj)，這種情況稱為沖突。如上例的關(guān)鍵字85和49，其對(duì)應(yīng)的哈希

9、地址都為1，即產(chǎn)生沖突。,例：設(shè)有一組關(guān)鍵字值85,72,49,58,15,70,90,38，哈希函數(shù)h(k) = k mod 12。則對(duì)應(yīng)的哈希地址為1,0,1,10,3,10,6,2, 采用哈希技術(shù)要解決的兩個(gè)主要問題：,構(gòu)造一個(gè)好的哈希函數(shù)，使出現(xiàn)沖突的機(jī)會(huì)盡可能少些；,設(shè)計(jì)一個(gè)有效的解決沖突的辦法, 哈希函數(shù)的構(gòu)造方法,構(gòu)造哈希函數(shù)要考慮以下幾點(diǎn),1) 哈希函數(shù)的定義域必須包括要存儲(chǔ)的數(shù)據(jù)元素的全部關(guān)鍵字; 而如果散列表允許有 m 個(gè)地址，則哈希函數(shù)的值域必須在 0 到 m-1 之間,2)由哈希函數(shù)計(jì)算出的地址應(yīng)均勻分布在散列地址空間內(nèi),3)哈希函數(shù)應(yīng)該是簡(jiǎn)單的，能在較短時(shí)間內(nèi)計(jì)算出結(jié)

10、果,直接定位法,取關(guān)鍵字的某個(gè)線性函數(shù)作為哈希函數(shù)，即h(k)=ak+b。其中，k為關(guān)鍵字，a、b為常數(shù)。,常用哈希函數(shù),數(shù)學(xué)分析法,當(dāng)關(guān)鍵字的位數(shù)比存儲(chǔ)區(qū)域地址碼的位數(shù)多時(shí)，可以取關(guān)鍵字中位值分布比較均勻的若干位作為哈希函數(shù)的值。這種方法適合于所有關(guān)鍵字為已知的情況。,除留余數(shù)法,選擇一個(gè)適當(dāng)?shù)恼麛?shù)p (p通常選為不大于哈希表長(zhǎng)度 m 的最大素?cái)?shù)），用p去除關(guān)鍵字，取其余數(shù)作為哈希地址，即h(k)=k%p (pm)。, 解決沖突的方法：開放地址法和鏈地址法,開放地址法,當(dāng)沖突發(fā)生時(shí)形成一個(gè)地址序列，按序列順序逐個(gè)檢查各地址單元，直至找到一個(gè)未被占用的單元為止，將發(fā)生沖突的數(shù)據(jù)元素存入該地址

11、單元中。,線性探查序列,平方探查序列,設(shè)哈希表的長(zhǎng)度是m，發(fā)生沖突的地址是d,d+1, d+2, , m-1, 0, 1, , d-1,(d+12)%m, (d-12)%m, (d+22)%m, (d-22)%m, ,例1,線性探查法建立哈希表,設(shè)哈希表的長(zhǎng)度11，哈希函數(shù)是h(k) = k % 11，將整數(shù)序列54,77,94,89,14,45,76存入哈希表。按平方探查法處理沖突,例2,0,1,2,3,4,5,6,7,8,9,10,54,77,94,89,54 % 11 = 10,77 % 11 = 0,94 % 11 = 6,89 % 11 = 1,14 % 11 = 3,45 % 11

12、 = 1 (沖突),76 % 11 = 10 (沖突),14,45,76,鏈地址法,將哈希地址相同的數(shù)據(jù)元素存儲(chǔ)到同一個(gè)單鏈表中，哈希表中的每個(gè)存儲(chǔ)單元中不再存放數(shù)據(jù)元素而是存放相應(yīng)單鏈表的頭指針,14.2 排序,1. 排序的基本概念, 排序：將文件中的記錄按排序碼非遞減(或非遞增)的順序重新排列, 排序碼：數(shù)據(jù)元素中的一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)。排序碼可以是關(guān)鍵字，也可以是其他若干數(shù)據(jù)項(xiàng)的組合。, 排序算法的穩(wěn)定性：如果在待排序的元素序列中，存在著多個(gè)排序碼相同的元素，按照某種排序算法排序后，這些元素的相對(duì)位置仍保持不變，則稱該排序算法是穩(wěn)定的，否則就是不穩(wěn)定的。,2. 插入排序, 基本思想：把元素e

13、i(0in) 依次插入到由S中前i個(gè)元素組成的已經(jīng)排好序的序列e0, e1, ,ei-1的適當(dāng)位置上，插入后S的前i+1個(gè)元素仍為有序。, 直接插入排序：,以順序查找的辦法找到要插入的元素在已排好序的元素序列中應(yīng)處的位置。 所有元素分成2個(gè)集合：已排序記錄集和待排序記錄集。初始時(shí)，已排序記錄集只有一個(gè)元素，即e0，待排序記錄集是所有剩余元素。然后每次從待排序記錄集中選取一個(gè)元素，使用順序查找的方法，找到其在已排序記錄集中的位置，將其插入到該位置，直到待排序記錄集為空。, 例：,待排序記錄為50,20,75,34,40,34,40,75,20,50, 直接插入排序的函數(shù)示例：, 算法分析：,直接

14、插入排序的平均時(shí)間復(fù)雜度是O(n2),直接插入排序是穩(wěn)定的排序算法,對(duì)于一個(gè)長(zhǎng)度較短、接近有序的序列，直接插入排序是十分有效的,在插入ei時(shí)，e0, e1, , ei-1是一個(gè)有序序列，所以可以用二分查找法尋找ei的插入位置，從而減少比較次數(shù)。 二分插入排序是穩(wěn)定的排序算法，其平均時(shí)間復(fù)雜度仍是O(n2), 二分插入排序：,3. 選擇排序, 基本思想：把元素ei(0in) 依次插入到由S中前i個(gè)元素組成的已經(jīng)排好序的序列e0, e1, ,ei-1的適當(dāng)位置上，插入后S的前i+1個(gè)元素仍為有序。,在初始時(shí)，已排好序的元素序列為空，待排序的元素序列中包括了需要排序的所有元素, 直接選擇排序：,基本

15、思想：用逐個(gè)比較的辦法從待排序的元素序列中選出最小的元素。依次對(duì)i=0, 1, 2, ,n-2分別執(zhí)行如下的選擇和交換步驟：在元素序列ei, ei+1, , en-1中選擇出最小的元素ek；當(dāng)ki時(shí)，交換ei與ek的值。經(jīng)上述n-1次的選擇和交換后，排序工作即已完成。,直接選擇排序函數(shù)模板：,直接選擇排序算法是不穩(wěn)定算法，其平均時(shí)間復(fù)雜度為O(n2), 演示：, 樹形選擇排序：,基本思想： 首先對(duì)n個(gè)待排序元素的排序碼兩兩進(jìn)行比較，得到 個(gè)比較的優(yōu)勝者（排序碼較小者），然后對(duì)這些優(yōu)勝者再進(jìn)行兩兩比較，如此反復(fù)，直至選出排序碼最小的元素。 在下一步選擇排序碼為次小的元素時(shí)，只需把樹當(dāng)中與已選出元

16、素對(duì)應(yīng)的葉結(jié)點(diǎn)的值設(shè)置為最大（），并從該葉結(jié)點(diǎn)開始和其兄弟結(jié)點(diǎn)進(jìn)行比較，修改從該葉結(jié)點(diǎn)到根結(jié)點(diǎn)路徑上各結(jié)點(diǎn)的值，即可選出排序碼次小的元素。,算法的時(shí)間復(fù)雜度O(nlog2n)，該算法是穩(wěn)定的。, 堆排序：,基本思想： 首先，用需要排序的元素的排序碼構(gòu)造一個(gè)堆（稱為建堆），這樣就可以找到排序碼最小的元素，將其取出；然后，用剩下的排序碼繼續(xù)建堆。如此反復(fù)進(jìn)行直至全部元素有序。,堆是一棵完全二叉樹，其中每個(gè)分支結(jié)點(diǎn)的值均小于或等于左、右子女的值。位于堆頂位置的結(jié)點(diǎn)（即完全二叉樹的根結(jié)點(diǎn)）的值是最小的。,堆排序的關(guān)鍵步驟有兩個(gè)：一是建立初始堆；二是在取出堆頂后把剩余的結(jié)點(diǎn)調(diào)整為堆。,首先，把所有元素的

17、排序碼組織到一棵完全二叉樹中。然后從完全二叉樹中結(jié)點(diǎn)編號(hào)排在最后的那個(gè)分支結(jié)點(diǎn)km( )開始，逐步地把以km、km-1、km-2為根的子樹建成堆，最后，當(dāng)以k0（k0是完全二叉樹的根結(jié)點(diǎn)）為根的完全二叉樹也是堆時(shí)，整個(gè)建堆過程也就完成了。,建立初始堆：,考慮以ki為根的子樹，設(shè)ki的左、右子樹均已是堆。為將該子樹也調(diào)整為堆，只需將ki與其左子女k2i+1和右子女k2i+2進(jìn)行比較。如果kik2i+1且kik2i+2，則以ki為根的子樹已經(jīng)是堆。否則，將ki與其最小的那個(gè)子結(jié)點(diǎn)（不妨設(shè)為k2i+1）交換位置。交換后，在以ki為根的子樹中，除了與其交換位置的子樹外，其余部分均滿足堆的定義，而以k2

18、i+1（其值由于與ki交換已發(fā)生了變化）為根的子樹的左、右子樹原來已經(jīng)是堆，這樣可使用前述過程將以k2i+1為根的子樹調(diào)整為堆。如此遞推下去，即可完成建堆工作。,建立初始堆示例：,無需交換,取出堆頂后將剩余結(jié)點(diǎn)調(diào)整為堆：,堆建成后，從堆頂取走值最小的結(jié)點(diǎn)，然后將最后一個(gè)結(jié)點(diǎn)kn-1提升到根結(jié)點(diǎn)的位置上，得到一棵新的完全二叉樹。雖然這棵二叉樹可能不是堆，但其左、右子樹都是堆。因此，當(dāng)把此二叉樹調(diào)整為堆時(shí)，只需從根結(jié)點(diǎn)開始自上而下地進(jìn)行調(diào)整即可。,具體示例見教材圖14.10,子樹調(diào)整為堆的模板函數(shù)：,演示, 算法分析：,堆排序算法的時(shí)間復(fù)雜度為O(nlog2n),堆排序算法是不穩(wěn)定的,如果需要排序的元素?cái)?shù)目較少一般并不提倡使用堆排序算法，但如果元素?cái)?shù)目較多，堆排序算法還是很有效的, 冒泡排序：,設(shè)待排序的元素序列為S=e0, e1, , en-1，要求按升序排列,基本思想： 從待排序記錄集的一端（這里假定為低端）對(duì)相鄰的兩個(gè)元素（e0和e1，e1和e2，en-2和en-1）依次比較它們的排序碼，若不符合排序的順序要求，就將相應(yīng)的兩個(gè)元素互換，此過程稱為一趟冒泡排序，最多經(jīng)過n-1趟冒泡排序，排序工作即可完成。,每趟排序的結(jié)果是將待排序記錄集中排序碼最大的元素交換到待排序記錄集最后一個(gè)元素的位置。假設(shè)在一趟冒泡排序時(shí)，從ej+1以后沒有發(fā)生元素的互換，則說明ej+1以后