第6章查找表張成文北京郵電大學計算機學院編輯ppt第6章查找第6章查找6.1相關概念和術語[術語]查找表同一類型的記錄(數據元素)的集合。

數據元素之間存在著松散的關系。為了提高查找的效率，可在元素之間人為地附加某種確定的關系。關鍵字記錄(數據元素)中的某個數據項的值。

主關鍵字該關鍵字可以唯一地標識一個記錄。

次關鍵字該關鍵字不能唯一標識一個記錄。查找指定某個值，在查找表中確定是否存在一個記錄，該記錄的關鍵字等于給定值。靜態查找表對查找表的查找僅是以查詢為目的，不改動查找表中的數據。動態查找表在查找的過程中同時插入不存在的記錄，或刪除某個已存在的記錄。查找成功查找表中存在滿足查找條件的記錄。查找不成功查找表中不存在滿足查找條件的記錄。數據項1數據項2……記錄（數據元素）2編輯ppt第6章查找6.2靜態查找表6.2.1順序表的查找6.2.2有序表的查找6.2.3索引順序表的查找數據穩定，變動很少的查找表3編輯ppt第6章查找6.2.1順序表的查找

靜態查找表以順序表表示012nST.elem[0..n]a1a2an[算法描述]typedefstruct{ ElemType*elem; intlength;}SSTable;keyintSearch_Seq1(SSTableST,KeyTypekey){ i=1；

while(i<=ST.length&&ST.elem[i].key!=key)i++; if(i<=ST.length)returni;elsereturn0;}//Search_Seq1intSearch_Seq2(SSTableST,KeyTypekey){ ST.elem[0].key=key; for(i=ST.length;ST.elem[i].key!=key;i--)；

returni;}//Search_Seq24編輯ppt第6章查找[程序設計技巧]

設置監視哨，查找時每一步不必檢測位置是否越界，提高算法效率。[算法特點]算法簡單，對表中元素排列順序無任何要求n很大時查找效率較低改進措施：非等概率查找時，可將查找概率高的記錄盡量排在表前部。逐個查找的方法也可用于線性鏈表表示的靜態查找表5編輯ppt第6章查找6.2.2有序表的查找

滿足r[i].keyr[i+1].key,1i<n

仍可用順序查找，但在找不到時不需比較到表尾，只需比較到比給定值大的記錄就可終止。[折半(對半/二分)查找法]

01234567891011

0513192137566475808892lowmidhigh=(low+high)/2

K=21lhmK=85

lhm1116111615371194541011101096編輯ppt第6章查找[算法描述]intSearch_Bin(SSTableST,keytypekey){low=1;high=ST.length;//置區間初值

while(low<=high) { mid=(low+high)/2; if(key==ST.elem[mid].key) returnmid;//找到待查元素

elseif(key<ST.elem[mid].key)high=mid-1;//繼續在前半區間進行查找

elselow=mid+1;//繼續在后半區間進行查找

}return0;//順序表中不存在待查元素}//Search_Bin7編輯ppt第6章查找6.2.3索引順序表的查找

[表的構造]

索引表index[1..b]

最大關鍵字值224286

起始地址159

主表r[1..n]（分塊有序/有序）

key12221382833384286765063

其它項

123456789101112[分塊查找步驟]1)折半或者順序查找索引表，確定所在塊2)在已確定的塊中順序查找/折半查找8編輯ppt第6章查找[性能分析]索引順序查找的平均查找長度=

查找“索引”的平均查找長度

+查找“塊”的平均查找長度9編輯ppt第6章查找[算法特點]實用中，各塊大小不一定相等分塊查找的代價是附加索引表的存儲空間開銷和建立索引表的時間開銷可以在主表的每塊后預留空閑位置，以便進行插入和刪除操作時只涉及相應的塊和該塊的索引項。主表中各塊可以集中順序存儲，也可以按塊分別順序存儲；主表中的記錄還可以采用單鏈表，或每塊組成一個單鏈表。主表索引表10編輯ppt第6章查找6.3動態查找表二叉排序樹頻繁進行插入、刪除的查找表11編輯ppt第6章查找二叉排序樹BST(二叉查找/搜索樹)1.定義

二叉排序樹或者是空樹，或者是滿足如下性質的二叉樹：

1)若其左子樹非空，則左子樹上所有結點的值均小于根結點的值；

2)若其右子樹非空，則右子樹上所有結點的值均大于等于根結點的值；

3)其左右子樹本身又各是一棵二叉排序樹2.性質中序遍歷一棵二叉排序樹，將得到一個以關鍵字遞增排列的有序序列45245312289012編輯ppt第6章查找在二叉排序樹上的操作

通常，取二叉鏈表作為存儲結構1)查找BitreeSearchBST(BiTreeT,KeyTypekey)//在二叉排序樹T中查找關鍵字值為key的結點，//找到返回該結點的地址，否則返回空。

{if(（!T）||EQ(key,T->data.key))

return(T);

elseif(LT(key,T->data.key))

return(SearchBST(T->lchild,key));

elsereturn(SearchBST(T->rchild,key));}//SearchBSTP228-9.5（a）452453122890Tkey=28查找成功key=32查找失敗null13編輯ppt第6章查找452453122890T32fStatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p)//f指向當前結點的雙親,初始調用值為NULL。//查找成功，p指向該結點，并返回TRUE；//查找失敗，p指向查找路徑上的最后一個結點，并返回FALSE{if(!T){p=f;returnFALSE;}elseifEQ(key,T->data.key){p=T;returnTRUE;}elseifLT(key,T->data.key)returnSearchBST(T->lchild,key,T,p);elsereturnSearchBST(T->rchild,key,T,p);}//SearchBSTP228-9.5(b)StatusInsertBST(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,P)){s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!T)T=s;elseifLT(e.key,p->data.key)p->lchild=s;elsep->rchild=s;returnTRUE;}elsereturnFALSE}//InsertBSTP228-9.62)插入14編輯ppt第6章查找3)生成從空樹出發，反復調用插入操作InsertBST即可。[例]{10，18，3，8，12，2，7，3}101018101831018381018381210183812210183812271018381227315編輯ppt第6章查找4)刪除53

20901050869541241528891304587899239(1)(2)(2)(3)被刪除結點為*p的不同情況分析：

p是葉子結點：修改其雙親指針即可p只有左孩子：用p的左子樹代替以p為根的子樹

p只有右孩子：用p的右子樹代替以p為根的子樹p有兩個孩子：找到p的中序后繼(或前趨)結點q；

q的數據復制給p；刪除只有右孩子(或左孩子)/無孩子的q。16編輯ppt第6章查找之前各種查找表的結構特點：記錄在表中的位置和它的關鍵字之間不存在一個確定的關系查找的過程為給定值依次和集合中各個關鍵字進行比較，查找的效率取決于和給定值進行比較的關鍵字個數。不同的表示方法，其差別僅在于：