數(shù)據(jù)結構查找方法

1、2 / 9 H Q|X| 恢復窗口折半查找乂稱二分查找，是針對有序表進行查找的簡單、 有效而又較常用的方法。所謂有序表，即要求表中的 各元素按關鍵字的值有序（升序或降序）存放。折半查找不像順序查找那樣，從第一個記錄開始逐個順 序搜索，其基本思想是：首先選取表中間位置的記錄, 將其關鍵字與給定關鍵字k進行比較，若相等，則查找 成功；否則，若k值比該關鍵字值大，則要找的元素一 定在表的后半部分（或稱右子表），則繼續(xù)對右子表 進行折半查找；若k值比該關鍵字值小，則要找的元素 一定在表的前半部分（左子表），同樣應繼續(xù)對左子 表進行折半查找。每進行一次比較，要么找到要查找 的元素，要么將查找的范圍縮小一

2、半。如此遞推，直 到查找成功或把要查找的范圍縮小為空（查找失?。﹐設表的長度為n,表的被查找部分的頭為low,尾為high, 初始時，low=l,high=n,k為關鍵字的值。4 / 9 .E閆Q區(qū)恢復窗口采用折半查找，當查找成功時，最少比較次數(shù)為I 一次，如在上例中查找關鍵字值為18的結點， 只需一次比較。最多經(jīng)過log2n次比較之后，待 查找子表要么為空,要么只剩下一個結點，所 以要確定香找央敗需妻log2n次或log2n+1次化 較?？梢宰C明，折半查找的平均查找長度是： 從折半查找的平均查找長度ASL來看，當表的長 度n很大時，該方法尤其能顯示出其時間效率。 但由于折半查找的表仍是線性表

3、，若經(jīng)常要進 行插入、刪除操作，則元素排列費時太多，因 此折半查找比較適合于一經(jīng)建立就很少改動而 又需要經(jīng)常查找的線性表，較少查找而又經(jīng)常 需要改動的線性表可以采用鏈接存儲，使用順 序查找。常用查找算法：二分查找（Binary Search）二分查找又稱折半查找，它是一種效率較高的查找方法。二分查找要求：線性表是有序表，即表中結點按關鍵字有序，并且要用向量作為表的 存儲結構。不妨設有序表是遞增有序的。二分查找的基本思想二分查找的基本思想是：（設Rlow.high是當前的查找區(qū)間）（1）首先確定該區(qū)間的中點位置：mid = |_（low + highi）/2）J（2）然后將待查的K值與Rmid.

4、key比較：若相等，則查找成功并返回此位置，否則須 確定新的查找區(qū)間，繼續(xù)二分查找，具體方法如下：若Rmid.keyK，則由表的有序性可知Rmid.n.keys均大于K，因此若表中存在關 鍵字等于K的結點，則該結點必定是在位置mid左邊的子表R1.mid-1中，故新的查找區(qū) 間是左子表R1.mid-1。類似地，若Rmid.keyK，則要查找的K必在mid的右子表Rmid+1.n中，即新的 查找區(qū)間是右子表Rmid+1.n。下一次查找是針對新的查找區(qū)間進行的。因此，從初始的查找區(qū)間R1.n開始，每經(jīng)過一次與當前查找區(qū)間的中點位置上的結 點關鍵字的比較，就可確定查找是否成功，不成功則當前的查找區(qū)間

5、就縮小一半。這一過程 重復直至找到關鍵字為K的結點，或者直至當前的查找區(qū)間為空（即查找失?。r為止。實戰(zhàn)訓練:合并果子 (fruit.pas / dpr / c / cpp)【問題描述】在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分 成了不同的堆。多多決定把所有的果子合成一堆。每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的 重量之和。可以看出，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多 在合并果子時總共消耗的體力等于每次合并所耗體力之和。因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié) 省體力。假定每個果子重量都為1，并且已知

6、果子的種類數(shù)和每種果子的數(shù)目， 你的任務是設計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的 體力耗費值。例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?、2堆合并，新堆數(shù)目 為3，耗費體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目 為12，耗費體力為12。所以多多總共耗費體力=3+12=15?？梢宰C明15為最小的 體力耗費值?！据斎胛募枯斎胛募ruit.in 包括兩行，第一行是一個整數(shù)n（1 = n=10000），表示 果子的種類數(shù)。第二行包含n個整數(shù)，用空格分隔，第i個整數(shù)ai（1 = ai=20 000）是第i種果子的數(shù)目?！据敵鑫募枯敵鑫募ruit.ou

7、t 包括一行，這一行只包含一個整數(shù)，也就是最小的體力 耗費值。輸入數(shù)據(jù)保證這個值小于231?！緲永斎搿?129【樣例輸出】15進制轉換（2000年全國青少年信息學（計算機）奧林匹克分區(qū)聯(lián)賽復賽試題）問題描述：我們可以用這樣的方式來表示一個十進制數(shù)：將每個阿拉伯數(shù)字乘以一個以該數(shù) 字所處位置的（值減1）為指數(shù)，以10為底數(shù)的冪之和的形式。例如，123可表 示為1*10A2+2*10A1+3*10A0這樣的形式。與之相似的，對二進制數(shù)來說，也可 表示成每個二進制數(shù)碼乘以一個以該數(shù)字所處位置的(值-1 )為指數(shù)，以2為底 數(shù)的冪之和的形式。一般說來，任何一個正整數(shù)R或一個負整數(shù)-R都可以被選 來作

8、為一個數(shù)制系統(tǒng)的基數(shù)。如果是以R或-R為基數(shù)，則需要用到的數(shù)碼為0， 1,.R-1。例如，當R=7時，所需用到的數(shù)碼是0，1，2,3，4，5和6，這與其是R或-R無關。如果作為基數(shù)的數(shù)絕對值超過10，則為了 表示這些數(shù)碼，通常使用英文字母來表示那些大于9的數(shù)碼。例如對16進制數(shù) 來說，用A表示10，用B表示11，用C表示12，用D表示13，用E表示14，用F表示15。在負進制數(shù)中是用-R作為基數(shù)，例如-15( +進制)相當于110001 (-2進制)，并且它可以被表示為2的冪級數(shù)的和數(shù)：110001=1*(-2)A5+1*(-2)A4+0*(-2)A3+0*(-2)A2+0*(-2)A1+1*(-2)A0問題求解：設計一個程序，讀入一個十進制數(shù)的基數(shù)和一個負進制數(shù)的基數(shù)，并將此十進制 數(shù)轉換為此負進制下的數(shù)：-R6 (-2，-3，-4,.-20輸入：輸入的每行有兩個輸入數(shù)據(jù)。第一個是十進制數(shù)N (-32768=N=32767 );第二個是負進制數(shù)的基數(shù)-R。輸出：結果顯示在屏幕上，相對于輸入，應輸出此負進制數(shù)及其基數(shù)，若此基數(shù)超過 10，則參照16進制的方式處理。樣例：輸入30000 -2