[cpp] view plaincopy

 

1. #include <stdio.h>  
2. #include <stdlib.h>  
3.   
4. #define INT_BY_BIT 32  
5. #define MASK 0x1F  
6. #define SHIFT 5  
7.   
8. #define N 1000000  
9.   
10. int a[N/INT_BY_BIT+1];  
11. void set_bit(int x) {a[x>>SHIFT] |= 1 << (x & MASK);}  
12. void clear_bit(int x) {a[x>>SHIFT] &= ~(1<<(x & MASK));}  
13. int test_bit(int x){return a[x>>SHIFT]&(1<<(x & MASK));}  
14.   
15. int main()  
16. {  
17. //  int a[N/INT_BY_BIT+1];  
18.     int i;  
19.     for(i=0;i<N;i++)  
20.     {  
21.         clear_bit(i);  
22.     }  
23.     while (scanf("%d",&i) != EOF)  
24.     {  
25.         set_bit(i);  
26.     }  
27.     for(i=0;i<N;i++)  
28.     {  
29.         if(test_bit(i))  
30.         {  
31.             printf("%d",i);  
32.             printf(" ");  
33.         }  
34.     }  
35.     return 0;  
36. }  

1，如果某个数字可能出现最多8次，应该如何用位图排序？
答：可以用一个字节来表示一个数

2，如果有10000000个数字，但是内存只有1M，而10000000需要1.25M，用过如何排序？
答：可以通过两趟排序完成，第一趟排序1到5000000，第二次排序5000000到10000000

[数据结构]利用位图排序