Расшифровка поведения qsort

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

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

xxxxxbxbbbxfbxfbffffbxfxbbfbbbxxfxbxxfbbbbxbfxbxfbxbsxbbbxxbbxxffxbxfxfxbxxbxxfbbbfbxbbx
bbbsxfxbxbxxbfbfxbxxbxxbfxxbxsbfxxfxfxfffxbfxffbbfffsxsfbfbxbxbbbxxsbfbfbbbbbbxxfxfxffxf
xbxxbxfxbfbxbxxbxbxxbxbbffxxbxxffxxbxfxbxffxfsfxxfxxfxxfxfxxfxxbsxxbbbxsxxbbxxxbxfxsbxxx
ffbxfxxffbxxxfxxfxxfxfxxfffbxxxbxxxfffxsbbfffffxxxbbfxsbffxbxxfxbxxfbbfsbffsfffxfxfxbbffx
bxxfxbxxfxbbbfxxbbfxxbbbsxbxfbfbbxxbbfffxxfxxbbbfxxbxxxbbxxxbfxffxxxffxfxxffbxfsxbxxxfxfx
fsbbbxxxbfxfffsfxxxfssxxxfxfxxxxbxbbbxxbxxxxxxxxxxxxxxxxxxxfbfxxffxxbxxxxxxxsxsxxxxxxxxsxb
bxxxxxfxbxxxxfxxfxxxxxbbxfffbxbsxffbbbxsfbbfffbxbfbbxxbxxbbxxbffxfxxfxfbbxxbxfxxsfxxfxxbxf
xxbxxxbxbxbbxbbffxxxxbfbfxxxxxxfxffxxxxxxxxxxxxxxxxxxxxxbxffxbxbxbbxbbxxfbxfxbxxbxxbxbxxxb
xxbxbxbfbbffffffsbbxxbffbxfxxfxbfbfffsxbxxxsxxbbbbbxxxbxxxfxxfffxxxxxxxxxxxxxfxxbxxxxxxxxx
xxbfbxxxxxxxxxxxxxxxxxxxxxxxxxxbxbxxxxxfxxbxxxxffxbxxxxffxfbfffxbxxfxbfxbxxfxbxbfxxxxxfxbx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxsbxxxxffxfxxxxxxxxxfxfxxxbffffxxxfbxbxfxxxxxxxxxxxxxxxxxxxxf
fxfxbfxxxfxxxxx

Я думаю, что проблема связана либо с моим вызовом функции, либо с методом сравнения.

int compare(const void *a, const void *b){
  return *(char * const *) a - *(char * const *) b;
}

и используется в

qsort(temp, lineCount, sizeof(char), compare);

где temp — это массив символов выше, а lineCount — это количество символов в массиве. Как целостность массива, так и размер были проверены путем тестирования.

Любая помощь приветствуется.


c qsort
person Jason    schedule 12.09.2011    source источник

Ответы (3)


arrow_upward
5
arrow_downward

char * const * — это указатель на указатель на char. Вам просто нужен указатель на char.

Пытаться:

int compare(const void *a, const void *b){
    return *(const char *) a - *(const char *) b;
}

Кроме того, sizeof(char) всегда равно 1 по определению. Так что некоторые программисты на C никогда бы не написали это так. (Это вопрос мнения, облегчает ли это чтение кода или просто сигнализирует о том, что вы на самом деле не знаете язык. В этом случае мне это нравится, но просто к вашему сведению.)

person Nemo    schedule 12.09.2011
comment
Я бы предпочел видеть sizeof *temp на случай изменения типа, но я использую необработанный 1 в зависимости от фазы луны и тому подобного. - person Chris Lutz; 12.09.2011

arrow_upward
1
arrow_downward

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

int compare(const void *a, const void *b)
{
    char* alpha = (char*)a;   // Might get const-warning on these lines, ignore for now.
    char* beta  = (char*)b;

    if (*alpha == *beta) return 0;
    if (*alpha < *beta) return -1;
    return 1;
}

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

Как только он снова заработает, вы можете снова объединить его в одну компактную строку кода.

person abelenky    schedule 12.09.2011

arrow_upward
1
arrow_downward

Попробуй это:

int compare(const void *a, const void *b){
  return *(const char *) a - *(const char *) b;
}

Но ИМХО, qsort вообще не нужен!

Просто создайте таблицу int[256] (или меньше) и повторите массив, чтобы записать количество каждого символа:

int res[256];
memset(res, 0, 256*sizeof(int));
int i;
for (i=0;i<lineCount;i++){
    res[tmp[i]]++;
}

Это обеспечит O (N) по сравнению с O (NlogN) qsort.

person ZhangChn    schedule 12.09.2011