4.衡量查找算法的標準

1.時間復雜度

一個查找算法的時間復雜度越低，說明利用這個查找算法查找到對應關鍵字的數(shù)據(jù)元素就越快

2.空間復雜度

一個查找算法的空間復雜度越低，說明這個查找算法占用的內(nèi)存空間少

3.平均查找長度（ASL）

平均查找長度為確定數(shù)據(jù)元素（或記錄）在表中的位置所進行的和關鍵字比較的次數(shù)的平均值

n:查找表的長度，即表中所含元素（或記錄）的個數(shù)

Pi:查找到第i個元素的概率

Ci:查找第i個元素時，和各個數(shù)據(jù)元素（或記錄）的關鍵字比較的次數(shù)

二、靜態(tài)查找表

1.順序查找

算法思路

i.從表中的最后一個數(shù)據(jù)元素開始

ii.逐個進行數(shù)據(jù)元素的關鍵字和給定值進行比較

iii.如果某個數(shù)據(jù)元素的關鍵字與給定值比較相等，則查找成功

iv.如果直到第一個數(shù)據(jù)元素都比較不相等，則查找不成功

算法舉例

?如上圖所示，我們的目標是查找關鍵字為64的這個數(shù)據(jù)元素，因此對應的給定值就是64，我們從查找表的表尾開始查找，依次對比關鍵字，當比對到第7個元素的時候發(fā)現(xiàn)64等于第七個元素的關鍵字64，因此查找成功

算法性能分析

?對于順序表而言，Ci=n-i+1

?在等概率查找的情況下,Pi=1/n

因此 ASL=n*P1+(n-1)*P2+......+2Pn-1+Pn=(n+1)/2

不等概率

如果被查找的記錄概率不等時，取

Pn≥Pn-1≥···≥P2≥P1

若查找概率是無法事先測定的，則查找過程采取的改進方法是，將剛查找到的記錄直接移到表尾的位置之上

算法特點

優(yōu)點：

1.算法簡單易實現(xiàn)

2.適應性強，對表結構無任何要求

缺點：

1.ASL（平均查找長度較大)

2.當n很大時，即為大規(guī)模數(shù)據(jù)時，查找的效率很低

算法實現(xiàn)

本算法的實現(xiàn)是基于順序表的，因此需要先構造一個順序表，順序表的實現(xiàn)可以參考我的往期文章

順序表的實現(xiàn)? 當然了也可以用數(shù)組來替代，但是關鍵的不管是用什么結構，首元素不能存放數(shù)據(jù)，因為首元素的作用是作為哨兵存在的，因此關鍵數(shù)據(jù)存儲于第二個位置及以后

int sqsearch(sqlist sl,int key)
{
    int searchtime=0;//定義查找次數(shù)
    int i=sl.length-1;//得到順序表的長度
    sl.element[0]=key;//設置哨兵
    while (sl.element[i]!=key)//檢查元素
    {
        i--;
    }
    searchtime=sl.length-i;//得到查找次數(shù)
    if (i==0)//如果查找到了哨兵說明沒查找到對應元素
    {
        return 0;
    }
    return i;//返回查找到的元素下標
}

2.折半查找

算法思路

折半查找是基于有序表的查找方法，因此本算法所處理的數(shù)據(jù)是經(jīng)過排序的，算法基本原理如下：

確定待查記錄的范圍(在前半部分或是后半部分),然后繼續(xù)確定范圍直到找到該元素為止

1.n個對象從小到大存放在有序順序表ST中，k為給定值
2.設low、high指向待查元素所在區(qū)間的下界、上界，即low=1, high=n
3.設mid指向待查區(qū)間的中點，即mid=(low+high)/2
4.讓k與mid指向的記錄比較
? 若k<ST[mid].key，則high=mid-1?? ?[上半?yún)^(qū)間]
? 若k>ST[mid].key，則low=mid+1?? ??? ?[下半?yún)^(qū)間]
5.重復3,4操作，直至low>high時，查找失敗

算法舉例

?算法分析

判定樹

我們先不管要查找的Key是什么，我們將查找的整個過程中檢查element[mid]的順序列出來，我們就可以得到一顆描述查找過程的二叉樹，我們稱之為判定樹，如下圖所示：

