Reverse di una lista??

[giack83]

Buongiorno a tutti,

mi potreste indicare perpiacere, il codice per effettuare un REVERSE di una lista di interi classica?

Grazie mille per l'aiuto.

[leadergl]

l'ho scritto di getto ma credo funzioni:

typedef struct tipolista
{
int elem;
struct tipolista *next;
}lista;

//inverta una lista concatenata
lista *invertList(lista *top)
{
lista *in;
lista *mid;
lista *last;

in=top;
mid=top->next;
last=mid->next;

if (top!=NULL)
{
do
{
mid->next=in;
top->next=last;
in=mid;
mid=last;
if (last!=NULL) last=last->next;
} while (last!=NULL);
}
return in;
}

[^TiGeRShArK^]

ehm...
non hai specificato in ke linguaggio...
in java ad esempio basta utilizzare Collection.sort(lista) e poi scorrersi la lista al contrario oppure Collection.sort(lista, compareOperator) per ottenere la lista ordinata nell'ordine voluto.....

[AnonimoVeneziano]

#include <list>
using namespace std;

int main(int argc, char *argv[])
{
list<int> lista;
lista.push_front(1);
lista.push_front(2);
lista.push_front(3);

lista.reverse();

for(list<int>::iterator it = list.begin(); it != list.end(); it++)
cout << *it << endl;

return 0;
}


:stordita:

[giack83]

Grazie per le risposte che mi avete dato, :-)

una piccola cosa ancora.....
ho a che farer con gli alberi. Crearli sono capace ma mi potete dire com'è il codice se dato
un albero binario volgio calcolare l'altezza della'lbero(cioè la profondita) ed la distanza tra due nodi perpiacere?

sono possibili tali operazioni? se si com'è il codice? non riesco a caire come si riesce a fare.

Grazie mille.

[mjordan]

Grazie per le risposte che mi avete dato, :-)

una piccola cosa ancora.....
ho a che farer con gli alberi. Crearli sono capace ma mi potete dire com'è il codice se dato
un albero binario volgio calcolare l'altezza della'lbero(cioè la profondita) ed la distanza tra due nodi perpiacere?

sono possibili tali operazioni? se si com'è il codice? non riesco a caire come si riesce a fare.

Grazie mille.

La parola "alberi" è un po generica. Suppongo tu stia parlando di classici "alberi binari di ricerca", la cui altezza corrisponde alla profondità massima raggiunta da un nodo (il nodo che ha distanza massima dalla radice definisce l'altezza dell'albero, per intenderci). Per trovarla basta che implementi una funzione (ricorsiva o iterativa) che prosegui dalla radice fino all'ultimo nodo disponibile nei due sottoalberi disponibili. Già implementando un qualsiasi algoritmo di attraversamento di un albero puoi arrivare allo scopo. Lo stesso dicasi per la distanza.

[71104]

non è necessario che siano alberi binari di ricerca affinché si possano realizzare algoritmi per calcolarne l'altezza massima e la distanza tra due nodi: è sufficiente che siano alberi binari ;)
se poi sono di ricerca non cambia niente per quei due algoritmi; infine se sono AVL allora il primo algoritmo penso che diventi più semplice perché forse si può trovare la maniera di calcolarne l'altezza in tempo O(log(n)) anziché O(n), con n = numero di nodi.

[mjordan]

non è necessario che siano alberi binari di ricerca affinché si possano realizzare algoritmi per calcolarne l'altezza massima e la distanza tra due nodi: è sufficiente che siano alberi binari ;)
se poi sono di ricerca non cambia niente per quei due algoritmi;


