题目：
输入：给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数），且其中每个数都小于等于n，n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
分析：
1、归并排序。你可能会想到把磁盘文件进行归并排序，但题目要求你只有1MB的内存空间可用，所以，归并排序这个方法不行。
2、位图方案。熟悉位图的朋友可能会想到用位图来表示这个文件集合。例如正如编程珠玑一书上所述，用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合，边框用如下字符串来表示集合{1,2,3,5,8,13}：
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
上述集合中各数对应的位置则置1，没有对应的数的位置则置0。
说明：使用bitset方法必须满足的条件是：不能有重复的数字
#include <assert.h>
#include <bitset>
#include <iostream>
using namespace std;
const int maxEachScan = ;
const int maxSortNumber = ; void SortBigNumber()
{
FILE *fp_unSortFile = fopen("d:\\unSort_data.txt","r+");
FILE *fp_SortFile = fopen("d:\\sort_data.txt", "w+");
assert(fp_unSortFile);
bitset<maxEachScan> bit_map; //因为数据比较大，分成两次执行,这里相当于定义了一个数组来保存所有结果
bit_map.reset(); //置0
int num; /*第一遍遍历*/
while (fscanf(fp_unSortFile,"%d",&num)!=EOF)
{
if (num < maxEachScan)
bit_map.set(num, ); //bitset内部机制,保存在bit_map中
} for (int i = ; i < maxEachScan; i++) //遍历bit_map
{
if (bit_map[i] == )
fprintf(fp_SortFile, "%d", i); //这里就是将数据用bit保存（放在bitmap中），再输出的时候输出其对应的数字
} /*第二遍遍历*/
bit_map.reset();
fseek(fp_unSortFile,,SEEK_SET); //移到文本的开头
while (fscanf(fp_unSortFile,"%d",&num)!=EOF)
{
if (num >= maxEachScan&&num < maxSortNumber)
bit_map.set(num-maxEachScan, );
} for (int i = ; i < maxEachScan; i++)
{
if (bit_map[i] == )
fscanf(fp_SortFile,"%d",i+maxEachScan);
} fclose(fp_unSortFile);
fclose(fp_SortFile);
}
需要用到的函数：
1.fseek： 用来将指针移到指定位置，本代码主要是移动到文本开头，进行第二次扫描
2.bitset 容器
bitset:: reset 用来将bit位全部置0
bitset:: set 给bit位置设置0或者1 来表示这个bit有没有元素
// bitset::set
#include<iostream>// std::cout
#include<bitset>// std::bitset
int main ()
{
std::bitset<> foo;
std::cout << foo.set()<<'\n';//
std::cout << foo.set(,)<<'\n';//
std::cout << foo.set()<<'\n';//
return0;
}
Edit&Run
Output:
3.文件的读取
fscanf(fp_unSortFile,"%d",&num)!=EOF %d可以限定我们读取的是int类型EOF判断文件尾部