时间戳

首页 > 解决方案 > 在c中使用通用快速排序对char**数组进行排序

arrays - 在c中使用通用快速排序对char**数组进行排序

问题描述

我目前正在对我制作的通用快速排序进行单元测试，我将在下面发布代码，以及我正在使用的比较方法以及我正在运行以测试它的代码。
我发现的问题是数组实际上没有被排序。断言失败，如果我在排序后尝试打印数组，它只会按预定顺序打印值。
我尝试对 int 和 float 值的算法进行单元测试，它的排序很好。
我相信问题可能在于我可能没有正确转换 void 指针，导致未定义的行为

void quicksort(void* pointer, int size, int start, int end, int (*compare)(void*,void*)){
    if(end > start){
        int index = partition(pointer, size, start, end,compare);
        quicksort(pointer,size,start,index-1,compare);
        quicksort(pointer,size,index+1,end,compare);
    }
}

int partition(void * pointer, int size, int start, int end, int (*compare)(void*,void*)){
    int beginning = start + 1;
    int ending = end;
    while(beginning <= ending){
        if(compare(&pointer[beginning*size],&pointer[start*size]) >= 0){
            beginning++;
        }
        else{
            if(compare(&pointer[ending*size],&pointer[start*size]) == -1){
                ending--;
            }
            else{
                swap(&pointer[beginning*size],&pointer[ending*size],size);
                beginning++;
                ending--;
            } 
        }
    }
    swap(&pointer[start*size],&pointer[ending*size],size);
    return ending;
}

void swap(void* datablocka, void* datablockb, size_t elem_size){
    char temp;
    char *chara = datablocka;
    char *charb = datablockb;
    while(elem_size--){
        temp = chara[elem_size];
        chara[elem_size] = charb[elem_size];
        charb[elem_size] = temp;
    }
}

int compare_string(void* first, void* second){
    char * a = first;
    char * b = second;
    int compare = strcmp(a,b);
    if (compare < 0) return 1;
    else if(compare == 0) return 0;
    else return -1;
}

void quicksort_string_utest() {
  char* a[] = {"a","aaa","abba","mime","pippo","cacciatorpediniere"};
  char* b[] = {"a","aaa","abba","cacciatorpediniere","mime","pippo"};
  int end = (sizeof(a)/sizeof(a[0]))-1;
  quicksort(a, sizeof(a[0]), 0, end, compare_string );
  for(int i = 0; i < 6; i++){
    assert(strcmp(a[i],b[i]) == 0);
  }
}

我真的很感谢你的帮助，因为你可以看到我无法解决这个问题

标签： arraysccastingquicksortgeneric-programming

解决方案

在这个程序中，传递给比较函数compare_string的是指向数组元素的指针。

在这种情况下，数组的元素是char*并且传递的是指向 的指针char*。

因此，要获取指向字符串的指针，您必须取消引用传递的指针。

尝试这个：

int compare_string(void* first, void* second){
    char ** a = first;
    char ** b = second;
    int compare = strcmp(*a,*b);
    if (compare < 0) return 1;
    else if(compare == 0) return 0;
    else return -1;
}

推荐阅读