Ошибка сегментации в коде сортировки слиянием - PullRequest
Новая
       9

Ошибка сегментации в коде сортировки слиянием

0 голосов
/ 08 мая 2018

Я написал эту программу сортировки слиянием на c ++, но после запуска кода я получаю сообщение об ошибке «Ошибка сегментации (сброшено ядро)». Даже если нет ошибки компиляции. Подскажите, пожалуйста, в чем я ошибаюсь? Принимая входные данные в массиве, он показывает эту ошибку. Если я изменю его на push_back, то с вводом все в порядке, но позже в функции слияния будет показана та же ошибка. 

//merging 2 sorted subarrays.
#include <iostream>
#include <vector>
using namespace std;

void merge(vector <int> &a,vector <int> &b,vector <int> &c)
{
    int i=0,j=0,k=0,bL=b.size(),cL=c.size();
    while(i<bL && j<cL)
    {
        if(b[i]<c[j])
        {
            a[k]=b[i];
            i++;k++;
        }
        else
        {
            a[k]=c[j];
            j++;k++;
        }
    }
    while(i<bL)
    {
        a[k]=b[i];
        i++;k++;
    }
    while(j<cL)
    {
        a[k]=c[j];
        j++;k++;
    }
    cout<<"array a inside merge is: "<<endl;
    for(int p=0;p<a.size();p++)
    {
        cout<<a[p]<<endl;
    }

}
void mergeSort(vector <int> &a)
{
    vector <int> l, r;
    int mid;
    if(a.size()<2) return;

    mid = a.size()/2;
    for(int i=0;i<mid;i++)
    {
        l[i]=a[i];
    }
    for(int i=mid;i<a.size();i++)
    {
        r[i-mid]=a[i];
    }
    mergeSort(l);
    mergeSort(r);
    merge(a, l, r);
}
int main()
{
    int n;
    vector <int> a;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    mergeSort(a);
    for(int p=0;p<n;p++)
    {
        cout<<a[p]<<endl;
    }
    return 0;
}

Ответы [ 3 ]

0 голосов
/ 08 мая 2018

Причиной возникновения ошибки сегментации является то, что вы обращаетесь к ячейке памяти, которая не существует (точнее сказать, что не выделено ). Скажем, у вас есть вектор длины 3, и вы пытаетесь получить доступ к 4-й позиции, вы получаете ошибку сегментации.

В отличие от ответа @ doctorlove, я бы сказал, что можно использовать []. Однако вам нужна следующая реализация (показана только для main(), пожалуйста, используйте ту же логику в других функциях). Для получения дополнительной информации см. Документацию std::vector. 

int main()
{
    size_t n;

    std::cin >> n;
    std::vector <int> a(n);

    for(int i=0;i<n;++i)
    {
        std::cin >> a[i];
    }

    // mergeSort(a);

    for(int i=0;i<n;++i)
    {
        std::cout << a[i] << "\n";
    }
    return 0;
}

Надеюсь, это поможет. Приветствия.

0 голосов
/ 08 мая 2018

вот окончательный код после изменений: 

//merging 2 sorted subarrays.
#include <iostream>
#include <vector>
using namespace std;

void merge(vector <int> &a,vector <int> &b,vector <int> &c)
{
    int i=0,j=0,k=0,bL=b.size(),cL=c.size();
    while(i<bL && j<cL)
    {
      if(b[i]<c[j])
      {
        a[k]=b[i];
        i++;k++;
      }
      else
      {
        a[k]=c[j];
        j++;k++;
      }
    }
    while(i<bL)
    {
      a[k]=b[i];
      i++;k++;
    }
    while(j<cL)
    {
      a[k]=c[j];
      j++;k++;
    }
    cout<<"array a inside merge is: "<<endl;
    for(int p=0;p<a.size();p++)
    {
      cout<<a[p]<<endl;
    }

}
void mergeSort(vector <int> &a)
{
    vector <int> l, r;
    int mid;
    if(a.size()<2) return;

    mid = a.size()/2;
    for(int i=0;i<mid;i++)
    {
      l.push_back(a[i]);
    }

    //change2
    for(int i=0;i<a.size()-mid;i++)
    {
      r.push_back(a[mid+i]);
    }
    mergeSort(l);
    mergeSort(r);
    merge(a, l, r);
}
int main()
{
    int n;
    cin>>n;

    //change1
    vector <int> a(n);
    for(int i=0;i<n;i++)
    {
      cin>>a[i];
    }
    mergeSort(a);
    cout<<"Final array is:"<<endl;
    for(int p=0;p<n;p++)
    {
      cout<<a[p]<<endl;
    }
    return 0;
}
0 голосов
/ 08 мая 2018

Когда вы обращаетесь к элементу в векторе, используя [], вы можете получить ошибку сегмента. Этот код, 

vector <int> a;

дает пустой вектор.

Запрос a[0] не будет работать, если в a еще ничего нет. Попытка установить значение a[0] также не будет работать. Не существует Тем не менее.

У вас похожая проблема в mergeSort при использовании 

vector <int> l, r;

Это также пустые векторы.

Вы можете использовать push_back (или даже emplace_back) для добавления новых элементов. Или используйте перегрузку конструктора , чтобы указать, сколько элементов вы хотите. Например, 

vector <int> a(10);

дает вам вектор из десяти целых, поэтому a[0] прекрасно подходит для чтения или записи. a[11] нет.

Сначала попрактикуйтесь в использовании вектора, затем попробуйте сортировку слиянием.

...