c - 当在由结构组成的树上使用 qsort() 时，我没有收到排序后的数组

Question

在由结构组成的树上使用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:%d\n",i, node->key, node->count);
    //arr[i] = node;
    arr[i] = newNodeBST2(node->key, node->count);
    //printf("added array[%d]: %s\n", i, arr[i]->key);
    i++;
    if (node->right != NULL)
        i = AddToArray(node->right, arr, i);

    return i;
}

我希望输出给我一个排序数组，但输出是:

0 
0 
49 
6

Answer 1

您没有数组，请阅读文档:

The qsort() function sorts an array with nmemb elements of size size.

如果您使用 count 构建一个临时数组和指向以下项目的指针，我们可以使用 qsort 来获取项目的排序列表，而无需更改数据结构:

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

遍历你的树并填充sorted数组，然后你可以对其进行qsort。请注意，当树更新时，排序版本将变得无效。

另一种方法是使用 count 作为键来创建另一棵树。每当原始树更新时，该辅助树也将失效。但是，如果您需要始终维护树的计数排序版本，我们可以更新两棵树。

正如评论中所建议的，树的排序算法根本不是一个好主意。这相当于按照我的建议使用 count 作为键创建一棵新树。