資料結構--查找查找的基本概念線性表的查找樹表的查找哈希表的查找
Point：折半查找 、二叉排序樹的構造和查找、 哈希函數（除留餘數法）的構造 、哈希函數解決沖突的方法及其特點
查找的基本概念
• 查找表 :
由同一類型的資料元素（或記錄）構成的集合
• 關鍵字
記錄中某個資料項的值，可用來識别一個記錄
• 主關鍵字：
唯一辨別資料元素
• 次關鍵字：
可以辨別若幹個資料元素
對查找表經常進行的操作有：
（1）查詢元素；
（2）檢索屬性；
（3）插入；
（4）删除。
分為靜态查找（1)(2)和動态查找(3)(4)
平均查找長度ASL
線性表的查找
一、順序查找（線性查找）
适用于順序表或線性連結清單表示的靜态查找表,表内元素之間無序
順序表的表示
typedef struct {
ElemType *R; //表基址
int length; //表長
}SSTable;
查找函數：
int LocateELem(SqList L,ElemType e)
{ for (i=0;i< L.length;i++)
if (L.elem[i]==e) return i+1;
return 0;
}
//改進
int Search_Seq( SSTable ST , KeyType key ){
//若成功傳回其位置資訊，否則傳回0
ST.R[0].key =key;
for( i=ST.length; ST.R[i].key!=key; --i );
//不用for(i=n; i>0 && ST.R[i].key!=key; --i)
return i;
}
//設定了監視哨，減少了檢查是否查找完畢的判斷，省時；
• 空間複雜度：一個輔助空間。 • 時間複雜度：
1) 查找成功
ASLs(n)=(1+2+ ... +n)/n =(n+1)/2
2)查找不成功 ASLf =n+1
特點：
• 算法簡單，對表結構無任何要求（順序和鍊式） • n 很大時查找效率較低 • 改進措施： 非等機率 查找時，可按照查找機率進行排序。
易錯：
n個數存在一維數組A[1..n]中，在進行順序查找時，這n個數的排列有序或無序其平均查找長度ASL：查找機率相等時，ASL相同；
查找機率不等時，如果從前向後查找，則按查找機率由大到小排列的有序表其ASL要比無序表ASL小。
二、折半查找（二分或對分查找）
非遞歸：
int Search_Bin(SSTable ST,KeyType key) {
//若找到，則函數值為該元素在表中的位置，否則為0
low=1;
high=ST.length;
while(low<=high) {
mid=(low+high)/2;
if(key==ST.R[mid].key)
return mid;
else if(key<ST.R[mid].key)
high=mid-1;//前一子表查找
else
low=mid+1; //後一子表查找
}
return 0; //表中不存在待查元素
}
遞歸（僞碼）：
int Search_Bin (SSTable ST, keyType key, int low, int high)
{
if(low>high) return 0; //查找不到時傳回0
mid=(low+high)/2;
if(key等于ST.elem[mid].key) return mid;
else if(key小于ST.elem[mid].key)
……..//遞歸
else……. //遞歸
}
折半查找的性能分析－判定樹
性能分析：
– 查找過程：每次将待查記錄所在區間縮小一半，比順序查找效率高 , 時間複雜度 O(log2 n) – – 适用條件： 采用順序存儲結構的有序表 ，不宜用于鍊式結構 •
三、分塊查找（塊間有序，塊内無序）
特點：分塊有序，即分成若幹子表，要求每個子表中的數值都比後一塊中數值小（但子表内部未必有序）。
然後将各子表中的最大關鍵字構成一個索引表，表中還要包含每個子表的起始位址（即頭指針）。
分塊查找過程：
① 對索引表使用折半查找法（因為索引表是有序表）；
② 确定了待查關鍵字所在的子表後，在子表内采用順序查找法（因為各子表内部是無序表）；
樹表的查找
特點：
表結構在查找過程中動态生成
對于給定值key，若表中存在，則成功傳回；否則插入關鍵字等于key 的記錄。
二叉排序樹
性質：
（1）若其左子樹非空，則左子樹上所有結點的值均小于根結點的值；
（2）若其右子樹非空，則右子樹上所有結點的值均大于等于根結點的值；
（3）其左右子樹本身又各是一棵二叉排序樹
（4）中序周遊為遞增的有序序列
查找
// 遞歸
BSTree SearchBST(BSTree T,KeyType key) {
if((!T) || key==T->data.key) return T;
else if (key<T->data.key) return SearchBST(T->lchild,key); //在左子樹中繼續查找
else return SearchBST(T->rchild,key); //在右子樹中繼續查找
}
//非遞歸
BSTree SearchBST(BSTree T, int k) {
//在以T為根的二叉排序樹中查找關鍵值為k的結點
{ p=T;
while(p!==NULL)
{ if (p->key==k) return(p); //查找成功
else if (p->key>k) p=p->lch ; //進入左子樹查找
else p=p->rch ; //進入右子樹查找
}
return(NULL);
}
插入
① 若二叉排序樹是空樹，則key成為二叉排序樹的根；
② 若二叉排序樹非空， 則将key與二叉排序樹的根進行比較：
a) 如果 key 的值等于根結點的值，則停止插入； b) 如果 key 的值小于根結點的值，則将 key 插入左子樹； c) 如果 key 的值大于根結點的值，則将 key 插入右子樹。
插入的元素一定在葉結點上
void InsertBST(BSTree *bst, KeyType key)
//若在二叉排序樹中不存在關鍵字等于key的元素， 插入該元素
{ BSTree s;
if (*bst==NULL) //遞歸結束條件
{
s=(BSTree)malloc(sizeof(BSTNode)); //申請新的結點s
s-> key=key;
s->lchild=NULL; s->rchild=NULL;
*bst=s;
}
else if (key < (*bst)->key)
InsertBST(&((*bst)->lchild), key); //将s插入左子樹
else if (key > (*bst)->key)
InsertBST(&((*bst)->rchild), key); //将s插入右子樹
}
查找的性能分析 ：
平均查找長度和二叉樹的形态有關，即
最好：log2n（形态勻稱，與二分查找的判定樹相似）
最壞: （n+1)/2（單支樹）
問題：如何提高二叉排序樹的查找效率？
盡量讓二叉樹的形狀均衡，即使其為平衡二叉樹(對于一棵有n個結點的AVL樹，其高度保持在O(log2n)數量級，ASL也保持在O(log2n)量級。)
平衡二叉樹：
• 左、右子樹是平衡二叉樹； • 所有結點的左、右子樹深度之差 （平衡因子） 的絕對值≤ 1
如果在一棵AVL樹中插入一個新結點，就有可能造成失衡，此時必須重新調整樹的結構，使之恢複平衡。
哈希表的查找
哈希查找：既是一種查找方法，又是一種存貯方法，稱為散列存貯。散列存貯的記憶體存放形式也稱為哈希表或散清單。
散列查找是通過構造哈希函數來得到待查關鍵字的位址。為了保證哈希表查找得以實作，必須使記錄的存放規則和查找規則一緻，即：使用同樣的哈希函數。在存儲時，以每個記錄的關鍵字為自變量，通過哈希函數計算出存儲位址，将該記錄存放在存儲位址對應的存儲單元中。在查找時，以查找值為自變量，通過哈希函數計算出位址，從該位址所對應的存儲單元中取出記錄資料。
基本思想：記錄的存儲位置與關鍵字之間存在對應關系，Loc(i)=H(keyi)（哈希函數）
優點：查找速度極快O(1),查找效率與元素個數n無關
沖突是不可能避免的，減少沖突的方法
構造好的哈希函數
構造哈希函數（最常用）除留餘數法 ：Hash(key)=key mod p (p是一個整數)
制定一個好的解決沖突方案：
1.開放定址法
線性探測法
Hi=(Hash(key)+di) mod m ( 1≤i < m )
其中：m為哈希表長度
di 為增量序列 1，2，…m-1，且di=i
優點：隻要哈希表未被填滿，保證能找到一個空位址單元存放有沖突的元素。
缺點：可能使第i個哈希位址的同義詞存入第i+1個位址，這樣本應存入第i+1個哈希位址的元素變成了第i+2個哈希位址的同義詞，……，産生“聚集”現象，降低查找效率。是以産生了二次探測法。
二次探測法
di= 12 、 -12 、 22、 - 22 …
該方法規定，若在d位址發生沖突，下一次探查位置為d+12，d-12,d+22，d- 22， …，直到找到一個空閑位置為止。
僞随機探測法
Hi=(Hash(key)+di) mod m ( 1≤i < m )
其中：m為哈希表長度
di 為随機數
2.鍊位址法（拉鍊法）
基本思想：相同哈希位址的記錄鍊成一單連結清單，m個哈希位址就設m個單連結清單，然後用一個數組将m個單連結清單的表頭指針存儲起來，形成一個動态的結構（尾插法）。
鍊位址法的優點：
• 非同義詞不會沖突，無“聚集”現象 • 連結清單上結點空間 動态申請 ，更适合于表長不确定的情況
哈希表的查找
哈希查找過程與哈希表的建立過程是一緻的
給定值與關鍵字比較
#define m<哈希表長度>
#define NULLKEY <代表空記錄的關鍵字值>
typedef int KeyType;
typedef struct {
KeyType key;
…
} RecordType ;
typedef RecordType HashTable[m] ;
//哈希查找算法(線性探測再散列)：
int HashSearch( HashTable ht, KeyType K) {
p0=hash(K);
if (ht[p0].key==NULLKEY)
return (-1);
else if (ht[p0].key==K)
return (p0);
else { //用線性探測再散列解決沖突
for (i=1; i<=m-1; i++) {
pi=(p0+i) % m;
if (ht[pi].key==NULLKEY)
return (-1);
else if (ht[pi].key==K)
return (pi);
}
return (-1);
}
}
哈希表的平均查找長度是裝填因子α（
）的函數，而與待散列元素數目n無關。是以， 無論元素數目n有多大，都能通過調整α，使哈希表的平均查找長度較小。
ps：鍊位址法優于開位址法