3.2查找算法

　　查找就是在按某種數據結構形式存儲的數據集合中，找出滿足指定條件的結點。

　　按查找的條件分類：

　　u 有按結點的關鍵碼查找;

　　u 關鍵碼以外的其他數據項查找;

　　u 其他數據項的組合查找;

　　按查找數據在內存或外存：分內存查找和外存查找。

　　按查找目的：

　　u 查找如果只是為了確定指定條件的結點存在與否，成為靜態查找;

　　u 查找是為確定結點的插入位置或為了刪除找到的結點，稱為動態查找。

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

　　u 順序存儲線性表的查找

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

　　u 分塊查找

　　分塊查找的過程分兩步，先用二分法在索引表中查索引項，確定要查的結點在哪一塊。然后，再在相應塊內順序查找。

　　u 鏈接存儲線性表的查找

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

　　動態查找表的不同表示方法：

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

　　u 若左子樹不空，則左子樹上的所有節點的值都小于根節點的值;

　　u 若右子樹不空，則右子樹上的所有節點的值都大于根節點的值;

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

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

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

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

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

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

　　　　　　　計算機軟考軟件設計師練習試題及答案解析匯總