来自编程珍珠的 bsort 示例

发布于 2024-12-10 00:24:27 字数 716 浏览 1 评论 0原文

在《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[深度] 我该如何实现这个？

原文

In Programming Pearls there is an algorithm that sorts varying length arrays but sorts in time proportional to the sum of their length. For example, if we have a record array x[0...n-1], and each record has an integer length and a pointer to array bit[0...length-1].

The code is implemented this way:

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);
}

My question is that, given the record:

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

I know how to get the string length, but what about with a bit array? How could I make a bit array suitable for this string array? And even x[i].bit[depth] how can I implement this?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

国粹 2024-12-17 00:24:27

字符数组（或任何其他类型）也是位数组 - 毕竟字符是由位组成的。因此，您不必创建单独的数组，只需找到一种访问数组中给定位的方法即可。为此，您必须使用一些位操作。您可以在此处找到一些如何完成此操作的示例：有没有更聪明的方法从位数组中提取？。

基本上，您首先必须找出所需位所在的字节，然后获取该特定位的值。一些事情：

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 不在数组之外），并与 x[i]。

Arrays of chars (or any other type, for that matter) are also arrays of bits - chars are made of bits, after all. So you don't have to create a separate array, you just have to find a way to access a given bit in the array. For that, you'll have to use some bit manipulations. You can find a few examples of how this could be done here: Any smarter way to extract from array of bits?.

Basically, you first have to figure out the byte the required bit is at, and then get that specific bit's value. Something along:

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

Now wrap this in a function (possibly with additional bound checks, to make sure the given required_bit is not outside of the array), and use with x[i].

回复收藏 0 原文

~没有更多了~