1

Programming Pearls には、さまざまな長さの配列をソートするアルゴリズムがありますが、それらの長さの合計に比例して時間でソートします。たとえば、レコード arrayx[0...n-1]があり、各レコードに整数の長さと array へのポインタがあるとします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 の配列 (またはその他のタイプ) もビットの配列です。結局のところ、char はビットで構成されています。したがって、別の配列を作成する必要はありません。配列内の特定のビットにアクセスする方法を見つけるだけで済みます。そのためには、いくつかのビット操作を使用する必要があります。これを行う方法のいくつかの例をここで見つけることができます:ビット配列から抽出するよりスマートな方法はありますか? .

基本的に、最初に必要なビットがあるバイトを把握し、次にその特定のビットの値を取得する必要があります。何かに沿って：

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 に答える