Проблема с qsort () - сортировка выполнена неправильно (C) - PullRequest
Новая
       12

Проблема с qsort () - сортировка выполнена неправильно (C)

4 голосов
/ 11 октября 2010

У меня есть вопрос, касающийся qsort.

Это немного странно, но моя функция qsort не дает правильного вывода.Странно то, что некоторые из моих функций сравнения идентичны моим прошлым проектам, но они не дают мне правильного ввода вообще.Я не уверен, как это проверить.

Например: 

int comp_name_asc(const void *a, const void *b)
{
  const Rec *prec1 = (const Rec *) a;
  const Rec *prec2 = (const Rec *) b;
  return strcmp(prec1->name, prec2->name); 
}

int comp_name_desc(const void *a, const void *b)
{
  const Rec *prec1 = (const Rec *) a;
  const Rec *prec2 = (const Rec *) b;
  return strcmp(prec2->name, prec1->name);
}

Вторая функция должна быть в порядке убывания, но результат идентичен: она всегда в порядке возрастания.Я проверил, чтобы убедиться, что правильная функция введена в нужное время.Rec - это typedef для структуры, которую я создал, которая имеет параметр char * name.

Также (ИЗМЕНЕНО, чтобы избежать переполнения): 

int comp_size_asc(const void *a, const void *b)
{
  const Rec *prec1 = (const Rec *) a;
  const Rec *prec2 = (const Rec *) b;

  if (prec1->byteSize > prec2->byteSize)
    return 1;
  else if (prec1->byteSize < prec2->byteSize)
    return -1;
  else
    return 0;
}

Результат совершенно странный, не восходящий илипо убыванию (то есть: 500, 515, 100, 200 ...).byteSize имеет тип off_t, полученный путем выполнения: 

char *path; // Build the path
struct stat sb;
if (lstat(path, &sb) == 0) {
  // Read sb.st_size

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

Любые идеи или способы отладки этого приветствуются.Спасибо.

РЕДАКТИРОВАТЬ:

Добавление вызова qsort: 

int index = 0;
Rec **array = (Rec **) malloc(sizeof(Rec *) * capacity);
// Adds element to the array...
qsort(array, index, sizeof(Rec *), comp_name_desc);

(Каждый раз, когда элемент добавляется в массив, индекс увеличивается.)

Спасибо.

РЕДАКТИРОВАТЬ:

Решение было дано ниже.Спасибо!

Мне пришлось изменить: 

const Rec *prec1 = (const Rec *) a;

на 

const Rec *prec1 = *(const Rec **) a;

из-за того, как я определил свой массив.Спасибо!

Ответы [ 3 ]

3 голосов
/ 11 октября 2010

У вас есть массив Rec, а точнее массив Rec указателей?Я спрашиваю, потому что функция сравнения получает как указатели параметров в массив, а не непосредственно на ваши записи.

Вот демонстрация обоих способов: 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Rec {
  char *name;
} Rec;

/*
 * The pointers a and b point directly into the array,
 * where the Records themselves are.
 */
static int
cmp_Rec_by_name(const void *a, const void *b) {
  const Rec *rec1 = (Rec *)a;
  const Rec *rec2 = (Rec *)b;
  return strcmp(rec1->name, rec2->name);
}

/*
 * The pointers point directly into the array, where
 * not the records but pointers to them are. So they
 * are a pointer to a pointer to a record.
 */
static int
cmp_Rec_ptr_by_name(const void *a, const void *b) {
  const Rec *rec1 = *(Rec **)a;
  const Rec *rec2 = *(Rec **)b;
  return strcmp(rec1->name, rec2->name);
}

static void
sort_Rec(void) {
  Rec record[3];

  record[0].name = strdup("hello");
  record[1].name = strdup("world");
  record[2].name = strdup("how are you");
  qsort(record, 3, sizeof (Rec), cmp_Rec_by_name);

  for (int i = 0; i < 3; i++)
    printf("%s\n", record[i].name);
}

static void
sort_Rec_ptr(void) {
  Rec *(record[3]);

  record[0] = malloc(sizeof (Rec));
  record[1] = malloc(sizeof (Rec));
  record[2] = malloc(sizeof (Rec));
  record[0]->name = strdup("hello");
  record[1]->name = strdup("world");
  record[2]->name = strdup("how are you");
  qsort(record, 3, sizeof (Rec *), cmp_Rec_ptr_by_name);

  for (int i = 0; i < 3; i++)
    printf("%s\n", record[i]->name);
}

int
main() {
  sort_Rec();
  sort_Rec_ptr();
  return 0;
}
2 голосов
/ 11 октября 2010

Вы никогда не должны сравнивать числа, вычитая одно из другого.Это обычно приводит к переполнению со знаком типов и не будет работать вообще с неподписанными типами.Общая идиома сравнения чисел с результатом в трех состояниях такова: 

(a > b) - (a < b)

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

0 голосов
/ 11 октября 2010

слыша, каково поведение, можно предположить, что имена на самом деле не являются именами, если strcmp() поменял местами два аргумента и результаты все еще возрастают. Одним из предложений может быть распечатка имен с использованием printf, а также сокращение имен до 2 или 3 (количество записей), чтобы упростить отладку и выяснить, почему он ведет себя так.

...