数据结构:静态查找动态查找
概念
1、靜態查找
首先無論是靜態查找還是動態查找,都要有查找的對象,也就是包含很多同類型數據的“表”,這個“表”可以理解為一個由同類型數據元素組成的一個“集合”,該集合可以用各種容器來存儲,例如數組、鏈表、樹等,我們統稱這些存儲數據的數據結構為——查找表。可見,查找表有時是我們傳統意義的表,有時候是很復雜的一種結構。
靜態查找就是我們平時概念中的查找,是“真正的查找”。之所以說靜態查找是真正的查找,因為在靜態查找過程中僅僅是執行“查找”的操作,即:(1)查看某特定的關鍵字是否在表中(判斷性查找);(2)檢索某特定關鍵字數據元素的各種屬性(檢索性查找)。這兩種操作都只是獲取已經存在的一個表中的數據信息,不對表的數據元素和結構進行任何改變,這就是所謂的靜態查找。
2、動態查找
看到上面靜態查找的概念,動態查找就很好理解了,個人總覺得動態查找不像是“查找”,更像是一個對表進行“創建、擴充、修改、刪除”的過程。動態查找的過程中對表的操作會多兩個動作:(1)首先也有一個“判斷性查找”的過程,如果某特定的關鍵字在表中不存在,則按照一定的規則將其插入表中;(2)如果已經存在,則可以對其執行刪除操作。動態查找的過程雖然只是多了“插入”和“刪除”的操作,但是在對具體的表執行這兩種操作時,往往并不是那么簡單。
哪種查找對應各自查找表,如有序表可以為靜態查找表,也可以為動態查找表。依查找方式決定。
一、靜態查找表
1.順序查找
假設每個記錄的查找概率相等,順序查找的平均查找長度:
假設查找成功與不成功的可能性相同,對每個記錄查找概率也相等,則,此時平均查找長度為
2.有序表查找
折半查找:這個查找過程類似二叉樹,具有n個節點的判定樹深度為,平均查找長度為
3.索引順序表的查找(分塊查找)
對子表建立一個索引表,包括兩項內容:關鍵字項(值為該子表內最大關鍵字)和指針項(指向該子表的第一個記錄在表中的位置)。索引表按關鍵字有序,表或者有序,或者分塊有序。
由于索引項按關鍵字有序,則確定塊的查找可以用順序表查找,也可以用折半查找,塊中記錄是任意排列的,在塊中只能是順序查找。
分塊查找由這兩種查找算法簡單合成。分塊查找的平均查找長度為
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?,?
其中:為查找索引表確定所在塊的平均查找長度,為在塊中查找元素的平均查找長度。
一般情況下,為進行分塊查找,可以將長度為n的表均勻的分成b塊,每塊含有s個記錄;假定表中每個記錄的查找概率相等。用順序查找確定所在塊,分塊查找的平均查找長度為
? ? ? ? ? ? ? ? ? ? ? ? ? ??
分塊查找是折半查找和順序查找的一種改進方法,折半查找雖然具有很好的性能,但其前提條件時線性表順序存儲而且按照關鍵碼排序,這一前提條件在結點樹很大且表元素動態變化時是難以滿足的。而順序查找可以解決表元素動態變化的要求,但查找效率很低。如果既要保持對線性表的查找具有較快的速度,又要能夠滿足表元素動態變化的要求,則可采用分塊查找的方法。
分塊查找的速度雖然不如折半查找算法,但比順序查找算法快得多,同時又不需要對全部節點進行排序。當節點很多且塊數很大時,對索引表可以采用折半查找,這樣能夠進一步提高查找的速度。
分塊查找由于只要求索引表是有序的,對塊內節點沒有排序要求,因此特別適合于節點動態變化的情況。當增加或減少節以及節點的關鍵碼改變時,只需將該節點調整到所在的塊即可。在空間復雜性上,分塊查找的主要代價是增加了一個輔助數組。
平均查找長度:
以一個牛客網上的題目為例:設順序線性表的長度為30,分成5塊,每塊6個元素,如果采用分塊查找并且索引表和塊內均采用順序查找,則其平均查找長度為( ? ? )。
分塊查找會分兩部分進行,第一步先進行索引表查找判斷其在那個字表中,第二步然后進行在字表中的查找
索引表有5個元素 所以平均查找長度為:(1+5)/2=3
字表中有6個元素,所以平均查找長度為:(1+6)/2=3.5
所以總的平均查找長度為3+3.5=6.5
二、動態查找表
2.1二叉排序樹與AVL樹
2.1.1二叉排序樹
含有n個節點的二叉排序樹的平均查找長度和樹的形態有關,最好和成正比,當先后插入的關鍵字有序,構成的二叉排序樹蛻變為單支樹,樹的深度為n,最壞情況,平均查找長度為。
2.1.2平衡二叉樹(AVL樹)
它或者是一棵空樹,或者是具有下列性質的二叉樹:它的左子樹和右子樹都是平衡二叉樹,且左右子樹的深度之差絕對值不超過1。結點平衡因子定義為左子樹深度減右子樹深度(-1,0,1)。平均查找時間復雜度。
2.2B-樹和B+樹
一棵m階B-樹,或為空樹,或滿足下列特性的m叉樹:(是一種平衡的多路查找樹)
m階B+樹和m階B-樹的差異在于:
參考文獻:
數據結構(C語言版),嚴蔚敏?
https://blog.csdn.net/pamchen/article/details/8476134
總結
以上是生活随笔為你收集整理的数据结构:静态查找动态查找的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 数据结构:哈希表函数构造和冲突解决方法
- 下一篇: python错误处理