首页 / 操作系统 / Linux / C 版 位图排序法

问题： 给10^7 个 不重复的整数， 排序位图实现：基本思路： 使用一位来表示一个数 例如集合 {1， 3， 5， 8}，  可以用 位图 {10101001} 来表示。即对应位置为1 如下图所示.关键操作有： 1） 找到数据所对应的字节位置 2）找到数据对应的字节中位位置 3） 判断某位为1， 置某位为1 etc方法：1） 找到 对应字节位置: 如果系统是32 位的话 相当于将 数据/32, 使用位操作 数据 >> 52）  找到对应字节的位位置: 如果系统是32位的话 相当于将 数据%32, 使用位操作 数据 &0x1F3）数字 a 的 第i位 是1： 方法 a & （1 << i） ，将数据a的第 i位 置1 a | （1 << i）具体步骤：#define MAX 5000000
#define SHIFT 5
#define MASK 0x1F
#define DIGITS 32int bitmap[1 + MAX/DIGITS]; // 先找到数据n 所在位置bitmap[n >> SHIFT]
// 然后将这个整数的 所对应的数据n的位置 置1； （n & MASK） 是找到对应为位位置； 与运算 置1
void set（int n）
{
    bitmap[n >> SHIFT] = bitmap[n >> SHIFT] | （1 << （n & MASK））;
}// 置0 采用 & 运算
void clear（int n）
{
   bitmap[n >> SHIFT] = bitmap[n >> SHIFT] & （~ 1 << （n & MASK））;
}//采用 & 运算
void test（int n）
{
      return bitmap[n >> SHIFT] & （1 << （n & MASK））;
}
int main（）{ for（int i = 1; i <= MAX; i++）
 {
    clear（i）;
  }  // open data file with unsorted data
  FILE *fp_unsort_file = fopen（"data.txt", "r"）;
  assert（fp_unsort_file）;
  FILE* fp_sort_file = fopen（"sortByC.txt", "w"）;
  assert（fp_sort_file）;  int n;
  while（fscanf（fp_unsort_file, "%d ", &n） ！= EOF）
  {
    set（n%MAX）;
  }  for（int i = 1; i <= MAX; i++）
  {
   if（test（i））
    {
    fprintf（fp_sort_file, "%d ", i）;
    }
  }
  if（fp_unsort_file ！= NULL）
  {
    fclose（fp_unsort_file）;
  }
  if（fp_sort_file ！= NULL）
  {
    fclose（fp_sort_file）;
  }}另外C++ 实现了bitmap 也可以直接用
 
C++ 标准的STL

1. // 初始化
2. bitset<max_each_scan> bit_map;
3. bit_map.reset（）;
4. // 置1
5. while（fscanf（fp_unsort_file, "%d ", &n） ！= EOF）
6. {
7. if（num < max）
8. {
9. bit_map.set（n, 1）;
10. }
11. }
12. // 判断
13. for （int i = 0; i < max; i++）
14. {
15. if（bit_map[i] == 1）
16. {
17. fprintf（fp_sort_file, "%d ", i）;
18. }
19. }

《C++ 设计新思维》 下载见 http://www.linuxidc.com/Linux/2014-07/104850.htmC++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码 http://www.linuxidc.com/Linux/2014-05/101227.htm读C++ Primer 之构造函数陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm读C++ Primer 之智能指针 http://www.linuxidc.com/Linux/2011-08/40177.htm读C++ Primer 之句柄类 http://www.linuxidc.com/Linux/2011-08/40175.htm将C语言梳理一下，分布在以下10个章节中：

1. Linux-C成长之路（一）：Linux下C编程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
2. Linux-C成长之路（二）：基本数据类型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
3. Linux-C成长之路（三）：基本IO函数操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
4. Linux-C成长之路（四）：运算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
5. Linux-C成长之路（五）：控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
6. Linux-C成长之路（六）：函数要义 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
7. Linux-C成长之路（七）：数组与指针 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
8. Linux-C成长之路（八）：存储类，动态内存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
9. Linux-C成长之路（九）：复合数据类型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
10. Linux-C成长之路（十）：其他高级议题

本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-08/105693.htm