1

我遇到了以下问题：

int sort_compare(const void *x, const void *y) {
    const int *xi = *(const int **) x;
    const int *yi = *(const int **) y;

    for (int i = 0; i < block_size; i++) {
        comp_x[i] = block[(*xi + i) % block_size];
        comp_y[i] = block[(*yi + i) % block_size];
    }

    return memcmp(comp_x, comp_y, block_size);
}

void sort() {
    for (int i = 0; i < block_size; i++) {
        printf("%d,", to_sort[i]);
    }
    puts("");
    qsort(to_sort, block_size, sizeof (int), sort_compare);
    for (int i = 0; i < block_size; i++) {
        printf("%d,", to_sort[i]);
    }
    puts("");
}

values:
    block_size = 5;
    block = "jkldj";
    comp_x, compy_y and to_sort are well allocated

output:
    0,1,2,3,4,
    3,0,1785357420,1,1684826986,

to_sort 包含来自（圆形）字符串的第一个字母，例如

qwer
werq
erqw
rqwe

, 表示为 (0,1,2,3) 需要排序为

erqw
rqwe
qwer
werq

，表示为 (2,3,0,1)。我似乎得到了非常大的数字，这是为什么呢？

提前致谢！

4

3 回答 3

2

传入比较器的x和是指向数组元素的指针。y您的数组元素是ints，因此要获取int值，您需要将void指针转换为int指针并取消引用。你的代码中有一个额外的间接层，它应该看起来像这样：

int xi = *(const int *) x;
int yi = *(const int *) y;

然后在进行数据比较时直接使用xiand而不是and 。yi*xi*yi

作为一种优化，无需将数据复制到单独的数组中，然后再复制memcmp它们——您可以在循环中自己比较它们：

for (int i = 0; i < block_size; i++) {
    char data_x = block[(xi + i) % block_size];
    char data_y = block[(yi + i) % block_size];
    if (data_x != data_y)
        return data_x - data_y;
}

return 0;

作为进一步的优化，如果您将block数组中的数据加倍（例如，使其具有"qwerqwer"而不是只是"qwer"），您可以在一次调用中进行比较memcmp，因为您不再需要处理环绕。 进行了高度优化，因此如果您有大量数据，使用手写的 for 循环memcmp会快得多。memcmp

于 2012-10-19T19:13:56.577 回答
1

当你初始化

const int *xi = *(const int **) x;
const int *yi = *(const int **) y;

元素的地址to_sort被解释为 a const int**，然后取消引用以给出xiand的值yi。这将（如果s 大于s to_sort，则可能超出）中的值解释为指针。int*int

您应该只转换void*s：

const int *xi = (const int *) x;
const int *yi = (const int *) y;
于 2012-10-19T18:58:41.467 回答
1

qsort() 通过给它一个 N 项的线性列表来唱歌，其中任何给定的 item(n) 地址都可以使用基于地址 + 每个“item”的大小来计算。所以从一些简单的东西开始，我所说的简单是指一个指针列表。

首先，可以通过简单地将副本拼接到原始缓冲区来模拟缓冲区的循环性（理想情况下少一个字符，但我不会对一个字节争论不休）。IE

"qwer" ==> "qwerqwer"

这可以通过以下方式完成：

char *buff = malloc(2 * blocksize);
memcpy(buff, to_sort, blocksize);
memcpy(buff+blocksize, to_sort, blocksize);

现在你有偏移量 0..(blocksize-1)，每个都是一个块大小的字符，可以在没有任何特殊指针数学的情况下相互比较。

接下来，构建要实际排序的指针列表，在这种情况下，

char** ptrs = malloc(sizeof(char*) * blocksize); 
for (i=0;i<blocksize;i++)
    ptrs[i] = buff+i;

接下来，一个比较两个“项目”的函数。我们通过地址传递给我们的项目是指向字符串的指针。同样，过去左右的地址是内存位置，我们将找到两个 char *。地址本身不是char *：

int block_compare(const void *left, const void *right)
{
    // memcmp would work for most platforms, but not all, so...
    return strncmp(*(char **)left, *(char **)right, blocksize);
}

最后，将其发送到 qsort() ，如下所示：

qsort(ptrs, blocksize, sizeof(char*), block_compare);

最终输出将是一个块大小的指针列表，指向制造的循环缓冲区，每个指针都引用一个块大小的块。上述所有内容的全文如下：

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>

size_t blocksize = 0;

int block_compare(const void *left, const void *right)
{
    // memcmp would work for most platforms, but not all, so...
    return strncmp(*(char **)left, *(char **)right, blocksize);
}


int main(int argc, char* argv[])
{
    char to_sort[] = "qwer";
    size_t i = 0;

    // set blockize
    blocksize = strlen(to_sort);

    char *buff = malloc(2 * blocksize);
    memcpy(buff, to_sort, blocksize);
    memcpy(buff+blocksize, to_sort, blocksize);

    char ** ptrs = malloc(blocksize * sizeof(char*));
    for (i=0;i<blocksize;++i)
        ptrs[i] = buff+i;

    // now send the pointer list to qsort()
    qsort(ptrs, blocksize, sizeof(*ptrs), block_compare);

    // ptrs is sorted. do with it what you will.
    for (i=0;i<blocksize;i++)
    {
        fwrite(ptrs[i], sizeof(char), blocksize, stdout);
        fwrite("\n", sizeof(char), 1, stdout);
    }
    fflush(stdout);

    free(ptrs);
    free(buff);

    return EXIT_SUCCESS;
}

使用“qwer”会产生：

erqw
qwer
rqwe
werq

另一个示例，使用“asubstantiallylongerstringtest”

allylongerstringtestasubstanti
antiallylongerstringtestasubst
asubstantiallylongerstringtest
bstantiallylongerstringtestasu
erstringtestasubstantiallylong
estasubstantiallylongerstringt
gerstringtestasubstantiallylon
gtestasubstantiallylongerstrin
iallylongerstringtestasubstant
ingtestasubstantiallylongerstr
llylongerstringtestasubstantia
longerstringtestasubstantially
lylongerstringtestasubstantial
ngerstringtestasubstantiallylo
ngtestasubstantiallylongerstri
ntiallylongerstringtestasubsta
ongerstringtestasubstantiallyl
ringtestasubstantiallylongerst
rstringtestasubstantiallylonge
stantiallylongerstringtestasub
stasubstantiallylongerstringte
stringtestasubstantiallylonger
substantiallylongerstringtesta
tantiallylongerstringtestasubs
tasubstantiallylongerstringtes
testasubstantiallylongerstring
tiallylongerstringtestasubstan
tringtestasubstantiallylongers
ubstantiallylongerstringtestas
ylongerstringtestasubstantiall

伙计，我希望这就是你要找的。（哇）。

于 2012-10-19T19:57:13.017 回答