Mi sono espresso male, non intendevo dire che si possono fare solo con gli alberi di ricerca. Solo una supposizione, quindi. Supposizione motivata dalla seguente riflessione. Gli alberi binari, a parte il grado due dell'albero, consente l'inserimento dei nodi in qualsiasi posizione. In altre parole, l'ordine dei nodi in un albero binario non è importante. In genere, in informatica, gli alberi binari semplici vengono utilizzati esclusivamente come rappresentazione per gli heap a loro volta usati come code di priorità (heap min/max). Utilizzare un normale albero binario come struttura dati per effettuare le classiche operazioni non ha senso, poichè inserimento, cancellazione e ricerca richiedono un tempo pari a O(n), non diverso che usare una semplice lista concatenata. Da cui la supposizione dell'albero binario di ricerca (semplice o sue varianti). Che poi, soffermandomi un attimo, "distanza fra due nodi" che significa in un albero... La distanza si calcola sempre con un nodo ed indica il numero di nodi che intercorrono fra il nodo in questione e la radice dell'albero. Io questo intendevo prima. Cioè il concetto di distanza tradizionale.


infine se sono AVL allora il primo algoritmo penso che diventi più semplice perché forse si può trovare la maniera di calcolarne l'altezza in tempo O(log(n)) anziché O(n), con n = numero di nodi.


In che senso scusa... Calcolare l'altezza di un albero è sempre O(n), indipendentemente dal tipo di albero :mbe:

[giack83]

Grazie per le risposte,

cmq si è un albero binario di ricerca indicato come:

struct cella{

[giack83]

Grazie per le risposte,

è un albero binario di ricerca indicato con:

struct cella{

int valore;
struct cella *dx;
struct cella *sx;
};

mi potreste scrivere il codice perpiacere? xche non so proprio come fare queste due funzioni di calcolo profondità e distanza tra due nodi..... perpiacere......

[71104]

In che senso scusa... Calcolare l'altezza di un albero è sempre O(n), indipendentemente dal tipo di albero :mbe: era solo un'idea: se l'albero è AVL allora vuol dire che in ogni nodo l'altezza del sottoalbero sinistro differisce da quella del destro al più di un fattore associato al nodo stesso (fattore di bilanciamento) che può assumere al massimo valore assoluto 1; di conseguenza penso che (idea non verificata) per calcolare l'altezza massima di un albero AVL è sufficiente effettuare un qualsiasi percorso radice-foglia (tempo O(log(n))) contando i nodi e tenendo anche conto di eventuali differenze di altezza indicate nei fattori di bilanciamento; se per esempio sono arrivato al kappesimo nodo, quindi ho contato un'altezza k, e vedo che il suo fattore di bilanciamento è 1, allora vorrà dire che il sottoalbero sinistro è più alto del destro, percui per contare un'altezza corretta dovrò scendere a sinistra.

EDIT: un attimo che provo a scriverlo, così è più chiaro...

EDIT2: eccolo qua:

typedef struct _NODE {
int Key;
int Bal;
struct _NODE *Left, *Right;
} NODE, *TREE;

int Height(TREE Tree) {
if (!Tree) {
return 0;
}
if (Tree->Bal < 0) {
return Height(Tree->Right) + 1;
}
return Height(Tree->Left) + 1;
}

sarebbe interessante provarlo e vedere se funziona veramente... il tempo è sicuramente O(log(n)) ;)

[71104]

ed eccolo qua anche in forma iterativa:

typedef struct _NODE {
int Key;
int Bal;
struct _NODE *Left, *Right;
} NODE, *TREE;

int Height(TREE Tree) {
int Res = 0;
for (TREE Node = Tree; Node; ) {
Res++;
if (Node->Bal < 0) {
Node = Node->Right;
}
else {
Node = Node->Left;
}
}
return Res;
}

decisamente preferibile.

[alexanderf]

Salve ragazzi cio sto programmino che mi visualizza i numeri primipero no riesco a far visualizzare i suoi divisori esempio cio 3 e divisible solo con 3 oppure cio 4 e divisibile con 2 e 4
public class NumeriPrimi{
static int primo;
static int i;
public static String numeroPrimo(int primo){
if(primo==2){
return"è un numero primo";
}else if (primo==3){
return "è un numero primo";
}else if (primo==5){
return "è un numero primo";
}

if ((primo%2)==0) {

return"non è numero primo";
}else if ((primo%3)==0){
return"non è un numero primo";
}else if ((primo%5)==0){
return"non è un numero primo";
}
return"é un numero primo";

}

public static void main(String args[])
{
//NumeriPrimi primo = new NumeriPrimi();
String risposta=NumeriPrimi.numeroPrimo(3) System.out.println(risposta);
}
} :muro: :muro: :muro:

[mjordan]

sarebbe interessante provarlo e vedere se funziona veramente... il tempo è sicuramente O(log(n)) ;)

Come fai a dire che è O(log(n))?

[mjordan]

Salve ragazzi cio sto programmino che mi visualizza i numeri primipero no riesco a far visualizzare i suoi divisori esempio cio 3 e divisible solo con 3 oppure cio 4 e divisibile con 2 e 4
public class NumeriPrimi{
static int primo;
static int i;
public static String numeroPrimo(int primo){
if(primo==2){
return"è un numero primo";
}else if (primo==3){
return "è un numero primo";
}else if (primo==5){
return "è un numero primo";
}

if ((primo%2)==0) {

return"non è numero primo";
}else if ((primo%3)==0){
return"non è un numero primo";
}else if ((primo%5)==0){
return"non è un numero primo";
}
return"é un numero primo";

}

public static void main(String args[])
{
//NumeriPrimi primo = new NumeriPrimi();
String risposta=NumeriPrimi.numeroPrimo(3) System.out.println(risposta);
}
} :muro: :muro: :muro:

Qui' sei off-topic. Apri un thread e usa il tag code per postare il codice.

[giack83]

Salve,

il codice scritto da "leadergl" ho provto a farlo girare ma se ristampo la mia lista (originale: 4->5->8->9......) mi viene stampato solamente :

4->9, cioè il primo elemento e l'ultimo elemento.

xche?

avrei bisogno che ad esempio data la lista:
4->5->8->9
e quindi stampa 4,5,8,9, con il reverse mi dovrebbe stampare l'inverso quindi 9,8,5,4........ come si puo fare??

infine, per la profondita ho risolto grazie, ma sempre per alberi binari è possibile Calcolare la distanza tra due nodi? cioè riempiamo l'albero con i valori, poi ne scegliamo due a nostro piacimento tra quelli inseriti e calcoliamo la distanza....

mi potreste dire tale funzione?

Grazie cmq per le risposte che mi avete dato, siete stati gentilissimi.

[mjordan]

Salve,

il codice scritto da "leadergl" ho provto a farlo girare ma se ristampo la mia lista (originale: 4->5->8->9......) mi viene stampato solamente :

4->9, cioè il primo elemento e l'ultimo elemento.

xche?

avrei bisogno che ad esempio data la lista:
4->5->8->9
e quindi stampa 4,5,8,9, con il reverse mi dovrebbe stampare l'inverso quindi 9,8,5,4........ come si puo fare??


Perchè non posti il codice completo anche del codice che usi per creare la lista (utilizzando il tag quote)?


infine, per la profondita ho risolto grazie, ma sempre per alberi binari è possibile Calcolare la distanza tra due nodi? cioè riempiamo l'albero con i valori, poi ne scegliamo due a nostro piacimento tra quelli inseriti e calcoliamo la distanza....

mi potreste dire tale funzione?

Grazie cmq per le risposte che mi avete dato, siete stati gentilissimi.

Ma che utilità dovrebbe avere? La distanza si calcola dalla radice non da due nodi. Se un nodo si trova nel sottoalbero sinistro, che distanza dovrebbe avere da un nodo che sta nel sottoalbero destro? Non ha senso.

[Qu@ker]

Prova un po'...

lista *inverti(lista *l)
{
lista *newl = NULL;

if (! l || ! l->next)
return l;
if (! l->next->next)
newl = l->next;
else
newl = inverti(l->next);
l->next->next = l;
l->next = NULL;

return newl;
}

[71104]

Come fai a dire che è O(log(n))? per te invece la stima quant'è?

[^TiGeRShArK^]