?設我們有這么一個表，我們對其得到其的判定樹：

性能分析(查找成功bs與查找失敗bsf)

tips:以下的所有l(wèi)og都表示的是以2為底數(shù)的對數(shù)

我們可以知道，一個二叉樹的每一層的節(jié)點最多有2^(i-1)個節(jié)點(i為層數(shù)),因此對于一個k層的二叉樹,我們一共有:

?共2^k-1個節(jié)點,,因此有n個結點的判定樹的深度為k=log(n+1)，因此折半查找法在查找過程中進行的比較次數(shù)最多不超過log(n+1)。設有序表的長度n=2^h-1（即h=log (n+1)）,則描述折半查找的判定樹是深度為h的滿二叉樹，樹中層次為1的結點有1個，層次為2的結點有2個，層次為h的結點有2^(h-1)個，假設表中每個記錄的查找概率相等，則查找成功時折半查找的平均查找長度:

我們來對折半算法的ASL進行解析：首先我們對ASL的概念進行回顧

?因為查找概率相等，因此Pi=1/n,我們將其從式子中提出來就得到了:

?我們再對Ci的概念進行回顧：

?我們可以知道，我們現(xiàn)在對元素的檢查已經(jīng)不再是像順序查找一樣一個一個進行檢查了，而是像一顆樹一樣進行檢查，且根據(jù)我們所選擇的Key不同，每次從樹的頂端開始走的路徑都不同，且一次走一層，因此我們就可以把查找第i個元素時同給定值Key比較的次數(shù)轉換為查找第j層元素時同給定值Key比較的次數(shù),我們可以知道一個深度為h的樹每層有2^(j-1)個節(jié)點，每個節(jié)點的上面都有j層，因此Ci就等于 j x 2^(j-1),我們代入ASL計算公式后就可以得到:

?當我們查找失敗的時候，也就是說我們查找到了判定樹的最后一層的下一層，對此要具體例子具體計算，我在下面貼出一篇我覺得寫的不錯的文章，有興趣的可以繼續(xù)對ASL的計算進行了解：

ASL平均查找長度（查找失敗與查找成功時的ASL計算)https://blog.csdn.net/weixin_38233103/article/details/109248616?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166314104016782391812654%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=166314104016782391812654&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~hot_rank-4-109248616-null-null.142%5Ev47%5Econtrol_1,201%5Ev3%5Econtrol_2&utm_term=%E6%8A%98%E5%8D%8A%E6%9F%A5%E6%89%BE%E7%9A%84%E5%B9%B3%E5%9D%87%E6%9F%A5%E6%89%BE%E9%95%BF%E5%BA%A6&spm=1018.2226.3001.4187

算法實現(xiàn)

int binarysearch(sqlist sl,int key)
{
    int left,mid,right ;
    left=0;//初始化三個標志位
    right=sl.length-1;
    mid=(left+right)/2;
    while (sl.element[mid]!=key)//當未查找到時就一直進行查找
    {
        if(left<=right)//當left<=right意味著還能繼續(xù)查找 
        {
            if (key>sl.element[mid])
            {
                left=mid+1;
                mid=(left+right)/2;
            }
            else
            {
                right=mid-1;
                mid=(left+right)/2;
            }
                
        }
        else//當left>right說明已經(jīng)越界了，也代表著查找失敗
        {
            cout<<"查找失敗!"<<endl;
            break;
        } 
    }
    if (sl.element[mid]==key)//最后對結果進行檢查并返回對應值
    {
        cout<<"查找成功!"<<endl;
        return mid;
    }
    else
    {
        return -1;//查找失敗就返回-1
    }      
}

3.分塊查找

算法介紹

分塊查找是一種索引順序表(分塊有序表)查找方法，索引順序表(分塊有序表)將整個表分成幾塊，塊內(nèi)無序，塊間有序，所謂塊間有序是指后一塊表中所有記錄的關鍵字均大于前一塊表中的最大關鍵字

分塊查找包含兩個表：分別是主表和索引表

