數(shù)據(jù)結(jié)構(gòu)08查找教學(xué)課件

第8章查找81》查找的基本概念82》靜態(tài)查找算法83〉二叉查找樹的動(dòng)態(tài)查找散列及散列表的動(dòng)態(tài)查找民郵電出版社點(diǎn)密此處結(jié)羨狼通過計(jì)算機(jī)獲取信息的手段,就是通常所說的“查找”,或“檢索”。它是最為常見、使用頻率最高、程序中耗費(fèi)時(shí)間最多的種對(duì)數(shù)據(jù)的操作,是讀取、插入、修改、刪除等操作的基礎(chǔ)民郵電出版社點(diǎn)密此處結(jié)羨狼本章主要介紹以下幾個(gè)方面的內(nèi)容:·有關(guān)查找的基本概念;·各種靜態(tài)査找算法;基于二叉查找樹的動(dòng)態(tài)査找算法·基于散列表的動(dòng)態(tài)査找算法。民郵電出版社點(diǎn)密此處激映8.1查找的基本概念設(shè)集合T里有n條記錄,形式如下:k1,I1),(k2,I2),(k3,I3),…,(knIn)其中,k1、k2、…、k是互不相同的n個(gè)關(guān)鍵字值,I1是與k相關(guān)聯(lián)的記錄信息(1≤i≤n)。給定某個(gè)值K?！安檎摇本褪且诩蟃中尋找出一個(gè)記錄(k,I),使得有k=K民郵電出版社點(diǎn)密此處激映查找成功的含義就是在T里找到一個(gè)關(guān)鍵字為k的記錄,使得k=K;查找失敗就是在T里找不到記錄,使得kK(可能在T里不存在這樣的記錄)。民郵電出版社點(diǎn)密此處結(jié)羨狼記錄中的關(guān)鍵字k;,是記錄(即數(shù)據(jù)元素)中的一個(gè)數(shù)據(jù)項(xiàng)。由于互不相同,因此可以用它們來標(biāo)識(shí)記錄。能夠唯一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng),被稱為是記錄的“主關(guān)鍵字”,簡(jiǎn)稱“關(guān)鍵字(Key)”;不能唯標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng),稱為記錄的“次關(guān)鍵字”。民郵電出版社點(diǎn)密此處激映有n條記錄的集合T是實(shí)施查找的基礎(chǔ)。在討論查找問題時(shí),常把T稱為“査找表”如果查找只是為了獲取是否成功以及相應(yīng)的記錄信息,并不去改變查找表的內(nèi)容,那么這種査找稱為“靜態(tài)査找”,這時(shí)的查找表稱為“靜態(tài)査找表”;如果查找過程會(huì)伴隨著對(duì)數(shù)據(jù)元素的變更,那么這種查找稱為“動(dòng)態(tài)査找”,這時(shí)的查找表稱為“動(dòng)態(tài)查找表”民郵電出版社點(diǎn)密此處激映查找時(shí),人們總是用給定值K與各記錄的關(guān)鍵字k;(1≤m)進(jìn)行比較的。若用C表示查找第個(gè)記錄時(shí)需要進(jìn)行比較的次數(shù),用P表示要查找第i個(gè)記錄的概率,那么查找成功的“平均查找長(zhǎng)度(ASL)”為:ASL=∑P*C民郵電出版社點(diǎn)密此處激映82靜態(tài)查找算油對(duì)于一般的無序線性表(順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)),進(jìn)行靜態(tài)查找時(shí)采用的都是大家熟悉的順序查找算法。也就是從查找表的第1個(gè)記錄開始,將K按順序依次與每個(gè)記錄的關(guān)鍵字比較,直到找到要查找的記錄(找到),或到達(dá)查找表的末尾(沒有找到)為止。這種查找的效率是比較低的。民郵電出版社點(diǎn)密此處激映若已經(jīng)根據(jù)某種規(guī)則對(duì)靜態(tài)查找