secondo i miei ricordi dovrebbe essere effettivamente log(n) in qunato il numero di nodi presenti nell'albero cresce esponenzialmente con l'aumentare dell'altezza...
quindi scorrendo solo l'altezza di un ramo si può eseguire l'algoritmo in un tempo log(n) (con n ovviamente inteso il numero totale di nodi)

[AnonimoVeneziano]

Dovrebbe essere log(n) anche per me , perchè l'altezza di un albero bilanciato con "n" nodi è generalmente "log(n)" e quindi bisogna fare "log(n)" passaggi per arrivare in fondo all' albero

Ciao

EDIT: Se mancasse la variabile Bal nel nodo dell' albero allora sarebbe necessario farlo in "n" passaggi

[^TiGeRShArK^]

EDIT: Se mancasse la variabile Bal nel nodo dell' albero allora sarebbe necessario farlo in "n" passaggi
si infatti... nel caso di albero non bilanciato è o(n).....

[giack83]

Guardate vi ho allegato il file in txt dove dentro c'è il codice della mia lista semplice come mi avevate chiesto....

se volete potete modificarlo introducendo la funzione Reverse della lista....

cosi dopo ci guardo e riesco a capire. Grazie mille.

[Qu@ker]

#include <stdio.h>
#include <stdlib.h>

typedef struct cella {
int val;
struct cella *next;
} cella;

void stampa(cella *t)
{
for (; t; t = t->next)
printf("%d ", t->val);
putchar('\n');
}

cella *inverti(cella *l)
{
cella *newl = NULL;

if (! l || ! l->next)
return l;
newl = (l->next->next) ? inverti(l->next) : l->next;
l->next->next = l;
l->next = NULL;

return newl;
}

int main()
{
int i;
cella *testa = NULL;

for (i = 0; i < 5; i++) {
cella *newcella = malloc(sizeof(struct cella));
scanf("%d", &newcella->val);
newcella->next = testa;
testa = newcella;
}
stampa(testa);
testa = inverti(testa);
stampa(testa);

return 0;
}

[mjordan]

secondo i miei ricordi dovrebbe essere effettivamente log(n) in qunato il numero di nodi presenti nell'albero cresce esponenzialmente con l'aumentare dell'altezza...
quindi scorrendo solo l'altezza di un ramo si può eseguire l'algoritmo in un tempo log(n) (con n ovviamente inteso il numero totale di nodi)

Il numero di nodi massimo contenibile da un albero binario di altezza h è 2^h - 1 nodi totali. Tuttavia non consideri che trovare l'altezza di un albero implica lo scorrimento di tutti i nodi, per vedere quale è che si trova alla profondità massima e cioè O(n). Che l'altezza in media in un albero bilanciato sia O(log(n)) è un conto, ma il calcolo dell'altezza di un albero non corrisponde alla visita del percorso piu' lungo.

[mjordan]

Dovrebbe essere log(n) anche per me , perchè l'altezza di un albero bilanciato con "n" nodi è generalmente "log(n)" e quindi bisogna fare "log(n)" passaggi per arrivare in fondo all' albero

Ciao


Fai log(n) passaggi per arrivare in fondo all'albero se sai già qual'è il percorso a profondità massima. Nel caso lo devi trovare, come fai a dire che ci vogliono log(n) passaggi?

[71104]

[...]il calcolo dell'altezza di un albero non corrisponde alla visita del percorso piu' lungo. come no...? :mbe:
stiamo parlando di alberi binari?

[71104]

Fai log(n) passaggi per arrivare in fondo all'albero se sai già qual'è il percorso a profondità massima. Nel caso lo devi trovare, come fai a dire che ci vogliono log(n) passaggi? 1) per te è lecito se io parlando di alberi binari il "percorso a profondità massima" lo chiamo "il percorso più lungo"?
2) per trovare il "percorso a profondità massima", o il "percorso più lungo", in un albero binario qualsiasi ci impiego un tempo lineare nel caso peggiore, ma quando si tratta di alberi AVL se parto dalla radice a ogni passo so già se scendere a destra o a sinistra grazie al fattore di bilanciamento, quindi trovo subito il percorso in questione.

