軟考軟件設(shè)計師專題講義九：數(shù)據(jù)結(jié)構(gòu)相關(guān)算法

　　3.2查找算法

　　查找就是在按某種數(shù)據(jù)結(jié)構(gòu)形式存儲的數(shù)據(jù)集合中，找出滿足指定條件的結(jié)點(diǎn)。

　　按查找的條件分類：

　　u 有按結(jié)點(diǎn)的關(guān)鍵碼查找;

　　u 關(guān)鍵碼以外的其他數(shù)據(jù)項查找;

　　u 其他數(shù)據(jù)項的組合查找;

　　按查找數(shù)據(jù)在內(nèi)存或外存：分內(nèi)存查找和外存查找。

　　按查找目的：

　　u 查找如果只是為了確定指定條件的結(jié)點(diǎn)存在與否，成為靜態(tài)查找;

　　u 查找是為確定結(jié)點(diǎn)的插入位置或為了刪除找到的結(jié)點(diǎn)，稱為動態(tài)查找。

　　這里簡單介紹幾種常見的查找方法。

　　u 順序存儲線性表的查找

　　這是最常見的查找方式。結(jié)點(diǎn)集合按線性表組織，采用順序存儲方式，結(jié)點(diǎn)只含關(guān)鍵碼，并且是整數(shù)。如果線性表無序，則采用順序查找，即從線性表的一端開始逐一查找。而如果線性表有序，則可以使用順序查找、二分法查找或插值查找。

　　u 分塊查找

　　分塊查找的過程分兩步，先用二分法在索引表中查索引項，確定要查的結(jié)點(diǎn)在哪一塊。然后，再在相應(yīng)塊內(nèi)順序查找。

　　u 鏈接存儲線性表的查找

　　對于鏈接存儲線性表的查找只能從鏈表的首結(jié)點(diǎn)開始順序查找。同樣對于無序的鏈表和有序的鏈表查找方法不同。

　　動態(tài)查找表的不同表示方法：

　　二叉排序樹(二叉查找樹)：或者是一棵空樹，或者是具有下列性質(zhì)的一棵樹：

　　u 若左子樹不空，則左子樹上的所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值;

　　u 若右子樹不空，則右子樹上的所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值;

　　u 它的左右子樹也分別是二叉排序樹;

　　二叉排序樹的查找分析：在隨機(jī)的情況下，其平均查找長度為1+4logn;

　　平衡二叉樹：或者是棵空樹，或者是具有下列性質(zhì)的二叉樹：

　　u 它的左子樹和右子樹都是平衡二叉樹;

　　u 左子樹和右子樹的深度之差不會超過1;

　　平衡二叉樹的查找分析：在查找過程中和給定值進(jìn)行比較的關(guān)鍵字個數(shù)不超過樹的深度，，因此其平均查找的時間復(fù)雜度是O(logn);

　　　　　　　計算機(jī)軟考軟件設(shè)計師練習(xí)試題及答案解析匯總