61線性查找62折半查找63分快查找64二元查找樹(shù)65散列-wenkub.com
2025-09-16 09:51 本頁(yè)面
【正文】 秋 Slide. 6 27 地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Key 1 29 17 9 35 11 25 12 成功探 測(cè)次數(shù) 1 1 1 1 2 1 1 2 失敗探 測(cè)次數(shù) 1 2 1 3 2 1 1 1 1 6 5 4 3 查找成功的平均查找長(zhǎng)度： ASLs=(6+4)/8= 查找失敗的平均查找長(zhǎng)度： ASLu=(6 1+2+3+2+6+5+4+3)/13= (2)使用鏈地址法處理沖突構(gòu)造散列表。 （ 1）采用除留余數(shù)法構(gòu)造散列函數(shù)，線性探測(cè)法處理沖突，要 求新插入鍵值的平均探測(cè)次數(shù)不多于 ，請(qǐng)確定散列表 的長(zhǎng)度 m及相應(yīng)的散列函數(shù)。 秋 Slide. 6 23 (1) 使用線性探測(cè)法解決沖突，即步長(zhǎng)為 1，對(duì)應(yīng)地址為： H(13)=1+(13%7)=7 H(15)=1+(15%7)=2 H(22)=1+(22%7)=2(沖突 )， H1(22)=(2+1)%8=3 H(8)=1+(8%7)=2(沖突 )， H1(8)=(2+1)%8=3 (仍沖突 ) H2(8)=(3+1)%8=4 H(34)=1+(34%7)=7(沖突 )， H1(34)=(7+1)%8=0 H(19)=1+(19%7)=6 H(21)=1+(21%7)=1 地址 0 1 2 3 4 5 6 7 Key 34 21 15 22 8 19 13 探測(cè)次數(shù) 2 1 1 2 3 1 1 哈希表 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國(guó)家示范性軟件學(xué)院 2020 失敗查找平均查找長(zhǎng)度： ASLu 查找失敗，但找到插入位置的平均比較次數(shù) 。 秋 Slide. 6 20 解決沖突的幾種方法 ： ?開(kāi)放定址法 Hi = ( H(key) + di ) MOD m i = 1,2,…,k ( k≤m2 ) H(key) 為哈希函數(shù)， m為表長(zhǎng)， d i 為增量序列： (1) di = 1,2,3,…,m 1 (2) di = 12,12,22,22,…, 177。key+b 。key+b 。 return(1) ； //是二元排序樹(shù) } 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國(guó)家示范性軟件學(xué)院 2020 if(pdatapreval) return 0。 int top=0,preval=min。 } else return ( deletemin( Flchild ) 。 tmp = Fdata 。 else if( Flchild == NULL ) F = Frchild 。 秋 Slide. 6 13 Void delete ( keytype k , BST amp。 Flchild = NULL 。 } 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國(guó)家示范性軟件學(xué)院 2020 if ( p == NULL ) return Null 。 celltype *lchild,*rchild 。 if ( k == F[ j ].key ) return j 。amp。amp。int L 。 } } 調(diào)用： Bsearch(F,1,n,k) 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國(guó)家示范性軟件學(xué)院 2020 else { m=( i + j ) / 2。2j1 h j=1 =(n+1)/n else low = mid + 1 。 up = last ?！?n－ i+1) n i=1 = (n+1)/2 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 6 5 性能分析 定義 為確定紀(jì)錄在查找表中的位置，需和給定值進(jìn)行比較 的關(guān)鍵字個(gè)數(shù)的期望值稱(chēng)為查找算法在查找成功時(shí)的 平均查找長(zhǎng)度 (Average Search Length)。 } Struct celltype { records data 。 p=F。 線性查找 算法一：順序表 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國(guó)家示范性軟件學(xué)院 2020 } / *Search */ Struct records { keytype key 。 F[0].key = k 。 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 6 1 線性查找 折半查找 分快查找 二元查找樹(shù) 散列法 第六章 查 找 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 6 2 查找分類(lèi) 傳統(tǒng)的查找方法 較先進(jìn)的查找方法 （ 散列法 ） 線性查找 折半查找 分快查找 二元查找樹(shù) 幾個(gè)概念： ?查找表 ：由同一類(lèi)型的數(shù)據(jù)元素（或紀(jì)錄）構(gòu)成的集合。 秋 Slide. 6
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1