主表：用數(shù)組存放待查記錄,每個數(shù)據(jù)元素包含關鍵字
索引表:用鏈表存放每個結點,每個節(jié)點含有本塊的最大關鍵字和本塊第一個結點下標

算法思想

1.我們將所有元素放入數(shù)組中，我們稱之為主表

2.我們由數(shù)組的長度length來自己規(guī)定塊長n，得到索引表的長度為length/n

3.我們對每個塊進行遍歷找出最大關鍵字，并將該塊的首元素下標與最大關鍵字存入索引表中

4.以此類推直到所有塊被操作完畢

5.我們對索引表按照最大關鍵字的大小進行排序

6.然后我們利用順序查找對索引表進行操作

7.找到不小于key值得塊我們對該塊進行順序查找我們的key

8.找不到我們就對下一個塊進行順序查找來找我們的key

9.以此類推直到查找到key或查找失敗

算法舉例

?????????我們將一組數(shù)據(jù)存入主表，我們根據(jù)數(shù)據(jù)的數(shù)量11，我們設定分塊長度為4,由此我們可以得到索引表的長度為11/4=3,然后我們對主表進行分塊,得到三塊，將每塊的首元素索引以及最大關鍵字存儲入索引表中并對索引表依據(jù)最大關鍵字進行排序就得到了下圖:

?采用折半查找方法在索引表中找到塊[第2塊],用順序查找方法在主表對應塊中找到和key值對應的元素，即第三元素，我們返回這個元素的下標作為查找結果

?算法實現(xiàn)

鏈表類及鏈表相關操作

class node
{
    public:
    int maxkey;
    int firstindex;
    node *next;

};
//創(chuàng)建鏈表,因為創(chuàng)建一個鏈表一定要有一個頭節(jié)點，這個頭節(jié)點是沒有數(shù)據(jù)的
node* createlist()
{
    node* head=(node*)calloc(1,sizeof(node));//使用calloc為指針分配內(nèi)存
    if(head==NULL)//并且要注意，在c++中，calloc和malloc返回的是void，因此要通過q‘強制轉換才能繼續(xù)使用
    {
        return NULL;
    }
    return head;
}
//創(chuàng)建節(jié)點
node* createnode(int maxkey,int firstindex)
{
    node* newnode=(node*)calloc(1,sizeof(node));
    if(newnode==NULL)
    {
        return NULL;
    }
    newnode->maxkey=maxkey;
    newnode->firstindex=firstindex;
    return newnode;
}
//添加元素：把數(shù)據(jù)從尾部插入
void pushback(node *head,int maxkey,int firstindex)
{
    node* newnode=createnode(maxkey,firstindex);
    node* curnode=head;
    while(curnode->next!=NULL)
    {
        curnode=curnode->next;
    }
    //插入數(shù)據(jù)
    curnode->next=newnode;
}

void print(node*head)
{
    node* curnode=head->next;
    while (true)
    {
        if(curnode->next!=NULL)
        {
            cout<<"當前節(jié)點maxkey:"<<curnode->maxkey<<" 當前節(jié)點firstindex:"<<curnode->firstindex<<endl;
            curnode=curnode->next;
        }
        else
        {
            cout<<"當前節(jié)點maxkey:"<<curnode->maxkey<<" 當前節(jié)點firstindex:"<<curnode->firstindex<<endl;
            break;
        }
    }  
}

node* find(node* list,int num)
{
    node* ptr=list;
    for (int i = 0; i < num; i++)
    {
        ptr=ptr->next;  
    }
    return ptr;
    
}

?分塊查找

