编程珠玑 epub_编程珠玑：位图法排序

  本文关键词：编程珠玑，由笔耕文化传播整理发布。

问题描述

输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=107。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。

输出：按升序排列的输入正数的列表。

约束：最多有1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化。

程序设计与实现概要：

应用位图或位向量表示集合。可用一个10位长的字符串来表示一个所有元素都小于10的简单的非负整数集合，例如，，可以用如下字符串表示集合{1,2,4,5,8}:

0  1  1  1  0  1  0  0  1  0  0

代表集合中数值的位都置为1，其他左所有的位置为0.编程珠玑当中建议是一年个一个具有1000万个位的字符串来表示这个文件，那么这个文件的所占容量为10000000 bit=107bit，不到1MB的大小，其中，当且精当整数i在文件中存在，第i为1，这个表示利用了该问题的三个在排序问题中不常见的属性：输入数据限制在相对较小的范围内；数据没有重复；而且对于每条记录而言，除了单一个整数外没有其他关联数据。

如给定表示文件中整数集合的位图数据结构，则可以分三个阶段来编写程序

第一阶段：将所有的位都置为0，从而将集合初始化为空。

第二阶段：通过读入文件中的每个整数来建立集合，将每个对应的位置都置为1。

第三阶段：检验每一位，如果该为为1，就输出对应的整数，有此产生有序的输出文件。

下面的C语言的实现和C++的实现代码

C语言：

所申请的int数组如下所示：

字节位置=数据/32;(采用位运算即右移5位)

位位置=数据%32;(采用位运算即跟0X1F进行与操作)。

#include

  本文关键词：编程珠玑，由笔耕文化传播整理发布。