欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

數(shù)據(jù)結(jié)構(gòu)之位圖(bitmap)詳解

 更新時(shí)間:2014年08月28日 10:14:21   投稿:junjie  
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)之位圖詳解,本文講解了位圖的基本知識(shí)、位圖的實(shí)現(xiàn)方法、位圖的應(yīng)用等內(nèi)容,需要的朋友可以參考下

1.  概述

位圖(bitmap)是一種非常常用的結(jié)構(gòu),在索引,數(shù)據(jù)壓縮等方面有廣泛應(yīng)用。本文介紹了位圖的實(shí)現(xiàn)方法及其應(yīng)用場(chǎng)景。

2. 位圖實(shí)現(xiàn)

(1)自己實(shí)現(xiàn)
在位圖中,每個(gè)元素為“0”或“1”,表示其對(duì)應(yīng)的元素不存在或者存在。

復(fù)制代碼 代碼如下:

#define INT_BITS sizeof(int)
 
#define SHIFT 5 // 2^5=32
 
#define MASK 0x1f // 2^5=32
 
#define MAX 1024*1024*1024 //max number
 
int bitmap[MAX / INT_BITS];
 
/*
 
* 設(shè)置第i位
 
* i >> SHIFT 相當(dāng)于 i / (2 ^ SHIFT),
 
* i&MASK相當(dāng)于mod操作 m mod n 運(yùn)算
 
*/
 
void set(int i) {
 
bitmap[i >> SHIFT] |= 1 << (i & MASK);
 
}
 
//獲取第i位
 
int test(int i) {
 
return bitmap[i >> SHIFT] & (1 << (i & MASK));
 
}
 
//清除第i位
 
int clear(int i) {
 
return bitmap[i >> SHIFT] & ~(1 << (i & MASK));
 
}

(2)函數(shù)庫(kù)實(shí)現(xiàn)

C++的STL中有bitmap類,它提供了很多方法,詳見(jiàn):http://www.cplusplus.com/reference/stl/bitset/

3.  位圖應(yīng)用

3.1    枚舉
(1)全組合
字符串全組合枚舉(對(duì)于長(zhǎng)度為n的字符串,組合方式有2^n種),如:abcdef,可以構(gòu)造一個(gè)從字符串到二進(jìn)制的映射關(guān)系,通過(guò)枚舉二進(jìn)制來(lái)進(jìn)行全排序。

復(fù)制代碼 代碼如下:

null——> 000000
f——> 000001
e——> 000010
ef——> 000011
……
abcedf——> 111111

(2)哈米爾頓距離

枚舉算法,復(fù)雜度是O(N^2),怎樣降低復(fù)雜度呢?
如果是N 個(gè)二維的點(diǎn),那么我們可以怎么用較快的方法求出

通過(guò)簡(jiǎn)單的數(shù)學(xué)變形,我們可以得到這樣的數(shù)學(xué)公式:

通過(guò)觀察,我們發(fā)現(xiàn)每一對(duì)相同元的符號(hào)必定相反,如:x_i-y_i,于是我們有了一個(gè)二進(jìn)制思想的思路,那就是枚舉這些二i維的點(diǎn)的x 軸y 軸前的正負(fù)號(hào),這樣就可以用一個(gè)0~3 的數(shù)的二進(jìn)制形式來(lái)表示每個(gè)元素前面的正負(fù)號(hào),1表示+號(hào),0表示−號(hào),如:2 表示的二進(jìn)制位形式為10表示x_i-y_i。這樣我們就可以通過(guò)2^2*N次記錄下這些二元組的不同的符號(hào)的數(shù)值,對(duì)于每個(gè)二進(jìn)制來(lái)表示的不同的式子只需記錄下他們的值,這樣我們只需求max_i 和min_i出這些相同的二進(jìn)制表示的式子max_i –min_i,最后我們就可以解出ans=max{max_i-min_i}。

通過(guò)位圖,算法時(shí)間復(fù)雜度可將為O(N)。

3.2   搜索

設(shè)計(jì)搜索剪枝時(shí),需要保存已經(jīng)搜索過(guò)的歷史信息,有些情況下,可以使用位圖減小歷史信息數(shù)據(jù)所占空間。

3.3 壓縮

(1)在2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù),注,內(nèi)存不足以容納這2.5億個(gè)整數(shù)?

