c - 关于具有邻接矩阵表示的非方向图

Question

我想使用尽可能少的内存为图形算法创建矩阵表示。

所以我决定尝试使用矩阵值的位表示，但我也知道用 C 来做这个(据我所知)是不可能的，因为位是不可寻址的。

然后我在这里阅读了一篇文章，建议使用一个可以帮助我这样做的结构，例如，一个 int(4 字节，所以 32 位)，并且通过一些魔法和位移，将它用作“数组” "位。

明白了，但我真的不知道我究竟是怎么做到的。我很困惑...

我正在考虑使用一个结构来存储一个指向 n 个字节的 int/void 指针，该指针对应于分配的“n”位数和该表示中的“k”位数的最少字节数，一些东西诸如此类。

所以我认为您可以帮助我了解什么是这种解决方案的最佳方法。

注意:为什么我这么困惑？我还在计算机科学专业毕业，刚开始学习图表。也刚刚完成了一个关于它的实验室项目(将其实现为矩阵但使用一些数学魔法只分配矩阵的一半并将其表示为对称的)，但我正在尝试扩展这个问题。也因为我非常好奇:)

谢谢大家。

P.S.:差点忘了，我是用 C 语言编程的，但我能很好地理解 C++、.Net 语言和 Java。再次感谢。

Answer 1

这里有几个棘手的问题:处理大型数组中的各个位；并用一维数组模拟二维数组。最好先分别解决这些问题。

从一些帮助您处理各个位的辅助函数开始。像这样的东西:

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 上的操作.

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. */