第10章查找(已修改)
2025-08-01 07:13 本頁面
【正文】 第 10章 查找 查找的基本概念 靜態(tài)查找表 動態(tài)查找表 哈希表 主要知識點 查找的基本概念 查找 :查詢 關(guān)鍵字 是否在 (數(shù)據(jù)元素集合）表中的過程。也稱作 檢索 。 主關(guān)鍵字 :能夠惟一區(qū)分各個不同數(shù)據(jù)元素的關(guān)鍵字 次關(guān)鍵字 :通常不能惟一區(qū)分各個不同數(shù)據(jù)元素的關(guān)鍵字 查找成功 :在數(shù)據(jù)元素集合中找到了要查找的數(shù)據(jù)元素 查找不成功 :在數(shù)據(jù)元素集合中沒有找到要查找的數(shù)據(jù)元素 靜態(tài)查找 :只查找，不改變數(shù)據(jù)元素集合內(nèi)的數(shù)據(jù)元素 動態(tài)查找 :既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素 靜態(tài)查找表 :靜態(tài)查找時構(gòu)造的存儲結(jié)構(gòu) 動態(tài)查找表 :動態(tài)查找時構(gòu)造的存儲結(jié)構(gòu) 平均查找長度 :查找過程所需進行的關(guān)鍵字比較次數(shù)的平均值 ,是衡量查找算法效率的最主要標準 ,其數(shù)學(xué)定義為： ?? ??niii CPA S L1其中， Pi是要查找數(shù)據(jù)元素出現(xiàn)的概率， Ci是查找相應(yīng)數(shù)據(jù)元素的比較次數(shù)。 定義要 查找數(shù)據(jù)元素的結(jié)構(gòu)體為： typedef struct { KeyType key。 } DataType。 靜態(tài)查找表 靜態(tài)查找表主要有三種結(jié)構(gòu)： 順序表 有序順序表 索引順序表 在順序表上查找的 基本思想是： 從順序表的一端開始，用給定數(shù)據(jù)元素的關(guān)鍵字逐個和順序表中各數(shù)據(jù)元素的關(guān)鍵字比較，若在順序表中查找到要查找的數(shù)據(jù)元素，則查找成功，函數(shù)返回該數(shù)據(jù)元素在順序表中的位置；否則查找失敗，函數(shù)返回 1。 查找函數(shù)設(shè)計如下： int SeqSearch(DataType a[], int n, KeyType key) //在 a[0]a[n1]中順序查找關(guān)鍵碼為 key的數(shù)據(jù)元素 //查找成功時返回該元素的下標序號；失敗時返回 1 { int i = 0。 while(i n amp。amp。 a[i].key != key) i++。 if(a[i].key == key) return i。 else return 1。 } 算法分析 查找成功時的平均查找長度 ASL成功 為： ????????niinii ninCPA S L112/)1(1成功查找失敗時的平均查找長度 ASL失敗 為 2/)1(111???? ????ninCPA S Lniinii失敗時間效率為 O(n) 有序順序表上的查找算法主要有 順序查找 和 折半查找 兩種方法。 一 、 順序查找 有序順序表上的順序查找算法和順序表上的查找算法方法類同 二、二分查找（ 又稱 折半查找） 算法的基本思想： 先給數(shù)據(jù)排序 （例如按升序排好），形成 有序表， 然后再將 key與 正中 元素相比，若 key小，則縮小至前半部內(nèi)查找；再取其 中值 比較，每次縮小 1/2的范圍，直到查找成功或失敗為止。反之，如果 key大，則縮小至后半部內(nèi)查找。 二分查找算法如下： int BiSearch(DataType a[], int n, KeyType key) //在有序表 a[0]a[n1]中二分查找關(guān)鍵碼為 key的數(shù)據(jù)元素 //查找成功時返回該元素的下標序號；失敗時返回 1 { int low = 0, high = n 1。 //確定初始查找區(qū)間上下界 int mid。 while(low = high) { mid = (low + high)/2。 //確定查找區(qū)間中心下標 if(a[mid].key == key) return mid。 //查找成功 else if(a[mid].key key) low = mid + 1。 else high = mid 1。 } return 1。 //查找失敗 } 算法分析 查找成功時的平均查找長度 ASL成功 為： 查找失敗時的平均查找長度 ASL失敗 為 nnnninCPA S Lnikiiii 221 11 lo g1)1(lo g112 ??????? ? ?? ??成功)1(lo g)1(lo g1 221 1????? ? ?? ?nnnCPA S Lniniii失敗 當(dāng)順序表中的數(shù)據(jù)元素個數(shù)非常大時，采用 在順序表上建立索引表 的辦法提高查找速度。把要在其上建立索引表的順序表稱作 主表 。主表中存放著數(shù)據(jù)元素的 全部信息 ，索引表中只存放主表中要查找數(shù)據(jù)元素的 主關(guān)鍵字和索引信息 。 8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85 14 0 0 34 5 1 66 10 2 85 15 3 key link 下標 索引表 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 key 其它域 位置 主表 索引表結(jié)構(gòu)圖 索引表中的數(shù)據(jù)元素由兩個域構(gòu)成 ， key域 為被索引的若干個數(shù)據(jù)元素中關(guān)鍵字的 最大值 ， link域 為被索引的若干個數(shù)據(jù)元素中 第一個 數(shù)據(jù)元素的位置編號 。 完全索引表 :和主表項完全相同，但只包含索引關(guān)鍵字和該數(shù)據(jù)元素在主表中位置信息的索引表 二級索引表 :當(dāng)主表中的數(shù)據(jù)元素個數(shù)非常龐大時，按照建立索引表的同樣方法對索引表再建立的索引表。二級以上的索引結(jié)構(gòu)稱作 多級索引結(jié)構(gòu) 等長索引表 :索引表中的每個索引項對應(yīng)主表中的數(shù)據(jù)元素個數(shù)相等 。反之稱為 不等長索引表 。不等長索引表中的 索引長度可隨著動態(tài)插入和動態(tài)刪除過程改變 ,因此不僅適用于 靜態(tài)查找 問題，而且也適用于 動態(tài)查找 問題。 相關(guān)術(shù)語 假設(shè)索引表的長度為 m， 主表中每個子表的長度為 s， 并假設(shè)在索引表上和在主表上均采用順序查找算法 ， 則索引順序表上查找算法的 平均查找長度 為： 122 12 1 ??????? smsmA S L算法分析 動態(tài)查找表
公司管理相關(guān)推薦
鄂ICP備17016276號-1