c - 在 C : swapping pointers leads to unexpected results 中排序

Question

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

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

Answer 1

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

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

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