C語言位圖算法詳解

更新時間：2014年09月10日 09:32:35 投稿：shichen2014

這篇文章主要介紹了C語言實現(xiàn)的位圖算法,主要包括了位圖算法的定義與應用,對于C程序算法設計的學習有一定的借鑒價值,需要的朋友可以參考下

本文詳細講述了位圖算法的定義與C語言實現(xiàn)方法，分享給大家供大家參考之用。具體如下：

位圖法定義：

位圖法就是bitmap的縮寫，所謂bitmap，是用每一位來存放某種狀態(tài)，適用于大規(guī)模數(shù)據，但數(shù)據狀態(tài)又不是很多的情況。通常是用來判斷某個數(shù)據存不存在的。

例如，要判斷一千萬個人的狀態(tài)，每個人只有兩種狀態(tài)：男人，女人，可以用0，1表示。那么就可以開一個int數(shù)組，一個int有32個位，就可以表示32個人。操作的時候可以使用位操作。

數(shù)據結構：

unsigned int bit[N];

在這個數(shù)組里面，可以存儲 N * sizeof(int) * 8個數(shù)據，但是最大的數(shù)只能是N * sizeof(int) * 8 - 1。假如，我們要存儲的數(shù)據范圍為0-15，則我們只需要使得N=1，這樣就可以把數(shù)據存進去。如下圖：

數(shù)據為【5，1，7，15，0，4，6，10】，則存入這個結構中的情況為:

位圖法應用：

一、給40億個不重復的unsigned int的整數(shù)，沒排過序的，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那40億個數(shù)當中

申請512M的內存

一個bit位代表一個unsigned int值

讀入40億個數(shù)，設置相應的bit位

讀入要查詢的數(shù)，查看相應bit位是否為1，為1表示存在，為0表示不存在

二、使用位圖法判斷整形數(shù)組是否存在重復

判斷集合中存在重復是常見編程任務之一，當集合中數(shù)據量比較大時我們通常希望少進行幾次掃描，這時雙重循環(huán)法就不可取了。位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創(chuàng)建一個長度為max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上1，如遇到 5就給新數(shù)組的第六個元素置1，這樣下次再遇到5想置位時發(fā)現(xiàn)新數(shù)組的第六個元素已經是1了，這說明這次的數(shù)據肯定和以前的數(shù)據存在著重復。這種給新數(shù)組初始化時置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運算次數(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;
}

三、使用位圖法進行整形數(shù)組排序

首先遍歷數(shù)組，得到數(shù)組的最大最小值，然后根據這個最大最小值來縮小bitmap的范圍。這里需要注意對于int的負數(shù)，都要轉化為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ù)據

輸入：一個最多包含n個正整數(shù)的文件，每個數(shù)都小于n，其中n=10,000,000 輸入文件中沒有重復的整數(shù)，沒有其他數(shù)據與該整數(shù)相關聯(lián)。

輸出：按升序排列這些數(shù)。

約束：有 1MB多（不超過2MB）的內存空間可用，有充足的硬盤空間。

#include<stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
/* a[i>>SHIFT]是第i位應該在第幾個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程序算法設計的學習能有所幫助。

您可能感興趣的文章: