一、順序表的順序查找
1、順序查找
由表的一端開始，逐個檢測每個記錄是不是要查的記錄。找到則查找成功，一直找到另一端還沒找到則失敗。
1）順序存儲結構下的順序查找
#include <iostream>
using namespace std;
typedef int KeyType;
struct RecType
{
KeyType key;//關鍵字域
};
//崗哨設在r[0]
int SeqSearch(RecType r[],KeyType k,int n)
{//順序表為r[1~n]
int i=n;
r[0].key=k;
while(r[i].key!=r[0].key) i--;
return i;
}
//崗哨設在r[n+1]
int SeqSearch1(RecType r[],KeyType k,int n)
{
r[n+1].key=k;
int i=1;
while(r[i].key!=k) i++;
return i%(n+1);
}
int main()
{
RecType r[]={0,1,2,3,4,5,6};
int length=sizeof(r)/sizeof(int);
KeyType key=3,key1=4;
int i=SeqSearch(r,key,length-1);
int j=SeqSearch1(r,key1,length-1);
cout <<i<<' '<<j<< endl;
return 0;
}
順序查找--二分查找--靜态樹表的查找--分塊查找
2）以連結清單為存儲結構的順序查找
隻能從頭節點順連結清單查到尾節點，逐個比較。
#include <iostream>
using namespace std;
typedef int KeyType;
struct Node
{
KeyType key;//關鍵字域
Node *next;//指針
};
Node *LinkSearch(Node *first,KeyType k,int &j)
{
Node *p=first->next;
j=1;
while(p)
{
if(p->key==k)
return p;
else
{
p=p->next;
j++;
}
}
j=0;//沒找到則j=0
return NULL;//沒找到傳回空指針
}
2、時間複雜度分析
執行時間主要取決于關鍵字的比較次數。 平均查找長度 （Average Search Length，ASL） 需和指定key進行比較的關鍵字的個數的期望值，成為查找算法在查找成功時的平均查找長度。
對于含有n個資料元素的查找表，查找成功的平均查找長度為：ASL = Pi*Ci的和。
Pi：查找表中第i個資料元素的機率。
Ci：找到第i個資料元素時已經比較過的次數。
順序查找 查找 成功時的平均查找長度為：
（假設每個資料元素的機率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
當查找 不成功時，需要n次比較，時間複雜度為O(n);
二、有序表的折半查找（二分查找）
1、描述
給定有序表按關鍵字有序，先确定待查記錄所在範圍，然後逐漸縮小範圍，直到找到或找不到為止。
#include <iostream>
using namespace std;
typedef int KeyType;
struct RecType
{
KeyType key;//關鍵字域
};
int BinSearch(RecType r[],int n,int k)
{//r[0~n-1]
int low=0,high=n-1;
while(low<high)
{
int mid=(low+high)/2;
if(r[mid].key==k) return mid;//找到
else if(r[mid].key>k) high=mid-1;//在左半段
else low=mid+1;//在右半段
}
return 0;
}
int main()
{
RecType r[]={1,2,3,4,5,6};
int length=sizeof(r)/sizeof(int);
KeyType key=3;
int i=BinSearch(r,length,key);
cout <<"下标："<<i<< endl;
return 0;
}
2、性能分析
把目前查找區間的中間位置上的結點作為根，左子表和右子表中的結點分别作為根節點的左子樹和右子樹。由此得到的二叉樹，稱為描述二分查找樹的判定樹。判定樹隻與表中元素總數有關，與各個元素數值無關。
在判定樹中，将所有節點的空左右孩子處加一個方形節點，并用線條連接配接起來，陳這些方形節點為判定樹的外部節點，由n個節點構成的判定樹外部節點數目為n+1。二分查找中，查找不成功就是走了一條從根節點到外部節點的路徑，比較次數為該路徑上内部節點的個數。 例：具有10個元素的有序表的二分查找的判定樹為 1 2 3 4 5 6 7 8 9 10
對于此圖，我麼可以得出：
查找成功的最少次數：1
查找成功最多的次數：4
查找成功的平均次數：ASL=（1*1+2*2+3*4+4*3）/10=2.9=3次；
查找不成功的最少次數：3
查找不成功的最多次數：4
查找不成功的平均次數：ASLunsucc=（3*5+4*6）/（5+6）=39/11=4次；
n個節點的判定樹的深度為[lo g 2 n ]+1，故二分查找在查找不成功時，比較次數最多不超過[log2n]+1。
--->斐波那契查找
斐波那契序列F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)（n>=2）：1,1,2,3,5,8,13,21，.......... 方法：在斐波那契數列找一個等于略大于查找表中元素個數的數F[n]，将原查找表擴充為長度為F[n](如果要補充元素，則補充重複最後一個元素，直到滿足F[n]個元素)，完成後進行斐波那契分割，即F[n]個元素分割為前半部分F[n-1]個元素，後半部分F[n-2]個元素，找出要查找的元素在哪一部分并遞歸，直到找到。
斐波那契查找的時間複雜度還是O(log 2 n )，但是 與折半查找相比，斐波那契查找的優點是它隻涉及加法和減法運算，而不用除法，而除法比加減法要占用更多的時間，是以，斐波那契查找的運作時間理論上比折半查找小，但是還是得視具體情況而定。 折半查找的middle = (low + hight)/2，除法可能會影響效率，而斐波那契的middle = low + F[k-1] -1，純加減計算，速度要快一些。 對于斐波那契數列：1、1、2、3、5、8、13、21、34、55、89……（也可以從0開始），前後兩個數字的比值随着數列的增加，越來越接近黃金比值0.618。比如這裡的89，把它想象成整個有序表的元素個數，而89是由前面的兩個斐波那契數34和55相加之後的和，也就是說把元素個數為89的有序表分成由前55個資料元素組成的前半段和由後34個資料元素組成的後半段，那麼前半段元素個數和整個有序表長度的比值就接近黃金比值0.618，假如要查找的元素在前半段，那麼繼續按照斐波那契數列來看，55 = 34 + 21，是以繼續把前半段分成前34個資料元素的前半段和後21個元素的後半段，繼續查找，如此反複，直到查找成功或失敗，這樣就把斐波那契數列應用到查找算法中了。
有序表序列個數n=F(k)-1， 當有序表的元素個數不是斐波那契數列中的某個數字時，需要把有序表的元素個數長度補齊，讓它成為斐波那契數列中的一個數值，當然把原有序表截斷肯定是不可能的，不然還怎麼查找。
開始将k值與第F(k-1)位置的記錄進行比較(及mid=low+F(k-1)-1),比較結果也分為三種
1）相等，mid位置的元素即為所求
2）>，low=mid+1,k-=2;
說明：low=mid+1說明待查找的元素在[mid+1,high]範圍内，k-=2 說明範圍[mid+1,high]内的元素個數為
n-(F(k-1))= F(k)-1-F(k-1)=F(k)-F(k-1)-1=F(k-2)-1個，是以可以遞歸的應用斐波那契查找。
3）<，high=mid-1,k-=1。
說明：high=mid-1說明待查找的元素在[low,mid-1]範圍内，k-=1 說明範圍[low,mid-1]内的元素個數為F(k-1)-1個，是以可以遞歸 的應用斐波那契查找。
#include <iostream>
#include <vector>
using namespace std;
const int MAX_SIZE = 20;
int a[] = { 1, 5, 15, 22, 25, 31, 39, 42, 47,49,59,68,88};
//a[0~n-1]
void Fibonacci(int F[])
{//斐波那契序列
F[0] = 0;
F[1] = 1;
for (size_t i = 2; i < MAX_SIZE; i++)
F[i] = F[i - 1] + F[i - 2];
}
int FibonacciSearch(int value)
{//斐波那契查找
int F[MAX_SIZE];//斐波那契序列F[0]~F[19]
Fibonacci(F);
int n = sizeof(a) / sizeof(int);//數組a所含元素個數
int k = 0;
while (n > F[k] - 1)//最後找到一個合适的k，使n<=F[k]-1
k++;
vector<int> temp;
temp.assign(a, a + n);//把數組a中元素指派到目前容器temp中
for (size_t i = n; i < F[k] - 1; i++)
temp.push_back(a[n - 1]);//若n<F[k]-1，擴充數組temp，最後的元素都是a[n-1]
//temp[0~n-1]
int l = 0, r = n - 1;
while (l <= r)
{
int mid = l + F[k - 1] - 1;//mid=low+F[k-1]-1
if (temp[mid] < value){
l = mid + 1;
k = k - 2;
}
else if (temp[mid] > value){
r = mid - 1;
k = k - 1;
}
else{
if (mid < n)
return mid;
else
return n - 1;
}
}
return -1;
}
int main()
{
int index = FibonacciSearch(47);
cout << index << endl;//index為數組下标（0~n-1）
}
--->插值查找
在介紹插值查找之前，首先考慮一個新問題，為什麼上述算法一定要是折半，而不是折四分之一或者折更多呢？ 打個比方，在英文字典裡面查“apple”，你下意識翻開字典是翻前面的書頁還是後面的書頁呢？如果再讓你查“zoo”，你又怎麼查？很顯然，這裡你絕對不會是從中間開始查起，而是有一定目的的往前或往後翻。 同樣的，比如要在取值範圍1 ~ 10000 之間 100 個元素從小到大均勻分布的數組中查找5， 我們自然會考慮從數組下标較小的開始查找。 經過以上分析，折半查找這種查找方式，不是自适應的（也就是說是傻瓜式的）。二分查找中查找點計算如下： mid=(low+high)/2, 即mid=low+1/2*(high-low); 通過類比，我們可以将查找的點改進為如下： mid=low+(key-a[low])/(a[high]-a[low])*(high-low)， 也就是将上述的比例參數1/2改進為自适應的，根據關鍵字在整個有序表中所處的位置，讓mid值的變化更靠近關鍵字key，這樣也就間接地減少了比較次數。 基本思想：基于二分查找算法，将查找點的選擇改進為自适應選擇，可以提高查找效率。當然，內插補點查找也屬于有序查找。 注： 對于表長較大，而關鍵字分布又比較均勻的查找表來說，插值查找算法的平均性能比折半查找要好的多。反之，數組中如果分布非常不均勻，那麼插值查找未必是很合适的選擇。 複雜度分析：查找成功或者失敗的時間複雜度均為O(log2(log2n))。
#include <iostream>
#include <vector>
using namespace std;
int InsertionSearch(int r[],int n,int k)
{//r[0~n-1]
int low=0,high=n-1;
while(low<high)
{
int p=k-r[low],q=r[high]-r[low];
int mid=low+(p/q)*(high-low);
if(r[mid]==k) return mid;//找到
else if(r[mid]>k) high=mid-1;//在左半段
else low=mid+1;//在右半段
}
return 0;
}
int main()
{
int r[]={1,2,3,4,5,6};
int length=sizeof(r)/sizeof(int);
int key=6;
int i=InsertionSearch(r,length,key);
cout <<"下标："<<i<< endl;
return 0;
}
三、靜态樹表的查找
靜态樹表為的是解決查找機率不等的記錄。一般情況下，我們都是預設各個記錄等機率查找的，但是有些記錄可能不是等機率的。我們可能會首先搜尋一些機率大的記錄。 例：
次優查找樹和最優查找樹的查找性能僅差1%-2%，而構造最優查找樹花費時間代價較高，構造次優查找樹的時間複雜度為O(nlog2n)。現構造一棵二叉樹， 使得二叉樹的帶權内部路 徑長度PH值在所有具有同樣權值的二叉樹中近似最小，稱為次優查找樹。 PH=w 1 h 1 +w 2 h 2 +.......，n個乘積的和，n為二叉樹上節點個數，hi為第i個節點在二叉樹上的層數，即深度，wi為節點的權。 次優查找二叉樹構造過程：
代碼：
#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdlib.h>
using namespace std;
//樹節點結構
typedef struct treenode
{
struct treenode *left;//左孩子
char data;//資料
int weight;//權重
struct treenode *right;//右孩子
}Treenode,* Treep;
int low=1,high=10;//共9個節點
char *R;//字元數組
int *weight;//權重數組
int *sw;//累計權值表sw[i]=w1+w2+...+wi
//初始化二叉樹
void init_tree(Treep &root)
{
root=NULL;
cout<<"初始化成功!"<<endl;
}
//建立二叉樹
void SecondOptimal(Treep &rt, char R[],int sw[], int low, int high)
{//由有序表R[low....high]及其累積權值表sw(其中sw[0]==0)遞歸構造次優查找樹T
int i=low;
int min = fabs(sw[high] - sw[low]);//ΔP1
int dw = sw[high] + sw[low-1];//dw為sw[high]
for(int j=low+1; j<=high; j++)//選擇最小的ΔPi值
{
if(fabs(dw-sw[j]-sw[j-1]) < min)
{
i=j;//i記錄要選擇的根節點
min=fabs(dw-sw[j]-sw[j-1]);
}
}
cout<<"i="<<i<<' ';
rt=(Treep)malloc(sizeof(Treenode));
rt->data=R[i]; //生成節點
if(i==low) //左子樹為空
rt->left = NULL;
else //構造左子樹
SecondOptimal(rt->left, R, sw, low, i-1);
if(i==high) //右子樹為空
rt->right = NULL;
else //構造右子樹
SecondOptimal(rt->right, R, sw, i+1, high);
}//SecondOptimal
//前序周遊二叉樹
void pre_order(Treep &rt)
{
if(rt!=NULL)
{
cout<<rt->data<<" ";
pre_order(rt->left);
pre_order(rt->right);
}
}
//查找二叉樹中是否存在某元素
int seach_tree(Treep &rt,char key)
{
if(rt==NULL)
return 0;
else
{
if(rt->data==key)
{
return 1;
}
else
{
if(seach_tree(rt->left,key) || seach_tree(rt->right,key))
return 1; //如果左右子樹有一個搜尋到，就傳回1
else
return 0; //如果左右子樹都沒有搜尋到，傳回0
}
}
}
int main()
{
Treep root;
init_tree(root); //初始化樹
R=(char *)malloc( high*sizeof(char) );
for(int i=low; i<high; i++)
R[i]='A'+i-1;//R[1]~R[9]:A~I
cout<<"構造次優查找樹的點R[]:"<<endl;
for(int i=low-1; i<high; i++)
cout<<setw(3)<<R[i]<<" ";//R[0]為空，
cout<<endl;
weight=(int *)malloc( high*sizeof(int) );
weight[0]=0;
weight[1]=1;
weight[2]=1;
weight[3]=2;
weight[4]=5;
weight[5]=3;
weight[6]=4;
weight[7]=4;
weight[8]=3;
weight[9]=5;
cout<<"構造次優查找樹的點的權值weight[]:"<<endl;
for(int i=low-1; i<high; i++)
cout<<setw(3)<<weight[i]<<" ";
cout<<endl;
sw=(int *)malloc( high*sizeof(int) );
sw[0]=0;
for(int i=low; i<high; i++)
{
sw[i]=sw[i-1]+weight[i];//算法描述中的si
}
cout<<"構造次優查找樹的點累積權值sw[]:"<<endl;
for(int i=low-1; i<high; i++)
cout<<setw(3)<<sw[i]<<" ";
cout<<endl;
//建立二叉樹
SecondOptimal(root, R, sw, low, high-1);
//前序周遊二叉樹
cout<<endl<<"前序周遊序列是:"<<endl;
pre_order(root);
cout<<endl;
//查找二叉樹中是否存在某元素
cout<<"輸入要查找的元素!"<<endl;
char ch;
cin>>ch;
if(seach_tree(root,ch)==1)
cout<<"yes!"<<endl;
else
cout<<"no!"<<endl;
return 0;
}
四、分塊查找
分塊查找又稱索引順序查找，它是順序查找的一種改進方法。 方法描述：将n個資料元素"按塊有序"劃分為m塊（m ≤ n）。每一塊中的結點不必有序，但塊與塊之間必須"按塊有序"；即第1塊中任一進制素的關鍵字都必須 小于第2塊中任一進制素的關鍵字；而第2塊中任一進制素又都必須小于第3塊中的任一進制素，……。 操作步驟： step1 先選取各塊中的最大關鍵字構成一個索引表； step2 查找分兩個部分：先對索引表進行二分查找或 順序查找，以确定待查記錄在哪一塊中；然後，在已确定的塊中用順序法進行查找。 特點： （1）比順序查找快很多嗎，但不如二分查找快 （2）也适合于線性連結清單存儲的查找表 （3）即可作為靜态查找法，也可作為動态查找法。因在塊内無序，若塊内沒有查找到，則可插入，此前該塊内應有空，且索引表應含每一塊的上下界。 時間複雜性分析： 時間複雜度：O(log(m)+N/m)，N個元素，分為N/M塊，每塊含M個元素。
代碼：
代碼：
#include <iostream>
#include <vector>
using namespace std;
typedef struct
{
int r[100];
int length;
}SSTable; //資料表，被查找表
//分塊查找——索引查找
typedef struct
{
int key; //關鍵字域
int stadr;//起始位址
}IndexItem; //索引表中索引項的結構類型
typedef struct
{
IndexItem elem[51];
int length;
}IndexTable;//索引表
int Search_Index(SSTable &ST,IndexTable &ID,int k)
{ //索引查找關鍵字k
int low,high,mid;
int p=0;//p用來儲存查找的關鍵字所屬的索引中的位置
int s,t;//s,t分别用來儲存查找的關鍵字所在塊的起始和終點位置
low=0;
int found=0;
high=ID.length-1;
while(low<=high&&found!=1)
{//該循環是用對半查找的方法，對索引表進行查找，進而定位要查找的元素所在的塊
mid=(low+high)/2;
if(k>ID.elem[mid-1].key&&k<=ID.elem[mid].key)
{p=mid;found=1;}//判斷關鍵字對應哪個索引位置，就是k比前一個值大，比後一個值小，
//那個大的就是k對應的索引位置
else if(k>ID.elem[mid].key)
low=mid+1;
//else if(k<ID.elem[mid].key)
else
high=mid-1;
}
cout<<"索引表下标p="<<p<<"即在第"<<p+1<<"塊中."<<endl;
s=ID.elem[p].stadr;
if(p==ID.length-1)
t=ST.length-1;//這裡對p的判斷很重要，p若是索引中最後一個位置，則t應該為ST的表長
else
t=ID.elem[p+1].stadr-1; //終止位置為後一塊的起始位址減1
while(k!=ST.r[s]&&s<=t)//這裡在塊裡進行順序查找
s++;
if(s>t)
return -1;
else
return s;
}
//建立需要查找的表，和對半查找用的索引表
void CreateTable(SSTable &ST,IndexTable &ID,int n,int m)
{
int i;
cout<<"請輸入待查序清單的長度：";
cin>>ST.length;
cout<<"請輸入每一個元素：";
for(i=0;i<n;i++)
cin>>ST.r[i];
cout<<"請輸入索引表的長度：";
cin>>ID.length;
cout<<"請輸入索引表的元素(資料和起始位址)：";
for(i=0;i<m;i++)
cin>>ID.elem[i].key>>ID.elem[i].stadr;
}
int main()
{
SSTable ST;
IndexTable ID;
CreateTable(ST,ID,16,4);
int i=Search_Index(ST,ID,24);
if(i==-1)
cout<<"沒找到！"<<endl;
else
cout<<"ST.r["<<i<<"]="<<ST.r[i]<<endl;
return 0;
}