1

在 Programming Pearls 中有一种算法可以对不同长度的数组进行排序,但排序的时间与它们的长度之和成正比。例如,如果我们有一个记录数组x[0...n-1],并且每条记录都有一个整数长度和一个指向数组的指针bit[0...length-1]

代码是这样实现的:

void bsort(l, u, depth){
    if (l >= u)
        return ;
    for (i = l; i <= u; i++){
        if (x[i].length < depth)
            swap(i, l++);
    }
    m = l;
    for (int i = l; i < u; i++){
        if (x[i].bit[depth] == 0)
            swap(i, m++);
    }
    bsort(l, m - 1, depth + 1);
    bsort(m, u, depth + 1);
}

我的问题是,鉴于记录:

x[6] = {"car", "bus", "snow", "earth", "dog", "mouse"}

我知道如何获取字符串长度,但是使用位数组呢?我怎样才能制作一个适合这个字符串数组的位数组?甚至x[i].bit[depth]我该如何实现呢?

4

1 回答 1

1

字符数组(或任何其他类型,就此而言)也是位数组 - 毕竟,字符是由位组成的。所以你不必创建一个单独的数组,你只需要找到一种方法来访问数组中的给定位。为此,您必须使用一些位操作。您可以在这里找到一些如何做到这一点的示例:任何更聪明的方法来从位数组中提取?.

基本上,您首先必须找出所需位所在的字节,然后获取该特定位的值。伴随着一些东西:

char* array = "the array";
int required_bit = 13;
int bit = required_bit & 0x7;  // get the bit's offset in its byte
int byte = required_bit >> 3;  // get the bit's byte
int val = (array[byte] >> bit) & 0x1; // check if the bit is 1

现在将它包装在一个函数中(可能带有额外的边界检查,以确保给定required_bit的不在数组之外),并使用 with x[i]

于 2011-10-15T05:53:04.223 回答