Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3232844
  • 博文数量: 367
  • 博客积分: 9916
  • 博客等级: 中将
  • 技术积分: 7199
  • 用 户 组: 普通用户
  • 注册时间: 2011-05-29 23:27
个人简介

简单!

文章分类

全部博文(367)

文章存档

2013年(51)

2012年(269)

2011年(47)

分类: C/C++

2013-04-26 22:41:41

    所谓的Bit-map就是用一个bit位来标记某个元素对应的Value,而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面可以大大节省。算法思想比较简单,但关键是如何确定十进制的数映射到二进制bit位的map图。

优点:
    1.运算效率高,不许进行比较和移位;
    2.占用内存少,比如数据N=10000000;只需占用内存为N/8=1250000Byte=1.25M。
缺点:
    所有的数据不能重复,即不可对重复的数据进行排序和查找。    


    假设有一文件里面存储了大量的数据且以升序的方式排列,例如以下形式:
  1. 3
  2. 6
  3. 7
  4. 16
  5. 23
  6. 57
  7. 89
   
      测试代码如下:
  1. #include<stdlib.h>
  2. #include<unistd.h>
  3. #include<string.h>
  4. #include<stdio.h>

  5. #define MAXLINE 1024
  6. #define CHAR_BIT_LEN    8

  7. static int bitmap_setbit(char *pos, int base, int new)
  8. {
  9.     if(pos == NULL || (new < base))
  10.         return -1;

  11.     pos += (new - base)/CHAR_BIT_LEN;
  12.     *pos |= 1<<((new - base)%CHAR_BIT_LEN);

  13.     return 0;
  14. }

  15. static int bitmap_checkbit(char *pos, int base, int data)
  16. {
  17.     if(pos == NULL || (data < base))
  18.         return 0;

  19.     pos += (data - base)/CHAR_BIT_LEN;

  20.     return (*pos & (1<<((data - base)%CHAR_BIT_LEN)) ? 1:0);
  21. }

  22. int main(int argc, char **argv)
  23. {
  24.     FILE *fp = NULL;
  25.     char line[MAXLINE] = {0};
  26.     int linesNum = 0;
  27.     int base;
  28.     char pos[256] = {0};

  29.     fp = fopen(argv[1], "r");
  30.     if(fp == NULL) {
  31.         printf("can not open file %s\n", argv[1]);
  32.         return -1;    
  33.     }

  34.     while ((fgets(line, MAXLINE, fp)) != NULL) {
  35.         line[strlen(line)-1] = '\0';
  36.         if(++linesNum == 1)
  37.             base = atoi(line);

  38.         bitmap_setbit(pos, base, atoi(line));
  39.         if(bitmap_checkbit(pos, base, atoi(line)) == 1)
  40.             printf("sucess:data checked in file!\n");
  41.         else
  42.             printf("fail:data not in file\n");
  43.     }

  44.     if(bitmap_checkbit(pos, base, 78) == 1)
  45.         printf("sucess:data checked in file!\n");
  46.     else
  47.         printf("fail:data not in file\n");

  48.     fclose(fp);
  49.     fp = NULL;

  50.     return 0;
  51. }

阅读(2385) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册