Newsgroup: it.comp.lang.c++
Titolo: Puntatori ed allocazione di memoria

Salve a tutti. Sto avendo qualche problema con i puntatori. Ho creato
una lista dove ogni nodo è una struttura contenente un intero ed un
puntatore al nodo successivo. Ora ho creato una funzione che dovrebbe
ricostruire una nuova lista, cancellando l'ennesimo nodo, con n passato
come parametro. Ho pensato di dichiarare nella funzione un array di
altri nodi, facendo in modo di dare loro gli stessi dati di quelli
della lista di partenza. A quel punto li collego insieme dando
all'i-esimo nodo un puntatore all'(i+1)-esimo nodo. Alla fine della
funzione ritorno un puntatore al primo elemento della nuova lista. Il
problema a cui non avevo pensato è che questo array che ho utilizzato
ha visibilità locale, e quindi all'uscita dalla funzione viene
eliminato. Esiste un modo per risolvere questo problema? Il prototipo
della funzione che scrive deve essere questo (è un esercizio che lo
richiede): . Ho anche pensato di dichiarare l'array all'esterno della
funzione, ma non posso dato che la sua dimensione la calcolo
all'interno della funzione stessa. Voi come fareste?
Grazie mille.
Luca

 richiede): .
Scusate, non ho inserito il prototipo: Node* delete(int n, Node*list)
dove Node è una struttura con questa definizione: struct Node{int
info;Node*next;}.
Grazie.
Luca

 eliminato. Esiste un modo per risolvere questo problema? 
non capisco quale sia il problema... stai usando new?
void f(int* &ptr, int &size)
{
   size = (rand()%100) + 1;
   ptr = new int[size];
}
int main()
{
   srand(time(0));
   int *ptr = 0;
   int size = 0;
   f(ptr,size);	/**/
   for(int i=0;i<size;++i)
      ptr[i] = i;
   for(int i=0;i<size;++i)
      cout << ptr[i] << endl;
   delete [] ptr;
}
questo non ha nulla a che vedere con le liste, ma l'array viene allocato
in f() e non cessa di esistere quando si esce da f.
[ovviamente dopo new devi accertarti che la memoria e' stata allocata.]
il problema di fondo e' che credo che tu non dovresti allocare nessun
nuovo nodo, ma limitarti a cancellare quello che devi cancellare.
Tommaso
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

Luca ha scritto:

No, niente vettori. Questo costruisce una nuova lista:
Node* delete_node(int n, Node* list) {
	if( list == 0 ) return 0; // prima la cond. terminaz. ricorrenza
	if( n == 0 ) return delete_node( n-1, list->next );
	Node* ret = new Node();
	ret->info = list->info;
	ret->next = delete_node( n-1, list->next );
	return ret;
}
Mi sono divertito a dare una definizione leggermente diversa dalla
solita (ormai pallosa), permettendomi di usare anche i numeri negativi
per n. Se non ti piace, modificala adattandola alle tue esigenze...
... e spero che funzioni, perché non l'ho certo controllata al
calcolatore. :-) Ah, con n negativo non toglie nulla, ovviamente.
PS: fammi indovinare: corso di Programmazione 1? ;-)
PPS: nome infelice per una funzione, "delete"... non compila con quel
nome perché è una keyword del C++
-- 
Matteo Settenvini
FSF Associated Member
Email : 
mat...@member.fsf.org
-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCS d--(-) s+:- a-- C++ UL+++
P?>++ L+++>$ E+>+++ W+++ N++ o?
w--- O- M++ PS++ PE- Y+>++
PGP+++ t+ 5 X- R tv-- b+++ DI+
D++ G++ e h+ r-- y?
------END GEEK CODE BLOCK------

 }
L'idea sembra carina ed elegante.
Una nota personale: io tendo ad usare la ricorsione per strutture dati
come gli alberi binari ad esempio, dove con 2 alla 32 elementi
nell'albero (se bilanciato) la pronfondita ricorsiva e' 32.
Con una lista, se hai 2 alla 32 elementi, con una funzione come la tua,
la profondita' ricorsiva e' 2 alla 32. Ora la ricorsione usa lo stack
per sapere dove ritornare, in piu' ci sono le variabili locali che
dichiari sullo stack, etc... insomma un uso notevole dello stack;-)
Pensa solo a Node *ret, questo puntatore innocuo. Lo stack ne
conterrebbe 2 alla 32!
In pratica una ricetta per stack overflow.
Oltre a questo c'e' anche il leggero overhead di dover fare una chiamata
a funzione per ogni elemento della lista. Ma questo a mio avviso non e'
il problema maggiore.
Io, per quanto sicuramente meno elegante, userei una soluzione
iterativa. Ovvio che come esercizio, la soluzione ricorsiva va piu' che
bene per un esercizio universitario pero'!


 nodo che deve essere cancellato?!
Beh, anche io avrei fatto così, ma l'esercizio da precisamente quel
prototipo, quindi non mi pare che avrebbe comunque senso non creare una
nuova lista, dato che ritorna il puntatore. Comunque si specifica anche
nuova lista.
Grazie per la soluzione, ho fatto proprio così alla fine.
Luca

 nome perché è una keyword del C++
Si, lo so. Ma la consegna era quella. Ovviamente per fare le prove
cambiavo il nome.
Ciao e grazie ancora.
Luca

 Grazie per la soluzione, ho fatto proprio cosě alla fine.
pero' dubito fortemente che usare un array di Nodi sia un buona
soluzione al tuo problema.


 Tommaso


 
Se vuoi un consiglio, prova a riscrivere la stessa funzione passando due
riferimenti al posto che due parametri per valore.


 Non male per una "semplice" listina! :-D
Il problema e' che la tua funzione con ogni probabilita' si pianta
molto ma molto prima.
 
Ciao,
Nicola

> avviso non e' il problema maggiore.
Come ti avevo pre-annunciato, la velocita' di esecuzione e' il problema
minore.
La mia versione iterativa e' solo un 25% piu' veloce della tua
ricorsiva.
Se vuoi fare delle prove ti posto la versione iterativa che ho usato,
scritta male ed in fretta; puoi migliorarla tu se vuoi.
La funzione e' appositamente lunga (per rendere piu' snello il for
principale).
<CODE>
Node* CreaNuovaSenzaN(Node *list, int n)
{ 
   Node *ret=0; 
   // se c'e' almeno un elemento.     
   if(list){
      Node *tmp=0;      
      int i=0;
      // se n==0 caso salto il primo nodo:
      if(!n){list=list->next;++i;}
      // primo nodo da mettere in nuova lista:
      tmp = ret = new Node;  
      tmp->info = list->info; 
      list=list->next;
      ++i;
      // altri nodi da mettere:
      for(;list;list=list->next,++i){ 
         if(i==n) continue;
         tmp->next = new Node; 
         tmp = tmp->next; 
         tmp->info = list->info; 
      }
      // termino la lista:    
      if(tmp) tmp->next = 0;                 
   } 
   return ret; 
}
</CODE>
Ok, forse tutto questo era piu' interessante su di un NG di C ...


 </CODE>
Non ci vuole molto a migliorarla visto che c'e' un errore che si
verificare in un caso specifico.
Ovviamente questo dimostra solo che quando possibile conviene usare i
containers STL.
Tommaso
P.S. ad ogni modo i dati riportati rimangono attendibili.
