第5章常用算法查找

1、零基礎(chǔ)學(xué)算法第5章：常用算法'查找課程安排查找的基本概念5.2簡單查找二叉排序樹5.4索引查找 5.5哈希表5-1查找的基本概念主關(guān)鍵字和次關(guān)鍵字 查找結(jié)果 靜態(tài)查找表和動態(tài)查找表5.2簡單查找順序查找從線性表的一端開始，依次將每個記錄的關(guān)鍵字與給定值 進行比較，若某個記錄的關(guān)鍵字等于給定值，表示查找成功， 返回記錄序號；若將線性表中所有記錄都比較完，仍未找到關(guān) 鍵字與給定值相等的記錄，則表示查找失敗，返回一個失敗值。折半查找又稱為二分查找。這種查找方法要求查找表的數(shù)據(jù)是線性 結(jié)構(gòu)保存，并且還要求查找表中的數(shù)據(jù)是按關(guān)鍵字由小到大有 序排列。6965903792628545.2簡單查找折

2、半查找6122837546569839092第次tmid6122837546569839092第2次tmid6122837546569839092第3次fmid61228I5465698390925.3二叉排序樹5.3.1二叉排序樹的定義二叉排序數(shù)或者是一棵空樹，或者是一 棵具有以下性質(zhì)的二叉樹：（1）若它有左子樹，則左子樹上所有結(jié)點的數(shù)據(jù)均小于根結(jié)點的數(shù)據(jù)。（2）若它有右子樹，則右子樹上所有結(jié)點的數(shù)據(jù)均大于根結(jié)點的數(shù)據(jù)。1237（3）左、右子樹本身又各是一棵二叉 排序樹。5.3二叉排序樹插入結(jié)點査找結(jié)點刪除結(jié)點5-3插入結(jié)點査找結(jié)點刪除結(jié)點二叉排序樹5.3二叉排序樹刪除葉結(jié)點5.3二叉排序樹

3、刪除無右子樹結(jié)點5.3二叉排序樹刪除有左右子樹結(jié)點28 j： 833790上移結(jié)點655.4索引查找5.4.1索引的概念主表和索引表創(chuàng)建索引的一般過程索引的特點5.4索引查找5.4.1索引查找算法在索引表中進行查找引查找的過程是：（1）首先根據(jù)給定的關(guān)鍵字key,按定義的函數(shù)計算出索引值indexl,在索 引表上查找出索引值等于indexl的索引項，以確定對應(yīng)子表在主表中的開 始位置和長度，（2）接著根據(jù)從索引表中獲取的開始序號start,在主表指定位置（即子表的 開始處）順序查找關(guān)鍵字key。向主表中插入數(shù)據(jù)在線性表的索引存儲結(jié)構(gòu)上進行插入和刪除運算的算法，與查找算法 類似，其具體過程如下:

4、（1）根據(jù)待插入元素的值查找索引表，確定出對應(yīng)的子表。（2）接著，根據(jù)待插入元素的關(guān)鍵字，在該子表中做插入元素的操作。（3）插入完成后，修改索引表中的相應(yīng)子表的長度。5-5哈希表5.5.1哈希表概述哈希表的基本思想是：以線性表中每個元素的關(guān)鍵字key為 自變量，通過一定的函數(shù)關(guān)系h(key)計算岀函數(shù)的值，把這個 值作為數(shù)組的下標(biāo)，將元素存入對應(yīng)的數(shù)組元素中。函數(shù)h(key)稱為哈希函數(shù)，函數(shù)的值稱為哈希地址。線性表：69, 65, 90, 37, 92, 6, 2& 54哈希函數(shù)：h(key)二key % 13012345678910111265922869637905,5哈希表5.5.2構(gòu)造哈希函數(shù)直接定址法除法取余法數(shù)字分析法平方取中法折疊法5,5哈希表5.5.3處理沖突開放地址法-線性探測法-雙哈希函數(shù)探測法0123456789101112659228546