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已经消灭了。

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

另一种策略是为每个函数提出一系列单元测试，以隔离测试每个构建块。

Answer 2

我不喜欢让事情悬而未决。IDK 如果我与其他方法相比实际修改了核心功能。特别是弹出功能。但我想我会发布它以保持完整性。

void quicksort(NODE **top,NODE **last,int * size)
{
    if((*size)>3)
    {
        NODE *pivot = pop(last);
        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++;
            }
            else 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);
        if(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)
    {
        NODE *a=(*top);
        NODE *b=(*top)->next;
        if(a->value<b->value) { swap(&(a->value),&(b->value)); }
        //if((*top)->value<(*top)->next->value) swap(&((*top)->value),&((*top)->next->value));
    }
}