6-1查找概述v第六章查找技術關鍵碼數(shù)據(jù)元素、結點、頂點關鍵碼：可以標識一個記錄的某個數(shù)據(jù)項鍵值：關鍵碼的值56女李爽000535女齊梅000457女劉楠000335男張亮000248男王剛0001年齡性別姓名職工號1982.92003.71979.92003.71990.4工作時間主關鍵碼：可以唯一標識一個記錄的關鍵碼次關鍵碼：不能唯一標識一個記錄的關鍵碼什么是查找查找：在相同類型的記錄構成的集合中找出滿足給定條件的記錄50女李爽000525女齊梅000447女劉楠000325男張亮000238男王剛0001年齡性別姓名職工號1972.92003.71979.92003.71990.4工作時間查找的結果：若在查找集合中找到了與給定值相匹配的記錄，則稱查找成功；否則，稱查找失敗給定的查找條件可能是多種多樣的把查找條件限制為“匹配”，即查找關鍵碼等于給定值的記錄

靜態(tài)查找：不涉及插入和刪除操作的查找動態(tài)查找要求插入、刪除、查找均有較好的效率，適用于：查找與插入和刪除操作在同一個階段進行例如：當查找成功時，要刪除查找到的記錄當查找不成功時，要插入被查找的記錄動態(tài)查找：涉及插入和刪除操作的查找靜態(tài)查找只注重查找效率，適用于：（1）查找集合一經(jīng)生成，便只對其進行查找，而不進行插入和刪除操作（2）經(jīng)過一段時間的查找之后，集中地進行插入和刪除等修改操作查找的分類查找結構查找結構：面向查找操作的數(shù)據(jù)結構，即查找基于的數(shù)據(jù)結構查找結構

查找方法

已經(jīng)有了數(shù)據(jù)結構的概念，為什么要強調查找結構？（1）幾乎所有的數(shù)據(jù)結構都提供了查找作為基本操作，但對于數(shù)據(jù)結構整體來說，查找并不是最重要的操作（3）數(shù)據(jù)結構+算法=程序：不同的查找結構，會獲得不同的查找效率（2）對于查找結構來說，查找是最重要的基本操作，重要的是查找效率線性表：適用于靜態(tài)查找，順序查找、折半查找等技術樹表：適用于動態(tài)查找，二叉搜索樹的查找技術散列表：靜態(tài)查找和動態(tài)查找均適用，采用散列技術查找基于的數(shù)據(jù)模型是什么？集合集合注意到，都是把集合組織成XXX表，為什么？理解起來，集合最常用的表示法是列舉法，習慣上，也稱為表查找結構平均查找長度如何評價查找算法的效率呢？和關鍵碼的比較次數(shù)關鍵碼的比較次數(shù)與哪些因素有關呢？其中：n：問題規(guī)模，查找集合中的記錄個數(shù)

pi：查找第i個記錄的概率ci：查找第i個記錄所需的關鍵碼的比較次數(shù)ASL?==niiicp1平均查找長度：查找算法進行的關鍵碼比較次數(shù)的