資料結構的查找問題

一、

1、查找表，是由同一類型的資料元素（或記錄）構成的集合；關鍵字，key是資料元素中某個資料項的值，又稱為鍵值；也可以辨別一個記錄的某個資料項（字段），稱為關鍵碼；若此關鍵字可以唯一地辨別一個記錄，則稱此關鍵字為主關鍵字；對于那些可以識别多個資料元素或記錄的關鍵字，稱為次關鍵字；

2、查找表按照操作方式可分為靜态查找表和動态查找

靜态查找表，隻作查找操作的查找表，主要操作有（1）：查詢某個特定的額資料元素是否在查找表中；（2）：檢索某個特定的資料元素和各種屬性；

動态查找表，在查找過程中同時插入查找表中不存在的資料元素，或者從查找表中删除已經存在的某個資料元素；即查找時插入或删除；

二、順序表查找

1、順序表查找，也叫線性查找，查找過程是從表中第一個（或最後一個）記錄開始，逐個進行記錄的關鍵字和給定值比較，若某個記錄的關鍵字和給定值相等，則查找成功，找到所查的記錄；如果知道最後一個記錄，其關鍵字和給定值比較都不等時，則表中沒有所查的記錄，查找不成功。

三、有序表查找

1、二分查找，前提是線性表中的記錄必須是關鍵碼有序，線性表必須采用順序存儲；二分查找的基本思想：在有序表中，取中間記錄作為比較對象，若給定值與中間記錄的關鍵字相等，則查找成功；若給定值小于中間記錄的關鍵字，則在中間記錄的左半區繼續查找；若給定值大于中間記錄的關鍵字，則在中間記錄的右半區繼續查找；不斷重複上述過程，直到查找成功，或所有查找區域無記錄，查找失敗為止；

2、插值查找，根據要查找的關鍵字key與查找表中最大最小記錄的關鍵字比較後的查找方法，其核心就在于插值的計算公式

low+(key-a[low])*(high-low)/(a[high]-a[low])

3、斐波那契查找

四、線性索引查找

1、索引，就是把一個關鍵字與它對應的記錄相關聯的過程；

2、線性索引，就是将索引項集合組織為線性結構，也成為索引表；

3、稠密索引，指線上性索引中，将資料集中的每個記錄對應一個索引項；對于稠密索引這個索引表來說，索引項一定是按照關鍵碼有序的排列；

4、分塊索引：

分塊有序，就是把資料集的記錄分成了若幹塊，并且這些塊需要滿足兩個條件：塊内無序和塊間有序；每塊對應一個索引項；

5、分塊索引的索引項結構分為三個資料項：最大關鍵碼，存儲每一塊中的最大關鍵字；塊中的記錄個數，用于指向塊首資料元素的指針；

6、反向索引，索引項的通用結構是：次關鍵碼和記錄号表；

其中記錄号表存儲具有相同次關鍵字的所有記錄的記錄号（可以是指向記錄的指針或者是該記錄的主關鍵字）

五、二叉排序樹

1、二叉排序樹也就是二叉查找樹，或者是一棵空樹，或者是具有以下性質的二叉樹：

若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

它的左、右子樹也分别為二叉排序樹；

六、平衡二叉樹AVL

1、平衡二叉樹是一種二叉排序樹，其中每一個節點的左子樹和右子樹的高度差至多等于1；

2、将二叉樹上結點的左子樹深度減去右子樹深度的值稱為平衡因子BF；

3、距離插入結點最近的，且平衡因子的絕對值大于1的結點為根的子樹，稱為最小不平衡子樹；

七、多路查找樹（B樹）

1、多路查找樹，其每一個結點的孩子數可以多于兩個，且每一個結點出可以存儲多個元素；

2、2-3樹，一種多路查找樹，其中的每一個結點都具有兩個孩子或三個孩子；一個2結點包含一個元素和兩個孩子（或沒有孩子），且與二叉排序樹類似；一個3結點包含一小一大兩個元素和三個孩子（或沒有孩子）；

3、2-3-4樹，一個4結點包含小中大三個元素和四個孩子（或沒有孩子），一個4結點要麼沒有孩子，要麼具有4個孩子；如果某個4結點有孩子的話，左子樹包含小于最小元素的元素，第二子樹包含大于最小元素，小于第二進制素的元素；第三子樹包含大于第二進制素，小于最大元素的元素；右子樹包含大于最大元素的元素；

