61線性查找62折半查找63分快查找64二元查找樹65散列(已修改)
2025-10-11 09:51 本頁面
【正文】 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學院 2020 秋 Slide. 6 1 線性查找 折半查找 分快查找 二元查找樹 散列法 第六章 查 找 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學院 2020 秋 Slide. 6 2 查找分類 傳統(tǒng)的查找方法 較先進的查找方法 （ 散列法 ） 線性查找 折半查找 分快查找 二元查找樹 幾個概念： ?查找表 ：由同一類型的數(shù)據(jù)元素（或紀錄）構(gòu)成的集合。 ?關(guān)鍵字 ：數(shù)據(jù)元素中某一數(shù)據(jù)項的值，用以表示一個數(shù)據(jù)元素。 ?靜態(tài)查找 ：查找 +提取數(shù)據(jù)元素屬性信息 ?動態(tài)查找 ：查找 +（插入或刪除元素） 查找 ：根據(jù)給定的值，在查找表中確定一個其關(guān)鍵字等于給定值 的紀錄或數(shù)據(jù)元素。 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學院 2020 秋 Slide. 6 3 Int Search ( k, last, F ) Keytyoe k, int last。 LIST F 。 /* 在 F中查找關(guān)鍵字為 k的紀錄，若找到，則返回該紀錄 所在的下標，否則返回 0 */ { int i 。 F[0].key = k 。 i = last 。 while ( F[i].key != k ) i = i –1 。 return i 。 } / *Search */ Struct records { keytype key 。 fields other 。 } Typedef records LIST[maxsize] 。 LIST F 。 線性查找 算法一：順序表 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學院 2020 秋 Slide. 6 4 LIST Search( k, F ) Keytype k。 LIST F 。 { LIST p 。 p=F。 while ( p! = NULL ) if ( p == k ) return p 。 else p = pnext 。 return p 。 } Struct celltype { records data 。 celltype * next 。 } Typedef celltype * LIST 。 算法二：鏈表 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學院 2020 秋 Slide. 6 5 性能分析 定義 為確定紀錄在查找表中的位置，需和給定值進行比較 的關(guān)鍵字個數(shù)的期望值稱為查找算法在查找成功時的 平均查找長度 (Average Search Length)。 設 Pi為查找表中第 i個記錄的概率。 ∑Pi=1 Ci為比較次數(shù) ASL = ∑PiCi n i=1 在等概率情況下 Pi=1/n，且一般情況下 Ci = n－ i+1 ASL = nP1+(n1)P2+…+2 Pn1+Pn = 1/n∑(n－ i+1) n i=1 = (n+1)/2 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學院 2020 秋 Slide. 6 6 折半查找 查找表 =[05,13,19,21,37,56,64,75,80,88,92] Key=21 05 13 19 21 37 56 64 75 80 88 92 Low=1 mid=6 Up=11 Up=5 mid=3 Low=4, mid=4 05 13 19 21 37 56 64 75 80 88 92 Low=1 mid=6 Up=11 Key=85 low=5 mid=9 Low=10, mid=10 Low=10 Up=9 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學院 2020 秋 Slide. 6 7 Int binarysearch(keytype k, LIST F ) { int low , up , mid 。 low = 1 。 up = last 。 while ( low = up ) { mid = ( low + up ) / 2 。 if ( F[mid].key = = k ) return mid 。 else if ( F[mid].key k ) up = mid – 1 。 else low = mid + 1 。 } return –1 } 折半查找算法 折半查找算法分析 6 3 9 1 4 7 10 2 5 8 11 h n=2h1 ( h=log2(n+1) ) ASLbs= ∑PiCi Pi=1/n n i=1 = 1/n
教學課件相關(guān)推薦
鄂ICP備17016276號-1