7

在程序开始时，我为一个字符指针数组分配内存：

char **buffer = calloc( 20, sizeof(char *) );

然后用户最多可以输入 20 个单词：

buffer[i] = calloc( 40, sizeof(char) );
fgets( buffer[i], 40, stdin )`

之后我想对这个数组进行排序。如果我按如下方式使用我的交换功能，它会按预期工作：

void swap(char *args1, char *args2) {
    char tmp[40];
    strcpy( tmp, args1 );
    strcpy( args1, args2 );
    strcpy( args2, tmp );
}

void sort( char **args, int count ) {
    ...
    swap( args[i], args[j] );
    ...
}

经过思考后，我注意到这是对 CPU 的浪费，因为我所要做的实际上是将指针重定向到相应的字符串。所以我重写了我的交换函数：

void swap(char **args1, char **args2) {
    char *tmp = *args1;
    *args1 = *args2;
    *args2 = tmp;
}

void sort( char **args, int count ) {
    ...
    swap( &args[i], &args[j] );
    ...
}

但是，这根本行不通，结果非常出乎意料，我不知道为什么（我尝试了几次 printf 调用等等）......我的理解是指针只是被重定向并因此交换，假设内存看起来像这样：

(begin of char**):
100: *160
108: *200
116: *240
124: *280
...
(begin of char*):
160: Hello!\0
200: World!\0
...

我的想法是更改指针而不是数组以减少 CPU 工作量（这里：将 100 中的指针与 108 中的指针交换）：

(begin of char**):
100: *200
108: *160
116: *240
124: *280
...
(begin of char*):
160: Hello!\0
200: World!\0
...

我试图尽可能彻底地解释这一点，如果解释太多，我很抱歉。如果有人能让我深入了解这一点并提供帮助，我将非常高兴！

完整的代码（带有工作的 strcpy）可以在这里找到：http: //pastie.org/5361481

4

2 回答 2

5

您的排序函数最终应该如下所示：

void sort(char ** args, const int start, const int end) {
        char **pivot = &args[end];
        int i = start-1, j = start;
        while( j < end ) {
                int cmp = strcmp( *pivot, args[j] );
                if( cmp > 0 )
                        swap( &args[++i], &args[j] );
                j++;
        }
        swap( &args[++i], pivot );
        if( start + 1 < i )
                sort( args, start, i - 1 );
        if( end - 1 > i )
                sort( args, i + 1, end );
}

我怀疑您没有将枢轴设为 a char**，而是将其保留为 a char*。如果你这样做，那么每当你进行交换时，你实际上并没有交换数组中的两个元素，而是用一个局部变量交换数组的一个元素。枢轴变量最终指向不同的字符串，而不是最后一个数组成员指向不同的字符串。

于 2012-11-11T17:56:10.353 回答
3 
    char *pivot = args[end];
...
    swap( &args[++i], &pivot );

这是你的问题。您不想将指针与局部变量交换，而是与数组中的实际枢轴元素（即args+end）交换。这里的工作示例

于 2012-11-11T18:05:43.753 回答