C (новичок): Почему мой qsort не работает? РЕДАКТИРОВАТЬ: от одной ошибки к другой

Я делаю упражнение K&R 6-4, а именно:

6-4. Напишите программу, которая печатает на входе отдельные слова, отсортированные в порядке убывания частоты их появления. Предшествуйте каждому слову его количество.

Я решил создать структуру с именем dstncFreqNode6_4:

struct dstncFreqNode6_4
{
   char *word;
   int count;
   struct dstncFreqNode6_4 *left;
   struct dstncFreqNode6_4 *right;
};

Затем я проанализировал ввод на наличие слов и для каждого отдельного слова создал один узел "dstncFreqNode6_4" и два указателя на него: один для вставки в BST (для добавления новых слов/обновления количества уже встреченных слов) и один для вставить в глобальный массив указателей "dsntFredNode6_4".

Это было сделано для того, чтобы я мог обновлять количество слов (узлов) путем обхода BST (который содержит указатели на все встреченные до сих пор слова). После того, как весь ввод будет проанализирован, массив указателей будет отсортирован по переменным «количества» членов, а затем напечатан. Поскольку

Код добавления новых слов/обновления счетчиков находится здесь:(Я не думаю, что с этим что-то не так, так как BST и массив заполнены правильно, так что вы можете игнорировать это) :

//"wordCounts" is originally a global dstncFreqNode6_4** declared outside the function, numWords is the current length of the array

struct dstncFreqNode6_4 *addFreqNode6_4(struct dstncFreqNode6_4 *root, char *word)
{

    if(root == NULL)
    {

       root = (struct dstncFreqNode6_4 *) malloc(sizeof(struct dstncFreqNode6_4));
       root -> word = word;
       root -> count = 1;

       root -> left = NULL;
       root -> right = NULL;


       struct dstncFreqNode6_4 **p;

       wordCounts = (struct dstncFreqNode6_4 **) realloc(wordCounts, sizeof(struct dstncFreqNode6_4*) * (numWords +1));
       p = wordCounts + numWords++;

       (*p) = root;

    }
    else if(strcmp(word, root -> word) < 0)
        root -> left = addFreqNode6_4(root -> left, word);
    else if(strcmp(word, root -> word) > 0)
        root -> right = addFreqNode6_4(root -> right, word);
    else
        root -> count++;

return root;

}

Итак, у меня все работает правильно, кроме сортировки; он просто не будет сортировать массив. То есть... порядок элементов остается неизменным EDIT: я получаю ошибку сегментации. EDIT #2: Теперь ошибки сегментации нет; исходная проблема все еще существует.

Я использую метод qsort stlib.h; функция сравнения, которую я использую:

int qcmp6_4(const void *a, const void *b)
{
    return (*(struct dstncFreqNode6_4 **)a) -> count - (*(struct dstncFreqNode6_4 **)b) -> count;
}

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

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

ИЗМЕНИТЬ

Извините, вот вызов qsort:

qsort(wordCounts, numWords, sizeof(struct dstncFreqNode6_4 *), qcmp6_4);

РЕДАКТИРОВАНИЕ № 2:

Следуя предложению, я сделал "wordCounts" массив указателей на узлы (весь код в этом посте был обновлен, чтобы отразить это). Таким образом, по сути, BST и массив содержат одинаковую информацию (на самом деле указатели массива инициализируются соответствующим указателем в BST), но их использование различно. BST используется для добавления новых слов/обновления количества уже встреченных слов, а в конце массив сортируется (по количеству слов) и печатается. Однако я столкнулся с той же проблемой, с которой столкнулся изначально: порядок массива остается прежним после вызова qsort.


c struct algorithm qsort
person Kevin    schedule 19.10.2010    source источник
comment
Итак, вы показали нам почти все, кроме фактического вызова qsort с реальным массивом. Думаешь, это может быть важно?   -  person abelenky    schedule 19.10.2010
comment
Ваш комментарий позволил мне заглянуть в свой код и выяснить, что я использовал размер указателя моего узла, а не размер моего узла для qsort. Итак, проблема с несортировкой устранена... теперь единственная проблема в том, что у меня ошибка сегментации!   -  person Kevin    schedule 19.10.2010
comment
Ошибку сегментации должно быть легко найти с помощью отладчика. Установите точку останова и выполняйте код построчно, пока ошибка не обнаружит себя.   -  person abelenky    schedule 19.10.2010
comment
Я последовал предложению R.. и сделал wordCount массивом указателей на узлы. Это избавило от ошибки сегментации, однако исходная проблема все еще сохраняется.   -  person Kevin    schedule 19.10.2010

Ответы (2)


arrow_upward
0
arrow_downward

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

Кстати, я вижу, что вы используете realloc. Та же проблема с указателями на элементы массива возникнет с realloc всякий раз, когда ему придется переместить выделенный массив в новое место, чтобы удовлетворить новому требованию размера, только намного хуже: все указатели узлов теперь будут указывать на недопустимые адреса, и их использование будет привести к неопределенному поведению.

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

person R.. GitHub STOP HELPING ICE    schedule 19.10.2010
comment
Проблема с realloc - это то, что меня беспокоило и о чем я знал, но я не видел, как это повлияет на то, что я пытаюсь сделать. - person Kevin; 19.10.2010
comment
Итак, я реализовал массив указателей, однако проблема все еще сохраняется. - person Kevin; 19.10.2010

arrow_upward
0
arrow_downward

Итак, мне удалось заставить его сортировать с помощью моей собственной реализации быстрой сортировки. Версия stlib.h по-прежнему оставляет мой массив несортированным. Можно ли его использовать только для массивов примитивных типов? Потому что это единственная причина, по которой я вижу, что она не работает.

Вот мой собственный код qsort для справки:

void swapFreq6_4(struct dstncFreqNode6_4 **a, struct dstncFreqNode6_4 **b)
{
   struct dstncFreqNode6_4 *t=*a; *a=*b; *b=t;
}

void **sortFreq6_4(struct dstncFreqNode6_4 **arr, int beg, int end)
{

   if (end > beg + 1)
   {
      struct dstncFreqNode6_4 *piv = *(arr + beg);
      int l = beg + 1;
      int r = end;


     while (l < r)
     {
         if ( (*(arr + l))-> count <= piv -> count)
             l++;
         else
             swapFreq6_4((arr + l), (arr + --r));
     }



     swapFreq6_4((arr + --l), (arr + beg));
     sortFreq6_4(arr, beg, l);
     sortFreq6_4(arr, r, end);

  }
}

Кто-нибудь знает, почему код qsort stdlib не работает с моей структурой? Я использую его неправильно (мой вызов к нему, а также функция сравнения находятся в исходном сообщении)?

person Kevin    schedule 19.10.2010