本文詳細(xì)講述了位圖算法的定義與C語言實現(xiàn)方法，分享給大家供大家參考之用。具體如下：
位圖法定義：
位圖法就是bitmap的縮寫，所謂bitmap，是用每一位來存放某種狀態(tài)，適用于大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來判斷某個數(shù)據(jù)存不存在的。
例如，要判斷一千萬個人的狀態(tài)，每個人只有兩種狀態(tài)：男人，女人，可以用0，1表示。那么就可以開一個int數(shù)組，一個int有32個位，就可以表示32個人。操作的時候可以使用位操作。
數(shù)據(jù)結(jié)構(gòu)：
unsigned int bit[N];
在這個數(shù)組里面，可以存儲 N * sizeof(int) * 8個數(shù)據(jù)，但是最大的數(shù)只能是N * sizeof(int) * 8 - 1。假如，我們要存儲的數(shù)據(jù)范圍為0-15，則我們只需要使得N=1，這樣就可以把數(shù)據(jù)存進(jìn)去。如下圖：
數(shù)據(jù)為【5，1，7，15，0，4，6，10】，則存入這個結(jié)構(gòu)中的情況為:
位圖法應(yīng)用：
一、給40億個不重復(fù)的unsigned int的整數(shù)，沒排過序的，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那40億個數(shù)當(dāng)中
申請512M的內(nèi)存
一個bit位代表一個unsigned int值
讀入40億個數(shù)，設(shè)置相應(yīng)的bit位
讀入要查詢的數(shù)，查看相應(yīng)bit位是否為1，為1表示存在，為0表示不存在
二、使用位圖法判斷整形數(shù)組是否存在重復(fù)
判斷集合中存在重復(fù)是常見編程任務(wù)之一，當(dāng)集合中數(shù)據(jù)量比較大時我們通常希望少進(jìn)行幾次掃描，這時雙重循環(huán)法就不可取了。位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創(chuàng)建一個長度為max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上1，如遇到 5就給新數(shù)組的第六個元素置1，這樣下次再遇到5想置位時發(fā)現(xiàn)新數(shù)組的第六個元素已經(jīng)是1了，這說明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復(fù)。這種給新數(shù)組初始化時置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運(yùn)算次數(shù)最壞的情況為2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長的話效率還能提高一倍。
#include<stdio.h>#include<stdlib.h>#include<string.h>#include<stdbool.h>bool hasDuplicatedItem(int *a, int len){ int length, max, i; length = len; max = a[0]; for(i = 1; i < length; i++){ if(a[i] > max) max = a[i]; } int *arr; arr = (int*)malloc(sizeof(int) * (max + 1)); for(i = 0; i < length; i++){ if(arr[a[i]]) return true; else arr[a[i]] = 1; } return false;}int main(){ int length; int test[] = {0,1,2,3,45,12,13}; length = (sizeof(test) / sizeof(test[0])); if(hasDuplicatedItem(test, length)) printf("hasDuplicatedItem!/n"); else printf("hasNoDuplicatedItem!/n"); return 0;}三、使用位圖法進(jìn)行整形數(shù)組排序
首先遍歷數(shù)組，得到數(shù)組的最大最小值，然后根據(jù)這個最大最小值來縮小bitmap的范圍。這里需要注意對于int的負(fù)數(shù)，都要轉(zhuǎn)化為unsigned int來處理，而且取位的時候，數(shù)字要減去最小值。
#include<stdio.h>#include<stdlib.h>#include<string.h>#include<stdbool.h>void bitmapSort(int *a, int len){ int length, max, min, i, index; length = len; min = max = a[0]; //找出數(shù)組最大值 for(i = 1; i < length; i++){ if(a[i] > max){ max = a[i]; } if(min > a[i]) { min = a[i]; } } //得到位圖數(shù)組 int *arr; arr = (int*)malloc(sizeof(int) * (max - min + 1)); for(i = 0; i < length; i++){ index = a[i] - min; arr[index]++; } //重整a中的元素 int arr_length; arr_length = max - min + 1; index = 0; for(i = 0; i < arr_length; i++){ while(arr[i] > 0){ a[index] = i + min; index++; arr[i]--; } }}void print(int *a, int n){ int i; for(i = 0; i < n; i++) { printf("%d ", a[i]); } printf("/n");}int main(){ int length; int test[] = {50,1,26,3,45,12,13}; length = sizeof(test) / sizeof(test[0]); print(test, length); bitmapSort(test, length); print(test, length); return 0;}四、位圖法存數(shù)據(jù)
輸入：一個最多包含n個正整數(shù)的文件，每個數(shù)都小于n，其中n=10,000,000 輸入文件中沒有重復(fù)的整數(shù)，沒有其他數(shù)據(jù)與該整數(shù)相關(guān)聯(lián)。
輸出： 按升序排列這些數(shù)。
約束：有 1MB多（不超過2MB） 的內(nèi)存空間可用，有充足的硬盤空間。
#include<stdio.h>#define BITSPERWORD 32#define SHIFT 5#define MASK 0x1F#define N 10000000int a[1 + N/BITSPERWORD];/* a[i>>SHIFT]是第i位應(yīng)該在第幾個int上 *//* (1<<(i & MASK))是第i位在該int上的第幾個bit */void set(int i){ a[i>>SHIFT] |= (1<<(i & MASK));}void clr(int i){ a[i>>SHIFT] &= ~(1<<(i & MASK));}int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK));}int main(){ int i; for(i = 0; i < N; i++) clr(i); while(scanf("%d", &i) != EOF) set(i); for(i = 0; i < N; i++) if(test(i)) printf("%d/n", i); return 0;}希望本文所述對大家C程序算法設(shè)計的學(xué)習(xí)能有所幫助。
新聞熱點
疑難解答
圖片精選
