軟件技術(shù)基礎(chǔ)新課件(查找與排序).ppt

1、第 1 /209頁(yè),第2篇 數(shù)據(jù)結(jié)構(gòu),南昌大學(xué) 機(jī)電工程學(xué)院 涂海寧C,第 2 /209頁(yè),第13章 查 找 和 排 序,第 3 /209頁(yè),1、線性查找,查找(Searching)，也稱檢索，亦即查表，就是在大量的信息集中尋找一個(gè)“特定的”信息元素。人們幾乎每天都要做“查找”工作，如查尋電話號(hào)碼、查字典、查圖書目錄卡片等。為確切定義查找，先引入幾個(gè)概念。 查找表：由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。,第 4 /209頁(yè),關(guān)鍵字(key)：數(shù)據(jù)元素中可以惟一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。如學(xué)生的學(xué)號(hào)，居民身份證號(hào)等。 查找就是根據(jù)給定的關(guān)鍵字值，在查找表中確定一個(gè)關(guān)

2、鍵字等于給定值的記錄或數(shù)據(jù)元素。若存在這樣的數(shù)據(jù)元素，則稱查找是成功的，否則稱查找不成功。 決定查找操作的是關(guān)鍵字，因此這里討論時(shí)，只關(guān)注記錄中的關(guān)鍵字域，而一概忽略記錄中其它諸域的信息。,第 5 /209頁(yè),查找是最耗費(fèi)時(shí)間的部分，查找算法的優(yōu)劣密切關(guān)系著查找操作的速度，因此對(duì)查找算法應(yīng)認(rèn)真研究。 關(guān)于查找，目前主要研究?jī)煞矫娴膯栴}： (1) 查找的方法。 因?yàn)椴檎夷硞€(gè)數(shù)據(jù)元素依賴于該數(shù)據(jù)元素在一組數(shù)據(jù)中所處的位置，即該組數(shù)據(jù)的組織方式，故應(yīng)按照數(shù)據(jù)元素的組織方式?jīng)Q定采用的查找方法；反過來，為了提高查找方法的效率，要求數(shù)據(jù)元素采用某些特殊的組織方式。,第 6 /209頁(yè),(2) 查找算法的評(píng)

3、價(jià)。 衡量算法的標(biāo)準(zhǔn)主要有兩個(gè)：時(shí)間復(fù)雜度和空間復(fù)雜度。查找算法一般只需很少的輔助空間，因此更關(guān)心的是它的時(shí)間復(fù)雜度。 在查找算法中，基本運(yùn)算是給定值與關(guān)鍵字的比較，所以算法的主要時(shí)間是花費(fèi)在“比較”上。 下面用平均查找長(zhǎng)度的概念，來評(píng)價(jià)查找算法的好壞。,第 7 /209頁(yè),對(duì)于含有n個(gè)數(shù)據(jù)元素的查找表，查找成功時(shí)的平均查找長(zhǎng)度為,ASL =,其中，Pi為查找第i個(gè)數(shù)據(jù)元素的概率；Ci為查到第i個(gè)數(shù)據(jù)元素時(shí)，需與關(guān)鍵字進(jìn)行比較的次數(shù)。,第 8 /209頁(yè),線性查找 線性查找也稱順序查找，是最簡(jiǎn)單、常用的查找技術(shù)。 基本思想是：從表的一端開始，依次將每個(gè)元素的關(guān)鍵字同給定值K進(jìn)行比較，若某個(gè)元素

4、的關(guān)鍵字等于給定值K，則表明查找成功，返回該元素的下標(biāo)；反之，若直到所有元素都比較完畢，仍找不到關(guān)鍵字為K的元素，則表明查找失敗，返回特定的值。,第 9 /209頁(yè),順序查找方法既適用于以順序存儲(chǔ)結(jié)構(gòu)，也適用于以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在本章的有關(guān)查找和排序算法中，假設(shè)線性表均采用順序存儲(chǔ)結(jié)構(gòu)，其類型說明為：,第 10 /209頁(yè),#define MAXLEN n/* n為查找表中元素個(gè)數(shù)的最大可能值*/ struct element int key; /*設(shè)關(guān)鍵字的類型為整型*/ int otherterm;/*為說明起見，除關(guān)鍵字外只有一個(gè)整型數(shù)據(jù)項(xiàng)*/ ; typedef struct eleme

5、nt DATATYPE; DATATYPE tableMAXLEN;,第 11 /209頁(yè),算法 順序查找算法。 int seqsearch1(DATATYPE A, int k) int i=0; while(Ai.key!=k) /*查找失敗，返回1*/ 若對(duì)此算法進(jìn)行一些改進(jìn)，在表尾增加一個(gè)關(guān)鍵字為指定值K的記錄(即所謂的“前哨”)，可避免每“比較”一次，就要判別查找是否結(jié)束。當(dāng)n很大時(shí)，大約可節(jié)省一半的時(shí)間。,第 12 /209頁(yè),算法 改進(jìn)的（即增加“前哨” ）順序查找算法。 #define MAXLEN n+1 int seqsearch2(DATATYPE A,int k) in

