c - 双链表上的快速排序导致错误指针？

Question

我写这篇文章是为了理解各种排序算法并判断在不同情况下哪种算法最有效。因为我从来没有真正学过它们:(

这是我对维基百科伪代码的解释，添加了额外的“相等”列表以提高速度(希望如此)。以及其他一些小的补充。一旦排序接近尾声(剩余 2 或 3 个节点)，我的程序就会崩溃。该程序按降序排序。

GDB 在 while 循环中指示其顶部变量的错误指针。显然它在列表末尾没有空指针。我怀疑快速列表功能很好，但它是导致问题的支持功能之一。我需要帮助来发现我做错了什么

快速排序:

void quicksort(NODE **top,NODE **last,int * size)
{
    if((*size)>3)
    {
        NODE *pivot = pop(last);
        *last=0;
        NODE *greater_node=0;int greater=0; NODE * glast=0;
        NODE *equal_node=0;int equal=0;
        NODE *less_node=0;int less=0; NODE * llast=0;
        int pivot_value=pivot->value;
        int value_at=0;
        while(*top)
        {
            value_at=(*top)->value;
            if(value_at>pivot_value)
            {
                push2(&greater_node,pop(top));
                if(!greater) { glast=greater_node; }
                greater++;
            }
            if(value_at<pivot_value)
            {
                push2(&less_node,pop(top));
                if(!less) { llast=less_node; }
                less++;
            }
            else
            {
                push2(&equal_node,pop(top));
                equal++;
            }
        }
        quicksort(&greater_node,&glast,&greater);
        quicksort(&less_node,&llast,&less);
        cat(&equal_node,less_node);
            cat(&pivot,equal_node);
        cat(&greater_node,pivot);
            *top=greater_node;
        *size = greater+less+equal+1;
    }
    else if((*size)==3)
    {
        NODE *a=(*top);
        NODE *b=(*top)->next;
        NODE *c=(*top)->next->next;
        if(a->value<b->value) { swap(&(a->value),&(b->value)); }
        if(b->value<c->value) { swap(&(b->value),&(c->value)); }
        if(a->value<b->value) { swap(&(a->value),&(b->value)); }
    }
    else if((*size)==2)
    {
            if((*top)->value<(*top)->next->value) swap(&((*top)->value),&((*top)->next->value));
    }
}

Answer 1

我没有深入了解快速排序函数本身，但您的 pop() 看起来很可疑。具体来说，如果 *top 指向第一个元素，则

        (*top)=(*top)->next;

在你有机会用它做任何有用的事情之前，它已经消灭了 *top。

我的总体建议是找到代码出现故障的最简单输入，然后在调试器中单步调试程序，观察发生了什么。这应该使您能够查明事情开始偏离计划的确切时刻。

另一种策略是为每个功能提出一系列单元测试，以单独测试每个构建 block 。