C语言位图算法详解

本文详细讲述了位图算法的定义与C语言实现方法,分享给大家供大家参考之用。具体如下:

位图法定义:

位图法就是bitmap的缩写,所谓bitmap,是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

例如,要判断一千万个人的状态,每个人只有两种状态:男人,女人,可以用0,1表示。那么就可以开一个int数组,一个int有32个位,就可以表示32个人。操作的时候可以使用位操作。
 
数据结构:

unsigned int bit[N];

在这个数组里面,可以存储 N * sizeof(int) * 8个数据,但是最大的数只能是N * sizeof(int)  * 8 - 1。假如,我们要存储的数据范围为0-15,则我们只需要使得N=1,这样就可以把数据存进去。如下图:

数据为【5,1,7,15,0,4,6,10】,则存入这个结构中的情况为:

位图法应用:

一、给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中

申请512M的内存

一个bit位代表一个unsigned int值

读入40亿个数,设置相应的bit位

读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在

二、使用位图法判断整形数组是否存在重复

判断集合中存在重复是常见编程任务之一,当集合中数据量比较大时我们通常希望少进行几次扫描,这时双重循环法就不可取了。位图法比较适合于这种情况,它的做法是按照集合中最大元素max创建一个长度为max+1的新数组,然后再次扫描原数组,遇到几就给新数组的第几位置上1,如遇到 5就给新数组的第六个元素置1,这样下次再遇到5想置位时发现新数组的第六个元素已经是1了,这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
bool hasDuplicatedItem(int *a, int len)
{
  int length, max, i;
  length = len;
  max = a[0];
  for(i = 1; i < length; i++){
    if(a[i] > max)
      max = a[i];
  }
  int *arr;
  arr = (int*)malloc(sizeof(int) * (max + 1));
  for(i = 0; i < length; i++){
    if(arr[a[i]])
      return true;
    else
      arr[a[i]] = 1;
  }
  return false;
}
int main()
{
  int length;
  int test[] = {0,1,2,3,45,12,13};
  length = (sizeof(test) / sizeof(test[0]));
  if(hasDuplicatedItem(test, length))
    printf("hasDuplicatedItem!\n");
  else
    printf("hasNoDuplicatedItem!\n");
  return 0;
}

三、使用位图法进行整形数组排序

