《常用算法查》PPT課件.ppt

零基礎(chǔ)學(xué)算法,第5章: 常用算法查找,課程安排,5.1 查找的基本概念 5.2 簡(jiǎn)單查找 5.3 二叉排序樹 5.4 索引查找 5.5 哈希表,5.1 查找的基本概念,主關(guān)鍵字和次關(guān)鍵字 查找結(jié)果 靜態(tài)查找表和動(dòng)態(tài)查找表,5.2 簡(jiǎn)單查找,順序查找 從線性表的一端開始，依次將每個(gè)記錄的關(guān)鍵字與給定值進(jìn)行比較，若某個(gè)記錄的關(guān)鍵字等于給定值，表示查找成功，返回記錄序號(hào)；若將線性表中所有記錄都比較完，仍未找到關(guān)鍵字與給定值相等的記錄，則表示查找失敗，返回一個(gè)失敗值。 折半查找 又稱為二分查找。這種查找方法要求查找表的數(shù)據(jù)是線性結(jié)構(gòu)保存，并且還要求查找表中的數(shù)據(jù)是按關(guān)鍵字由小到大有序排列。,69,65,90,37,92,6,28,54,5.2 簡(jiǎn)單查找,折半查找,5.3 二叉排序樹,二叉排序數(shù)或者是一棵空樹，或者是一棵具有以下性質(zhì)的二叉樹： （1）若它有左子樹，則左子樹上所有結(jié)點(diǎn)的數(shù)據(jù)均小于根結(jié)點(diǎn)的數(shù)據(jù)。 （2）若它有右子樹，則右子樹上所有結(jié)點(diǎn)的數(shù)據(jù)均大于根結(jié)點(diǎn)的數(shù)據(jù)。 （3）左、右子樹本身又各是一棵二叉排序樹。,5.3.1 二叉排序樹的定義,5.3 二叉排序樹,插入結(jié)點(diǎn) 查找結(jié)點(diǎn) 刪除結(jié)點(diǎn),5.3 二叉排序樹,插入結(jié)點(diǎn) 查找結(jié)點(diǎn) 刪除結(jié)點(diǎn),5.3 二叉排序樹,刪除葉結(jié)點(diǎn),5.3 二叉排序樹,刪除無(wú)右子樹結(jié)點(diǎn),5.3 二叉排序樹,刪除有左右子樹結(jié)點(diǎn),5.4 索引查找,主表和索引表 創(chuàng)建索引的一般過(guò)程 索引的特點(diǎn),5.4.1 索引的概念,5.4 索引查找,在索引表中進(jìn)行查找 引查找的過(guò)程是： （1）首先根據(jù)給定的關(guān)鍵字key，按定義的函數(shù)計(jì)算出索引值index1，在索引表上查找出索引值等于index1的索引項(xiàng)，以確定對(duì)應(yīng)子表在主表中的開始位置和長(zhǎng)度， （2）接著根據(jù)從索引表中獲取的開始序號(hào)start，在主表指定位置（即子表的開始處）順序查找關(guān)鍵字key。 向主表中插入數(shù)據(jù) 在線性表的索引存儲(chǔ)結(jié)構(gòu)上進(jìn)行插入和刪除運(yùn)算的算法，與查找算法類似，其具體過(guò)程如下： （1）根據(jù)待插入元素的值查找索引表，確定出對(duì)應(yīng)的子表。 （2）接著，根據(jù)待插入元素的關(guān)鍵字，在該子表中做插入元素的操作。 （3）插入完成后，修改索引表中的相應(yīng)子表的長(zhǎng)度。,5.4.1 索引查找算法,5.5 哈希表,哈希表的基本思想是：以線性表中每個(gè)元素的關(guān)鍵字key為自變量，通過(guò)一定的函數(shù)關(guān)系h(key)計(jì)算出函數(shù)的值，把這個(gè)值作為數(shù)組的下標(biāo)，將元素存入對(duì)應(yīng)的數(shù)組元素中。 函數(shù)h(key)稱為哈希函數(shù)，函數(shù)的值稱為哈希地址。,5.5.1 哈希表概述,線性表：,哈希函數(shù)：,5.5 哈希表,直接定址法 除法取余法 數(shù)字分析法 平方取中法 折疊法,5.5.2 構(gòu)造哈希函數(shù),