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成長之路（十）：其他高級議題