c - 使用快速排序对字符数组进行排序

Question

我想对字符数组进行排序。然而，每次我运行该程序时，它在到达 QuickSort 函数时都会崩溃。可能是什么问题导致了这样的影响？我正在使用指针数组来对数组进行排序。

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

void print(char** A, int n){
    int i = 0;
    for (i = 0; i < n; i++){
        printf("%s\n", A[i]);
    }
}

int Partition(char** A, int p, int r){
    char *temp = (char*)malloc(sizeof(char)*30);
    char *x = (char*)malloc(sizeof(char)*30);
    x = A[r];
    int i = p - 1;
    int j = 0;
    for(j = p; j<=r; j++){
        if(strcmp(A[j],x) <=0){
            i=i+1;
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            }
        }
    if(i<r){
         return i;
    }else{
        return i-1;
    }

    free(temp);
    free(x);

}

void QuickSort(char** A, int p, int r){
    if(p<r){
        int q = Partition(A, p, r);
        QuickSort(A, p, q);
        QuickSort(A, q+1, r);
    }
}


int main(){
    int i = 0;

    char **A = (char**) malloc(12*sizeof(char*));

    for(i = 0; i < 12; i++){
        A[i] = (char*) malloc(sizeof(char)*30);
    }

    strcpy(A[0], "imarr");
    strcpy(A[1], "ikak");
    strcpy(A[2], "agh");
    strcpy(A[3], "ogss");
    strcpy(A[4], "alllll");
    strcpy(A[5], "ackm");
    strcpy(A[6], "plccc");
    strcpy(A[7], "strrr");
    strcpy(A[8], "raat");
    strcpy(A[9], "omhhh");
    strcpy(A[10], "rrors");
    strcpy(A[11], "basds");

    QuickSort(A, 0, 12);

    print(A, 12);

    free(A);

    return 0;
}

Answer 1

替换

QuickSort(A, 0, 12);

与

QuickSort(A, 0, 11);

编译运行一下，然后再思考。我想你应该足够聪明，自己弄清楚为什么 12 不正确而 11 可以。

顺便说一句，我认为这个问题确实应该去https://codereview.stackexchange.com/

已编辑:抱歉，我一开始没有注意到这个问题:

在Partition中，这三行很奇怪:

char *x = (char*)malloc(sizeof(char)*30);
x = A[r];
......
free(x);

没有问题(意味着没有崩溃，但实际上存在内存泄漏，因为分配的 x 没有被释放，而且 A 也被错误地释放)在这种情况下，因为 A 数组也是由 malloc 分配的。
此外，当您在交换时使用 temp 作为保存 char* 值的变量时，无需分配内存。查看编辑后的代码:

int Partition(char** A, int p, int r){
    char *temp;
    char *x = A[r];
    int i = p - 1;
    int j = 0;
    for(j = p; j<=r; j++){
        if(strcmp(A[j],x) <=0){
            i=i+1;
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            }
        }
    if(i<r){
         return i;
    }else{
        return i-1;
    }
}