# 工学1号馆

home

## 位图算法

Wu Yudong    June 01, 2015     Algorithm   571

unsigned int bit[N];

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

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

#include<stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define N 10000000
int a[1 + N/BITSPERWORD];

/* a[i>>SHIFT]是第i位应该在第几个int上 */

void set(int i)
{
}

void clr(int i)
{
}

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("%dn", i);
return 0;
}