位图法是《编程珠玑》第一章中出现的磁盘排序算法。
题目:一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7,且所有正整数都不重复。求如何将这n个正整数升序排列。
约束:最多有1MB的内存空间可用,有充足的磁盘存储空间。
分析:这个题目的最大亮点是只有1MB的内存空间,我们可以通过计算得出,内存只有1MB可以储存的int(4byte)有10^3*10^3/4=250 000个号码。而包含正整数的文件约为10^7个int大小。这意味着无法将所有文件中的正整数一次读取进入到内存空间中去进行排序算法。
思路:
用位图法解决问题本题。
我们想使用hash映射,将对应的正整数映射到位图集合中。即将正整数映射到bit集合中,每一个bit代表其映射的正整数是否存在。
比如{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
我们可以使用具有10^7位的字符串来表示这个文件。其中,当且仅当整数i在文件中存在时候,第i位为1
本例中 自己尝试用 int数组 (
很多人用 字符串存储,还不知道 具体的优势在哪块,希望高手指点)存储相应的映射位,最后通过检查相应位 来完成排序。
具体实现如下:
#include <stdio.h>
#include <stdlib.h>
#define MASK 0x0001
#define NUMBER 10000 //读取的整数个数
#define ARRAY_LEN (NUMBER/32+1)
//本测试机 int 为 32位
int b[ARRAY_LEN];
int main()
{
int n, m, i, k;
int temp;
FILE *fp;
fp = fopen("text.txt","r");
if(!fp)
{
printf("open error!");
exit(1);
}
while (fscanf(fp, "%d", &temp) == 1)//读取数据,存在的数据 将对应的bit位置1,例如 11 存在则 bit[11] = 1
{
n = temp / 32;
m = temp % 32;
b[n] = b[n] | (MASK<<m);//
printf("n = %d, m = %d, b[%d] = %x\n", n, m , n, b[n]);
}
fclose(fp);
for (i = 0; i < ARRAY_LEN; i++)//进行输出
{
for(k = 0; k < 32; k++)
{
if (b[i] & (MASK<<k))
{
printf("%d ",i*32+k);
}
}
}
return 0;
}
另可以做封装函数
void set(int i)
{
b[i>>SHIFT] |= (1<<(i&0x1f));
}
void clr(int i)
{
b[i>>SHIFT] &= ~(1<<(i&0x1f));
}
int test(int i)
{
return b[i>>SHIFT] & (1<<(i&0x1f));
}
test.txt 中数据格式 :324 334 12 23 45 55....
分享到:
相关推荐
编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码
我觉得不错,和大家分享! 编程珠玑 编程珠玑 编程珠玑
编程珠玑编程珠玑
编程珠玑和编程珠玑续两本,上传赚点分,填充填充填充
《编程珠玑(续)》是计算机科学方面的经典名著《编程珠玑》的姊妹篇,讲述了对于程序员有共性的知识。书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例,这些内容组成一个有机的整体,...
编程珠玑续、编程珠玑续本、编程珠玑续本、编程珠玑续本
编程珠玑2(中文)
编程珠玑,编程珠玑续以及源码,本书针对程序设计人员探讨了一系列的实际问题,这些问题是对现实中常见问题的归纳总结。作者虽然没有给出解决这些问题的具体代码,但始终非常富有洞察力和创造力地围绕着这些折磨...
编程珠玑源代码还有课后习题代码,官方版本
《编程珠玑》第一版是我早期职业生涯中阅读过的对我影响较大的书籍之一,在书中首次接触到的很多观点都让我长期受益。作者在这一版本中做了重要更新。新增加的很多例子让我耳目一新。 ——Steve McConnell,《代码...
编程珠玑II(编程珠玑·续) 扫描版6.56M pdf格式
编程珠玑英文原版,中文非扫描版带目录,和中文扫描版
编程珠玑是一本提升coding能力不可多得的好书,看书时,可以结合这个笔记,突出重点。
编程珠玑+续
这本书是《编程珠玑》高清pdf,如有侵权请告知。
编程珠玑(第二版)答案
编程珠玑 中英文 第2版(含源代码)
编程珠玑.pdf 面试必备,算法必备,各种算法的精彩解析
《编程珠玑》读书笔记