我收到合并排序的分段错误
I am getting segmentation fault for merge sort
我编程已经有一段时间了。但是我对算法了解不多。现在我决定学习一些算法。我正在学习合并排序。我正在从 Coreman 书中学习。这是我写的代码。
#include <iostream>
#include <cstdio>
using namespace std;
int infinity = 1000;
void merge_sort(int A[],int p, int r);
void merge(int A[], int p, int q, int r);
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n;
cin >> n;
int A[n];
for(int i=0; i<n; ++i)
{
cin >> A[i];
}
merge_sort(A,0,n);
for(int i=0; i<n; ++i)
{
cout << A[i] << endl;
}
return 0;
}
void merge_sort(int A[],int p, int r)
{
if(p<r)
{
int q = (r-p)/2;
merge_sort(A,p,q);
merge_sort(A,q,r);
merge(A,p,q,r);
}
return;
}
void merge(int A[], int p, int q, int r)
{
int n1 = q-p;
int n2 = r-q;
int L[n1+1], R[n2+1];
for(int i=0; i<n1; ++i)
{
L[i] = A[p+i];
}
for(int i=0; i<n2; ++i)
{
R[i] = A[q+i];
}
L[n1] = R[n2] = infinity;
for(int i=0; i<=n1; ++i)
{
cout << L[i] << endl;
}
for(int j=0; j<=n2; ++j)
{
cout << R[j] << endl;
}
for(int i=0, j=0, k=p; k<r; ++k)
{
if(L[i] <= R[j])
{
A[k] = L[i];
++i;
}
else
{
A[k] = R[j];
++j;
}
}
return;
}
但是我遇到了分段错误。我做错了什么?
这将是继续下去的一种方式Linux:
- 使用调试信息编译您的程序(
g++ -g merger_sort.cpp -o merger_sort
)
- 在调试器中加载它:
>>> gdb merge_sort
- 运行它:
(gdb) run
.
你会看到:
Program received signal SIGSEGV, Segmentation fault.
0x0000000000400b1e in merge_sort (A=0x7ffffffddda0, p=0, r=1)
- 看代码中的位置:
(gdb) layout src
- 查看回溯:
(gdb) bt
它很长...所以你有一个堆栈溢出:)使用调试器也看看为什么。
我编程已经有一段时间了。但是我对算法了解不多。现在我决定学习一些算法。我正在学习合并排序。我正在从 Coreman 书中学习。这是我写的代码。
#include <iostream>
#include <cstdio>
using namespace std;
int infinity = 1000;
void merge_sort(int A[],int p, int r);
void merge(int A[], int p, int q, int r);
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n;
cin >> n;
int A[n];
for(int i=0; i<n; ++i)
{
cin >> A[i];
}
merge_sort(A,0,n);
for(int i=0; i<n; ++i)
{
cout << A[i] << endl;
}
return 0;
}
void merge_sort(int A[],int p, int r)
{
if(p<r)
{
int q = (r-p)/2;
merge_sort(A,p,q);
merge_sort(A,q,r);
merge(A,p,q,r);
}
return;
}
void merge(int A[], int p, int q, int r)
{
int n1 = q-p;
int n2 = r-q;
int L[n1+1], R[n2+1];
for(int i=0; i<n1; ++i)
{
L[i] = A[p+i];
}
for(int i=0; i<n2; ++i)
{
R[i] = A[q+i];
}
L[n1] = R[n2] = infinity;
for(int i=0; i<=n1; ++i)
{
cout << L[i] << endl;
}
for(int j=0; j<=n2; ++j)
{
cout << R[j] << endl;
}
for(int i=0, j=0, k=p; k<r; ++k)
{
if(L[i] <= R[j])
{
A[k] = L[i];
++i;
}
else
{
A[k] = R[j];
++j;
}
}
return;
}
但是我遇到了分段错误。我做错了什么?
这将是继续下去的一种方式Linux:
- 使用调试信息编译您的程序(
g++ -g merger_sort.cpp -o merger_sort
) - 在调试器中加载它:
>>> gdb merge_sort
- 运行它:
(gdb) run
.
你会看到:
Program received signal SIGSEGV, Segmentation fault.
0x0000000000400b1e in merge_sort (A=0x7ffffffddda0, p=0, r=1)
- 看代码中的位置:
(gdb) layout src
- 查看回溯:
(gdb) bt
它很长...所以你有一个堆栈溢出:)使用调试器也看看为什么。