int blocksearch(int arr[],int arrlength,int key)
{
    //創(chuàng)建索引表
    node* list=createlist();
    //得到索引表
    cout<<"數(shù)組的長度為:"<<arrlength<<" 請輸入塊長:"<<endl;
    float blocklength;
    cin>>blocklength;
    float blocknumber1=arrlength/blocklength;
    int blocknumber2=arrlength/blocklength;
    int blocknumber;
    blocknumber=blocknumber1>blocknumber2?blocknumber2+1:blocknumber2; 
    int sllength=arrlength;
    int start=0;
    int length;
    for (int i = 1; i <=blocknumber; i++)
    {
        int max=0;
        sllength-=blocklength;
        //cout<<"當前sllength:"<<sllength<<endl;
        if (arrlength>blocklength)
        {
            length=blocklength;
        }
        else
        {
            length=sllength;
        }
        //cout<<"當前start:"<<start<<endl;
        //cout<<"當前l(fā)ength:"<<length<<endl;
        for (int j = start; j < start+length; j++)
        {
            if (arr[j]>max)
            {
                max=arr[j];
            }
            
        }
        //cout<<"索引表加入start:"<<start<<" max:"<<max<<endl;
        pushback(list,max,start);
        start+=blocklength;
    }
    //打印索引表
    cout<<"===============索引表================"<<endl;
    print(list);
    cout<<"===================================="<<endl;
    cout<<endl;
    //建新表對索引表進行排序
    node* newlist=createlist();
    node *curnode=list->next;
    cout<<"一共有"<<blocknumber<<"個塊"<<endl;
    for (int j = 0; j < blocknumber; j++)
    {
        int min=999;
        int mini=0;
        int i=0;
        int temp;
        while (curnode->next!=NULL)
        {
            i++;
            //cout<<"curnode的maxkey為:"<<curnode->maxkey<<endl;
            if (curnode->maxkey<min)
            {
                min=curnode->maxkey;
                mini=curnode->firstindex;
                temp=i;
            }
            //cout<<"curnode"<<curnode->maxkey<<"變?yōu)?<<curnode->next->maxkey<<endl;
            curnode=curnode->next;
        }
        //最后一個節(jié)點還要再操作一遍
        i++;
         //cout<<"curnode的maxkey為:"<<curnode->maxkey<<endl;
        if (curnode->maxkey<min)
        {
            min=curnode->maxkey;
            mini=curnode->firstindex;
            temp=i;
        }
        node* ptr=list;
        for (int k = 0; k < temp; k++)
        {
            ptr=ptr->next;
        }
        cout<<"找到的最小node的maxkey為:"<<ptr->maxkey<<endl;
        ptr->maxkey=1000;
        curnode=list->next;
        pushback(newlist,min,mini);
        //cout<<"索引表加入min:"<<min<<" mini:"<<mini<<endl;
        //cout<<"當前索引表最小maxkey為:"<<min<<endl;
    }
    //打印新索引表
    cout<<"===============新索引表================"<<endl;
    print(newlist);
    cout<<"===================================="<<endl;
    cout<<endl;
    
    //對新索引表進行順序查找
    int startindex=1;
    while (startindex<=blocknumber)
    {

        int target= find(newlist,startindex)->firstindex;
        for (int i = target; i < target+blocklength; i++)
        {
            if (key==arr[i])
            {
                return i;//查找到并返回下標
            }
                
        }
        startindex++;
    }
    return -1;//未查找到
}

main函數(shù)

int main()
{
    cout<<"請輸入數(shù)組長度:"<<endl;
    int arrlength;
    cin>>arrlength;
    int arr[arrlength];
    for (int i = 0; i < arrlength; i++)
    {
        cout<<"請輸入arr["<<i<<"]:";
        cin>>arr[i];
    }
    cout<<"請輸入key值:"<<endl;
    int key;
    cin>>key;
    blocksearch(arr,arrlength,key);
    return 0;
}

代碼執(zhí)行結果

?

三、總結

本文對查找進行了介紹，并且有對ASL平均查找長度進行講解和舉例計算，重點為三種算法的介紹和實現(xiàn)，其中順序查找作為最基本的查找算法是一定要掌握的，折半查找作為效率最高的算法尤其應該予以重視，分塊查找是介于順序查找和折半查找效率的一個算法，實現(xiàn)起來較麻煩，但是也需要掌握，如果喜歡本文的話希望可以點一個贊，你的肯定是我進步的動力！！！

????????????????????????????????????????????????????????????????????文章來源地址http://www.zghlxwxcb.cn/news/detail-774975.html

到了這里，關于C++數(shù)據(jù)結構之查找——靜態(tài)查找表（順序查找、折半查找、分塊查找 帶有gif以及圖示）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！