4、B樹（B-tree）是一種平衡的多路查找樹，2-3樹和2-3-4樹都是B樹的特例；

結點最大的孩子數目稱為B樹的階；是以，2-3樹是3階B樹，2-3-4樹是4階B樹；

5、一個m階的B樹具有如下屬性：

如果根結點不是葉節點，則其至少有兩棵子樹；

每一個非根的分支結點都有k-1個元素和k個孩子；其中m/2向上取整<=k<=m；每一個葉子結點n都有k-1個元素；

所有葉子結點都位于同一層次；

所有分支結點包含下列資訊資料（n,A0,K1,A1,…Kn,An），其中Ki為關鍵字，且

Ki<Ki+1

;Ai為指向子樹根結點的指針，且指針Ai-1所指子樹中所有結點的關鍵字均小于Ki，An所指子樹中所有結點的關鍵字均大于Kn，n*（m/2向上取整<=n<=m-1）為關鍵字的個數（或n+1為子樹的個數）；

6、B+樹，出現在分支結點中的元素會被當做它們在該分支結點位置的中序後繼者（葉子結點）中再次列出；另外，每一個葉子結點都會儲存一個指向後一葉子結點的指針；

7、一棵m階的B+樹和m階的B樹的差異在于：

有n棵子樹的結點中包含有n個關鍵字；

所有的葉子結點包含全部關鍵字的資訊，及指向含這些關鍵字記錄的指針，葉子結點本身依關鍵字的大小自小而大順序連結；

所有分支結點可以看成是索引，結點中僅含有其子樹中的最大（或最小）關鍵字；

八、散清單查找（哈希表）概述

1、散列技術是在記錄的存儲位置和它的關鍵字之間建立一個确定的對應關系f，使得每個關鍵字key對應一個存儲位置f(key)；其中對應關系f稱為散列函數，又稱為哈希（hash）函數；

采用散列結束将記錄存儲在一塊連續的存儲空間中，這塊連續存儲空間稱為散清單或哈希表（hash table）；關鍵字對應的記錄存儲位置稱為散列位址；

2、在存儲時，通過散列函數計算記錄的散列位址，并按此散列位址存儲該記錄；

當查找記錄時，通過同樣的散列函數計算記錄的散列位址，按此散列位址通路該記錄；

散列技術既是一種存儲方法，也是一種查找方法；

3、兩個關鍵字key1不等于key2,但是卻有f(key1)=f(key2)，這種現象稱為沖突，并把key1和key2稱為這個散列函數的同義詞；

九、散列函數的構造方法

1、好的散列函數：計算簡單，散列位址分布均勻；

2、直接定址法：取關鍵字的某個線性函數值為散列位址f(key)=a*key+b;

3、數字分析法：對數字進行一定左移、右移或旋轉

4、平方取中法：平方，取平方數中間三位數

5、折疊法：将關鍵字從左到右分割成位數相等的幾部分（注意最後一部分位數不夠時可以短些），然後将這幾部分疊加求和，并按散清單表長，取後幾位作為散列位址；

6、除留餘數法：f(key)=key mod p (p<=m)

7、随機法：f(key)=random (key);

十、處理散列沖突的方法

1、開放定址法：一旦發生沖突，就去尋找下一個空的散列位址，隻要散清單足夠大，空的散列位址總能找到，并将記錄存入；

f(key)=(f(key)+d) mod m

;

這種解決沖突的開放定址法稱為線性探測法；

2、本來都不是同義詞卻需要争奪一個位址的情況稱為堆積

3、增加平方運算的目的是為了不讓關鍵字都聚集在某一塊區域，稱為二次探測法

fi(key)=(f(key)+di) mod m (di=1^2,-1^2,2^2,-2^2,...,q^2,-q^2,q<=m/2)
           

4、在沖突時，對于位移量di采用随機函數計算得到，稱之為随機探測法；

5、再散列函數法：用多個散列函數，每當發生散列位址沖突時就換一個散列函數計算；

6、鍊位址法：将所有關鍵字為同義詞的記錄存儲在一個單連結清單中，稱這種表為同義詞子表；

7、公共溢出區法：為所有沖突的關鍵字建立一個公共的溢出區來存放；

十一、散清單查找實作

1、性能：

散列函數是否均勻；

處理沖突的方法；

散清單的裝填因子=填入表中的記錄個數/散清單長度；