C语言实现广义快速排序的一个问题

s3fp2yjn  于 2023-03-17  发布在  其他
关注(0)|答案(2)|浏览(144)

我试图创建一个方法来模拟库中提供的qsort。但是,我注意到出现了一个bug,导致了void* pivot = calloc(1,width);行的分段错误。有人能帮我分析一下吗?

void MyQuickSort(void* ary,int nlem, unsigned int width,int (* pfCompare) (const void *, const void *)){
    if(nlem<=1){
        return;
    }else{
        int left = (int) ary;
        int right = (int) ary+(nlem-1)*width;
        void* pivot = calloc(1,width);
        memmove((void *)pivot,ary,width);
        left = NULLL;
        //NULLL is a macro constant here

        while(left!=right){
            // as (void*)left is NULL, check (void*)right
            if(left == NULLL){
                if(pfCompare(pivot,(void*)right)<=0){
                right -= width;
                //remain the current ele
                }else if(pfCompare(pivot,(void*)right)>0){
                    memmove((void *)left,(void *)right,width);
                    right = NULLL;
                    //move the ele in right to left
                }
            }else{
                if(pfCompare(pivot,(void*)left)>=0){
                left += width;
                //remain the current ele
                }else if(pfCompare(pivot,(void*)left)<0){
                    memmove((void *)right,(void *)left,width);
                    left = NULLL;
                    //move the ele in left to right
            }
        }
        memmove((void *)left,pivot,width);

        MyQuickSort(ary,(left-width-(int)ary)/width,width,pfCompare);
        MyQuickSort(right+width,nlem-((left-width-(int)ary)/width),width,pfCompare);

        free(pivot);

    }
}
}

代码和错误的分析;如果可能的话修复错误;一些解释

fzwojiic

fzwojiic1#

基本上,错误从第一行开始:

  1. int left = (int) ary;-将指针转换为int并存储在int中。它没有任何意义
  2. int right = (int) ary+(nlem-1)*width;一样,甚至很难说出你的想法
  3. memmove((void *)pivot,ary,width);不会在没有原因的情况下进行强制转换。如果不是显式强制转换,则会避免p1和p2。不要使用强制转换来消除警告
  4. left = NULLL;什么是NULLL?如果是NULL,为什么要将其分配给int变量?
    等等等等。
    删除所有强制类型转换,阅读警告并重新考虑您所写的内容。
    我注意到出现了一个bug,导致void* pivot = calloc(1,width)行出现了分段错误;
    该行不调用未定义的行为,因此不太可能导致segfault
vfh0ocws

vfh0ocws2#

谢谢你,我刚刚修改了我的前一个,现在它的工作。我不应该随意使用整型为ary做偏移,这可能很容易导致错误。相反,我用一些char*指针,更兼容取代它。
以下是我修订版本的一部分:

char *left = (char *)ary;
        char *right = (char *)ary + (nlem - 1) * width;
        void *pivot = calloc(1, width);
        memmove(pivot, ary, width);
        int leftF = NUL;
        int rightF = NUL;

这里的NUL定义为模拟条件检查标志的宏常量,当然其他对应部分也做了修正。

相关问题