[mjordan]

come no...? :mbe:
stiamo parlando di alberi binari?

Si stiamo parlando di alberi binari. Il fatto è che il "calcolo" della profondità dell'albero implica trovarla, non visitarla. Nel trovarla, devi effettuare delle visite anche sulle altre foglie dell'albero. Ecco perchè "trovare l'altezza di un albero" non equivale a "visitare il cammino piu' lungo", semplicemente perchè il cammino piu' lungo non lo sai a priori ma, appunto, lo devi trovare.
Per il tuo secondo post non avevo capito che stavate parlando di AVL con fattore di bilanciamento. In ogni caso qualcuno mi deve spiegare perchè tutte le funzioni che calcolano l'altezza di un albero che trovo in alcune librerie (anche per alberi bilanciati) dicono che l'operazione richiede O(n).

[AnonimoVeneziano]

Fai log(n) passaggi per arrivare in fondo all'albero se sai già qual'è il percorso a profondità massima. Nel caso lo devi trovare, come fai a dire che ci vogliono log(n) passaggi?

Beh, ma col trucchetto della variabile "Bal" che 71104 ha messo nella struttura del nodo (mossa abbastanza ingegnosa) fa in modo di capire "da che parte" stia il percorso con profondità massima, quindi alla fine è log(n)

Ciao
EDIT:

PS: Nottambulo anche te? :D

[mjordan]

Beh, ma col trucchetto della variabile "Bal" che 71104 ha messo nella struttura del nodo (mossa abbastanza ingegnosa) fa in modo di capire "da che parte" stia il percorso con profondità massima, quindi alla fine è log(n)

Ciao
EDIT:

PS: Nottambulo anche te? :D

Si, non avevo capito che stavate parlando anche di fattore di bilanciamento.
Si domani non ho una mazza da fare e mi dedico al relax :D

[71104]

LOL, siamo in 3 :D
be' comunque mjordan come ti è stato spiegato nel caso degli alberi AVL "trovare" il percorso più lungo (la cui lunghezza corrisponde all'altezza, penso che questo ormai sia chiaro) corrisponde a "visitarlo" perché posso "predirlo" grazie al fattore di bilanciamento (campo che ho chiamato "Bal", che sta per "balance") che mi dice dove devo "girare".
per quanto riguarda le librerie che hai visto te vorrà dire che sono state scritte da niubbi che ti devo dire... :p
oppure il mio algoritmo non funziona, ma prima di ammettere una simile affermazione ne vorrei una prova, un esempio di albero AVL per il quale quell'algoritmo restituisce un'altezza errata :)
non che io escluda la possibilità di aver sbagliato eh...

[mjordan]

LOL, siamo in 3 :D
be' comunque mjordan come ti è stato spiegato nel caso degli alberi AVL "trovare" il percorso più lungo (la cui lunghezza corrisponde all'altezza, penso che questo ormai sia chiaro) corrisponde a "visitarlo" perché posso "predirlo" grazie al fattore di bilanciamento (campo che ho chiamato "Bal", che sta per "balance") che mi dice dove devo "girare".


Ho capito, sono 3 volte che lo dico che non avevo capito che stavate parlando di fattore di bilanciamento. ;)


per quanto riguarda le librerie che hai visto te vorrà dire che sono state scritte da niubbi che ti devo dire... :p


Non credo.


oppure il mio algoritmo non funziona, ma prima di ammettere una simile affermazione ne vorrei una prova, un esempio di albero AVL per il quale quell'algoritmo restituisce un'altezza errata :)


Puoi farla da solo anche in modo abbastanza empirico inserendo un campo destinato all'altezza nella radice e modificandolo durante la costruzione dell'albero, quando l'altezza in quel caso è nota. Poi costruisci una milionata di alberi in modo random con delle asserzioni che confrontano quanto tirato fuori dalla funzione e quello che c'è nel campo destinato all'altezza. Lo chiamerei un approccio "brute force testing" :asd:

non che io escluda la possibilità di aver sbagliato eh...

Ci mancherebbe.