6、t i=0； AMAXLEN1.key=k; while (Ai.key!=k) i+; if(iMAXLEN1) return i; /*查找成功，返回被查元素相對(duì)位置*/ else return 1; /*查找失敗，返回1*/ ,第 13 /209頁(yè),將AMAXLEN1稱作監(jiān)視哨，這個(gè)增加的記錄起到了邊界標(biāo)識(shí)的作用。 下面對(duì)改進(jìn)后的算法進(jìn)行一下性能分析，計(jì)算它的平均查找長(zhǎng)度。 對(duì)含有n個(gè)記錄的表，查找成功時(shí)的平均查找長(zhǎng)度為：,ASL =,從順序查找的過程看，Ci取決于所查元素在表中的位置，對(duì)于第一個(gè)記錄只要比較一次，對(duì)第n個(gè)記錄，需要比較n次，查找記錄Ai時(shí)，比較i次。設(shè)每個(gè)記錄的查找概率

7、相等，則Pi=1/n 。故此算法在等概率情況下查找成功的平均查找長(zhǎng)度為,ASL =,第 14 /209頁(yè),2、折半查找 如果查找表中的記錄按關(guān)鍵字排序，則可以采用一種高效率的查找方法折半查找，也稱二分查找。 基本思想是： 對(duì)于有序表，查找時(shí)先取表中間位置的記錄關(guān)鍵字與所給值進(jìn)行比較，若相等，則查找成功； 如果給定值大，則在后半部分繼續(xù)進(jìn)行折半查找； 否則在前半部分進(jìn)行折半查找，直到找到或者查找范圍為空而查不到為止。,第 15 /209頁(yè),折半查找的過程實(shí)際上是先確定待查元素所在的區(qū)域，然后逐步縮小區(qū)域，直到查找成功或失敗為止。 算法中需要用到三個(gè)變量,low表示區(qū)域下界,high表示上界,中間

8、位置mid=(low+high)DIV 2。 由于折半查找要求數(shù)據(jù)元素的組織方式應(yīng)具有隨機(jī)存取的特性，所以它只適用于以順序存儲(chǔ)結(jié)構(gòu)的有序（排序）表。,第 16 /209頁(yè),算法 折半查找算法。 #define MAXLEN n int binsearch(DATATYPE A, int k) int low=0,mid,high= MAXLEN1; while (lowAmid.key) low=mid+1; elsehigh=mid1; return 1;/*查找失敗，返回1*/ ,第 17 /209頁(yè),折半查找成功的平均查找長(zhǎng)度為 ASLbslog2 (n+1) 1(求解過程從略) 折半查

9、找的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，但只能對(duì)有序表進(jìn)行查找。它適用于一經(jīng)建立就很少變動(dòng)而又經(jīng)常需進(jìn)行查找的有序表。,第 18 /209頁(yè),例 一有序表的關(guān)鍵字序列為(5，12，18，20，35，50，64，72，80，88，95)，表長(zhǎng)為11，采用折半查找求其在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。 解：按照折半查找算法，對(duì)序列中11個(gè)元素的查找過程如下： (1) mid =(1+11)DIV 2 查到第6個(gè)元素50，比較1次； (2) mid =(1+5)DIV 2 查到第3個(gè)元素18，比較2次； 或mid =(7+11)DIV 2 查到第9個(gè)元素80，比較2次； (3) 依次類推，查到第1、

10、4、7和第10個(gè)元素需比較3次；查到第2、5、8和第11個(gè)元素需比較4次。,第 19 /209頁(yè),這個(gè)查找過程可用一棵二叉樹表示。 這種描述查找過程的二叉樹為判定樹，若樹中每個(gè)結(jié)點(diǎn)表示一個(gè)記錄， 結(jié)點(diǎn)中的值為該記錄在表中的位置。 結(jié)點(diǎn)在樹中所處的層數(shù)，即為采用折半查找此結(jié)點(diǎn)的步數(shù)（比較的次數(shù)）。步數(shù)最多不超過樹的深度,第 20 /209頁(yè),3、分塊查找 分塊查找又稱索引順序查找，這是順序查找的另一種改進(jìn)方法。 順序查找速度慢；而折半查找雖速度快，但要將線性表按關(guān)鍵字排序，而且必須采取順序存儲(chǔ)。在順序結(jié)構(gòu)里執(zhí)行插入、刪除操作都很困難。 如果要處理的線性表既希望較快的檢索又需要存儲(chǔ)結(jié)構(gòu)靈活，可以采

