C (principiante): Perché non il mio lavoro qsort? EDIT: Da un errore all'altro

Question

sto facendo K & R esercizio 6-4, che è:

  

6-4. Scrivere un programma che stampa le parole distinte suo ingresso ordinati in ordine di frequenza di occorrenza decrescente. Far precedere ogni parola per il suo conteggio.

Quello che ho deciso di fare è creare una struttura denominata dstncFreqNode6_4:

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

Ho poi analizzato l'input per le parole, e per ogni parola distinct creato un nodo "dstncFreqNode6_4" e due puntatori ad esso: uno da inserire in un BST (per aggiungere nuove parole / aggiornare i conteggi di parole già incontrati), e uno da inserire in una gamma globale di puntatori "dsntFredNode6_4".

Questo è stato fatto in modo che io possa aggiornare i conteggi di parole (nodi) attraversando il BST (che contiene puntatori a tutte le parole incontrate finora). Dopo l'intero ingresso è stato analizzato, la matrice di puntatori sarebbe stato risolto dai membri variabili 'contare', e poi stampato. Dal momento che la

Il codice l'aggiunta di nuove parole / aggiornare i conteggi è qui: ( non credo che qualcosa è sbagliato con esso, dal momento che la BST e la matrice sembrano essere popolato correttamente, quindi si può ignorare questa) :

//"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;

}

Così ho tutto che funziona diritto a meno che l'ordinamento; semplicemente non ordinare l'array. Vale a dire ... l'ordine degli elementi rimane invariato Modifica ottengo un errore di segmentazione Modifica # 2.: Nessun errore di segmentazione ora; il problema originale esiste ancora.

Sto usando il metodo di qsort stlib.h; la funzione di confronto che sto utilizzando è:

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

Non riesco a capire perché non sarà sorta correttamente. Io in realtà implementato il mio algoritmo quicksort e sto ottenendo gli stessi risultati. Io davvero non so a questo punto.

Sarebbe bello avere un po 'di fresco, e gli occhi esperti per me puntare nella direzione giusta. Grazie.

Modifica

Siamo spiacenti, ecco la chiamata a qsort:

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

Modifica # 2:

In seguito il suggerimento, ho fatto "wordcounts" un array di puntatori ai nodi ( tutto il codice in questo post è stato aggiornato per riflettere questo ). Quindi, in sostanza, la BST e l'array contengono informazioni identiche (infatti i puntatori campo vengono inizializzati al puntatore corrispondente nel BST), ma i loro usi sono differenti. La BST viene utilizzata per aggiungere nuove parole / aggiornare i contatori dei quelli già incontrati, e la matrice è ordinata alla fine (dal ciascuno dei conteggi le parole) e stampato. Tuttavia, sto correndo per lo stesso problema che in origine sono imbattuto in a:. L'ordine della matrice rimane la stessa dopo la chiamata a qsort

Answer 1

Così sono riuscito a farlo per ordinare con la mia implementazione di quicksort. La versione del stlib.h lascia ancora il mio allineamento non differenziati. Può essere usato solo su array di tipi primitivi? Perché questo è l'unico motivo che posso vedere che gli impedisce di lavorare.

Ecco il mio codice qsort personalizzato per riferimento:

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

  }
}

Qualcuno sa il motivo per cui il codice qsort del stdlib non funziona con il mio struct? Sto usando sbagliato (la mia chiamata ad esso, così come la funzione confrontando sono nel post originale)?

Answer 2

Sembra a me come si sta cercando di risolvere una serie di nodi che contengono ciascuno puntatori ad altri nodi nella matrice. Dopo la cernita, questi puntatori volontà del punto naturalmente agli elementi sbagliate della matrice. Forse questo è il tuo problema?

A proposito, vedo che si sta utilizzando realloc. Lo stesso problema con puntatori a elementi di matrice si presenti con realloc ogniqualvolta deve spostare l'array allocato in una nuova posizione per soddisfare il nuovo requisito di formato, solo molto peggio: i puntatori dei nodi ora tutto scegliere indirizzi non validi e il loro utilizzo causare un comportamento indefinito.

Una possibile soluzione potrebbe essere quella di non modificare la matrice originale di nodi, e invece fare una seconda serie di puntatori ai nodi e tipo che array di puntatori utilizzando una funzione di confronto che confronta i nodi a cui puntano a.