常用算法——查找實用教案

1、5.1 查找查找(ch zho)的基本概念的基本概念 主關(guān)鍵字和次關(guān)鍵字 查找結(jié)果( ji gu) 靜態(tài)查找表和動態(tài)查找表第1頁/共16頁第一頁，共17頁。5.2 簡單簡單(jindn)查找查找 順序查找 從線性表的一端開始(kish)，依次將每個記錄的關(guān)鍵字與給定值進(jìn)行比較，若某個記錄的關(guān)鍵字等于給定值，表示查找成功，返回記錄序號；若將線性表中所有記錄都比較完，仍未找到關(guān)鍵字與給定值相等的記錄，則表示查找失敗，返回一個失敗值。 折半查找 又稱為二分查找。這種查找方法要求查找表的數(shù)據(jù)是線性結(jié)構(gòu)保存，并且還要求查找表中的數(shù)據(jù)是按關(guān)鍵字由小到大有序排列。696590379262854第2頁/共16

2、頁第二頁，共17頁。5.2 簡單簡單(jindn)查找查找 折半(zhbn)查找 第3頁/共16頁第三頁，共17頁。5.3 二叉排序二叉排序(pi x)樹樹二叉排序數(shù)或者是一棵空樹，或者是一棵具有以下性質(zhì)(xngzh)的二叉樹：（1）若它有左子樹，則左子樹上所有結(jié)點的數(shù)據(jù)均小于根結(jié)點的數(shù)據(jù)。（2）若它有右子樹，則右子樹上所有結(jié)點的數(shù)據(jù)均大于根結(jié)點的數(shù)據(jù)。（3）左、右子樹本身又各是一棵二叉排序樹。5.3.1 二叉排序(pi x)樹的定義第4頁/共16頁第四頁，共17頁。5.3 二叉排序二叉排序(pi x)樹樹 插入結(jié)點 查找(ch zho)結(jié)點 刪除結(jié)點第5頁/共16頁第五頁，共17頁。5.3

3、二叉排序二叉排序(pi x)樹樹 插入結(jié)點 查找(ch zho)結(jié)點 刪除結(jié)點第6頁/共16頁第六頁，共17頁。5.3 二叉排序二叉排序(pi x)樹樹 刪除(shnch)葉結(jié)點第7頁/共16頁第七頁，共17頁。5.3 二叉排序二叉排序(pi x)樹樹 刪除(shnch)無右子樹結(jié)點第8頁/共16頁第八頁，共17頁。5.3 二叉排序二叉排序(pi x)樹樹 刪除有左右(zuyu)子樹結(jié)點第9頁/共16頁第九頁，共17頁。5.4 索引索引(suyn)查找查找 主表和索引表 創(chuàng)建索引的一般(ybn)過程 索引的特點 5.4.1 索引(suyn)的概念第10頁/共16頁第十頁，共17頁。5.4 索引

4、索引(suyn)查找查找 在索引(suyn)表中進(jìn)行查找 引查找的過程是： （1）首先根據(jù)給定的關(guān)鍵字key，按定義的函數(shù)計算出索引(suyn)值index1，在索引(suyn)表上查找出索引(suyn)值等于index1的索引(suyn)項，以確定對應(yīng)子表在主表中的開始位置和長度， （2）接著根據(jù)從索引(suyn)表中獲取的開始序號start，在主表指定位置（即子表的開始處）順序查找關(guān)鍵字key。 向主表中插入數(shù)據(jù) 在線性表的索引(suyn)存儲結(jié)構(gòu)上進(jìn)行插入和刪除運算的算法，與查找算法類似，其具體過程如下： （1）根據(jù)待插入元素的值查找索引(suyn)表，確定出對應(yīng)的子表。 （2）接著，根

5、據(jù)待插入元素的關(guān)鍵字，在該子表中做插入元素的操作。 （3）插入完成后，修改索引(suyn)表中的相應(yīng)子表的長度。5.4.1 索引(suyn)查找算法第11頁/共16頁第十一頁，共17頁。5.5 哈希表哈希表 哈希表的基本思想(sxing)是：以線性表中每個元素的關(guān)鍵字key為自變量，通過一定的函數(shù)關(guān)系h(key)計算出函數(shù)的值，把這個值作為數(shù)組的下標(biāo)，將元素存入對應(yīng)的數(shù)組元素中。 函數(shù)h(key)稱為哈希函數(shù)，函數(shù)的值稱為哈希地址。 5.5.1 哈希表概述(i sh)線性表：哈希函數(shù)(hnsh)：第12頁/共16頁第十二頁，共17頁。5.5 哈希表哈希表 直接定址法 除法取余法 數(shù)字(shz)

6、分析法 平方取中法 折疊法5.5.2 構(gòu)造(guzo)哈希函數(shù)第13頁/共16頁第十三頁，共17頁。5.5 哈希表哈希表 開放(kifng)地址法 線性探測法 雙哈希函數(shù)探測法5.5.3 處理(chl)沖突鏈接(lin ji)法第14頁/共16頁第十四頁，共17頁。性格決定命運性格決定命運, 專注專注成就成就(chngji)人人生生第15頁/共16頁第十五頁，共17頁。感謝您的觀看(gunkn)！第16頁/共16頁第十六頁，共17頁。NoImage內(nèi)容(nirng)總結(jié)5.1 查找的基本概念。5.1 查找的基本概念。5.3 二叉排序樹。二叉排序數(shù)或者是一棵空樹，或者是一棵具有(jyu)以下性質(zhì)的二叉樹：。（3）左、右子樹本身又各是一棵二叉排