1

我的问题是如何在以下情况下实现位图？
如果图的某个顶点在最小生成树（MST）中，则标记对应的位；稍后通过检查该位检查它是否在 MST 中。

一开始，我正在考虑使用 

typedef struct bit_t{    
   char bit0:1;
} bit;       

bit bitmap[num_of_vertex];

并使用位图数组记录位；

但后来我发现 sizeof (bitmap[num_of_vertex]) 是 num_of_vertex 字节，而不是 num_of_vertex/8 字节。所以它不像我想的那样节省空间；

到目前为止，我使用 

long bit_record = 0;   
...
bit_record |= 1<< u;//set vertex as in MST    
...

然后稍后使用以下命令检查顶点是否在 MST 中： 

static bool is_in_MST(int v, int bit_record){   
    int mask = 1 <<  v;   
    if (mask & bit_record)    
        return true;   
    else    
        return false;   
}

虽然代码有效，但如果 num_of_vertex 大于 32，它将不起作用。

通常如何实现上述情况下的位图？

4

2 回答 2

5

情况是你不能在 C 中拥有 1 位类型。最小的可寻址单元是 C 中的一个字节，所以即使你声明一个具有一位位域的结构，它也会被填充到一个字节（在至少）。您可以做的是创建一个字节数组，然后使用除法和模数访问数组中的位。

unsigned char bitmap[0x100] = { 0 };

void set_nth_bit(unsigned char *bitmap, int idx)
{
    bitmap[idx / CHAR_BIT] |= 1 << (idx % CHAR_BIT);
}

void clear_nth_bit(unsigned char *bitmap, int idx)
{
    bitmap[idx / CHAR_BIT] &= ~(1 << (idx % CHAR_BIT));
}

int get_nth_bit(unsigned char *bitmap, int idx)
{
    return (bitmap[idx / CHAR_BIT] >> (idx % CHAR_BIT)) & 1;
}
于 2013-06-15T06:39:14.213 回答
1

关于位图，这里有一个关于 Programming Pearls 的例子，我添加了一些注释：

#define BITPERWORD  32 //bits of int，which depends on your computer
#define N           10000000 // number of your elements
#define SHIFT       5 // 32 = 2^5
#define MASK        0x1F // 11111 in binary 
int a[N/BITPERWORD + 1]; //space for your bitmap

// i is the the bit you want to use
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));}

并且不要忘记一开始的初始化：

for(i=0;i<N;i++)
    clr(i);
于 2013-06-15T07:18:33.770 回答