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

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

1 голос
/ 19 октября 2010

Я делаю упражнение 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 (который содержит указатели на все слова, встречающиеся до сих пор).После того, как весь ввод был проанализирован, массив указателей будет отсортирован по переменным count и затем напечатан.Так как

Код, добавление новых слов / обновление счетчиков здесь: ( Я не думаю, что с этим что-то не так, поскольку 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;

}

Так что у меня все работает правильно, кроме сортировки;это просто не будет сортировать массив.То есть ... порядок элементов остается неизменным РЕДАКТИРОВАТЬ: Я получаю ошибку сегментации. РЕДАКТИРОВАТЬ # 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.

Ответы [ 2 ]

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

Так что мне удалось заставить его сортировать свою собственную реализацию быстрой сортировки. Версия 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 не работает с моей структурой? Я использую это неправильно (мой вызов к нему, а также функция сравнения в оригинальном сообщении)?

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

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

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

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

...