Почему этот код дает ошибку сегментации? - PullRequest
Новая
       8

Почему этот код дает ошибку сегментации?

0 голосов
/ 01 апреля 2020

Алиса играет в аркадную игру и хочет подняться на вершину списка лидеров и хочет отследить ее рейтинг. Его таблица лидеров работает следующим образом:

- Игрок с наибольшим количеством очков занял место в списке лидеров.

- Игроки, имеющие одинаковые очки, получают такой же номер рейтинга, и следующий игрок (и) ) получить сразу следующий номер рейтинга.

Например, четыре игрока в таблице лидеров имеют высокие баллы 100, 90, 90 и 80. Эти игроки будут иметь ранг 1, 2, 2 и 3 соответственно. Если Алиса набрала 70, 80 и 105 баллов, то после каждой игры ее рейтинг будет 4-м, 3-м и 1-м. 

#include <bits/stdc++.h>

using namespace std;


struct table{
    int rank;
    int score;
};

Это модифицированная функция двоичного поиска для поиска по партитуре. 

int search(vector<table> v,int low,int high,int n,int x){
    if(low<=high){
        int mid =(high+low)/2;
        if((v[mid].score==x) || (mid==0 && v[mid].score<x))
            return v[mid].rank;
        if(mid==n-1 && v[mid].score>x)
            return (v[mid].rank + 1);
        if(v[mid].score>x && x>v[mid+1].score && mid<n-1)
            return v[mid+1].rank;
        if(v[mid].score>x)
            return search(v,mid+1,high,n,x);
        else
            return search(v,low,mid-1,n,x);
    }
    return -1;
}

Основные функции скалолазания Leaderboard 

vector<int> climbingLeaderboard(vector<int> scores, vector<int> alice) {
    vector<table> v;
    vector<int> res;
    int n = scores.size();
    int m = alice.size();
    int x=1;
    for(int i=0 ; i<n ; i++){
        if(scores[i]!=scores[i-1] && i>0)
            x++;

        v[i].rank = x;
        v[i].score = scores[i];
    }
    int z;
    for(int i=0 ; i<m ; i++){
        x=alice[i];
        z = search(v,0,n-1,n,x);
        res.push_back(z);
    }
    return res;
}

Программа драйверов 

int main(){
    int scores_count;
    cin >> scores_count;
    vector<int> scores; `//vector for storing leaderboard scores`
    int k;
    for(int i=0 ; i<scores_count ; i++){
        cin >> k;
        scores.push_back(k);
    }
    int game_count;   `//number of games played by alice`
    vector<int> Alice;  `//vector for storing Alice's scores`
    for(int i=0 ; i<game_count ; i++){
        cin >> k;
        alice.push_back(k);
    }
    vector<int> result; `//vector for storing result rank of each game of Alice`
    result = climbingLeaderboard(scores,alice);
    for(auto i = result.begin() ; i!=result.end() ; i++){
        cout << *i << endl;
    }
    return 0;
}

Ответы [ 2 ]

1 голос
/ 01 апреля 2020

Проблема: в вашей функции climbingLeaderboard первый l oop попытается получить доступ к scores[i-1], когда для i задано значение 0, что приведет к отрицательному индексу для доступа std::vector.

Исправлено: изменение для l oop, чтобы оно начиналось с i = 1.

Проблема 2: Вы получаете доступ к v по индексу без создания каких-либо структур для хранения данных (например, v[i].rank = x).

Исправление 2: создайте экземпляр структуры и запишите в него данные, а затем выведите sh обратно в вектор v. В качестве альтернативы, зарезервируйте память для всего вектора в качестве предварительного выделения.

Проблема 3: При ближайшем рассмотрении ваша функция поиска определенно нарушена. Вероятно, вам следует проверить это изолированно от остальной части кода.

0 голосов
/ 02 апреля 2020

Ошибка дампа / сегментации ядра - это особая c ошибка, вызванная доступом к памяти, которая вам не принадлежит. Ошибка в функции: Основная функция climbingLeaderboard:

Доступ за пределами индекса массива

Запуск L oop С I = 1, когда вы набираете счет [i-1], который здесь в первом итерация будет иметь значение [-1] (индекс), и в c ++ 

for(int i=1; i<n ; i++){


    if(scores[i]!=scores[i-1] && i>0)
        x++;

    v[i].rank = x;
    v[i].score = scores[i];
}
отсутствует индекс -1
...