0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
創(chuàng)作中心

完善資料讓更多小伙伴認識你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

常見的查找算法匯總(含詳細代碼)5

jf_78858299 ? 來源:阿Q正磚 ? 作者:阿Q正磚 ? 2023-04-24 17:20 ? 次閱讀

test.c

/**
 * C語言實現(xiàn)的紅黑樹(Red Black Tree)
 *
 * @author skywang
 * @date 2013/11/18
 */


#include 
#include "rbtree.h"


#define CHECK_INSERT 0    // "插入"動作的檢測開關(guān)(0,關(guān)閉;1,打開)
#define CHECK_DELETE 0    // "刪除"動作的檢測開關(guān)(0,關(guān)閉;1,打開)
#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )


void main()
{
    int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
    int i, ilen=LENGTH(a);
    RBRoot *root=NULL;


    root = create_rbtree();
    printf("== 原始數(shù)據(jù): ");
    for(i=0; i

7、分塊查找

7.1、基本原理

分塊查找(Block Search)是一種基于分塊思想的查找算法。它將待查找的數(shù)據(jù)集合分成多個塊(Block),每個塊內(nèi)的數(shù)據(jù)按照某種方式有序排列。這樣就可以在查找時快速縮小查找范圍,從而提高查找效率。

分塊查找的基本原理如下:

  1. 將待查找的數(shù)據(jù)分成若干塊,并將每塊內(nèi)的數(shù)據(jù)按照某種方式有序排列。
  2. 確定各塊的范圍和關(guān)鍵字,用一張索引表來存放各塊的關(guān)鍵字和起始地址。
  3. 查找時,先在索引表中二分查找到關(guān)鍵字所在的塊,然后在該塊內(nèi)進行線性查找,直到找到目標數(shù)據(jù)。

分塊查找的注意事項和應用場景如下:

  1. 數(shù)據(jù)分塊要盡量均勻,使每塊數(shù)據(jù)量大致相等。
  2. 對每個塊內(nèi)的數(shù)據(jù)要按照某種方式有序排列,以便進行二分查找。
  3. 適合數(shù)據(jù)集合變動較少的情況,如果數(shù)據(jù)頻繁變動,需要不斷重構(gòu)索引表,效率較低。
  4. 分塊查找適合于數(shù)據(jù)量較大,但又不適合全部加載到內(nèi)存中的情況,比如外部文件查找。

7.2、代碼示例

#include 


// 定義塊的大小
#define BLOCK_SIZE 3


// 分塊查找函數(shù)
int blockSearch(int arr[], int n, int key)
{
    // 計算塊的數(shù)量
    int blockCount = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;


    // 創(chuàng)建一個塊數(shù)組,存儲每個塊的最大值
    int blockMax[blockCount];
    for (int i = 0; i < blockCount; i++) {
        int max = arr[i * BLOCK_SIZE];
        for (int j = 1; j < BLOCK_SIZE && i * BLOCK_SIZE + j < n; j++) {
            if (arr[i * BLOCK_SIZE + j] > max) {
                max = arr[i * BLOCK_SIZE + j];
            }
        }
        blockMax[i] = max;
    }


    // 在塊數(shù)組中查找key所在的塊
    int blockIndex = 0;
    while (blockIndex < blockCount && blockMax[blockIndex] < key) {
        blockIndex++;
    }


    // 在塊中進行線性查找
    int startIndex = blockIndex * BLOCK_SIZE;
    int endIndex = startIndex + BLOCK_SIZE;
    for (int i = startIndex; i < endIndex && i < n; i++) {
        if (arr[i] == key) {
            return i;
        }
    }


    return -1;
}


int main()
{
    int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int n = sizeof(arr) / sizeof(arr[0]);


    int key = 12;
    int index = blockSearch(arr, n, key);
    if (index == -1) {
        printf("%d not found\\n", key);
    } else {
        printf("%d found at index %d\\n", key, index);
    }


    return 0;
}

該程序定義了一個 BLOCK_SIZE 常量,表示塊的大小。在分塊查找函數(shù)中,首先計算塊的數(shù)量,然后創(chuàng)建一個塊數(shù)組,存儲每個塊的最大值。接下來,在塊數(shù)組中查找key所在的塊,并在該塊中進行線性查找。如果找到了key,則返回其下標,否則返回-1。最后,程序使用一個示例數(shù)組來測試分塊查找函數(shù),查找數(shù)組中的一個元素并輸出結(jié)果。

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學習之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請聯(lián)系本站處理。 舉報投訴
  • 數(shù)據(jù)
    +關(guān)注

    關(guān)注

    8

    文章

    6820

    瀏覽量

    88748
  • 代碼
    +關(guān)注

    關(guān)注

    30

    文章

    4723

    瀏覽量

    68242
  • 查找算法
    +關(guān)注

    關(guān)注

    0

    文章

    6

    瀏覽量

    5523
收藏 人收藏

    評論

    相關(guān)推薦

    實現(xiàn)TCP的C代碼封裝(代碼

    實現(xiàn)TCP的C代碼封裝(代碼
    的頭像 發(fā)表于 09-28 16:03 ?2421次閱讀
    實現(xiàn)TCP的C<b class='flag-5'>代碼</b>封裝(<b class='flag-5'>含</b><b class='flag-5'>代碼</b>)

    簡單的查找算法

    幾個比較基礎(chǔ)的查找算法:1. 無序鏈表的查找:主要是使用鏈表的遍歷操作來實現(xiàn)對于每個元素的訪問,和對比。通過在for循環(huán)中的if來判斷key相等的元素。如果找到就彈出val。如果沒有就返回null
    發(fā)表于 12-27 22:33

    isis 7 professional_元件查找代碼

    isis 7 professional元件查找代碼有各總isis 7 professional元件的查找代碼
    發(fā)表于 12-08 15:58 ?7次下載

    使用HTML5實現(xiàn)井字棋小游戲的算法代碼講解

    本文檔的主要內(nèi)容詳細介紹的是使用HTML5實現(xiàn)井字棋小游戲的算法代碼講解。
    發(fā)表于 08-07 17:33 ?1次下載
    使用HTML<b class='flag-5'>5</b>實現(xiàn)井字棋小游戲的<b class='flag-5'>算法</b>和<b class='flag-5'>代碼</b>講解

    圖論算法及MATLAB程序代碼詳細資料說明

    本文檔的主要內(nèi)容詳細介紹的是圖論算法及MATLAB程序代碼詳細資料說明。
    發(fā)表于 04-23 08:00 ?0次下載
    圖論<b class='flag-5'>算法</b>及MATLAB程序<b class='flag-5'>代碼</b>的<b class='flag-5'>詳細</b>資料說明

    詳解C語言二分查找算法細節(jié)

    我相信對很多讀者朋友來說,編寫二分查找算法代碼屬于玄學編程,雖然看起來很簡單,就是會出錯,要么會漏個等號,要么少加個 1。
    的頭像 發(fā)表于 06-22 09:05 ?2774次閱讀
    詳解C語言二分<b class='flag-5'>查找</b><b class='flag-5'>算法</b>細節(jié)

    MATLAB優(yōu)化算法匯總01

    MATLAB優(yōu)化算法匯總01
    發(fā)表于 10-08 10:57 ?0次下載

    MATLAB優(yōu)化算法匯總02

    MATLAB優(yōu)化算法匯總02
    發(fā)表于 10-08 10:59 ?0次下載

    MATLAB優(yōu)化算法匯總03

    MATLAB優(yōu)化算法匯總03
    發(fā)表于 10-08 11:01 ?0次下載

    A星路徑規(guī)劃算法完整代碼資料匯總

    A星路徑規(guī)劃算法完整代碼資料匯總
    發(fā)表于 12-03 17:16 ?11次下載

    匯總常見單片機原廠代碼倉庫,值得收藏

    匯總常見單片機原廠代碼倉庫,值得收藏
    發(fā)表于 12-03 16:06 ?9次下載
    <b class='flag-5'>匯總</b><b class='flag-5'>常見</b>單片機原廠<b class='flag-5'>代碼</b>倉庫,值得收藏

    常見查找算法匯總詳細代碼)1

    今天就把常見*查找算法也總結(jié)個通透, 還有詳細代碼解釋, 真的是寫完這篇感覺腦子已經(jīng)不是自己的了,還希望大家好好利用。
    的頭像 發(fā)表于 04-24 17:20 ?921次閱讀
    <b class='flag-5'>常見</b>的<b class='flag-5'>查找</b><b class='flag-5'>算法</b><b class='flag-5'>匯總</b>(<b class='flag-5'>含</b><b class='flag-5'>詳細</b><b class='flag-5'>代碼</b>)1

    常見查找算法匯總詳細代碼)2

    今天就把常見****查找算法也總結(jié)個通透, 還有詳細代碼解釋, 真的是寫完這篇感覺腦子已經(jīng)不是自己的了,還希望大家好好利用。
    的頭像 發(fā)表于 04-24 17:20 ?630次閱讀

    常見查找算法匯總詳細代碼)3

    今天就把常見****查找算法也總結(jié)個通透, 還有詳細代碼解釋, 真的是寫完這篇感覺腦子已經(jīng)不是自己的了,還希望大家好好利用。
    的頭像 發(fā)表于 04-24 17:20 ?733次閱讀

    常見查找算法匯總詳細代碼)4

    今天就把常見****查找算法也總結(jié)個通透, 還有詳細代碼解釋, 真的是寫完這篇感覺腦子已經(jīng)不是自己的了,還希望大家好好利用。
    的頭像 發(fā)表于 04-24 17:20 ?539次閱讀