在C中排序:交换指针会导致意外结果

Question

在程序开始时,我为一个char指针数组分配内存:

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*.如果你这样做,那么每当你进行交换时,你实际上并没有交换数组中的两个元素,而是使用局部变量交换数组的一个元素.pivot变量最终指向不同的字符串,而不是指向不同字符串的最后一个数组成员.