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

[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]

Originariamente inviato da 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.

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]

Originariamente inviato da 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;

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

[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]

Originariamente inviato da mjordan

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

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

[mjordan]

Originariamente inviato da 71104

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

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

[mjordan]

Originariamente inviato da 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);
}
}

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]

Originariamente inviato da 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??

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]

Originariamente inviato da mjordan

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)