數(shù)據(jù)結(jié)構(gòu)課件第九章

查找和排序是數(shù)據(jù)處理系統(tǒng)中最重要的兩個操作；其次是插入、刪除操作；討論查找、排序，不可避免要涉及文件、記錄、關(guān)鍵字等概念。文件——查找表，是由同一類型的數(shù)據(jù)元素(記錄)構(gòu)成的集合記錄——構(gòu)成文件的數(shù)據(jù)元素，是文件中可存取的數(shù)據(jù)的基本單位字段——數(shù)據(jù)項，數(shù)據(jù)的最小單位關(guān)鍵字——某個可以用來標(biāo)識記錄的數(shù)據(jù)項主關(guān)鍵字——某個可以用來唯一標(biāo)識記錄的數(shù)據(jù)項次關(guān)鍵字——可以用來識別若干記錄的數(shù)據(jù)項第九章查找數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第1頁!D01曲守寧數(shù)據(jù)庫004S01王永燕數(shù)據(jù)結(jié)構(gòu)003L01潘玉奇程序設(shè)計002S01嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)001………………………課程號課程名教師課程類別課程安排表文件記錄數(shù)據(jù)項主關(guān)鍵字次關(guān)鍵字?jǐn)?shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第2頁!對文件經(jīng)常進(jìn)行的操作有:1)查詢某個“特定”的數(shù)據(jù)元素是否存在4)對數(shù)據(jù)元素進(jìn)行排序2)插入某個數(shù)據(jù)元素3)刪除某個數(shù)據(jù)元素查找算法排序算法不管何種操作，都遵循一個重要的性質(zhì):都是對主關(guān)鍵字操作數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第3頁!9.1靜態(tài)查找9.1.1順序查找從表最后一個記錄開始，逐個向前進(jìn)行記錄關(guān)鍵字和給定值的比較，相等，查找成功；不等，比較下一個記錄；思想:直至個記錄，若均不等，則查找不成功。數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第4頁!9.1.2有序表的查找表中數(shù)據(jù)元素按照主關(guān)鍵字順序排列。折半查找斐波那契查找插值查找5，13，19，21，37，56，64，75，80，88，92數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第5頁!9.2動態(tài)查找表靜態(tài)查找只是對表中元素進(jìn)行檢索，返回成功或不成功；動態(tài)查找不但對表中元素進(jìn)行檢索，還可以通過檢索過程來實現(xiàn)表的更新；檢索到，則返回成功；檢索不到，則將新元素插入到表中適當(dāng)位置。數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第6頁!查詢操作:

13

8523

1837如何查找元素5?555查找成功！數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第7頁!同一序列，不同二叉排序樹的查找性能差別很大。例，{45,24,53,12,37,93}452453123793122437455393O(n)O(log

n+1)數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第8頁!例,ABCDABCDEFGABCDEFABCDFGE數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第9頁!如何在二叉排序樹的構(gòu)造過程中實現(xiàn)平衡化從而得到平衡二叉樹？例，序列{1324379053}13024-1037-2-10左旋，以失去平衡結(jié)點的兒子結(jié)點為基準(zhǔn)。37241300090-10-1053-20-210先右旋，以失去平衡結(jié)點的兒子結(jié)點為基準(zhǔn)。再左旋，以失去平衡結(jié)點的兒子結(jié)點為基準(zhǔn)。53905390370-1000平衡！數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第10頁!LL型:新結(jié)點加入到左子樹的左子樹中。11021調(diào)整規(guī)則:右旋，以失去平衡的結(jié)點的兒子結(jié)點為基準(zhǔn)，整棵子樹向右下方旋轉(zhuǎn)。ABBLBRARBABRARBL00數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第11頁!LR型:新結(jié)點加入到左子樹的右子樹中。1調(diào)整規(guī)則:ABBLARCCLCR先左旋，以失去平衡的結(jié)點的兒子結(jié)點為基準(zhǔn)，構(gòu)造成LL型。后右旋。1002-11數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第12頁!例，設(shè)關(guān)鍵字為年齡字段，H(key)=key年齡學(xué)號姓名01020356100........................12356100192021192021......張三王五李據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第13頁!(2)數(shù)字分析法對關(guān)鍵字進(jìn)行按“位”分析，取重復(fù)度小的若干位組合成哈希地址。例，多條記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，要求取兩位作為哈希地址。813465377137224781387422823013678142281781338967取4、5、6、7位中的任意兩位即可。數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第14頁!(4)折疊法將關(guān)鍵字從低到高分割成位數(shù)相同的幾部分，然后取各部分的疊加和(舍去進(jìn)位)作為哈希函數(shù)。例，圖書編號0–442–20586–404422058645864422004+)10088最終取四位0088作為哈希地址。數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第15頁!(6)隨機(jī)數(shù)法取關(guān)鍵字的隨機(jī)函數(shù)值作為哈希地址。H(key)=random(key)總結(jié):靈活運用協(xié)同工作數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第16頁!例，除留余數(shù)法中關(guān)鍵字28356377105p=21哈希地址7140140解決方法:因地制宜提高素質(zhì)數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第17頁!(1)開放定址法H(key)=(key)modm在keymodm的基礎(chǔ)上，若發(fā)現(xiàn)沖突，則使用增量di進(jìn)行新的探測，直至無沖突出現(xiàn)為止。H(key)哈希函數(shù)m哈希表長di增量序列關(guān)鍵如何設(shè)計di線性探測法二次探測法隨機(jī)探測法H(key)=(key+di

)modm數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第18頁!(2)再哈希法定義雙重哈希函數(shù)。H(key)R