11、用分塊查找。 分塊查找是順序查找和折半查找的折衷方案，特別適用于索引存儲(chǔ)結(jié)構(gòu)。,第 21 /209頁(yè),分塊查找基本思想： 按照表內(nèi)記錄的某種屬性（關(guān)鍵字）把表分成n(n1)個(gè)塊(子表)，每一塊中記錄的存放是任意的，但是塊與塊之間是有序的，即所謂“分塊有序”。 假如按關(guān)鍵字遞增順序進(jìn)行分塊排列，就是指第j塊的所有記錄的關(guān)鍵字均大于第j1塊的所有記錄的關(guān)鍵字(j=2,3,n)，并建立一個(gè)索引表。把每塊中的最大關(guān)鍵字值及每塊的第一個(gè)記錄在表中的位置存放在索引項(xiàng)中。 整個(gè)查找過程分兩步進(jìn)行： (1) 確定待查記錄所在的塊。 (2) 在塊內(nèi)按順序查找。,第 22 /209頁(yè),例 設(shè)給定值K=32，在圖4

12、-2所示的索引順序表中查找關(guān)鍵字等于K的記錄。,第 23 /209頁(yè),解：在圖4-2的表中有18個(gè)記錄，分成了三個(gè)子表(R1，R2，R6)，(R7，R8，R12)，(R13，R14，R18)。 先將K依次和索引表中各最大關(guān)鍵字進(jìn)行比較，因?yàn)?5K45，則關(guān)鍵字為32的記錄若存在，必定在第二個(gè)子表(塊)中。 從第二塊的第一個(gè)記錄，即表中的第7個(gè)記錄起進(jìn)行順序查找，直到r12.key=K為止。假如此塊中沒有關(guān)鍵字等于K的記錄，則查找不成功。 由于索引項(xiàng)的組成按關(guān)鍵字有序，則確定塊的查找可以用順序查找，亦可以用折半查找。而塊中記錄是任意排列的，則在塊中只能是順序查找。,第 24 /209頁(yè),分塊查找

13、的優(yōu)點(diǎn)是在表中插入或刪除一個(gè)元素時(shí)，只要找到該元素所屬的塊，然后在塊內(nèi)進(jìn)行插入和刪除。因?yàn)閴K內(nèi)元素的存放是任意的，所以插入和刪除時(shí)不需移動(dòng)大量元素。所付出的代價(jià)是增加了存放索引表的輔助空間。分塊查找也是常用的一種查找方法。,第 25 /209頁(yè),4、二叉排序樹的查找 在順序查找、折半查找和分塊查找方法中，折半查找的效率最高，要求數(shù)據(jù)元素按關(guān)鍵字排序，且不能用鏈表作存儲(chǔ)結(jié)構(gòu)。在對(duì)數(shù)據(jù)元素的插入和刪除操作時(shí)，為了保持查找表的有序性，勢(shì)必要移動(dòng)很多記錄，造成新的時(shí)間開銷。 當(dāng)插入和刪除頻繁進(jìn)行時(shí)，這種額外開銷就會(huì)抵消折半查找的優(yōu)點(diǎn)。,第 26 /209頁(yè),若我們對(duì)查找表只作查找運(yùn)算，則稱該表為靜態(tài)查

14、找表。 若對(duì)查找表既允許進(jìn)行查找運(yùn)算，又允許進(jìn)行插入和刪除運(yùn)算，則稱該表為動(dòng)態(tài)查找表。 前一節(jié)介紹的查找方法主要適用于靜態(tài)查找表的查找，所以可稱其為靜態(tài)查找算法。對(duì)于動(dòng)態(tài)查找表，為了能在其上方便地進(jìn)行插入和刪除操作，應(yīng)尋求相應(yīng)的動(dòng)態(tài)查找算法。 為滿足這種要求，需采用樹表，包括二叉排序樹、二叉平衡樹、B樹、B+樹、鍵樹，這里我們只介紹二叉排序樹的查找。,第 27 /209頁(yè),1二叉排序樹的查找 二叉排序樹(binary sort tree)或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹。 (1) 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； (2) 若它的右子樹不空，則右子樹上所有

