我试图使用合并排序来计算数组中的反转次数。但是在将数组传递给函数时出现分段错误。
#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函数时,将发生分段错误。为什么会出现此细分错误?
您可能在这里遇到无限递归问题:
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-page时遇到段错误。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句