歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C 版 位圖排序法

問題: 給10^7 個 不重復的整數, 排序

位圖實現:

基本思路: 使用一位來表示一個數 例如集合 {1, 3, 5, 8},  可以用 位圖 {10101001} 來表示。即對應位置為1 如下圖所示.

關鍵操作有: 1) 找到數據所對應的字節位置 2)找到數據對應的字節中位位置 3) 判斷某位為1, 置某位為1 etc

方法:

1) 找到 對應字節位置: 如果系統是32 位的話 相當於將 數據/32, 使用位操作 數據 >> 5

2)  找到對應字節的位位置: 如果系統是32位的話 相當於將 數據%32, 使用位操作 數據 &0x1F

3)數字 a 的 第i位 是1: 方法 a & (1 << i) ,將數據a的第 i位 置1 a | (1 << i)

具體步驟:

#define MAX 5000000
#define SHIFT 5
#define MASK 0x1F
#define DIGITS 32

int 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.htm

C++ 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成長之路(十):其他高級議題

Copyright © Linux教程網 All Rights Reserved