Блог

Главная - Вопросы по программированию - При использовании qsort () в дереве, состоящем из структур, я не получаю обратно отсортированный массив

При использовании qsort () в дереве, состоящем из структур, я не получаю обратно отсортированный массив

#c

#c

Вопрос:

Используя qsort в дереве, состоящем из структур, я не получаю обратно отсортированный массив.

Я пробовал манипулировать функцией сравнения и qsort но не уверен, в чем проблема.

 typedef struct nodeBST { // struct
    char *key;
    int count;
    struct nodeBST *left;
    struct nodeBST *right;
} nodeBST;
  
 qsort(*words, numTokensActual, sizeof(nodeBST), comparator); //qsort
  
 for (i = 0; i < numTokensActual; i  ) {
    printf("sorted words[%d]:%s: %d n", i,
           ((struct nodeBST *)words[i])->key,
           ((struct nodeBST *)words[i])->count); //traverse to print
}
  
 struct nodeBST *words[4]; //creation of array and malloc for space

int z;

for (z = 0; z < 4; z  ) {
    words[z] = malloc(sizeof(nodeBST));
}
  
 int comparator(const void *p, const void *q) { //compare function
    struct nodeBST *a = (struct nodeBST **)p;    
    struct nodeBST *b = (struct nodeBST **)q;

    return a->count - b->count;
} 
  
 printf("%d n"((struct nodeBST*)words[i])->count); //print output
  
 int numTokensActual = AddToArray(root, words, 0);
  
 int AddToArray(nodeBST *node,  nodeBST **arr, int i) {
    if (node == NULL)
        return i;

    if (node->left != NULL)
        i = AddToArray(node->left, arr, i);

    //printf("Adding To Array[%d]: %s:%dn",i, node->key, node->count);
    //arr[i] = node;
    arr[i] = newNodeBST2(node->key, node->count);
    //printf("added array[%d]: %sn", i, arr[i]->key);
    i  ;
    if (node->right != NULL)
        i = AddToArray(node->right, arr, i);

    return i;
}

Я ожидаю, что на выходе я получу отсортированный массив, но на выходе:

 0 
0 
49 
6

Комментарии:

1. struct nodeBST * a = (struct nodeBST**) p; ошибка на нескольких уровнях. Вам нужно отладить свой код , прежде чем запрашивать SO.

2. Мои входные данные для массива — это слова из текстового файла, которые я сохраняю как токены, а затем создаю массив структур, из которых я беру «количество» слов или частоты слов. Третье слово не появляется 49 раз.

3. Рассказчик, я отладил свой код, но не могу найти проблему. Просто не получается правильных сравнений.

4. qsort для непрерывно выделяемой памяти, для массива. Вы строите дерево. Вы должны написать qsort алгоритм самостоятельно.

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

Ответ №1:

У вас нет массива, прочитайте документацию:

Функция qsort () сортирует массив с элементами nmemb размером size.

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

 struct {
    int count;
    struct nodeBST *node;
} tempSortedNodes[numTokensActual];

Пройдитесь по вашему дереву и заполните sorted массив, затем вы можете выполнить qsort его. Обратите внимание, что отсортированная версия становится недействительной при обновлении дерева.

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

Алгоритм сортировки для дерева, предложенный в комментариях, вообще не является хорошей идеей. Это было бы эквивалентно созданию нового дерева с использованием count ключа as, как я предложил.