1、查找表：同一型別的資料元素構成的集合，
2、對查找表進行的操作：查詢某特定元素、檢索滿足條件的元素的屬性、插入元素、洗掉元素，
1）若對查找表進行的操作只涉及前兩種，則為靜態查找表；需要進行插入和洗掉，則為動態查找表，
2）適合靜態查找表的查找方法：順序查找、折半查找、散列查找，
3）適合動態查找表的查找方法：二叉排序樹（二叉平衡樹和B樹都是二叉排序樹的改進）的查找、散列查找，
3、順序查找（線性查找）：用于在線性表中進行查找，
1）一般線性查找表的順序查找
（1）對于n個元素的表，查找成功的平均查找長度為ASL成功=Pi(n-i-+1)，（從1到N求和），
（2）當每個元素查找概率相等時，即Pi=1/n，ASL成功=(n+1)/2，ASL失敗=n+1，
2）有序表的順序查找
查找成功的平均查找長度和一般線性查找表的順序查找一樣；查找不成功時ASL失敗=n/2+n/(n+1)，
3）一般線性表的存盤結構描述
typedef struct {
int * elem;//基地址
int tablelen;//表的長度
}SSTable;
4）在順序表ST中順序查找關鍵字為key的元素
int Seqsearch(SSTable ST, int key)
{
ST.elem[0] = key;
int i;
for ( i = ST.tablelen; ST.elem[i] != key; --i);
return i;
}
5）順序查找表，找到后和其前面的元素交換
int Seqsrch(SSTable r, int k)
{
int i = 0, temp;
while ((r.elem[i]!=k)&&(i<r.tablelen))
{
i++;
}
if (i < r.tablelen&&i>0)
{
temp = r.elem[i];
r.elem[i] = r.elem[i - 1];
r.elem[i - 1] = temp;
return --i;
}
else
{
return -1;
}
}
4、折半查找（二分查找）：僅適用于有序的順序表，
1）折半查找的程序用二叉樹描述，稱為判定樹，
（1）若有序序列有n個元素，則對應的判定樹有n個圓形的非葉結點和n+1個方形葉結點，
（2）當元素個數為n時，樹的高度為h=log2(n+1)，
2）查找成功的平均查找長度：ASL成功=log2(n+1)-1，折半查找的時間復雜度為O(log2n)，
3）折半查找的存盤結構必須具有隨即存取的特性，
4）折半查找---在有序表L中查找關鍵字為key的元素
int binarysearch(SSTable L, int key)
{
int low = 0, high = L.tablelen - 1, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (L.elem[mid] == key)
{
return mid;
}
else if (L.elem[mid] > key)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1;
}
5、有序表的順序查找和折半查找的區別：有序表的順序查找中的線性表可以為鏈式存盤結構，
6、分塊查找（索引順序查找）
1）操作：將查找表分成若干塊，塊內無序，塊間有序，
2）將長度為n的查找表均勻的分為b塊，每塊有s個記錄，在等概率情況下：
（1）若在塊內和索引表中均采用順序查找，則平均查找長度為ASL=(b+1)/2+(s+1)/2=(s2+2s+n)/2s；
（2）若s=√n，則平均查找長度取最小值√n+1，
（3）若對索引表采用折半查找，則平均查找長度為ASL=log2(b+1)+(s+1)/2，
7、B樹：所有結點的平衡因子均等于0的多路平衡查找樹，
1）B樹的階：B樹中所有結點的孩子結點數的最大值，
2）m階B樹的性質：
（1）每個結點至多有m棵子樹，即至多含有n-1個關鍵字；
（2）若根結點不是終端節點，則至少有兩棵子樹；
（3）除根結點外的所有非葉結點至少有m/2棵子樹，即至少含有m/2-1個關鍵字；
（4）非葉結點的結構
| n（結點中關鍵字的個數） | p0 | k1 | p1 | k2 | p2 | ... | kn | pn |
其中，ki為結點的關鍵字，且k1<k2<...<kn，pi為指向子樹根結點的指標，且pi-1所指子樹中所有結點的關鍵字均小于ki，pi所指子樹中所有結點的關鍵字均大于ki；
（5）所有葉結點都出現在同一層次上，
3）B樹的高度
若n>=1，則對于任意一棵包含n個關鍵字、高度為h、階數為m的B樹
（1）h>=logm(n+1)；
（2）若讓每個結點中的關鍵字個數達到最少，則容納同樣多關鍵字的B樹的高度達到最大，
4）B樹的查找
基本操作：在B樹中找結點，在結點內找關鍵字，
5）B樹的插入
（1）定位：找出插入該關鍵字的最底層中的某個非葉結點，（B樹中的插入關鍵字一定插入在最底層中的某個非葉結點內）
（2）插入：每個非失敗結點的關鍵字個時速都在區間[m/2-1,m-1]內，
插入后的結點關鍵字個數小于m，可以直接插入；插入后的結點關鍵字個數大于m-1，必須對結點進行分裂，
6）B樹的洗掉
（1）洗掉非終端結點時
若小于k的子樹中關鍵字個數>m/2-1，則找出k的前驅值，并用k的前驅值取代k，再遞回洗掉前驅，
若大于k的子樹中關鍵字個數>m/2-1，則找出k的后繼值，并用k的后繼值取代k，再遞回洗掉后繼，
若前后兩個子樹中關鍵字個數均為m/2-1，則直接將兩個子節點合并，直接洗掉k，
（2）洗掉終端結點時
直接洗掉關鍵字，若被洗掉關鍵字所在結點的關鍵字個數>m/2-1，直接洗掉，
兄弟夠借，若被洗掉關鍵字所在節點洗掉前的關鍵字個數=m/2-1，且與此結點相鄰的右（左）兄弟結點的關鍵字個數>=m/2-1，則調整該結點的兄弟結點及雙親結點，達到平衡，
兄弟不夠借，若被洗掉關鍵字所在節點洗掉前的關鍵字個數=m/2-1，且與此結點相鄰的右（左）兄弟結點的關鍵字個數=m/2-1，則將該結點的兄弟結點及雙親結點中的關鍵字進行合并，
8、B+樹
1）m階B+樹的性質：
（1）每個分支結點最多有m棵子樹；
（2）非葉根結點至少有兩棵子樹，其他每個分支結點至少有m/2棵子樹；
（3）結點的子樹個數與關鍵字個數相等；
（4）所有葉結點包含全部關鍵字及指向相應記錄的指標，葉結點中將關鍵字按大小順序排列，并且相鄰葉結點按大小順序互相鏈接起來；
（5）所有分支節點中僅包含它的各個子結點中關鍵字的最大值及指向其子結點的指標，
8、B樹和B+樹的區別
1）B+樹中，n個關鍵字的結點只含有n棵子樹，即每個關鍵字對應一顆子樹；B樹中，n個關鍵字的結點含有n+1棵子樹，
2）B+樹中，每個結點的關鍵字個數n的范圍m/2<=n<=m，根結點1<=n<=m；B樹中，每個結點的關鍵字個數n的范圍m/2-1<=n<=m-1，根結點1<=n<=m-1，
3）B+樹中，葉結點包含資訊，非葉結點僅起索引作用，非葉結點中的每個索引項只含有對應子樹的最大關鍵字和指向該子樹的指標，不含有該關鍵字對應記錄的存盤地址，
4）B+樹中，葉結點包含了全部關鍵字，即在非葉結點中出現的關鍵字也會出現在葉結點中；B樹中，葉結點包含的關鍵字和其他結點包含的關鍵字是不重復的，
9、散串列：根據關鍵字而直接進行訪問的資料結構，
散列函式：一個把查找表中的關鍵字映射陳該關鍵字對應的地址的函式，記作Hash(key)=Addr，
沖突：散列函式將兩個或兩個以上的不同關鍵字映射到同一個地址，
散串列建立了關鍵字和存盤地址之間的一種直接映射關系，
10、常用的散列函式
1）直接定址法
直接取關鍵字的某個線性函式值為散列地址，散列函式為H(key)=a*key+b,ab為常數，
適合關鍵字的分布基本連續的情況，不會產生沖突，
2）除留余數法
假定散串列的表長為m，取一個不大于m但最接近或等于m的質數p，散列函式為H(key)=key%p，
3）數字分析法
4）平方取中法
5）折疊法
11、處理沖突的方法
假定選定散列函式H(key)，Hi表示發生沖突后第i次探測的散列地址，
1）開放定址法：指可存放新表項的空閑地址既向它的同義詞表項開放，又向它的非同義詞表項開放，Ni=(H(key)+di)%m，（m表示散串列表長，di為增量序列），
當某一增量序列確定后，對應處理方法確定，通常有4種：線性探測法、平方探測法、再散列法、偽隨機序列法，
2）拉鏈法（鏈接法）
12、散串列的查找效率取決于三個因素：散列函式、處理沖突的方法、裝填因子，
裝填因子：一個表的裝滿程度，α=表中記錄數n/散串列長度m，α，發生沖突的可能性越大，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/55357.html
標籤：其他
上一篇：三維凸包