использование qsort, вызывающее ошибку сегментации - PullRequest
Новая
       8

использование qsort, вызывающее ошибку сегментации

1 голос
/ 18 сентября 2011

Ну, как часть изучения C ++, у моего проекта есть ограничение. Мне не разрешено использовать какие-либо библиотеки, кроме базовых, таких как <cstring> и некоторых других необходимых.

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

Cartwright   Wendy    93
Williamson   Mark     81
Thompson     Mark     100
Anderson     John     76
Turner       Dennis   56

Должен сортировать их по столбцам. И мой поиск по StackOverflow вернул результат от кого-то, кто тоже должен был сделать тот же проект несколько лет назад. Хахаха Qsort, основанный на столбце в c-строке?

Но в моем случае я просто использую глобальную переменную для столбца и продолжаю жизнь. Моя проблема возникла при реализации функции сравнения для qsort

В моем основном методе я называю 

qsort (data, i, sizeof(char*), compare);

, где data - это char * data[], а i - количество строк для сравнения. (В данном случае 5)

Ниже приведен мой код для метода сравнения 

int compare (const void * a, const void * b){
    char* line1 = new char[1000]; char* line2 = new char[1000];
    strcpy(line1, *((const char**) a));
    strcpy(line2, *((const char**) b));
    char* left = &(strtok(line1, " \t"))[column-1];
    char* right = &(strtok(line2, " \t"))[column-1];
    return strcmp(left, right);
}

1000 - это потому, что я просто обобщил (и специально сделал плохое кодирование), чтобы переобобщить, что ни одна строка не будет длиннее 1000 символов.

Что меня смущает, так это то, что когда я использую отладчик в Eclipse, я вижу, что он сравнивает его успешно в первый раз, а затем во втором раунде возникает ошибка сегментации при попытке их сравнения.

Я также пытался изменить код для назначения левого и правого на то, что ниже, но это тоже не помогло 

char* left = new char[100];
strcpy(left, &(strtok(line1, " \t"))[column-1]);
char* right = new char[100];
strcpy(right, &(strtok(line2, " \t"))[column-1]);

Пожалуйста, помогите мне понять, что является причиной ошибки сегментации. В первый раз он сравнивает два, слева = "Уильямсон" и справа = "Томпсон". Во второй раз он сравнивает (и пытается вылететь) left = "Cartwright" и right = "Thompson"

1 Ответ

4 голосов
/ 18 сентября 2011 
char* line1 = new char[1000]; char* line2 = new char[1000];

Это совсем не хорошо.Вы никогда не освобождаете это, поэтому вы теряете 2000 байтов при каждом вызове функции сравненияВ конечном итоге это приведет к нехватке памяти, и new сработает.(Или в Linux ваш процесс может быть убит OOM-убийцей).Это также не очень эффективно, когда вы могли бы просто сказать char line1[1000], что очень быстро, потому что он просто вычитает из указателя стека, а не потенциально просматривает свободный список или запрашивает у ядра больше памяти.

Нона самом деле вы могли бы делать сравнение без изменения или копирования строк.Например: 

static int
is_end_of_token(char ch)
{
    // If the string has the terminating NUL character we consider it the end.
    // If it has the ' ' or '\t' character we also consider it the end.  This
    // accomplishes the same thing as your strtok call, but WITHOUT modifying
    // the source buffer.
    return (!ch || ch == ' ' || ch == '\t');
}

int
compare(const void *a, const void *b)
{
   const char *strA = *(const char**)a;
   const char *strB = *(const char**)b;

   // Loop while there is data left to compare...
   while (!is_end_of_token(*strA) && !is_end_of_token(*strB))
   {
      if (*strA < *strB)
         return -1;      // String on left is smaller
      else if (*strA > *strB)
         return 1;       // String on right is smaller
      ++strA;
      ++strB;
   }

   if (is_end_of_token(*strA) && is_end_of_token(*strB))
      return 0;    // both strings are finished, so they are equal.
   else if (is_end_of_token(*strA))
      return -1;   // left string has ended, but right string still has chars
   else
      return 1;    // right string has ended, but left string still has chars
}

Но, наконец ... Вы используете std::string говорите?Ну, если это так, то предположить, что память, переданная в qsort, совместима с "const char **", немного странно, и я ожидаю, что она вылетит.В этом смысле, может быть, вы должны сделать что-то вроде: 

int compare(const void *a, const void *b)
{
    const char *strA = ((const std::string*)a)->c_str();
    const char *strB = ((const std::string*)b)->c_str();

    // ...
}

Но на самом деле, если вы используете C ++, а не C, вы должны использовать std::sort.

...