二分查找法、哈希查找法、二叉排序樹查找法等各種查找算法。1. 線性表上的查找： 主要分為三種線性結構：順序表，有序順序表，索引順序表。對於第壹種，我們采用傳統查找方法，逐個比較。對於及有序順序表我們采用二分查找法。對於第三種索引結構，我們采用索引查找算法。其中，二分查找還要特別註意適用條件以及其遞歸實現方法。 2.樹表上的查找： 樹表主要分為以下幾種：二叉排序樹，平衡二叉樹，B樹，鍵樹。由於二叉排序樹與平衡二叉樹是壹種特殊的二叉樹，所以與二叉樹的聯系就更為緊密。 二叉排序樹，它的中序遍歷結果是壹個遞增的有序序列。平衡二叉樹是二叉排序樹的優化，其本質也是壹種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定。 B樹是二叉排序樹的進壹步改進，也可以把B樹理解為三叉、四叉....排序樹。因為這兩種算法涉及到B樹結點的分裂和合並，是壹個難點。鍵樹也稱字符樹，特別適用於查找英文單詞的場合。壹般不要求能完整描述算法源碼，多是根據算法思想建立鍵樹及描述其大致查找過程。 3.基本哈希表的查找算法： 哈希表查找的基本思想是：根據當前待查找數據的特征，以記錄關鍵字為自變量，設計壹個function，該函數對關鍵字進行轉換後，其解釋結果為待查的地址。堆排序屬於選擇排序類型的排序，是壹樹形選擇排序。堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。 堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近於最壞性能。 由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。 堆排序是就地排序，輔助空間為O(1)， 它是不穩定的排序方法。堆排序，是利用堆這種數據結構的性質，通過堆元素的刪除、調整等壹系列操作將最小數選出放在堆頂。堆排序的特點是：在排序過程中，將R[l..n]看成是壹棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系，在當前無序區中選擇關鍵字最大(或最小)的記錄。堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這壹特征，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
vae.la
上一篇:X4基石新手攻略指南主要系統和機制常見問題下一篇:Node.js真的有高並發優勢嗎