时间戳

首页 > 解决方案 > C 归并排序算法中的分段错误

c - C 归并排序算法中的分段错误

问题描述

我试图在 C 中一个相当大的双向链表的键上合并排序 a，它有大约 100,000 个元素。以下是 DLL 元素的结构：

struct Pore {
    int ns;    /* voxel number */
    int radius;  /* effective radius of porosity surrounding a pore */
    struct Pore *next;
    struct Pore *prev;
};

在搜索了算法之后，我发现最常用的一个包括三个函数：mergeSort、merge和split。我将它们包括在这里...请原谅函数printf中的多个 s，merge因为我一直在尝试调试在 4097592-nd 递归进入merge函数时发生的分段错误。 Recur01并且Recur02是我为帮助调试而定义的全局变量。


void mergeSort(struct Pore **head)
{
    Recur01++;

    /* Base case: 0 or 1 pore */
    if ((*head) == NULL) {
        printf("\nEnter mergeSort %ld, list head is NULL ",Recur01);
        fflush(stdout);
        return;
    }
    if ((*head)->next == NULL) {
        printf("\nEnter mergeSort %ld, list head next is NULL ",Recur01);
        fflush(stdout);
        return;
    }

    printf("\nEnter mergeSort %ld",Recur01);
    fflush(stdout);
    /* Split head into 'a' and 'b' sublists */
    struct Pore *a = *head;
    struct Pore *b = NULL;
    split(*head, &a, &b);

    /* Recursively sort the sublists */
    mergeSort(&a);
    mergeSort(&b);

    /* Merge the two sorted halves */
    *head = merge(a,b);

    printf("\nExit mergeSort %ld",Recur01);
    fflush(stdout);
    return;
}

void split(struct Pore *head, struct Pore **a, struct Pore **b)
{
    int count = 0;
    int lngth = 1;
    struct Pore *slow = head;
    struct Pore *fast = head->next;
    struct Pore *temp;

    temp = head;
    while (temp->next != NULL) {
        lngth++;
        /*
        printf("\n    Length = %d",lngth);
        fflush(stdout);
        */
        if (temp->next) {
            temp = temp->next;
        }
    }

    while (fast != NULL) {
        printf("\nCount = %d",count);
        fflush(stdout);
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
        count++;
    }

    printf("\nDone with while loop, final count = %d",count);
    fflush(stdout);

    *b = slow->next;
    slow->next = NULL;
    printf("\nExit split");
    fflush(stdout);
    return;
}

struct Pore *merge(struct Pore *a, struct Pore *b)
{
    Recur02++;

    if (Recur02 >= 4097591) {
        printf("\nEnter merge %ld",Recur02);
        fflush(stdout);
    }

    /** If first linked list is empty, return the second list */

    /* Base cases */
    if (a == NULL) return b;

    if (b == NULL) return a;

    if (Recur02 >= 4097591) {
        printf("\n    Made it 01");
        fflush(stdout);
    }

    /* Pick the larger key */

    if (a->radius > b->radius) {
        if (Recur02 >= 4097591) {
            printf("\n    Made it 02 a is bigger, Recur02 = %ld",Recur02);
            fflush(stdout);
            printf("      a->next->ns = %d",a->next->ns);
            fflush(stdout);
            printf("      b->ns = %d",b->ns);
            fflush(stdout);
        }
        a->next = merge(a->next,b);
        a->next->prev = a;
        a->prev = NULL;
        if (Recur02 >= 4097591) {
            printf("\nExit merge a %ld",Recur02);
            fflush(stdout);
        }
        return a;
    } else {
        if (Recur02 >= 4097591) {
            printf("\n    Made it 02 b is bigger, Recur02 = %ld",Recur02);
            fflush(stdout);
            printf("      b->next->ns = %d",b->next->ns);
            fflush(stdout);
            printf("      a->ns = %d",a->ns);
            fflush(stdout);
        }
        b->next = merge(a,b->next);
        b->next->prev = b;
        b->prev = NULL;
        if (Recur02 >= 4097591) {
            printf("\nExit merge b %ld",Recur02);
            fflush(stdout);
        }
        return b;
    }
}

就像我说的那样，运行代码可以正常工作，直到我进入merge. 我printf在函数调用之前放了一个权利，在进入函数后立即放另一个。我也是printf函数参数中元素的键，它们看起来也不错。我不知道还有什么可以尝试弄清楚这一点。下面是输出的最后几十行：

Exit mergeSort 529095
Exit mergeSort 529095
Enter merge 4097591
    Made it 01
    Made it 02 a is bigger, Recur02 = 4097591      a->next->ns = 156692      b->ns = 20
Enter merge 4097591
Enter merge 4097592
    Made it 01
    Made it 02 a is bigger, Recur02 = 4097592      a->next->ns = 156693      b->ns = 20

这是在分段错误之前从缓冲区中刷新的最后一行。我已经没有关于如何调试它的想法，因此将不胜感激任何建议。

标签： csegmentation-faultmergesort

解决方案

分段错误是由于使用递归合并，该合并为每个合并的节点调用自身。主代码自上而下是可以的，因为这将具有 O(log2(n)) 的堆栈空间复杂度，但合并函数需要是迭代的。

最常用的

std::list::sort() 的原始实现是链表的自下而上合并排序，它使用列表的小数组（25 到 32）（或指向列表第一个节点的指针或迭代器）。

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

可能 std::list::sort 的大多数实现都是自下而上的，直到 Visual Studio 2015，它从使用列表数组切换到使用迭代器（以避免没有默认分配器等问题并提供异常安全）。这出现在之前的线程中，最初我只是接受了更改，假设切换到迭代器需要自上而下的更改。这个问题后来又出现了，所以我调查了一下，确定没有必要切换到自上而下的归并排序。我的主要遗憾是没有从最初的问题中调查这一点。我确实更新了我的答案以显示一个基于独立迭代器的自下而上合并排序，以及对 VS2019 包含文件中的 std::list::sort 的替换。

`std::list<>::sort()` - 为什么突然切换到自上而下的策略？

在大多数情况下，只要有足够的内存，将列表复制到数组（或向量）、对数组进行排序并创建新的排序列表会更快。如果大型链表中的节点是随机分散的，则几乎每个访问的节点都会导致缓存未命中。通过将列表移动到数组，通过合并排序对数组中的运行进行顺序访问对缓存更加友好。这就是 Java 对链表的本机排序的实现方式，尽管部分原因是由于对包括链表在内的多种容器类型使用了通用的 collections.sort()，而 C++ 标准库 std::list 是一个独立的容器使用它的列表特定成员函数键入。

推荐阅读