15、結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值； (3) 它的左、右子樹也分別為二叉排序樹。,第 28 /209頁(yè),二叉排序樹示例,第 29 /209頁(yè),二叉排序樹的中序遍歷，是一個(gè)有序序列（順序）。 故用這種方式存儲(chǔ)表，可以把順序表中折半查找速度快的優(yōu)點(diǎn)與鏈?zhǔn)浇Y(jié)構(gòu)中插入、刪除方便的優(yōu)點(diǎn)結(jié)合起來，使查找表既具有順序表那樣高的檢索效率，又具有鏈表那樣插入、刪除運(yùn)算的靈活性。,第 30 /209頁(yè),二叉排序樹查找的思想是： (1) 當(dāng)二叉排序樹不空時(shí)，首先將給定值K與根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較，若相等則查找成功； (2) 若給定值K小于根結(jié)點(diǎn)的值，則繼續(xù)在根的左子樹中查找；若給定值K大于根結(jié)點(diǎn)的值，則繼續(xù)在根的右

16、子樹中查找。 顯然這是一個(gè)遞歸查找過程。,第 31 /209頁(yè),2二叉排序樹的生成 對(duì)一組數(shù)據(jù)序列K1，K2，Kn，先設(shè)一棵空二叉樹，然后依次將序列中的元素生成結(jié)點(diǎn)后逐個(gè)插入到已生成的二叉排序樹中。步驟如下： (1) K1是二叉排序樹的根； (2) 若K2K1，則K2所在的結(jié)點(diǎn)應(yīng)插入到K1的左子樹上；否則插入到K1的右子樹上； (3) 讀Ki，若Ki K1(根)，則插入到根的左子樹上，否則Ki插入到根的右子樹上； (4) 若in，則繼續(xù)執(zhí)行步驟(3)，否則結(jié)束。,第 32 /209頁(yè),例 設(shè)有一組關(guān)鍵字序列為(48，24，53，20，35，90)，構(gòu)造二叉排序樹。,此二叉樹的中序遍歷是？,第

17、33 /209頁(yè),二叉排序樹的查找分析 二叉排序樹的平均查找長(zhǎng)度取決于二叉排序樹的深度。 這與折半查找類似（取決于其判定樹）。 然而，折半查找長(zhǎng)度為n的表的判定樹是惟一的，而含有n個(gè)結(jié)點(diǎn)的二叉排序樹卻不惟一。 所以，二叉排序樹查找成功的平均查找長(zhǎng)度取決于二叉排序樹的形狀，而二叉排序樹的形狀既與結(jié)點(diǎn)數(shù)目有關(guān)，更取決于建立二叉排序樹時(shí)結(jié)點(diǎn)的插入順序。,第 34 /209頁(yè),例 已知長(zhǎng)度為6的線性表是(45，24，53，13，30，85)，若按表中元素的順序依次插入，得到二叉排序樹如圖 (a)所示；若依次序13,24,30,45，53，85插入，得到二叉排序樹為圖 (b)所示,第 35 /209頁(yè),

18、二叉排序樹查找的平均比較次數(shù)取決于二叉樹的深度。 最好情況是：所生成的二叉排序樹中，任一結(jié)點(diǎn)的左、右子樹的深度相差都不超過1，即二叉排序樹是一棵平衡二叉樹。 最壞情況是：所生成的二叉排序樹蛻化為單支樹時(shí)，其平均比較次數(shù)就和順序查找相同了。,第 36 /209頁(yè),4、 散列（ 哈 希 查 找）,無(wú)論是順序查找、折半查找、分塊查找，還是二叉排序樹查找，都需進(jìn)行一系列和關(guān)鍵字的比較才能確定被查元素在查找表中的位置，查找的效率依賴于查找過程中所進(jìn)行的比較次數(shù)。 而哈希查找的思想與前面四種方法完全不同，哈希查找方法是利用關(guān)鍵字進(jìn)行某種運(yùn)算后直接確定元素的存儲(chǔ)位置，所以哈希查找方法是用關(guān)鍵字進(jìn)行計(jì)算元素存

19、儲(chǔ)位置的查找方法。 非常適用于數(shù)據(jù)元素長(zhǎng)度不等情況，如文件系統(tǒng),第 37 /209頁(yè),在討論哈希查找之前，先討論適用于哈希查找的查找表的組織方式哈希表。 4.3.1 哈希表的建立 哈希表的建立：以線性表中的每個(gè)元素的關(guān)鍵字K為自變量，通過一種函數(shù)H(K)計(jì)算出函數(shù)值，然后將該元素存入與該函數(shù)值相應(yīng)的存儲(chǔ)單元中。 查找時(shí)，只要根據(jù)要查找的關(guān)鍵字用同樣的函數(shù)計(jì)算出地址H(K)，然后直接到相應(yīng)的單元中去取所要找的元素。 通過函數(shù)H(K)計(jì)算的函數(shù)值建立起來的符號(hào)（地址）表就稱為哈希表。,第 38 /209頁(yè),問題：對(duì)同一個(gè)哈希函數(shù)H(K)和兩個(gè)關(guān)鍵字K1和K2，如果K1K2，而H(K1)=H(K2)

