數(shù)據(jù)結(jié)構(gòu)講義第9章查找

《數(shù)據(jù)結(jié)構(gòu)講義第9章查找》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第9章查找9.1基本概念和術(shù)語9.2靜態(tài)查找表9.2.1順序查找9.2.2折半查找9.2.3分塊查找9.3動態(tài)查找表9.3.1二叉排序樹9.3.2平衡二叉樹9.3.3B-樹和B+樹9.4哈希表9.4.1什么是哈希表9.4.2哈希函數(shù)的構(gòu)造方法9.4.3處理沖突的方法9.4.5哈希表的查找和分析9.5小結(jié)9.1基本概念和術(shù)語1數(shù)據(jù)項(也稱項或字段):是具有獨立含義的標(biāo)識單位，是數(shù)據(jù)不可分割的最小單位。2組合項由若干項、組合項構(gòu)成。3數(shù)據(jù)元素（記錄）是由若干項、組合項構(gòu)成的數(shù)據(jù)單位，是在某一問題中作為整體進(jìn)行考慮和處理的基本單位。9.1基本概念和術(shù)語4關(guān)鍵碼（key）

2、關(guān)鍵碼是數(shù)據(jù)元素（記錄）中某個項或組合項的值，用它可以標(biāo)識一個數(shù)據(jù)元素（記錄）。能唯一確定一個數(shù)據(jù)元素（記錄）的關(guān)鍵碼，稱為主關(guān)鍵碼(PrimaryKey)；不能唯一確定一個數(shù)據(jù)元素（記錄）的關(guān)鍵碼，稱為次關(guān)鍵碼(SecondaryKey)。9.1基本概念和術(shù)語5查找表(SearchTable)是由具有同一類型（屬性）的數(shù)據(jù)元素組成的集合（又稱為字典）。分為靜態(tài)查找表和動態(tài)查找表兩類:靜態(tài)查找表(StaticSearchTable)：僅對查找表進(jìn)行查找操作，而不能改變的表；動態(tài)查找表(DynamicSearchTable)：對查找表除進(jìn)行查找操作外，允許向表中插入

3、或刪除表中數(shù)據(jù)元素的表。9.1基本概念和術(shù)語6.查找(searching)按給定的某個值kx，在查找表中確定一個其關(guān)鍵碼等于kx的數(shù)據(jù)元素（記錄）。9.1基本概念和術(shù)語7數(shù)據(jù)元素類型說明typedefstruct{/*出生日期類型定義*/charyear[5]；/*年：用字符型表示，寬度為4個字符*/charmonth[3]；/*月：字符型，寬度為2*/chardate[3]；/*日：字符型，寬度為2*/}BirthDate；typedefstruct{/*數(shù)據(jù)元素類型定義*/charnumber[7]；/*學(xué)號：字符型，寬度為6*/charname[9]；/*姓

4、名：字符型，寬度為8*/charsex[3]；/*性別：字符型，寬度為2*/BirthDatebirthdate；/*出生日期:構(gòu)造類型*/charcomefrom[21]；/*來源：字符型，寬度為20*/intresults；/*成績：整型，寬度由“C語言”決定*/}ElemType；9.1基本概念和術(shù)語8查找表的類型定義例：用線性表表示查找表：（1）用順序表來表示查找表：typedefMAXSIZE1000typedefstruct{//順序存儲結(jié)構(gòu)ElemTypeelem[MAXSIZE+1]；intlength;}SStable;（2）用單鏈表表示查找表t

5、ypedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;用其它形式表示的線性表的類型定義在以后的章節(jié)中解釋。9.1基本概念和術(shù)語說明：本章以后討論中，涉及的關(guān)鍵碼類型和數(shù)據(jù)元素類型統(tǒng)一說明如下：typedefstruct{KeyTypekey；/*關(guān)鍵碼字段，可以是整型、字符型、構(gòu)造型等*/……/*其它字段*/}ElemType；9.2靜態(tài)查找表9.2.1順序查找9.2.2折半查找9.2.3分塊查找9.2靜態(tài)查找表（基于線性表的查找）靜態(tài)查找表結(jié)構(gòu)靜態(tài)查找表是數(shù)據(jù)元素的線性表，可以是基于數(shù)組

6、的順序存儲或以線性鏈表存儲。typedefMAXSIZE1000typedefstruct{//順序存儲結(jié)構(gòu)ElemTypeelem[MAXSIZE+1]；intlength;}SStable;typedefstructLNode{//鏈?zhǔn)酱鎯Y(jié)構(gòu)ElemTypedata;structLNode*next;}LNode,*LinkList;9.2靜態(tài)查找表（基于線性表的查找）9.2.2順序查找(SequentialSearch)查找方法：從表的一端開始，向另一端逐個按給定值kx與關(guān)鍵碼進(jìn)行比較，若找到，查找成功，并給出數(shù)據(jù)元素在表中的位置；若整個表檢測完，仍未找到

7、與kx相同的關(guān)鍵碼，則查找失敗，給出失敗信息。例：給定kx=56,90，在下表中進(jìn)行順序查找。1913372105567592648088012345678910119.2靜態(tài)查找表（基于線性表的查找）9.2.1順序查找//不設(shè)置監(jiān)視哨的順序查找算法intsearch_Seq(SSTableST，KeyTypekx){i=l.length;while(i>=1&&ST.elem[i].key!=kx)i--;returni;}9.2靜態(tài)查找表（基于線性表的查找）9.2.1順序查找【算法9.1】以順序存儲為例，數(shù)據(jù)元素從下標(biāo)為1的數(shù)組單元開始存放，0號單元留空。in

8、tsear