bsort例子从编程珍珠 [英] bsort example from programming pearls

问题描述

在编程Pearls中有一种算法，对不同长度的数组进行排序，但是按照它们长度的总和成比例地进行排序。例如，如果我们有一个记录数组 x [0 ... n-1] ，并且每个记录都有一个整数长度和指向数组的指针 bit [0 ... length-1] 。

代码实现方式如下：

  void bsort（l，u，depth）{
 if（l> = u）
 return; 
 for（i = 1; i <= u; i ++）{
 if（x [i] .length  swap（i，l ++） 
} 
 m = l; 
 for（int i = l; 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] 我如何实现这个？

解决方案

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

基本上，你首先必须找出需要的位所在的字节，然后得到特定位的值。

  char * array =the array; 
 int required_bit = 13; 
 int bit = required_bit& 0x7; //在其字节中获取位的偏移量
 int byte = required_bit>> 3; //获取位的字节
 int val =（array [byte]>> bit）& 0x1; //检查位是否为1 
  

现在将这个包装在一个函数以确保给定的 required_bit 不在数组之外），并使用 x [i] p>

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?

解决方案

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].

这篇关于bsort例子从编程珍珠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！