C（初學者）：爲什麼我的qsort不能工作？編輯：從一個錯誤到另一個

Question

我做ķ& [R練習6-4，那就是：

6-4。編寫一個程序，在輸入中按照出現頻率的降序打印不同的單詞。在每個單詞的前面加上count。

我決定要做的就是創建一個名爲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：現在沒有分割錯誤;原來的問題依然存在。

我使用stlib.h的qsort方法;我使用的比較功能是：

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

我似乎無法弄清楚它爲什麼不能正確排序。我實際上實現了我自己的快速排序算法，並得到相同的結果。我現在真的不知道。

這將是很好，得到一些新鮮的，專家的眼睛指向我在正確的方向。謝謝。

編輯

對不起，這裏的調用快速排序：

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

編輯＃2：

以下的建議，我做了 「wordCounts」 的數組指向節點的指針（此帖子中的所有代碼已更新，以反映此）。所以實際上，BST和數組包含相同的信息（事實上，數組指針被初始化爲BST中的相應指針），但它們的用途是不同的。 BST用於添加新單詞/更新已經遇到的單詞的計數，並且在末尾（通過每個單詞的計數）對數組進行排序並打印。但是，我遇到了同樣的問題，我最初跑到：在調用qsort之後，數組的順序保持不變。

Answer 1

所以我設法讓它與我自己的quicksort實現排序。 stlib.h的版本仍然使我的數組未排序。它只能用於原始類型的數組嗎？因爲那是我看到阻止它工作的唯一原因。

下面是引用我的自定義快速排序代碼：

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); 

    } 
} 

有誰知道爲什麼STDLIB的快速排序的代碼不能與我的結構工作？我用錯了嗎（我的電話，以及比較功能都在原始文章中）？

Answer 2

它看起來像我試圖對一個節點數組進行排序，每個節點都包含指向數組中其他節點的指針。排序後，這些指針當然會指向數組中的錯誤元素。也許這是你的問題？

順便說一句，我看到你正在使用realloc。每當需要將分配的數組移動到一個新的位置以滿足新的大小要求時，數組元素指針的相同問題將會出現realloc，只會更糟糕：節點指針現在將全部指向無效地址並使用它們導致未定義的行爲。

一個可能的解決辦法是永遠不會改變原來的節點的數組，而不是使指針第二陣列節點和排序使用它們指向的節點進行比較的比較函數指針數組。