20、，這種現(xiàn)象稱為沖突。 在構(gòu)造哈希函數(shù)時(shí)應(yīng)避免沖突。但沒有沖突的函數(shù)是很不好找的，因?yàn)橥ǔ９：瘮?shù)是一個(gè)壓縮映象，即關(guān)鍵字集合大，地址集合小。一般只能盡可能地避免沖突的發(fā)生。 例如，一個(gè)符號(hào)表其標(biāo)識(shí)符至多由5個(gè)英文字母組成，則不同的標(biāo)識(shí)符可能有 265+264+263+262+26=12 356 630 (個(gè))。 如果一個(gè)標(biāo)識(shí)符對(duì)應(yīng)一個(gè)存儲(chǔ)地址，就不會(huì)發(fā)生沖突了，但這是不可能也沒有必要的。因?yàn)榇鎯?chǔ)空間難以滿足，而且任何一個(gè)源程序也不會(huì)有這么多的標(biāo)識(shí)符。,第 39 /209頁(yè),由于哈希法用哈希函數(shù)轉(zhuǎn)換記錄關(guān)鍵字得到存儲(chǔ)地址，把各記錄散列到相應(yīng)的存儲(chǔ)單元里去，所以也稱之為散列地址法或關(guān)鍵字轉(zhuǎn)換法。

21、對(duì)于哈希法，主要考慮兩個(gè)問題： (1) 構(gòu)造一個(gè)合適的哈希函數(shù)。分析數(shù)據(jù)元素的關(guān)鍵字集合之特點(diǎn)，找出適當(dāng)?shù)暮瘮?shù)H(K)，使計(jì)算出的存儲(chǔ)地址盡可能均勻地分布在哈希表中；同時(shí)也希望函數(shù)H(K)盡量簡(jiǎn)單，便于快速計(jì)算；哈希函數(shù)H(K)一般應(yīng)是一個(gè)壓縮映象函數(shù)，它應(yīng)具有較大的壓縮性，以節(jié)省存儲(chǔ)空間。,第 40 /209頁(yè),常用的構(gòu)造哈希函數(shù)的方法有： 數(shù)字分析法； 平方取中法； 折疊法； 除留余數(shù)法； 直接定址法； 隨機(jī)數(shù)法。,第 41 /209頁(yè),(2) 如何解決沖突。哈希函數(shù)應(yīng)具有較好的散列性，沖突是不可避免的，但應(yīng)盡量減少。若已知哈希函數(shù)及沖突處理方法，哈希表的建立步驟如下： Step1：取出一

22、個(gè)數(shù)據(jù)元素的關(guān)鍵字Key，計(jì)算其在哈希表中的存儲(chǔ)地址D=H(Key)。若存儲(chǔ)地址為D的存儲(chǔ)空間還沒有被占用，則將該數(shù)據(jù)元素存入；否則發(fā)生沖突，執(zhí)行Step2。 Step2：根據(jù)規(guī)定的沖突處理方法，計(jì)算關(guān)鍵字為Key的數(shù)據(jù)元素的下一個(gè)存儲(chǔ)地址。若該存儲(chǔ)地址的存儲(chǔ)空間沒有被占用，則存入；否則繼續(xù)執(zhí)行Step2，直到找出一個(gè)存儲(chǔ)空間沒有被占用的存儲(chǔ)地址為止。 Step3：重復(fù)Step1和Step2，直到所有的數(shù)據(jù)元素都被存儲(chǔ)為止。,第 42 /209頁(yè),4.3.2 處理沖突的方法 哈希法中不可避免地會(huì)出現(xiàn)沖突現(xiàn)象，所以關(guān)鍵的問題是如何解決沖突。處理沖突的方法多種多樣，常用的方法有：開放定址法、鏈地址

23、法、再哈希法和公共溢出區(qū)法。只介紹前兩種方法。 沖突是指H(K)的位置上已存有記錄，則“處理沖突”就是為該關(guān)鍵字的記錄找到另一個(gè)“空”的哈希地址。若得到的另一個(gè)哈希地址H1仍然發(fā)生沖突，則再求下一個(gè)地址H2，若H2仍沖突，再求H3，依次類推，直至Hk不發(fā)生沖突為止，則Hk為記錄在表中的地址。,第 43 /209頁(yè),1開放定址法 Hi =(H(key) + di)MOD m i=1，2，k (km1) 這里，m為哈希表表長(zhǎng)；di為增量序列。 按照增量序列的不同取法，開放定址法又分為線性探測(cè)再散列和二次探測(cè)再散列。 (1) 線性探測(cè)再散列 di=1，2，3，m1 (2) 二次探測(cè)再散列 di=12

