程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C說話位圖算法詳解

C說話位圖算法詳解

編輯：關於C++

C說話位圖算法詳解。本站提示廣大學習愛好者：（C說話位圖算法詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話位圖算法詳解正文

本文具體講述了位圖算法的界說與C說話完成辦法，分享給年夜家供年夜家參考之用。詳細以下：

位圖法界說：

位圖法就是bitmap的縮寫，所謂bitmap，是用每位來寄存某種狀況，實用於年夜范圍數據，但數據狀況又不是許多的情形。平日是用來斷定某個數據存不存在的。

例如，要斷定一萬萬小我的狀況，每一個人只要兩種狀況：漢子，女人，可以用0，1表現。那末便可以開一個int數組，一個int有32個位，便可以表現32小我。操作的時刻可使用位操作。

數據構造：

unsigned int bit[N];

在這個數組外面，可以存儲 N * sizeof(int) * 8個數據，然則最年夜的數只能是N * sizeof(int) * 8 - 1。假設，我們要存儲的數據規模為0-15，則我們只須要使得N=1，如許便可以把數據存出來。以下圖：

數據為【5，1，7，15，0，4，6，10】，則存入這個構造中的情形為:

位圖法運用：

1、給40億個不反復的unsigned int的整數，沒排過序的，然後再給一個數，若何疾速斷定這個數能否在那40億個數傍邊

請求512M的內存

一個bit位代表一個unsigned int值

讀入40億個數，設置響應的bit位

讀入要查詢的數，檢查響應bit位能否為1，為1表現存在，為0表現不存在

2、應用位圖法斷定整形數組能否存在反復

斷定聚集中存在反復是罕見編程義務之一，當聚集中數據量比擬年夜時我們平日願望少停止幾回掃描，這時候兩重輪回法就弗成取了。位圖法比擬合適於這類情形，它的做法是依照聚集中最年夜元素max創立一個長度為max+1的新數組，然後再次掃描原數組，碰到幾就給新數組的第幾地位上1，如碰到 5就給新數組的第六個元素置1，如許下次再碰到5想置位時發明新數組的第六個元素曾經是1了，這解釋此次的數據確定和之前的數據存在側重復。這類給新數組初始化時置零厥後置一的做法相似於位圖的處置辦法故稱位圖法。它的運算次數最壞的情形為2N。假如已知數組的最年夜值即能事前給新數組定長的話效力還能進步一倍。

#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;
}

3、應用位圖法停止整形數組排序

起首遍歷數組，獲得數組的最年夜最小值，然後依據這個最年夜最小值來減少bitmap的規模。這裡須要留意關於int的正數，都要轉化為unsigned int來處置，並且取位的時刻，數字要減去最小值。

#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];
  //找出數組最年夜值
  for(i = 1; i < length; i++){
    if(a[i] > max){
      max = a[i];
    }
    if(min > a[i]) {
      min = a[i];
    }
  }
  //獲得位圖數組
  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;
}

4、位圖法存數據

輸出：一個最多包括n個正整數的文件，每一個數都小於n，個中n=10,000,000 輸出文件中沒有反復的整數，沒有其他數據與該整數相干聯。

輸入：按升序分列這些數。

束縛：有 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法式算法設計的進修能有所贊助。