Qsorting 2d массивов указателей - PullRequest
Новая
       4

Qsorting 2d массивов указателей

1 голос
/ 12 марта 2012

Я пытаюсь отсортировать двумерный массив указателей, используя qsort.Единственная проблема, с которой я столкнулся сейчас, это то, что изначально я использовал статически объявленные массивы, теперь переключаясь на указатели.Я почти испытываю желание переключиться на структуры, но я упрям, что я не могу заставить это работать.

До сих пор я неправильно определял двумерный массив указателей [array2d [m] [3] был заданным размером]: 

     int **array2d;

     array2d = (int**)malloc((m)*sizeof(int*));

     for(i=0; i<=m; i++)
       array2d = [i]=(int*)malloc(3*sizeof(int));
     qsort(array2d, m, 3*sizeof(int**),comp);

Мое сравнение: 

int comp(const void* left, const void*right)                                                                                  
{

  const int *a = *(const int**)left;
  const int *b = *(const int**)right;

  return a-b;
}

Хотя я не уверен, как структурировать сравнение для работы с 2d указателями.

1 Ответ

1 голос
/ 14 апреля 2012

Из предоставленного вами фрагмента кода я предполагаю, что вы пытались отсортировать каждую строку матрицы отдельно. Первое, что я заметил, - это опечатка в распределении памяти столбцов (2-й индекс) матрицы.

Правильное выделение памяти для матрицы numRow x numColumns будет выглядеть следующим образом: 

/* loop counter */
int i;

/* dynamic array sizes */
const int numRow = 5;
const int numColumns = 25;

/* allocate the row pointers */
int **dynamic2d = (int **)malloc(numRow * sizeof(int *));

/* for each row pointer */
for(i = 0; i < numRow; i++)
{
    /* allocate columns */
    dynamic2d[i] = (int *)malloc(numColumns * sizeof(int));
}

Далее вы не сможете просто вызвать метод qsort (..) только один раз. Этот метод ожидает "плоский" или одномерный массив. Вам нужно будет вызывать метод qsort (...) отдельно для каждой строки матрицы. Это продемонстрировано ниже: 

/* sort array */
for(i = 0; i < numRow; i++)
    qsort(dynamic2d[i], numElements, sizeof(int *), comp);

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

Это простое исправление. Просто напишите логику для получения этих результатов, как показано ниже: 

int comp(const void* firstArg, const void* secondArg)
{
   /* get the values of the arguments */
   int first = *(int *)firstArg;
   int second = *(int *)secondArg;

   /* return the value as expected by the qsort() method */
   if(first < second)
   {
      return 1;
   }
   else if(second < first)
   { 
     return -1;
   }

   return 0;
}

Последнее, что следует отметить, это будет сортировать по величине к минимуму. Не переключайте логику в компараторе, если хотите меньше всего. Сортировка не даст точных результатов. Правильный способ сделать это - прочитать массив задом наперед, как показано ниже: Вы можете поменять местами аргументы в компараторе, чтобы изменить порядок сортировки или прочитать результаты задом наперед. 

int comp(const void* firstArg, const void* secondArg)
{
    /* get the values of the arguments */
    int first = *(int *)secondArg;
    int second = *(int *)firstArg;
    ...
}

или 

/* print greatest to smallest */
for(i = 0; i < numRow; i++)
{
    /* start at front and work to back */
    for(j = 0; j < numColumns; j++)
        printf("%d ", dynamic2d[i][j]);
    printf("\n");
}

/* print smallest to greatest */
for(i = 0; i < numRow; i++)
{
    /* start at back and work to front */
    for(j = numColumns- 1; j >= 0; j--)
        printf("%d ", dynamic2d[i][j]);
    printf("\n");
}

Надеюсь, это поможет! Если вам нужно отсортировать всю матрицу целиком ... это другой зверь вместе взятый.

...