24、，12，22，22，32，K2，K2 (Km/2),第 44 /209頁(yè),例如，哈希表中已填有關(guān)鍵字21，52，73的記錄，哈希函數(shù)為H(key)=key MOD 10。 現(xiàn)有第四個(gè)記錄，其關(guān)鍵字為82，由哈希函數(shù)得到的哈希地址為2，產(chǎn)生沖突。若用線性探測(cè)再散列處理沖突，得到的下一個(gè)地址為3，仍沖突；再求下一個(gè)地址為4，此地址為空，將82存入。,第 45 /209頁(yè),第 46 /209頁(yè),2鏈地址法 將所有具有相同哈希地址的記錄存儲(chǔ)在同一個(gè)單鏈表中。即H(K1)=H(K2)=H(K3)，稱K1，K2和K3為同義詞，鏈地址法就是將所有關(guān)鍵字為同義詞的記錄鏈在一起。這一點(diǎn)與鄰接表的思想非常類似。

25、例如將上例中處理沖突的方法改為鏈地址法，插入82和72后的情況如圖4-7所示。,第 47 /209頁(yè),用鏈地址法處理沖突產(chǎn)生的哈希表,第 48 /209頁(yè),4.3.3 哈希查找 在哈希表上查找的過程和構(gòu)造哈希表的過程基本一致。給定K值，根據(jù)建表時(shí)設(shè)定的哈希函數(shù)求得哈希地址，若表中此位置上沒有記錄，則查找不成功；否則比較關(guān)鍵字。若和給定值相等，則查找成功；否則根據(jù)造表時(shí)設(shè)定的處理沖突的方法找“下一地址”，直至哈希表中某個(gè)位置為“空”或者表中所填記錄的關(guān)鍵字等于給定值時(shí)為止。,第 49 /209頁(yè),從哈希表的查找過程可知，盡管可直接由關(guān)鍵字K計(jì)算出存儲(chǔ)地址H(K)，但由于“沖突”的產(chǎn)生，使得在哈希

26、表的查找過程中仍然需要用給定值K與元素的關(guān)鍵字進(jìn)行比較，所以平均查找長(zhǎng)度仍然可以作為評(píng)價(jià)哈希查找效率的標(biāo)準(zhǔn)。 值得注意的是，在采用鏈地址法解決沖突所產(chǎn)生的哈希表中，若要?jiǎng)h除表中的一個(gè)記錄，不能簡(jiǎn)單地直接刪除，因?yàn)檫@樣將截?cái)嗥渌哂邢嗤５刂返脑氐牟檎业刂?，所以?yīng)設(shè)定一個(gè)特殊的標(biāo)志以表明該元素已被刪除。,第 50 /209頁(yè),例4-5 設(shè)哈希函數(shù)H(K)= k MOD 7，哈希表的地址空間為06，對(duì)關(guān)鍵字序列(19，14，23，2，68，16，4)，按下述幾種解決沖突的方法分別構(gòu)造哈希表， 線性探測(cè)再散列； 二次探測(cè)再散列； 鏈地址法；并分別計(jì)算哈希查找成功時(shí)在等概率情況下的平均查找長(zhǎng)度。,

27、第 51 /209頁(yè),解：(1) 按照線性探測(cè)再散列法處理沖突構(gòu)造哈希表。 19 MOD 7 = 5 存入地址空間5 14 MOD 7 = 0 存入地址空間0 23 MOD 7 = 2 存入地址空間2 2 MOD 7 = 2 發(fā)生沖突 下一個(gè)存儲(chǔ)地址是(2+1)MOD 7 = 3 存入地址空間3 68 MOD 7 = 5 發(fā)生沖突 下一個(gè)存儲(chǔ)地址是(5+1)MOD 7 = 6 存入地址空間6 16 MOD 7 = 2 發(fā)生沖突 下一個(gè)存儲(chǔ)地址是(2+1)MOD 7 = 3 發(fā)生沖突,第 52 /209頁(yè),下一個(gè)存儲(chǔ)地址是(2+2)MOD 7 = 4 存入地址空間4 4 MOD 7 = 4 發(fā)生

28、沖突 下一個(gè)存儲(chǔ)地址是(4+1)MOD 7 = 5 發(fā)生沖突 下一個(gè)存儲(chǔ)地址是(4+2)MOD 7 = 6 發(fā)生沖突 下一個(gè)存儲(chǔ)地址是(4+3)MOD 7 = 0 發(fā)生沖突 下一個(gè)存儲(chǔ)地址是(4+4)MOD 7 = 1 存入地址空間1,第 53 /209頁(yè),用二次探測(cè)再散列法處理 沖突產(chǎn)生的哈希表,第 54 /209頁(yè),排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要運(yùn)算，它的功能是將一個(gè)數(shù)據(jù)元素的無(wú)序序列調(diào)整為一個(gè)有序序列。 經(jīng)排序的數(shù)據(jù)若按由大到小的順序排列，稱為降序；反之，若按由小到大的順序排列，稱為升序。,排 序,第 55 /209頁(yè),對(duì)數(shù)據(jù)進(jìn)行查找或其它操作時(shí)，有序數(shù)據(jù)和無(wú)序數(shù)據(jù)的執(zhí)行速度差別很大。