首先遍历数组,得到数组的最大最小值,然后根据这个最大最小值来缩小bitmap的范围。这里需要注意对于int的负数,都要转化为unsigned int来处理,而且取位的时候,数字要减去最小值。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
void bitmapSort(int *a, int len)
{
  int length, max, min, i, index;
  length = len;
  min = max = a[0];
  //找出数组最大值
  for(i = 1; i < length; i++){
    if(a[i] > max){
      max = a[i];
    }
    if(min > a[i]) {
      min = a[i];
    }
  }
  //得到位图数组
  int *arr;
  arr = (int*)malloc(sizeof(int) * (max - min + 1));
  for(i = 0; i < length; i++){
    index = a[i] - min;
    arr[index]++;
  }
  //重整a中的元素
  int arr_length;
  arr_length = max - min + 1;
  index = 0;
  for(i = 0; i < arr_length; i++){
    while(arr[i] > 0){
      a[index] = i + min;
      index++;
      arr[i]--;
    }
  }
}
void print(int *a, int n)
{
  int i;
  for(i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
}
int main()
{
  int length;
  int test[] = {50,1,26,3,45,12,13};
  length = sizeof(test) / sizeof(test[0]);
  print(test, length);
  bitmapSort(test, length);
  print(test, length);
  return 0;
}

四、位图法存数据

输入:一个最多包含n个正整数的文件,每个数都小于n,其中n=10,000,000 输入文件中没有重复的整数,没有其他数据与该整数相关联。

输出: 按升序排列这些数。

约束:有 1MB多(不超过2MB) 的内存空间可用,有充足的硬盘空间。

#include<stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
/* a[i>>SHIFT]是第i位应该在第几个int上 */
/* (1<<(i & MASK))是第i位在该int上的第几个bit */
void set(int i)
{
  a[i>>SHIFT] |= (1<<(i & MASK));
}
void clr(int i)
{
  a[i>>SHIFT] &= ~(1<<(i & MASK));
}
int test(int i)
{
  return a[i>>SHIFT] & (1<<(i & MASK));
}
int main()
{
  int i;
  for(i = 0; i < N; i++)
    clr(i);
  while(scanf("%d", &i) != EOF)
    set(i);
  for(i = 0; i < N; i++)
    if(test(i))
      printf("%d\n", i);
  return 0;
}

希望本文所述对大家C程序算法设计的学习能有所帮助。

(0)

相关推荐

  • C语言经典算法例题求100-999之间的“水仙花数

    题目:打印出所有的 "水仙花数 ",所谓 "水仙花数 "是指一个三位数,其各位数字立方和等于该数本身. 例如:153是一个 "水仙花数 ",因为153=1的三次方+5的三次方+3的三次方. 实现代码如下 #include <iostream> #include <Cmath> using namespace std; /* 求100-999之间的水仙花数 */ int main() { int number,hun,ten

  • 基于C语言实现简单的走迷宫游戏

    本文实例讲述了C语言实现简单的走迷宫游戏的方法,代码完整,便于读者理解. 学数据结构时用"栈"写的一个走迷宫程序,实际上用到双向队列,方便在运行完毕后输出经过的点. #include <cstdio> #include <deque> #include <windows.h> using namespace std; class node { public: int x,y; int lastOpt; }; deque<node> sta

  • C语言使用广度优先搜索算法解决迷宫问题(队列)

    本文实例讲述了C语言使用广度优先搜索算法解决迷宫问题.分享给大家供大家参考,具体如下: 变量 head 和 tail 是队头和队尾指针, head 总是指向队头, tail 总是指向队尾的下一个元素.每个点的 predecessor 成员也是一个指针,指向它的前趋在 queue 数组中的位置.如下图所示: 广度优先是一种步步为营的策略,每次都从各个方向探索一步,将前线推进一步,图中的虚线就表示这个前线,队列中的元素总是由前线的点组成的,可见正是队列先进先出的性质使这个算法具有了广度优先的特点.广

  • C语言实现魔方阵算法(幻方阵 奇魔方 单偶魔方实现)

    例如三阶魔方阵为: 魔方阵有什么的规律呢? 魔方阵分为奇幻方和偶幻方.而偶幻方又分为是4的倍数(如4,8,12--)和不是4的倍数(如6,10,14--)两种.下面分别进行介绍. 2 奇魔方的算法 2.1 奇魔方的规律与算法 奇魔方(阶数n = 2 * m + 1,m =1,2,3--)规律如下: 数字1位于方阵中的第一行中间一列:数字a(1 < a  ≤ n2)所在行数比a-1行数少1,若a-1的行数为1,则a的行数为n:数字a(1 < a  ≤ n2)所在列数比a-1列数大1,若a-1的列

  • C语言 数据结构中求解迷宫问题实现方法

    C语言 数据结构中求解迷宫问题实现方法 在学习数据结构栈的这一节遇到了求迷宫这个问题,拿来分享一下~ 首先求迷宫问题通常用的是"穷举求解" 即从入口出发,顺某一方向试探,若能走通,则继续往前走,否则原路返回,换另一个方向继续试探,直至走出去. 我们可以先建立一个8*8的迷宫其中最外侧为1的是墙 int mg[M+2][N+2]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,

  • c语言实现冒泡排序、希尔排序等多种算法示例

    实现以下排序 插入排序O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 希尔排序 O(n^1.25) 1.插入排序 O(n^2) 一般来说,插入排序都采用in-place在数组上实现.具体算法描述如下:⒈ 从第一个元素开始,该元素可以认为已经被排序⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置⒋ 重复步骤3,直到找到已排序的元素

  • 基于C语言实现的迷宫算法示例

    本文实例讲述了基于C语言实现的迷宫算法.分享给大家供大家参考,具体如下: 利用c语言实现迷宫算法,环境是vc++6.0. #include<stdio.h> #include<time.h> #include<cstdlib> int visit(int,int); void setmaze(); int maze[11][11]= { {0,0,2,2,2,2,2,2,2,2}, {2,0,2,2,0,2,0,2,0,2}, {2,0,2,0,0,0,0,0,0,2}

  • 基于C语言实现的迷宫游戏代码

    本文实例讲述了基于C语言实现迷宫游戏的方法,代码备有较为详尽的注释,便于读者理解.通过该游戏代码可以很好的复习C语言的递归算法与流程控制等知识,相信对于学习游戏开发的朋友有一定的借鉴价值. 完整的实例代码如下: #include <graphics.h> #include <stdlib.h> #include <stdio.h> #include <conio.h> #include <dos.h> #define N 20/*迷宫的大小,可改

  • 详解约瑟夫环问题及其相关的C语言算法实现

    约瑟夫环问题 N个人围成一圈顺序编号,从1号开始按1.2.3......顺序报数,报p者退出圈外,其余的人再从1.2.3开始报数,报p的人再退出圈外,以此类推.   请按退出顺序输出每个退出人的原序号 算法思想 用数学归纳法递推. 无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达O(nm),若nm非常大,无法在短时间内计算出结果.我们注意到原问题仅仅是要求出最后的胜利者的序号,而不是要读者模拟整个过程.因此如果要追求效率,就要打破常规,实

  • c语言 汉诺塔算法代码

    复制代码 代码如下: #include<stdio.h> void move(char a,char b) {     printf("%c->%c\n",a,b); } void han(int n,char a,char b,char c) {     if(n>0)     {         han(n-1,a,c,b);         move(a,b);         han(n-1,c,b,a);     } } int main() {   

  • C语言使用深度优先搜索算法解决迷宫问题(堆栈)

    本文实例讲述了C语言使用深度优先搜索算法解决迷宫问题.分享给大家供大家参考,具体如下: 深度优先搜索 伪代码 (Pseudocode)如下: 将起点标记为已走过并压栈; while (栈非空) { 从栈顶弹出一个点p; if (p这个点是终点) break; 否则沿右.下.左.上四个方向探索相邻的点 if (和p相邻的点有路可走,并且还没走过) 将相邻的点标记为已走过并压栈,它的前趋就是p点; } if (p点是终点) { 打印p点的坐标; while (p点有前趋) { p点 = p点的前趋;

随机推荐