(2)騰訊面試題:給40億個(gè)不重復(fù)的unsigned int的整數(shù),沒(méi)排過(guò)序的,然后再給一個(gè)數(shù),如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中?

4. 總結(jié)

Bitmap是一種非常簡(jiǎn)潔快速的數(shù)據(jù)結(jié)構(gòu),他能同使證存儲(chǔ)空間和速度最優(yōu)化(而不必空間換時(shí)間)。

5.  參考資料
(1)《C實(shí)現(xiàn)bitmap位圖》:http://www.dbjr.com.cn/article/54438.htm
(2)武森《淺談信息學(xué)競(jìng)賽中的“0”和“1”》

相關(guān)文章

  • QT?.pro文件使用解析

    QT?.pro文件使用解析

    QT工程的pro文件,在創(chuàng)建工程時(shí)由QTCreater自動(dòng)創(chuàng)建,我們可以往里面添加內(nèi)容,增加庫(kù)文件的聲明,包含路徑、預(yù)處理器定義,生成目錄,輸出中間目錄等等設(shè)置,本文就來(lái)介紹一下
    2022-04-04
  • 徹底掌握C語(yǔ)言strcpy函數(shù)的用法

    徹底掌握C語(yǔ)言strcpy函數(shù)的用法

    C語(yǔ)言中的strcpy函數(shù),是一種C語(yǔ)言的標(biāo)準(zhǔn)庫(kù)函數(shù),它用于對(duì)字符串進(jìn)行復(fù)制。本章帶你了解它的使用并模擬實(shí)現(xiàn)它
    2022-05-05
  • C語(yǔ)言實(shí)現(xiàn)電話簿管理系統(tǒng)

    C語(yǔ)言實(shí)現(xiàn)電話簿管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)電話簿管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-12-12
  • C語(yǔ)言指針基礎(chǔ)知識(shí)實(shí)例講解

    C語(yǔ)言指針基礎(chǔ)知識(shí)實(shí)例講解

    這篇文章主要介紹了C語(yǔ)言指針基本知識(shí)實(shí)例講解,文中實(shí)例講解的很清晰,有不太懂的同學(xué)可以研究下
    2021-02-02
  • C語(yǔ)言超詳細(xì)講解順序表的各種操作

    C語(yǔ)言超詳細(xì)講解順序表的各種操作

    大家好,今天給大家?guī)?lái)的是順序表,我覺(jué)得順序表還是有比較難理解的地方的,于是我就把這一塊的內(nèi)容全部整理到了一起,希望能夠給剛剛進(jìn)行學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人帶來(lái)一些幫助,或者是已經(jīng)學(xué)過(guò)這塊的朋友們帶來(lái)更深的理解,我們現(xiàn)在就開(kāi)始吧
    2022-05-05
  • [c++]變量聲明與定義的規(guī)則詳解

    [c++]變量聲明與定義的規(guī)則詳解

    這篇文章主要介紹了[c++]變量聲明與定義的規(guī)則詳解,對(duì)于學(xué)習(xí)c++的朋友來(lái)說(shuō)這是一個(gè)很細(xì)膩的文章,代碼完整,需要的朋友可以參考下
    2021-04-04
  • C++中動(dòng)態(tài)綁定和內(nèi)存管理的實(shí)現(xiàn)

    C++中動(dòng)態(tài)綁定和內(nèi)存管理的實(shí)現(xiàn)

    本文主要介紹了C++中動(dòng)態(tài)綁定和內(nèi)存管理的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2024-12-12
  • 詳解C++ string常用截取字符串方法

    詳解C++ string常用截取字符串方法

    這篇文章主要介紹了C++ string常用截取字符串方法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2019-05-05
  • C語(yǔ)言單鏈表的實(shí)現(xiàn)

    C語(yǔ)言單鏈表的實(shí)現(xiàn)

    單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu),用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。這篇文章主要介紹了C語(yǔ)言單鏈表的實(shí)現(xiàn) 的相關(guān)資料,需要的朋友可以參考下
    2016-04-04
  • C++中實(shí)現(xiàn)fibonacci數(shù)列的幾種方法

    C++中實(shí)現(xiàn)fibonacci數(shù)列的幾種方法

    本文主要介紹了C++中實(shí)現(xiàn)fibonacci數(shù)列的幾種方法,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-01-01

最新評(píng)論