數(shù)據(jù)結(jié)構(gòu)第08章--查找課件

1、數(shù)據(jù)結(jié)構(gòu)（C+版）第1章 緒論第2章 線性表第3章 排序第4章 串第5章 棧與隊(duì)列第6章 數(shù)組和廣義表第7章 樹(shù)和二叉樹(shù)第8章 查找第9章 圖第10章 綜合應(yīng)用設(shè)計(jì)第8章 查找8.1 查找的基本概念8.2 線性表的查找8.3 二叉排序樹(shù)及其查找算法8.4 哈希查找數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞8.1 查找的基本概念查找表與關(guān)鍵字查找操作與查找結(jié)果查找表所具有的數(shù)據(jù)結(jié)構(gòu)查找方法查找算法的性能評(píng)價(jià)靜態(tài)查找表與動(dòng)態(tài)查找表查找技術(shù)的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞8.2 線性表的查找8.2.1 順序查找8.2.2 折半查找8.2.3 分塊查找數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞8.2.1 順序查找順序表的順序查找數(shù)據(jù)結(jié)構(gòu)（

2、C+版）葉核亞順序表的順序查找算法實(shí)現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞2. 單鏈表的順序查找 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞在單鏈表類Onelink中增加順序查找算法 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞3算法分析數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞8.2.2 折半查找數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞2折半查找算法實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞8.2.3 分塊查找分塊查找算法的基本思想“塊間有序、塊內(nèi)無(wú)序”。 靜態(tài)查找表的分塊查找動(dòng)態(tài)查找表的分塊查找數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞2. 靜態(tài)查找表的分塊查找數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞3動(dòng)態(tài)查找表的分塊查找數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞8.3 二叉排序樹(shù)及其查找算法二叉排序樹(shù)的定義二叉排序樹(shù)又稱二叉查找樹(shù)，

3、它可以是一棵空樹(shù)，若非空時(shí)具有下述性質(zhì)：若根結(jié)點(diǎn)的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字值均小于等于根結(jié)點(diǎn)的關(guān)鍵字值。若根結(jié)點(diǎn)的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字值均大于等于根結(jié)點(diǎn)的關(guān)鍵字值。根結(jié)點(diǎn)的左、右子樹(shù)也分別為二叉排序樹(shù)。數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞2二叉排序樹(shù)的建立數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞3. 二叉排序樹(shù)插入結(jié)點(diǎn)的遞歸算法 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞建立二叉排序樹(shù)的算法 數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞4. 二叉排序樹(shù)的查找數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞8.4 哈希查找哈希函數(shù)與哈希表哈希查找技術(shù)的設(shè)計(jì)思想設(shè)計(jì)一個(gè)好的哈希函數(shù)，盡可能地減少?zèng)_突。因?yàn)闆_突是不可避免的，發(fā)生沖突時(shí)，使用一種解決沖突的有效方法。設(shè)計(jì)哈希函數(shù)解決沖突的方法線性開(kāi)放尋址法拉鏈法數(shù)據(jù)結(jié)構(gòu)（C+版）葉核亞采用拉鏈法的哈希表結(jié)構(gòu) 設(shè)哈希函數(shù)hash(k) = k % 10關(guān)鍵字序列：9，4，12，