【正文】 鍵字與給定值進(jìn)行比較，若某個(gè)記錄的關(guān)鍵字與給定值相等，則查找成功，找到所查的記錄；反之，若直到第一個(gè)記錄，其關(guān)鍵字和給定值比較都不相等，則表明表中沒(méi)有所查的記錄，查找失敗。 算法描述為 ： int Search(int d,int a[],int n) 2 { /*在數(shù)組 a[]中查找等于 D元素，若找到，則函數(shù)返回 d 在數(shù)組中的位置，否則為 0。其中 n 為數(shù)組長(zhǎng)度 */ int i ； /*從后往前查找 */ for(i=n1。a!=d。i) 此處程序正確嗎？ return i ； /*如果找不到，則 i為 0*/ } 二分查找 二分查找又稱折半查找，它是一種效率較高的查找方法。 二分查找要求 1） 必 須采用順序存儲(chǔ)結(jié)構(gòu) 。 2） 必須按關(guān)鍵字大小有序排列。 優(yōu)缺點(diǎn) 折半查找法的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好 。其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。 算法思想 首先，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩 個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。 重復(fù)以上過(guò)程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此 時(shí)查找不成功。 算法 復(fù)雜度 假設(shè)其數(shù)組長(zhǎng)度為 n，其算法復(fù)雜度為 O(log(n))， 下面提供一段二分查找實(shí)現(xiàn)的 偽代碼 : 總結(jié) 3 BinarySearch(max,min,des) middes then 此處程序正確嗎？ max=mid1 else min=mid+1 return max 折半查找法也稱為二分查找法，它充分利用了元素間的次序關(guān)系，采用分治策略，可在最壞的情況下用 O(log n)完成搜索任務(wù)。它的基本思想是，將 n 個(gè)元素分成個(gè)數(shù)大致相同的兩半，取 a[n/2]與欲查找的 x 作比較，如果 x=a[n/2]則找到 x，算法終止。如 果xa[n/2]，則我們只要在數(shù)組 a的右 半部繼續(xù)搜索 x。 分塊查找 step1 先選取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表 。 step2 查找分兩個(gè)部分：先對(duì)索引表進(jìn)行二分查找或順序查找，以確定待查記錄在哪一塊中；然后，在已確定的塊中用順序法進(jìn)行查找 。 方法描述 將 n個(gè)數(shù)據(jù)元素 按塊有序 劃分為 m塊（ m ≤ n ）。每一塊中的結(jié)點(diǎn)不 必有序，但塊與塊之間必須 按塊有序 ；即第 1 塊中任一元素的關(guān)鍵字都必須小于第 2塊中任一元素的關(guān)鍵字；而第 2 塊中任一元素又都必須小于第 3 塊中的任一元素， ?? 操作步驟 step1 先選取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表 。 step2 查找分兩個(gè)部分：先對(duì)索引表進(jìn)行二分查找或順序查找，以確定待查記錄在哪一塊中；然后，在已確定的塊中用順序法進(jìn)行查找 。 哈希表查找 4 基本原理 從此處開(kāi)始至正文最后一頁(yè)的文字部分格式，按照如下格式設(shè)置： 字體：正文宋體；字號(hào)：小四；段落中的格式為：正文：兩端對(duì)齊；首行縮進(jìn)： 2 字符；間距：段前段后均為： 0 行；行距： 倍行距。具體圖示如下： 代碼部分請(qǐng)仔細(xì)檢查正誤。然后按照上述正文設(shè)置格式以及代碼縮進(jìn)格式調(diào)整。 我 們使用一個(gè)下標(biāo)范圍比較大的數(shù)組來(lái)存儲(chǔ)元素?？梢栽O(shè)計(jì)一個(gè)函數(shù)（哈希函數(shù)， 也叫做 散列函數(shù) ），使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)）相對(duì)應(yīng)，于是用這個(gè)數(shù)組單元來(lái)存儲(chǔ)這個(gè)元素；也可以簡(jiǎn)單的理解為，按照關(guān)鍵字為每一個(gè)元素 分類(lèi) ，然后將這個(gè)元素存儲(chǔ)在相應(yīng) 類(lèi) 所對(duì)應(yīng)的地方。 但是，不能夠保證每個(gè)元素的關(guān)鍵字與函數(shù)值是一一對(duì)應(yīng)的，因此極有可能出現(xiàn)對(duì)于不同的元素，卻計(jì)算出了相同 的函數(shù)值，這樣就產(chǎn)生了 沖突 ，換句話說(shuō)，就是把不同的元素分在了相同的 類(lèi) 之中。后面我們將看到一種解決 沖突 的簡(jiǎn)便做法。 總的來(lái)說(shuō)， 直接定址 與 解決沖突 是哈希表的兩大特點(diǎn)。 函數(shù)構(gòu)造 構(gòu)造函數(shù) 的常用方法（下面為了敘述簡(jiǎn)潔，設(shè) h(k) 表示關(guān)鍵字為 k 的元素所對(duì)應(yīng)的函數(shù)值）： 總結(jié) 5 1) 除余法 選擇一個(gè)適當(dāng)?shù)恼麛?shù) p ，令 h(k ) = k mod p 這里， p 如果選取的是比較大的 素?cái)?shù) ，效果比較好。而且此法非常容易實(shí)現(xiàn)，因此是最常用的方法。 2) 數(shù)字選擇法 如果關(guān)鍵字的位數(shù)比較多，超過(guò)長(zhǎng)整型范圍而無(wú)法直接運(yùn)算，可以選擇其中數(shù)字分布比較均勻的若干位，所組成的新的值作為關(guān)鍵字或者直接作為函數(shù)值。 沖突處理 線性重新散列技術(shù)易于實(shí)現(xiàn)且可以較好的達(dá)到目的。令數(shù)組元素個(gè)數(shù)為 S ，則當(dāng) h(k) 已經(jīng)存儲(chǔ)了元素的時(shí)候， 依次探查 (h(k)+i) mod S , i=1,2,3?? ，直到找到空的存儲(chǔ)單元為止（或者從頭到尾掃描一圈仍未發(fā)現(xiàn)空單元，這就是 哈希表 已經(jīng)滿了，發(fā)生了錯(cuò)誤。當(dāng)然這是可以通過(guò)擴(kuò)大數(shù)組范圍避免的）。 支持運(yùn)算 哈希表支持的運(yùn)算主要有：初始化 (makenull)、哈希函數(shù)值的運(yùn)算 (h(x))、插入元素 (insert)、查找元素 (member)。 設(shè)插入的元素的關(guān) 鍵字為 x ， A 為存儲(chǔ)的數(shù)組。 初始化比較容易，例如 const empty=maxlongint。 // 用非常大的整數(shù)代表這個(gè)位置沒(méi)有存儲(chǔ)元素 p=9997。 // 表的大小 procedure makenull。 var i:integer。 begin for i:=0 to p1 do A:=empty。 End。 哈希函數(shù)值的運(yùn)算根據(jù)函數(shù)的不同而變化，例如除余法的一個(gè)例子： function h(x:longint):Integer。 begin h:= x mod p。 end。 我們注意到，插入和查找首先都需要對(duì)這個(gè)元素定位，即如果這個(gè)元素若存在，它應(yīng)該存儲(chǔ)在什么位置，因此加入一個(gè)定位的函數(shù) locate function locate(x:longint):integer。 var orig,i:integer。 6 begin orig:=h(x)。 i:=0。 while (ix)and(A[(orig+i)mod S]empty) do inc(i)。 //當(dāng)這個(gè)循環(huán)停下來(lái)時(shí)，要 么找到一個(gè)空的存儲(chǔ)單元，要么找到這個(gè)元 //素存儲(chǔ)的單元，要么表已經(jīng)滿了 locate:=(orig+i) mod S。 end。 插入元素 procedure insert(x:longint)。 var posi:integer。 begin posi:=locate(x)。 //定位函數(shù)的返回值 if A[posi]=empty then A[posi]:=x else error。 //error 即為發(fā)生了錯(cuò)誤，當(dāng)然這是可以避免的 end。 查找元素是否已經(jīng)在表中 procedure member(x:longint):boolean。 var posi:integer。 begin posi:=locate(x)。 if A[posi]=x then member:=true else member:=false。 end。 總結(jié) 7 2 算法實(shí)現(xiàn) 順序查找 在一個(gè)已知無(wú) (或有序）序隊(duì)列中找 出與給定關(guān)鍵字相同的數(shù)的具體位置。原理是讓關(guān)鍵字與隊(duì)列中的數(shù)從最后一個(gè)開(kāi)始逐個(gè)比較，直到找出與給定關(guān)鍵字相同的數(shù)為止，它的缺點(diǎn)是效率低下。 方法分類(lèi) (1） Java 實(shí)現(xiàn)方法 package search。 /*順序查找 * des 要查找的元素 * i 保存當(dāng)前元素的下標(biāo) */ public class OrderSearch { public static int ordersearch(int[] arry,int des){ int i=0。 for(。i=。i++){ if(des==arry[i]) return i。 } return 1。 } public static void main(String[] args){ int[] a=new int[]{2,3,5,6,7,3,}。 (ordersearch(a,3))。 } } (2) C 實(shí)現(xiàn)算法 8 int sq_search(keytype keyp[],int n,keytype key) { int i。 for(i=0。 in。 i++) if(key[i] == key) return i。//查找成功 return 1。//查找失敗 } 3） C++實(shí)現(xiàn)方法 int Seqsch(ElemType A[ ],int n,KeyType K) { //從 順序表 A的 n個(gè)元素中順序查找關(guān)鍵字為 K 的元素，若成功返回其下標(biāo)，否則返回 1 int i。 for( i=0。in。i++){ if(A[i].key==K) break。 } if(i=n1) //查找成功返回下標(biāo)，否則返回 1 return i。 elsereturn 1。} 4） php 實(shí)現(xiàn)方法 function seq_sch($array, $n, $k) { for($i=0。 $i$n。 $i++) { if( $array[$i]==$k) break。 } if ($i$n) { 總結(jié) 9 return $i。 }else{ return 1。 } } 二分查找 算法要求 1） 必須采用 順序存儲(chǔ)結(jié)構(gòu) 2） 必須按關(guān)鍵字大小有序排列。 算法復(fù)雜度 假設(shè)其 數(shù)組 長(zhǎng)度為 n，其算法復(fù)雜度為 o（ log（ n）） 下面提供一段二分查找實(shí)現(xiàn)的偽代碼 : BinarySearch(max,min,des) mid(max+min)/2 while(min=max) mid=(min+max)/2 if mid=des then return mid elseif mid des then max=mid1 else min=mid+1 return max 折半查找法也稱為二分查找法，它充分利用了元素間的次序關(guān)系，采用分治策略，可在最壞的情況下用 O(log n)完成搜索任務(wù)。它的基本思想是，將 n 個(gè)元素分成個(gè)數(shù)大致相同的兩半，取 a[n/2]與欲查找的 x作比較，如果 x=a[n/2]則找到 x，算法終止。如 果 xa[n/2]，則我們只要在 數(shù)組 a的左半部繼續(xù)搜索 x（這里假設(shè)數(shù)組元素呈升序排列）。如果 xa[n/2]，則我們只要在數(shù)組 a的右 半部繼續(xù)搜索 x。 10 代碼示例 1） Python 源代碼 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def binarySearch(lists,select): is_none=False iflists!=[]: cen_num=len(lists)/2 tlag=lists[cen_num] gt_list=lists[0:cen_num] lt_list=lists[cen_num+1:] if tlag==select: is_none=True return is_none elif tlagselect: is_se=binarySearch(gt_list,select) if notis_se: return binarySearch(lt_list,select) return is_none elif tlagselect: is_se=binarySearch(lt_list,select) if notis_se: return binarySearch(gt_list,select) return is_none 2） pascal 源代碼 1 2 programjjzx(input,output)。 var 總結(jié) 11 3 4 5 6 7 8 9 10 11 12 13 14 15 1