PDA

Visualizza la versione completa : [C] Alberi: stampa in ordine decrescente di occorrenze


tigerjack89
13-02-2012, 19:53
Ciao a tutti. Ennesimo problema per me, stavolta con gli alberi.
Il concetto generale degli alberi mi è ben chiaro, avendoli già studiati in java.
Tuttavia, ho ancora dei problemi.

Per esempio, in questo problema devo visualizzare in ordine decrescente di frequenza le stringhe dell'albero.
Ogni nodo è così strutturato

struct tnode
{
char *word; //la parola da memorizzare
int count; //il numero di occorrenze della parola
struct tnode *left; //un puntatore al nodo figlio sinistro
struct tnode *right; //e uno al destro
};

L'aggiunta di una parola all'albero riesco a gestirla bene, stessa cosa per quanto riguarda la stampa in ordine lessicografico delle parole. L'albero è fatto in modo che ogni nodo sinistro contiene solo parole lessicograficamente minori del nodo padre ed ogni nodo destro quelle maggiori.

Come faccio, a questo punto, a stampare invece non in base all'ordine lessicografico, ma a quello delle occorrenze di una data parola?
Ho provato in vari modi, ma tutti sbagliati :S. Eccone uno; in questo esempio la funzione searchmax cerca il valore massimo nella funzione, treeprintn dovrebbe stampare tutti i valori che hanno n occorrenze, mentre treeprintcount si occupa di passare i giusti valori alla funzione precedente.
Mentre la funzione di ricerca funziona alla perfezione, sulle altre due ho parecchi dubbi; eseguendo il programma, infatti, viene stampato solo il valore massimo.


void treeprintn(struct tnode *p, int n)
{
if (p != NULL && (p->count) == n)
{
printf("%3d %s\n", p->count, p->word);
treeprintn(p->left, n);
treeprintn(p->right, n);
}
}

void treecountprint(struct tnode *p)
{
int max = searchmax(p, 0);
int i = 1;
while (i <= max && p != NULL)
{
treeprintn(p, i);
i++;
}
}

int searchmax(struct tnode *p, int max)
{
if (p != NULL)
{
if ((p->count) > max)
max = p->count;
max = searchmax(p->left, max);
max = searchmax(p->right, max);
}

return max;
}

Ogni sorta di consiglio o suggerimento è sempre ben accetto :ciauz:

ramy89
13-02-2012, 19:59
Puoi fare una visita dfs (http://it.wikipedia.org/wiki/Depth-first_search) ricorsiva o iterativa se hai a disposizione una pila.
Durante la visita puoi mettere in un array tutte le occorrenze incontrate nei vari nodi (il valore count).
Alla fine della procedura hai questo array con tutte le occorrenze, lo ordini in senso decrescente.

tigerjack89
13-02-2012, 20:09
Originariamente inviato da ramy89
Puoi fare una visita dfs (http://it.wikipedia.org/wiki/Depth-first_search) ricorsiva o iterativa se hai a disposizione una pila.
Durante la visita puoi mettere in un array tutte le occorrenze incontrate nei vari nodi (il valore count).
Alla fine della procedura hai questo array con tutte le occorrenze, lo ordini in senso decrescente.
Non so se è quello che intendevi tu, ma ho risolto modificando semplicemente la funzione treeprintn in questo modo


void treeprintn(struct tnode *p, int n)
{
if (p != NULL)
{
if ((p->count) == n)
printf("%3d %s\n", p->count, p->word);
treeprintn(p->left, n);
treeprintn(p->right, n);
}
}
Ah, il potere di 5 minuti di pausa!! :D
Grazie mille comunque per l'aiuto. Come avresti implementato tu la funzione?

ramy89
13-02-2012, 20:29
Dici:



Per esempio, in questo problema devo visualizzare in ordine decrescente di frequenza le stringhe dell'albero.



Ma questa procedura:



void treeprintn(struct tnode *p, int n)
{
if (p != NULL)
{
if ((p->count) == n)
printf("%3d %s\n", p->count, p->word);
treeprintn(p->left, n);
treeprintn(p->right, n);
}
}

Stampa solo le parole che hanno n occorrenze.

tigerjack89
13-02-2012, 20:32
Originariamente inviato da ramy89
...cut...

E' proprio a questo che servono le altre due funzioni :)
Cerco prima il valore massimo, poi stampo di volta in volta tutti i nomi, partendo da quelli che hanno valore 1 fino ad arrivare a quelli col valore massimo.

ramy89
13-02-2012, 21:01
Certo che non è il massimo della velocità :confused:
Quanto è il valore massimo?
Potresti risolvere il tutto anche facendo una sola visita.

tigerjack89
13-02-2012, 21:27
Originariamente inviato da ramy89
Certo che non è il massimo della velocità :confused:
Quanto è il valore massimo?
Potresti risolvere il tutto anche facendo una sola visita.
Beh il valore massimo dipende da quante volte viene inserita la stessa parola.
In che modo si può fare una sola visita?

ramy89
15-02-2012, 13:56
Durante la visita dfs metti tutte le occorrenze in un array di interi.
Poi ordini l' array e stampi le occorrenze.

tigerjack89
15-02-2012, 16:52
Originariamente inviato da ramy89
Durante la visita dfs metti tutte le occorrenze in un array di interi.
Poi ordini l' array e stampi le occorrenze.
Mmm. Non riesco a seguirti. Forse perchè non ho idea di come si implementi una visita dfs :jam:

ramy89
15-02-2012, 17:13
C' è su wikipedia (leggi l' articolo), comunque ti faccio un esempio:


void dfs(struct tnode* p,int v[])
{
static int i=0;
if(p!=NULL)
{
v[i++]=p->count;
dfs(p->right,v);
dfs(p->left,v);
}
}


Parametri: N numeri degli elementi del grafo, i indice del prossimo nodo da inserire.E' ricorsiva ma si potrebbe anche fare con una pila.
Il grafo è un albero per cui ogni nodo viene visitato una volta.
Ora hai l' array disordinato, e hai chiamato N volte la procedura per ottenere tutti i valori dell' array.
Rimane solo da ordinarlo, se usi il qsort di stdlib.h in totale spendi n+nlogn.

Loading