29、如對(duì)有序表可采用折半查找等，而對(duì)無(wú)序表只能用順序查找。 排序在實(shí)際中應(yīng)用很廣，據(jù)統(tǒng)計(jì)，計(jì)算機(jī)處理的35%的機(jī)時(shí)是用于排序的。因此，研究高效率的排序方法是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要內(nèi)容。然而，目的不是參與具體的排序工作，而是研究分析排序算法中所運(yùn)用的大量基本的和重要的排序技術(shù)。,排 序,第 56 /209頁(yè),排序的分類 根據(jù)排序中所涉及的存儲(chǔ)器，可將排序分為內(nèi)部排序和外部排序兩大類。排序過程中，所有記錄都放在內(nèi)存中處理的稱為內(nèi)部排序；當(dāng)待排序的記錄很多，排序時(shí)不僅要使用內(nèi)存，而且還要使用外部存儲(chǔ)器的排序方法稱為外部排序。本節(jié)只討論內(nèi)部排序。 如果待排序的記錄中，存在多個(gè)關(guān)鍵字相同的記錄，經(jīng)排序后這些記錄

30、的相對(duì)次序仍然保持不變，則稱相應(yīng)的排序方法是穩(wěn)定的，否則稱為不穩(wěn)定的。,排 序,第 57 /209頁(yè),不同的排序方法有其不同的特點(diǎn)，只有根據(jù)所排序記錄的特點(diǎn)，才能找出合適的排序方法。 評(píng)價(jià)排序算法優(yōu)劣的標(biāo)準(zhǔn)主要是時(shí)間復(fù)雜度，對(duì)內(nèi)部排序而言，時(shí)間的主要開銷花在記錄的比較和移動(dòng)上，所以時(shí)間復(fù)雜度主要通過記錄的比較次數(shù)和移動(dòng)次數(shù)來反映。 為簡(jiǎn)單起見，采用順序存儲(chǔ)結(jié)構(gòu)存放所排序的記錄序列。其C語(yǔ)言描述如下：,排 序,第 58 /209頁(yè),#define N n struct record int key; int otheritem; ; typedef struct record RECORD; R

31、ECORD fileN+1; 其中n為待排序的記錄數(shù)目。,排 序,第 59 /209頁(yè),1、直接插入排序 插入排序的基本思想是把記錄逐一按其關(guān)鍵字的大小插入到已經(jīng)排好次序的記錄序列中的適當(dāng)位置，直到全部插入完為止。這很象打撲克牌時(shí)，一邊抓牌，一邊理牌的過程，每抓一張牌就把它插到適當(dāng)?shù)奈恢蒙先ァ?設(shè)有n個(gè)記錄(R1，R2，Rn)，已劃分為已排序部分和未排序部分，即插入Ri時(shí)，(R1，R2，Ri1)是已排好序的部分，(Ri，Ri+1，Rn)屬于未排序部分。用Ri依次與Ri1，Ri2，R1進(jìn)行比較，找出Ri在有序子文件中的插入位置，將Ri插入，原位置上的記錄至Ri1均順序后移一位。,排 序,第 60

32、 /209頁(yè),例4-6 設(shè)待排序記錄的關(guān)鍵字序列為(20，15，8，23，55，25)，寫出直接插入排序每一趟執(zhí)行后的序列狀態(tài)。 解：直接插入排序過程如圖4-11所示。,排 序,第 61 /209頁(yè),排 序,第 62 /209頁(yè),算法4-7 直接插入排序算法。 void insertsort(RECORD R,int n) /*注意設(shè)待排記錄放在R1到 Rn中*/ int i,j; for(i=2;i=n;i+) R0=Ri; j=i1; /*j總是指向有序序列的最后一個(gè)記錄*/ while(R0.keyRj.key) Rj+1=Rj;/*后移一位，設(shè)結(jié)構(gòu)體變量可以整體賦值*/ j; Rj+1

