关于用邻接矩阵表示的非定向图

Question

我想使用尽可能少的内存创建一个矩阵表示图算法。因此，我决定尝试使用矩阵值的位表示，但我也知道在C中这样做是不可能的，因为位不能被寻址。然后我在这里看到一篇帖子建议使用结构体来帮助我通过使用例如int（4字节，因此32位）和一些魔术和位移将其用作位“数组”。

我明白了，但我真的无法意识到我应该如何做到这一点。我感到困惑......

我考虑使用一个结构来存储与分配给'n'个位的最少字节数相对应的n个字节的int / void指针以及在该表示中的'k'个位数，例如这样。

因此，我认为您可以帮助我实现这种解决方案的最佳方法。

注意：为什么我如此困惑？我仍在攻读计算机科学学位，我刚开始学习图形。还刚刚完成了关于这个的实验室项目（将它实现为矩阵，但使用了一些数学技巧来仅分配矩阵的一半并将其表示为对称），但我正在尝试扩展这个问题。也因为我非常好奇：）

谢谢大家。

P.S .：几乎忘了，我在C中编程，但我可以非常好地理解C ++，.Net语言和Java。再次感谢。

- Giuliano

Answer 1

关于C语言中的位结构体，只是一条评论 - 在这里看看：

• http://www.cs.cf.ac.uk/Dave/C/node13.html
• http://msdn.microsoft.com/en-us/library/yszfawxh(VS.80).aspx

以下应该是如何使用位结构体的好指针。

- icyrock.com

---

有趣！不知道运算符“：”，所以我不需要成为一个位操作专家，哈哈。但是，不幸的是，正如C99标准所描述的：“一元&运算符的操作数必须是函数指示器、[]或一元*运算符的结果，或者是指定了一个非位域且未声明为寄存器存储类别说明符的对象的左值。”因此，位域是一个可能的答案，但我不能从它们中创建数组或矩阵。顺便说一句，很高兴知道我可以这样处理位，谢谢！:D - Giuliano

很高兴它有用。对于C语言有点生疏，所以不是说这不正确，但不确定我是否理解你所说的限制。上述内容只是关于&运算符的限制（即您不能执行a.b & c，其中a.b是一个位域），但我认为这并不意味着您不能创建一个a的数组。 - icyrock.com

你可以对结构体进行操作，但不能针对类型进行操作。不过这样已经足够了。我试图通过这个限制来表明，你无法从一个位中提取地址。& 运算符用于给出一个地址，并表示不能在位域上使用它。因此，位域不能直接声明为数组。这几乎是一个必然推论 =) - Giuliano

没错，但我想这会让你很容易地创建一个辅助函数。如果你的结构是以字节为导向的，那么你只需要一个获取/设置函数部分，它只需将地址除以8，然后使用简单的开关来获取/设置适当的位。当然，你的需求可能更大 :) - icyrock.com

不用客气，希望无论如何都能顺利解决。 - icyrock.com

Answer 2

这里有几个棘手的问题：在大数组中处理单个位，以及用一维数组模拟二维数组。最好先分别解决这些问题。

首先从一些帮助函数开始，让您可以处理单个位。类似于：

typedef unsigned int BYTE;  /* Int type to use for data. */
#define BYTE_SIZE (sizeof(BYTE)*8)   /* How many bits in each one. */

void set_bit(BYTE *data, int pos, int value)
{
    int index = pos / BYTE_SIZE;   /* Which byte to adjust. */
    int offset = pos % BYTE_SIZE;  /* Which bit within it. */
    /* 1 << offset turns into the place value for the bit at offset. */
    /* x | 1 << offset sets the bit there (an OR operation);
       ~(1 << offset) gets something with all bits except that bit set, and
       x & ~(1 << offset) clears the bit with an AND operation on x. */
    if (value)
        data[index] = data[index] | (1 << offset);
    else
        data[index] = data[index] & ~(1 << offset);
}

int test_bit(int *data
{
    int index = pos / BYTE_SIZE;
    int offset = pos % BYTE_SIZE;
    /* An AND operation to see if the bit is set, then compare against 0
       so that 1 or 0 is returned instead of the place value. */
    return (data[index] & (1 << offset)) != 0;
}

接下来，您可以通过使用一个结构来保存字节数组和一些关于维度的数据来提升级别。通过将对位 (x,y) 的操作转换为对位 y*width+x 的操作，可以使用 1 维数组模拟 2 维数组。

struct BITMATRIX
{
    BYTE *data;
    int width;
    int height;
}

void set_bit_matrix(struct BITMATRIX *bm, int x, int y, int value)
{
    int pos = y * bm->width + x;
    set_bit(bm->data, pos, value);
}

/* Etc. */

- Edmund

---

两个答案都可以完成任务（已经测试过了！），但这个答案实际上给了我一些我试图找到的算法。谢谢，Edmund :) - Giuliano

这个回答值得很多赞...严格来说，你的回答非常棒!!! - Abhishek Ghosh

这是我的实现，基于@Edmund提出的概念。请查看链接：https://github.com/Abhishekghosh1998/SO/blob/master/bit_matrix.c - Abhishek Ghosh