在递归插入排序中获取分段错误

我试图编写插入排序的递归代码，但我遇到了分段错误。请帮我解决这个问题。

#include <bits/stdc++.h>
using namespace std;
void insert(vector<int> &v,int temp){
if(v.size()==0||v[v.size()-1]<=temp){
v.push_back(temp);
return;
}
int val = v[v.size()-1];
v.pop_back();
insert(v, temp);
v.push_back(val);
return;
}
void sort(vector<int> &v){
if(v.size()==1) return;
int temp = v[v.size()-1];
v.pop_back();
sort(v);
insert(v,temp);
}
int main() {
int n;
vector<int> v;
cin>>n;
for(int i=0;i<n;i++)
cin>>v[i];
sort(v);
for(int i=0;i<n;i++)
cout<<v[i];
return 0;
}

这会创建一个空vector<int>：

vector<int> v;

访问其中的任何元素都会使您的程序具有未定义的行为。您可以通过向构造函数提供n或在创建空vector<int>后调用resize(n)来创建具有所需元素数的vector<int>。另一种选择是将其创建为空，然后将元素push_back()或emplace_back其中，在这种情况下，它将动态增长。

使用正确数量的元素创建它的示例：

int main() {
int n;
// verify that extraction of `n` succeeded and that `n > 0`:
if(!(std::cin >> n && n > 0)) {
std::cerr << "errorn";
return 1;
}
// create the vector with the correct number of elements
std::vector<int> v(static_cast<size_t>(n));
// use a range-based for loop to get a reference to each element:
for(int& val : v)
std::cin >> val;    // extract into the referenced `int`
sort(v);
// here you can use a range-based for loop to get a copy of each element
// (which is cheap in this case, since they are `int`s):
for(int val : v)
std::cout << val << ' ';
std::cout << 'n';
}

演示

笔记：

#include <bits/stdc++.h>- 切勿包含此非标准标头。包括标准标头，如iostream和vector
using namespace std;- 不要这样做。尤其是当您为sort等功能提供重载时，如果您包含bits/stdc++.h并执行using namespace std;，这些功能将可用。

问题是向量v是空的(意味着它的大小0)，并且您正在尝试访问其元素，从而导致未定义的行为。

vector<int> v; //this creates an empty vector named v
cin>>n;
for(int i=0;i<n;i++)
cin>>v[i]; //this leads to undefined behavior

在上面的代码片段中，向量v是一个空向量，这意味着它没有元素。因此，表达式cin >> v[i]会导致未定义的行为，因为您正在访问向量第i个索引处的元素，但向量内没有元素可供访问。

未定义的行为意味着可能发生任何¹的情况，包括但不限于提供预期输出的程序。但永远不要依赖(或基于)具有未定义行为的程序的输出得出结论。

因此，您看到(可能看到)的输出是未定义行为的结果。正如我所说，不要依赖具有UB的程序的输出。程序可能会崩溃(这就是您的情况)。

因此，使程序正确的第一步是删除UB。然后，只有这样，您才能开始推理程序的输出。

溶液

要解决此问题，您可以在创建矢量时指定矢量的大小，如下所示：

int n;
cin>>n;
vector<int> v(n);//create vector of size n

^{¹有关未定义行为的技术上更准确的定义，请参阅此处提到的内容：对程序的行为没有限制。}

你声明了一个空向量

int n;
vector<int> v;

所以在这个 for 循环中使用下标运算符

for(int i=0;i<n;i++)
cin>>v[i];

调用未定义的行为。

相反，您可以在输入n的值后最初声明带有n元素的向量，例如

int n;
cin>>n;
vector<int> v( n );
for(int i=0;i<n;i++)
cin>>v[i];

或者，您可以在已知n的值后调整矢量的大小，例如

int n;
vector<int> v;
cin>>n;
v.resize( n );
for(int i=0;i<n;i++)
cin>>v[i];

最好将变量 n 声明为具有无符号整数类型，例如

size_t n;

您可以使用基于范围的 for 循环代替 for 循环

size_t n = 0;
cin>>n;
std::vector<int> v( n );
for ( auto &item : v ) std;:cin >> item;

在函数sort中，您需要至少通过以下方式更改 if 语句中的条件

void sort( std::vector<int> &v ){
if ( v.size() < 2 ) return;
//...

因为通常用户可以传递一个空向量。

您可以使用成员函数back，而不是使用这样的表达式v[v.size()-1]。例如

int temp = v.back();

这使得代码更具可读性。

我将按以下方式定义函数，而无需冗余的返回语句

void insert( std::vector<int> &v, int value )
{
if (v.empty() || not( value < v.back() ) )
{
v.push_back( value );
}
else
{
int tmp = v.back();
v.pop_back();
insert( v, value );
v.push_back( tmp );
}
}
void sort( std::vector<int> &v )
{
if (not ( v.size() < 2 ))
{
int last = v.back();
v.pop_back();
sort( v );
insert( v, last );
}
}

这是一个演示程序。

#include <iostream>
#include <vector>
void insert( std::vector<int> &v, int value )
{
if (v.empty() || not( value < v.back() ) )
{
v.push_back( value );
}
else
{
int tmp = v.back();
v.pop_back();
insert( v, value );
v.push_back( tmp );
}
}
void sort( std::vector<int> &v )
{
if (not ( v.size() < 2 ))
{
int last = v.back();
v.pop_back();
sort( v );
insert( v, last );
}
}
int main()
{
std::vector<int> v = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
sort( v );
for (const auto &item : v)
{
std::cout << item << ' ';
}
std::cout << 'n';
}

程序输出为

0 1 2 3 4 5 6 7 8 9

建议：尽量避免使用指令

using namespace std;

这可能是名称冲突的原因，有时会使代码不清楚，即是否使用了标准C++函数或用户定义的函数。

溶液

相关内容

最新更新

热门标签：