(key)若H(key)出現(xiàn)沖突，則再使用R

(key)求取哈希地址。數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第19頁!二分查找法要求查找表中各元素的鍵值必須是()排列。

A．遞增或遞減B．遞增C．遞減D．無序數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第20頁!從一棵二叉排序樹中查找一個元素時，其平均時間復(fù)雜度為()。A．O(1)B．O(n)C．O(1og2n)D．O(n2)

數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第21頁!從有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素時，其查找長度分別為__________和__________。向一棵二叉排序樹中插入一個元素時，若元素的值小于根結(jié)點的值，則應(yīng)把它插入到根結(jié)點的__________子樹上。數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第22頁!數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第23頁!12...n-2n-1nTomAnnieJohnRoseJack查找John比較2次查找Jack比較n-1次若查找不存在比較n次數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第24頁!折半查找5，13，19，21，37，56，64，75，80，88，92lowhighmid=(low+high)/2查找211234567891011midmid=6high=mid–1=5highmid=3midlow

=mid+1=4lowmid=4mid找到查找85lowhighmid=6midlow

=mid+1=7lowmid=9midlow

=mid+1=10lowmid=10midhigh=mid–1=9highhigh<low查找不成功數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第25頁!9.2.1二叉排序樹(二叉分類樹)二叉排序樹或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：

(1)左子樹上所有結(jié)點的值均小于等于它的根結(jié)點的值；

(2)右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；

(3)根結(jié)點的左、右子樹也分別為二叉排序樹。

13

8523

1837數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第26頁!

13

8523

1837如何查找元素9?99

9查詢+插入操作:查找不成功，執(zhí)行插入。數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第27頁!為了實現(xiàn)二叉排序樹的平均查找長度和log

n等數(shù)量級，需要對二叉排序樹進(jìn)行“平衡化”處理，即構(gòu)造平衡二叉樹。9.2.2平衡二叉樹——AVL樹Adelson—Velskii—Landis平衡二叉樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹:其左子樹和右子樹的深度之差的絕對值不超過1；其左子樹和右子樹都是平衡二叉樹；平衡二叉樹首先是一棵二叉排序樹；數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第28頁!結(jié)點的平衡因子:該結(jié)點的左子樹的深度減去右子樹的深度。由于平衡二叉樹要求左右子樹深度之差的絕對值不大于1，故結(jié)點的平衡因子只可能為-1、0、1。4524531293例，0100-1可以證明平衡二叉樹的深度與logn同數(shù)量級。數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第29頁!平衡二叉樹調(diào)整規(guī)則:RR型:新結(jié)點加入到右子樹的右子樹中。1調(diào)整規(guī)則:左旋，以失去平衡的結(jié)點的兒子結(jié)點為基準(zhǔn)，整棵子樹向左下方旋轉(zhuǎn)。ABBLBRAL-10-2-1BAALBLBR00數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第30頁!RL型:新結(jié)點加入到右子樹的左子樹中。1調(diào)整規(guī)則:ABBRALCCLCR-100-211先右旋，以失去平衡的結(jié)點的兒子結(jié)點為基準(zhǔn)，構(gòu)造成RR型。后左旋。ACCLALBCRBR-2-1-1CBCLALACRBR0-10數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第31頁!9.3哈希表前面介紹的內(nèi)容中，記錄在文件中的存儲地址是隨機(jī)的三李四王五192120200305200301200302李四王五張三212019查找某一條記錄需要進(jìn)行一系列的“比較”。查找的效率依賴于比較的次數(shù)。能否在記錄的關(guān)鍵字和存儲地址之間構(gòu)造這樣一種關(guān)系f，使得關(guān)鍵字和存儲地址一一對應(yīng)？此對應(yīng)關(guān)系f稱為哈希函數(shù)。學(xué)號姓名年齡010203數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第32頁!1.哈希函數(shù)的構(gòu)造方法(1)直接定址法取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。H(key)=key(i)或H

(

key)=akey+b.(ii)(i)例，以年齡作為關(guān)鍵字(ii)例，統(tǒng)計解放后出生人口，以出生年份作為關(guān)鍵字地址出生年份011949021950231971481996..................H(key)=key–1949+1數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第33頁!(3)平方取中法取關(guān)鍵字平方后的中間幾位作為哈希函數(shù)。實驗證明:一個數(shù)字的平方值的中間部分通常對各位數(shù)字都比較敏感。200524200502012005022005032005X402098745764020105200400144120025X20048422002501024320025209820101441取4位48420243數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第34頁!(5)除留余數(shù)法H(key)=keymod

p例，關(guān)鍵字28336882107p=21哈希地址7125192數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第35頁!2.哈希沖突對于不同的關(guān)鍵字可能得到同一哈希地址，即key1≠key2，而f(key1)＝f(key2)，這種現(xiàn)象稱為哈希沖突。造成原因:A.主觀設(shè)計不當(dāng)例，數(shù)字分析法中813465377137224781387422823013678142281781338967沖突！數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第36頁!B.客觀存在如何設(shè)計都不可能完全避免沖突的出現(xiàn)？哈希地址是有限的，而記錄是無限的。解決方法:(1)開放定址法(2)再哈希法(3)鏈地址法(4)建立一個公共溢出區(qū)數(shù)據(jù)結(jié)構(gòu)課件第九章共43頁，您現(xiàn)在瀏覽的是第37頁!線性探測法di=1,2,3,…,m-1隨機(jī)探測法di=

隨機(jī)數(shù)二次探測法di=12,-12,22,-22,32,…,+k2-例，關(guān)鍵字為(17,60,29,38)，哈希表長11，H(ke