Слияние k отсортированных массивов - проблема с памятью - PullRequest
Новая
       6

Слияние k отсортированных массивов - проблема с памятью

0 голосов
/ 09 ноября 2018

Цель состоит в том, чтобы отсортировать матрицу слов i x j в одномерной матрице слов в алфавитном порядке (каждая строка в исходной матрице уже отсортирована). Матрица читается из файла и сохраняется в виде трехзвездочного указателя ***index, она динамически распределяется следующим образом (в отдельной функции): 

char ***index;
index= (char ***) malloc(*row * sizeof(char **));
...
for (int i = 0; i < *row; ++i){

    index[i]= (char **) malloc(*col * sizeof(char **));
    for (int j=0; j<*col; j++) {

        fscanf(fp,"%s",tmp);
        index[i][j]=strdup(tmp);
    }

}

Затем я передаю индекс моей функции сортировки: char **sort_data(char ***index, int row,int col).

Ничего особенного, только алгоритм сортировки слиянием, который:

  1. проверяет первые элементы каждой строки ***index
  2. перемещает самое маленькое слово в **sortedIndex

  3. заменяет отсортированное слово новым из той же строки. 

    char **sort_data(char ***index, int row,int col){

int i,posInIndex,smallestCharPos,*tracker;
char **sortedindex,*buffer;
sortedindex=(char **) malloc((row*col)*sizeof(char*));
tracker= (int*) calloc(row, sizeof(int));

posInIndex=0;
while (posInIndex<row*col) {
    smallestCharPos=-1;
    for (i=0; i<row; i++) {
        if ((smallestCharPos==-1)||(strcmp(index[i][tracker[i]], buffer)<0)) {
            smallestCharPos=i;
            buffer=index[i][tracker[i]];
        }

    }
    sortedindex[posInIndex]=index[smallestCharPos][tracker[smallestCharPos]];
    posInIndex++;
    tracker[smallestCharPos]++;
}
free(tracker);
return (sortedindex);

}

После некоторых итераций (зависит от размера матрицы) цикла for я получаю EXC_BAD_ACCESS (code=1, address=0x14000001f5) в операторе if, что наводит меня на мысль, что это проблема с моим распределением памяти, но я не могу определить ошибку.

Примером матрицы для сортировки может быть (эта конкретная матрица доставляет мне проблемы после 10 итераций цикла for):

Милан, Турин, Венеция

Бари Дженова Таранто

Флоренция Наполи Рома

Болонья Кальяри Палермо

1 Ответ

0 голосов
/ 09 ноября 2018

Проблема в том, что вы не отслеживаете, когда закончите со строкой. Даже если вы уже использовали все слова строки, вы просто продолжаете смотреть на строку, как будто есть еще слова для обработки.

Вам нужно добавить код, чтобы пропустить строки, которые уже полностью обработаны.

Попробуйте изменить это: 

if ((smallestCharPos==-1)||(strcmp(index[i][tracker[i]], buffer)<0)) {
     ...
}

до 

if (tracker[i] < col)
{
     if ((smallestCharPos==-1)||(strcmp(index[i][tracker[i]], buffer)<0)) {
         ...
     }
}
...