QСортировать массив структур malloc'd? - PullRequest
Новая
       44

QСортировать массив структур malloc'd?

0 голосов
/ 08 марта 2011

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

int textCompare ( const void * a, const void * b ){
    const char **x =(const char**)a;
    const char **y =(const char**)b;
    return strcmp(*x, *y);
}

Вот мой вызов qsort: где message** mList = malloc(INITIAL_CAPACITY * sizeof(message)); и count - отслеживание целого числа последнего элемента. message - это просто структура typedef, которая содержит int и указатель на символ. Я на 67% уверен, что правильно звоню qsort. Может ли кто-нибудь указать мне правильное направление? 

qsort (*mList, count, sizeof(message), textCompare);

[EDIT] Причина, по которой я объявляю сообщение *** вместо сообщения *, заключается в том, что я пытаюсь инициализировать «массив» указателей на структуры; если я не пойду об этом неправильно?

Ответы [ 3 ]

4 голосов
/ 08 марта 2011

Если вы действительно хотите отсортировать массив указателей на структуры сообщений, то вам нужно использовать это 

message **mlist = (message **)malloc(INITIAL_CAPACITY * sizeof(message *));

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

for(int i=0; i<INITIAL_CAPACITY; i++) {
  mlist[i] = (message *)malloc(sizeof(message));
  /*  initialize the members here  */
  mlist[i]->int = get_int();
  mlist[i]->char = get_char();  
  count++
  if(count >= NUM_TO_FILL_RIGHT_NOW)
   break;   
}

теперь вы можете сортировать массив указателей вместо самих структур. 

int textCompare( const void *a, const void *b ) {
  message *m1 = *(message **)a;
  message *m2 = *(message **)b;
  return strcmp(m1->char, m2->char);
}

Теперь вызовите qsort для массива указателей 

qsort( mlist, count, sizeof(message *), textCompare );

с помощью этого метода указатели находятся в смежной памяти (теоретически), но сами структуры выстраиваются по отдельности по мере необходимости. Кроме того, сортировка указателей обычно выполняется быстрее, чем сортировка структур из-за размера копируемого объекта. Указатели - это 8 байтов на 64-битной машине и 4 байта на 32-битной машине, и ваша структура может быть на самом деле меньше этой, но типичная структура будет больше, чем указатель.

1 голос
/ 08 марта 2011

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

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

typedef struct message {
  int i;
  char *p;
} message;

int textCompare(const void *a, const void *b) {
  const message *ma = a;
  const message *mb = b;
  return strcmp(ma->p, mb->p);
}

int main()
{
  int i;
  message* mList = malloc(10 * sizeof(message));
  mList[0].i = 0; mList[0].p = "zero";
  mList[1].i = 1; mList[1].p = "one";
  mList[2].i = 2; mList[2].p = "two";

  qsort(mList, 3, sizeof(message), textCompare);

  for(i = 0; i < 3; i++) {
    printf("%d %s\n", mList[i].i, mList[i].p);
  }
  return 0;
}

Обратите внимание на схему malloc вызова. Чтобы выделить массив типа T: 

T* var = malloc(array_size * sizeof(T));

Посмотрите, как в объявлении есть только один *, а оператор sizeof () получает на одну звездочку меньше, чем этот. Некоторые люди предпочитают эту форму: 

T* var = malloc(array_size * sizeof *var);

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

Также обратите внимание, что результат malloc.

отсутствует.

Также обратите внимание, как тип первого аргумента для qsort () соответствует типу преобразованных параметров в функции сравнения. В данном конкретном случае каждый из них message*.

Возможно, этот вызов qsort проще для понимания и поддержки: 

qsort(mList, 3, sizeof(*mList), textCompare);
1 голос
/ 08 марта 2011

Я не уверен, что при вызове malloc () выделяется правильный тип памяти для того, с чем вы хотите работать. Вы объявляете массив указателей, которые затем, в свою очередь, указывают на некоторый (возможный) массив указателей, но кажется, что вы резервируете память для фактического размера самих структур, т.е. вы резервируете память для массива сообщений, а не массив указателей на сообщения. Например, если вы разыменовываете mlist, на что указывает результирующий указатель? Предполагается ли указание на отдельную структуру сообщения или массив структур сообщений (т. Е. У вас есть некоторый двумерный массив структур сообщений, где каждый из mlist [0] - mlist [n] представляет указатель, указывающий на массив сообщений в куче, которые имеют произвольную длину по размеру)? Если предполагается, что он не указывает на что-то, а должна представлять собой фактическую структуру сообщения, тогда ваш вызов должен выглядеть примерно так: 

message* mlist = malloc(INITIAL_CAPACITY * sizeof(message));

, а не mlist типа message**.

Надеюсь, это поможет.

...