33、=R0; /*插入R0元素到有序序列中*/ 直接插入排序是穩(wěn)定的，其時(shí)間復(fù)雜度為O(n2)。,排 序,第 63 /209頁(yè),2、簡(jiǎn)單選擇排序 簡(jiǎn)單選擇排序的方法是在所有的記錄中選出關(guān)鍵字最?。ɑ蜃畲螅┑挠涗洠阉c第一個(gè)記錄交換存儲(chǔ)位置，然后再在余下的記錄中選出次小的關(guān)鍵字對(duì)應(yīng)的記錄，把它與第二個(gè)記錄交換，依此類推，直至排序完成。 例4-7 待排序的記錄關(guān)鍵字序列為(20，15，8，40，55，25)，寫出簡(jiǎn)單選擇排序每一趟執(zhí)行后的序列狀態(tài)。 解：簡(jiǎn)單選擇排序過程如圖4-12所示。,排 序,第 64 /209頁(yè),排 序,簡(jiǎn)單選擇排序示例,第 65 /209頁(yè),算法4-8 簡(jiǎn)單選擇排序。 voi

34、d selectsort(RECORD R,int n) /*注意待排記錄放在R1到Rn中*/ int i,j,k; RECORD temp; for(i=1;in;i+) k=i; for(j=i+1;j=n;j+) if(Rj.keyRk.key) k=j; if(i!=k) temp=Rk;Rk=Ri; Ri=temp; 簡(jiǎn)單選擇排序是不穩(wěn)定的，其時(shí)間復(fù)雜度是O(n2)。,排 序,第 66 /209頁(yè),3、冒泡排序 冒泡排序的基本思想為：從R1開始，兩兩比較相鄰記錄的關(guān)鍵字，即比較Ri和Ri+1(i=1，2，n1)的關(guān)鍵字大小，若升序(如KiKi+1)，則交換Ri和Ri+1的位置，如此經(jīng)

35、過一趟排序，關(guān)鍵字最大的記錄被安置在最后一個(gè)位置(Rn)上。然后再對(duì)前n1個(gè)記錄進(jìn)行同樣的操作，則具有次大關(guān)鍵字的記錄被安置在第n1個(gè)位置(Rn1)上。如此反復(fù)，進(jìn)行n1趟冒泡排序后所有待排序的n個(gè)記錄已經(jīng)按關(guān)鍵字由小到大有序。,排 序,第 67 /209頁(yè),若把各記錄看作按縱向排列，那么在這個(gè)排序過程中，關(guān)鍵字小的好比水中的氣泡往上漂浮(冒)，關(guān)鍵字大的好比水中的石塊沉入水底，故形象地取名為冒泡排序。 例4-8 待排序的記錄關(guān)鍵字序列為(20，15，8，40，55，25)，寫出冒泡排序每一趟執(zhí)行后的序列狀態(tài)。 解：冒泡排序過程如圖4-13所示，其中，橫線以下為已排好序的記錄。,排 序,第 6

36、8 /209頁(yè),排 序,冒泡排序示例,第 69 /209頁(yè),算法 冒泡排序算法。 void bubblesort(RECORD R,int n) /*注意待排記錄放在R1到Rn中*/ int i,j; RECORD temp; for(i=1;iRj+1.key) temp=Rj; /*交換元素，設(shè)結(jié)構(gòu)體變量可以整體賦值*/ Rj=Rj+1; Rj+1=temp; ,排 序,第 70 /209頁(yè),按照冒泡排序算法，對(duì)具有n個(gè)記錄的待排序序列要執(zhí)行n1趟冒泡排序。但從上例中我們可以發(fā)現(xiàn)，在進(jìn)行第三趟冒泡排序過程時(shí)，已沒有記錄進(jìn)行過交換，表明此時(shí)記錄序列已經(jīng)“正序”(有序)，后面的3趟沒有發(fā)生交換

37、。 因此應(yīng)該對(duì)算法加以改進(jìn)：使之能“記住”每趟冒泡排序過程中是否發(fā)生了“交換”，若某一趟冒泡未發(fā)生“交換”，表示此時(shí)記錄序列已經(jīng)有序，應(yīng)結(jié)束排序過程。,排 序,第 71 /209頁(yè),算法 改進(jìn)后的冒泡排序算法。 void bubblesort_m(RECORD R,int n) int i,j,flag; RECORD temp; i=1; do flag=0; /*在進(jìn)行每一趟冒泡之前置flag為0，表示無(wú)交換*/ for(j=1;jRj+1.key) temp=Rj; Rj=Rj+1; Rj+1=temp;flag=1; i+; while(in) ,排 序,第 72 /209頁(yè),分析冒泡排序的效率，很容易看出，若初始序列為“正序”，則只需一趟排序。反之，若初始序列為“逆序”，則需要進(jìn)行n1趟排序。 冒泡排序方法是穩(wěn)定的，其在最壞情況下的時(shí)間復(fù)雜度為O(n2)。但由于冒泡排序能“判別”記錄的狀態(tài)，所以當(dāng)待排序序列是基本有序的序列時(shí)