數據結構復習總結第九章查找

　　第九章查找

　　*************************************************************************************

　　查找的同時對表做修改操作(如插入或刪除)則相應的表稱之為動態查找表否則稱之為靜態查找表

　　衡量查找算法效率優劣的標准是在查找過程中對關鍵字需要執行的平均比較次數(即平均查找長度ASL)

　　*************************************************************************************

　　線性表查找的方法 ·順序查找逐個查找ASL=(n+)/;

　　·二分查找取中點int(n/)比較若小就比左區間大就比右區間用二叉判定樹表示ASL=(∑(每層結點數*層數))/N

　　·分塊查找要求分塊有序將表分成若干塊內部不一定有序並抽取各塊中的最大關鍵字及其位置建立有序索引表

　　*************************************************************************************

　　二叉排序樹(BST)定義是二叉排序樹是空樹或者滿足如下性質的二叉樹 ·若它的左子樹非空則左子樹上所有結點的值均小於根結點的值;

　　·若它的右子樹非空則右子樹上所有結點的值均大於根結點的值;

　　·左右子樹本身又是一棵二叉排序樹

　　二叉排序樹的插入建立刪除的算法平均時間性能是O(nlogn)

　　二叉排序樹的刪除操作可分三種情況進行處理 ·*P是葉子則直接刪除*P即將*P的雙親*parent中指向*P的指針域置空即可

　　·*P只有一個孩子*child此時只需將*child和*p的雙親直接連接就可刪去*p

　　·*p有兩個孩子則先將*p結點的中序後繼結點的數據到*p刪除中序後繼結點

　　*************************************************************************************

　　關於B樹(多路平衡查找樹)它適合在磁盤等直接存取設備上組織動態的查找表是一種外查找算法建立的方式是從下向上拱起

　　*************************************************************************************

　　散列技術將結點按其關鍵字的散列地址存儲到散列表的過程稱為散列散列函數的選擇有兩條標准簡單和均勻

　　常見的散列函數構的造方法 ·平方取中法hash=int((x^)%)

　　·除余法表長為mhash=x%m

　　·相乘取整法hash=int(m*(x*Aint(x*A));A=

　　·隨機數法hash=random(x)

　　*************************************************************************************

　　處理沖突的方法·開放定址法 ·一般形式為hi=(h(key)+di)%m≤i≤m開放定址法要求散列表的裝填因子α≤

　　·開放定址法類型 ·線性探查法address=(hash(x)+i)%m;

　　·二次探查法address=(hash(x)+i^)%m;

　　·雙重散列法address=(hash(x)+i*hash(y))%m;

　　·拉鏈法 ·是將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中

　　·拉鏈法的優點 ·拉鏈法處理沖突簡單且無堆積現象;

　　·鏈表上的結點空間是動態申請的適於無法確定表長的情況;

　　·拉鏈法中α可以大於結點較大時其指針域可忽略因此節省空間;

　　·拉鏈法構造的散列表刪除結點易實現

　　·拉鏈法也有缺點當結點規模較小時用拉鏈法中的指針域也要占用額外空間還是開放定址法省空間

From:http://tw.wingwit.com/Article/program/sjjg/201311/23747.html