c - 将数组传递给函数时出现段错误

Question

我试图使用合并排序来计算数组中反转的数量。但是当我将数组传递给函数时，我遇到了段错误。

#include <stdio.h>
#include <stdlib.h>

long long countInversionsBetween(long a[], long p, long q, long r)
{
    long n1 = q - p + 1;
    long* lt = malloc((n1 + 1) * sizeof(*lt));
    long iii;
    for (iii = 0; iii < n1; iii += 1)
    {
        lt[iii] = a[p + iii];
    }
    long n2 = r - q;
    long* rt = malloc((n2 + 1) * sizeof(*rt));
    for (iii = 0; iii < n2; iii += 1)
    {
        rt[iii] = a[q + 1 + iii];
    }
    rt[n2] = lt[n1] = 100000000;
    long long nInversionsBetween = 0;
    iii = 0;
    long jjj = 0;
    long kkk;
    for (kkk = p; kkk <= r; kkk += 1)
    {
        if (lt[iii] <= rt[jjj])
        {
            a[kkk] = lt[iii];
            iii++;
        }
        else
        {
            a[kkk] = rt[jjj];
            jjj++;
            nInversionsBetween++;
        }
    }
    free(lt);
    free(rt);
    return nInversionsBetween;
}

long long countInversionsWithin(long a[], long p, long r)
{
    if (p < r)
    {
        long q = (p + r) / 2;
        long long nInversionWithinL = countInversionsWithin(a, p, q);
        long long nInversionWithinR = countInversionsWithin(a, q, r);
        long long nInversionsBetween = countInversionsBetween(a, p, q, r);
        return nInversionWithinL + nInversionWithinR + nInversionsBetween;
    }
    else
    {
        return 0;
    }
}

int main()
{
    long long t;
    scanf("%lld", &t);
    getchar();
    long long iii;
    for (iii = 0; iii < t; iii += 1)
    {
        getchar();
        long n;
        scanf("%ld", &n);
        long* a = malloc(n * sizeof(*a));
        long jjj;
        for (jjj = 0; jjj < n; jjj += 1)
        {
            scanf("%ld", &a[jjj]);
        }
        printf("%lld\n", countInversionsWithin(a, 0, n - 1));
        free(a);
    }
    return 0;
}

当数组 a 传递给 main 中的函数 countInversionsWithin 时，会发生段错误。为什么我会遇到这个段错误？

Answer 1

您可能在这里遇到无限递归问题:

if (p < r)
    {
        long q = (p + r) / 2;
        long long nInversionWithinL = countInversionsWithin(a, p, q);
        long long nInversionWithinR = countInversionsWithin(a, q, r);

如果 p = 0 且 r = 1，则 q 等于 0，并且无限期地调用 countInversionsWithin(a, q, r) ，直到堆栈爆炸并且您在尝试写入 ro 页面时出现段错误。