Delphi & Pascal: Help liste

[gokan]

Ciao a tutti, mi hanno assegnato qualche esercizio sulle liste.
Il primo consite nel costruire una lista ed inserire vari valori.Poi l'utente inserisce un valore da ricercare nella lista ed eventualmente lo cancella.Ho qualche problema nella funzione eliminazione.Mi potreste aiutare

program lista2;
{$APPTYPE CONSOLE}
uses SysUtils;

type
  puntatore= ^elemento;
//Struttura degli elementi della lista
  elemento=record
     inf:integer;
     pun:puntatore;
   end;

(*La funzione crea_lista2 restituisce al programma principale il riferimento
  al primo elem. della lista, che è di tipo puntatore al record elemento*)
Function crea_lista2: puntatore;
var
  p,paus: puntatore;    (*p=punt. alla testa e paus=punt. ausiliario che*)
                          (*permette la creazione deglie elem. succ. della lista
                          senza perdere il punt. iniziale*)
  x: integer;      //Lo stesso tipo del campo inf (cioè integer)

begin
writeln;
write('Inserisci un''informazione(0 per finire): ');
readln(x);

if x=0 then p:=NIL      //se x=0 la lista è vuota(si chiude)
 else begin
//Creazione del primo elemento
new(p);            //Allocazione di spazio necessario a contenere un record di
                   //tipo elemento

p^.inf:=x;         (*Si copia il valore nella parte informazione di p*)
paus:=p;           //Sia p che paus puntano al primo elem. della lista

{Ora che abbiamo creato il rpimo elemento, si va avanti così finchè non viene
 inserito zero(questo è gestito dal ciclo while qui sotto}

while x<>0 do begin
writeln;
write('Inserisci un''informazione(0 per finire): ');
readln(x);

if x<>0 then begin
//Creazione dell'elemento successivo
new(paus^.pun);    (*Viene creato un nuovo elemento della lista, collegato al
                     precedente.Il puntatore all'elem. creato da new viene
                     assegnato al campo pun del record puntato da paus*)

paus:=paus^.pun;   //Viene aggiornato paus, in modo da puntare all'elem. succ.
paus^.inf:=x;      //La nuova informazione viene inserita nel campo corrispond.
end
else
  paus^.pun:=NIL;    //Marca di fine lista
  end;
 end;
crea_lista2:=p;    //Viene passato al chiamante il valore di p, punt.alla testa
end;

Function eliminazione(p:puntatore;var ele:integer):puntatore;
var
  paus:puntatore;     //puntatore ausiliario

begin
write('Inserisci l''elemento da eliminare: ');
readln(ele);
 begin
 paus:=p;
 while paus<>NIL do begin
   if paus^.inf<>ele then paus:=paus^.pun
   else dispose(paus);
                 end;
 end;
eliminazione:=p;
end;

(*Procedura ricorsiva per la visualizzazione della lista*)
Procedure vis2_lista(p:puntatore);
begin
 if p<>NIL then begin
 write(p^.inf);
 write('---> ');
 vis2_lista(p^.pun);
 end
else write('NIL');
end;



(*MAIN*)
var punt_lista: puntatore; //puntatore alla testa della lista
    valore:integer;

begin

 punt_lista:=crea_lista2;
 punt_lista:=eliminazione(punt_lista,valore);
 vis2_lista(punt_lista);

readln;
end.

[Reale_Augello]

... vorrei approfittare dell'occasione per fare spam, ma nella sezione download del mio sito (http://www.antoniofittipaldi.it/download/download.htm) trovi numerose realizzazioni di lista in C: ricordo anche di aver implementato delle procedure di cancellazione. Magari possono esserti utili per schiarirti le idee.

Ciao !

[gokan]

Originariamente inviato da Reale_Augello
... vorrei approfittare dell'occasione per fare spam, ma nella sezione download del mio sito (http://www.antoniofittipaldi.it/download/download.htm) trovi numerose realizzazioni di lista in C: ricordo anche di aver implementato delle procedure di cancellazione. Magari possono esserti utili per schiarirti le idee.

Ciao ! :)

Il mio C è un'pò arruginito..preferisco spremere le meningi ancora un'pò..
cmq grazie

Con l'occasione posto senza le faccine rompiscatole:

program lista2;
{$APPTYPE CONSOLE}
uses SysUtils;

type
  puntatore= ^elemento;
//Struttura degli elementi della lista
  elemento=record
     inf:integer;
     pununtatore;
   end;

(*La funzione crea_lista2 restituisce al programma principale il riferimento
  al primo elem. della lista, che è di tipo puntatore al record elemento*)
Function crea_lista2: puntatore;
var
  p,paus: puntatore;    (*p=punt. alla testa e paus=punt. ausiliario che*)
                          (*permette la creazione deglie elem. succ. della lista
                          senza perdere il punt. iniziale*)
  x: integer;      //Lo stesso tipo del campo inf (cioè integer)

begin
writeln;
write('Inserisci un''informazione(0 per finire): ');
readln(x);

if x=0 then p:=NIL      //se x=0 la lista è vuota(si chiude)
 else begin
//Creazione del primo elemento
new(p);            //Allocazione di spazio necessario a contenere un record di
                   //tipo elemento

p^.inf:=x;         (*Si copia il valore nella parte informazione di p*)
paus:=p;           //Sia p che paus puntano al primo elem. della lista

{Ora che abbiamo creato il rpimo elemento, si va avanti così finchè non viene
 inserito zero(questo è gestito dal ciclo while qui sotto}

while x<>0 do begin
writeln;
write('Inserisci un''informazione(0 per finire): ');
readln(x);

if x<>0 then begin
//Creazione dell'elemento successivo
new(paus^.pun);    (*Viene creato un nuovo elemento della lista, collegato al
                     precedente.Il puntatore all'elem. creato da new viene
                     assegnato al campo pun del record puntato da paus*)

paus:=paus^.pun;   //Viene aggiornato paus, in modo da puntare all'elem. succ.
paus^.inf:=x;      //La nuova informazione viene inserita nel campo corrispond.
end
else
  paus^.pun:=NIL;    //Marca di fine lista
  end;
 end;
crea_lista2:=p;    //Viene passato al chiamante il valore di p, punt.alla testa
end;

Function eliminazione(puntatore;var ele:integer)untatore;
var
  pausuntatore;     //puntatore ausiliario

begin
write('Inserisci l''elemento da eliminare: ');
readln(ele);
 begin
 paus:=p;
 while paus<>NIL do begin
   if paus^.inf<>ele then paus:=paus^.pun
   else dispose(paus);
                 end;
 end;
eliminazione:=p;
end;

(*Procedura ricorsiva per la visualizzazione della lista*)
Procedure vis2_lista(puntatore);
begin
 if p<>NIL then begin
 write(p^.inf);
 write('---> ');
 vis2_lista(p^.pun);
 end
else write('NIL');
end;



(*MAIN*)
var punt_lista: puntatore; //puntatore alla testa della lista
    valore:integer;

begin

 punt_lista:=crea_lista2;
  punt_lista:=eliminazione(punt_lista,valo
re);
 vis2_lista(punt_lista);

readln;
end.

[alka]

Secondo me, non è molto costruttivo che tu scriva sul forum tutto il codice dell'algoritmo. Dovresti cercare di implementarlo e di trovare esattamente in quale punto ci sono dei problemi, chiedendo poi opinioni sul metodo di risoluzione.

Dalle informazioni che hai fornito, l'unico modo per aiutarti è scriversi tutto il codice all'interno dell'ambiente di sviluppo, lanciarlo e debuggare passo passo, un processo relativamente lungo e quindi difficile da attuare...ecco perchè rispondono in pochi alla tua richiesta.

Dovresti prediligere la spiegazione del problema a livello verbale, invece di riportare tutto il codice dicendo "questo è il codice per la mia lista, ma non funziona...cosa c'è che non va?".

Spero di averti dato un'indicazione utile per il futuro.

Ciao!

[gokan]

Originariamente inviato da alka
Secondo me, non è molto costruttivo che tu scriva sul forum tutto il codice dell'algoritmo. Dovresti cercare di implementarlo e di trovare esattamente in quale punto ci sono dei problemi, chiedendo poi opinioni sul metodo di risoluzione.

Dalle informazioni che hai fornito, l'unico modo per aiutarti è scriversi tutto il codice all'interno dell'ambiente di sviluppo, lanciarlo e debuggare passo passo, un processo relativamente lungo e quindi difficile da attuare...ecco perchè rispondono in pochi alla tua richiesta.

Dovresti prediligere la spiegazione del problema a livello verbale, invece di riportare tutto il codice dicendo "questo è il codice per la mia lista, ma non funziona...cosa c'è che non va?".

Spero di averti dato un'indicazione utile per il futuro.

Ciao! :ciauz:

Io pensavo che inserendo tutto il codice, qualcuno tra gli utenti del forum, che magari ha i miei stessi problemi, potrebbe anche prendere spunto dalle mie funzioni e procedure:bhò:

Ritornando al mio problema...So che solo la funzione di eliminazione ha dei problemi,le altre funzioni le ho già usate in altri programmini.
Innanzitutto ammettiamo che la lista è composta in questo modo:

punt_testa-->4-->1-->4-->3-->NIL

In pratica, l'utente inserisce il valore che vuole eliminare dalla lista.Se io voglio eliminare dalla lista il valore 4 la nuova lista da visualizzare sarà:

punt_testa-->1-->3-->NIL

Io pensavo di far inserire il valore da eliminare all'utente; a questo punto si prende un puntatore ausiliari e si fa puntare anch'esso alla testa della lista (come fa già p); poi si comincia a scandire la lista con paus (in modo da lasciare che p punti sempre alla testa della lista, senza perderlo).Quando il campo inf dell'elemento puntato da paus è diverso da ele (il valore che vogliamo eliminare) si scorre la lista fino a NIL, segue che il valore
non è presente in lista; ALTRIMENTI, se è stato trovato liberiamo (dispose) paus.
Infine viene passato al chiamante il valore di p puntatore alla testa.

Function eliminazione (p:puntatore;var ele:integer):puntatore;
var
  paus:=puntatore;     //puntatore ausiliario

begin
write('Inserisci l''elemento da eliminare: ');
readln(ele);
 begin
 paus:=p;
 while paus<>NIL do begin
   if paus^.inf<>ele then paus:=paus^.pun
   else dispose(paus);
                 end;
 end;
eliminazione:=p;
end;

Penso che il problema sia al momento del passaggio di p alla funzione.
CChe ne dite?

[alka]

Credo che il mio suggerimento sia stato molto utile...infatti ora va molto meglio.

Non ho avuto il tempo di stendere codice di esempio ma dalle informazioni che mi hai fornito sulla struttura della tua lista e conoscendo come dovrebbe avvenire l'eliminazione di un elemento, credo di aver trovato l'errore.

Ho notato che quando individui il valore da eliminare, rimuovi semplicemente il "tassello" dalla lista con Dispose: ciò è corretto, ma manca un passaggio. Ogni elemento della lista contiene il valore intero da ospitare e l'indirizzo dell'elemento successivo. Seguendo il tuo procedimento, quando l'elemento da cancellare viene trovato, esso viene deallocato, ma non c'è il codice che permetta di mantenere solida la lista impostando l'elemento precedente a quello trovato affinchè punti all'elemento successivo a quello trovato.

Ciascun elemento possiede il riferimento al successivo; se elimini un elemento, quello prima non deve più puntare a quello eliminato, ma a quello immediatamente successivo.

Il mio consiglio è questo: quando scandisci la lista alla ricerca dell'elemento da cancellare, memorizzi ad ogni iterazione il puntatore all'elemento precedente di quello che stai analizzando. Se hai trovato l'elemento da cancellare, utilizzi il puntatore dell'elemento precedente facendo in modo che esso punti all'elemento che segue quello che stai per cancellare con Dispose().

In questo modo, mantieni il regolare concatenamento della lista dinamica.

Ciao!

[gokan]

Originariamente inviato da alka
Il mio consiglio è questo: quando scandisci la lista alla ricerca dell'elemento da cancellare, memorizzi ad ogni iterazione il puntatore all'elemento precedente di quello che stai analizzando. Se hai trovato l'elemento da cancellare, utilizzi il puntatore dell'elemento precedente facendo in modo che esso punti all'elemento che segue quello che stai per cancellare con Dispose().

Il problema è questo: non riesco a collegare l'elemento che precede l'elemento da eliminare e quello che lo segue.

p-->2-->3-->6-->NIL

Se elimino il 3 (solo con il dispose):

p-->2--> -->6-->NIL

In pratica il 2 e il 6 non sono collegati.Dovrei fare così:
p-->2-->6-->NIL

Ma come in termini di codice? Quando lavori con una pila (LIFO= Last In First Out) è facile fare l'eliminazione, perchè l'elemento da eliminare è quello puntato dalla testa (p).Per collegare p all'elem. succ. basta fare p:=p^.pun.
Ma non riesco a capire come devo tenere unita tutta la lista quando elimino un elemento che si trova in altre posizioni.

[alka]

Come ti ho detto, a mio parere devi introdurre una nuova variabile che, ad ogni iterazione del ciclo while, si memorizzi il puntatore all'elemento precedente, cioè quello assunto dalla variabile puntatore ausiliaria prima che questa venga riassegnata al nuovo indirizzo che corrisponde all'elemento successivo.

Quando individuerai l'elemento che deve essere eliminato, avrai a tua disposizione anche l'indirizzo dell'elemento precedente; prima di procedere con la rimozione fisica dell'elemento tramite la procedura Dispose, dovrai aggiornare il campo dell'elemento precedente affinchè punti all'elemento che segue quello che stai per cancellare.

...
pPrev := nil;
pAus := pLista;
while pAus <> nil do
begin
  if pAus^.Inf = Num then
  begin
    if pPrev <> nil then
      pPrev^.Pun := pAus^.Pun
    else
      pLista := pAus^.Pun;
    Dispose(pAus);
    pAus := nil;
  end
  else begin
    pPrev := pAus;
    pAus := pAus.Pun;
  end;
end;
...

Il codice è a puro titolo esemplificativo (non l'ho verificato, ma dovrebbe funzionare).

In particolare, mostra come mantenere il riferimento all'elemento precedentemente puntato e utilizzarlo per correggere i riferimenti degli elementi in fase di eliminazione.

Credo che tu debba anche passare sempre come parametro var il puntatore di inizio della lista poichè nel caso venga eliminato il primo elemento, anche quell'indirizzo deve essere modificato e restituito.

Ciao!

[gokan]

Innanzitutto grazie,la funzione è ok.
Volevo qualche delucidazione per qualche riga particolare di codice:
1) pPrev := NIL;

1)Nei miei programmini mettendo pLista a NIL significava che la lista è vuota e che quindi si chiude.Mettere questo puntatore a NIL è una sorta di inizializzazione?

2)if pPrev<> NIL then
pPrev^.pun := pAus^.pun

2)Non ho capito a cosa serve questo controllo se già noi abbiamo fatto pPrev:=NIL e sappiamo già che non è diverso da NIL

3)pAus:=NIL;

3)Perchè mettere pAus a NIL?


Un'altra cosa:se volessi eliminare anche le ricorrenze (può capitare di trovare più di un elemento nella lista che si debba eliminare)?

Grazie ancora.
ciao

[alka]

Rispondo a ciascuna delle tue domande:

1)
impostare la variabile pPrev a nil è una inizializzazione; tale variabile, ad ogni ciclo, contiene il puntatore all'elemento che precede quello che stiamo analizzando; se noi partiamo a scandire la lista dall'inzio, è ovvio che per il primo elemento, non avendo un precedente, avremo pPrev che vale nil, quindi non dovremo aggiornare alcun campo puntatore per il record dell'elemento precedente.

2)
pPrev è uguale a nil solo all'ingresso della funzione, ma quando noi passiamo al secondo elemento della lista, tale puntatore verrà inizializzato all'elemento precedente, cioè il primo, e così via. Questo ci consente, qualora troviamo l'elemento da eliminare, di usare il puntatore all'elemento precedente per aggiornare il campo che contiene l'indirizzo dell'elemento successivo facendolo puntare all'elemento che segue quello che stiamo per eliminare...insomma, teniamo legata assieme la lista escludendo il nodo da eliminare, che andiamo poi a deallocare con l'istruzione Dispose.

3)
ho impostato pAus a nil poichè il ciclo che scandisce la lista per controllare se esiste l'elemento cercato allo scopo di eliminarlo dura fino a quando il puntatore pAus è diverso da nil, cioè fino a quando abbiamo elementi da analizzare. Se noi vogliamo cancellare una sola ricorrenza dell'elemento cercato, basta che impostiamo pAus a nil dopo aver eliminato l'elemento e il ciclo si interrompe. Per continuarlo fino alla fine, eliminando tutte le ricorrenze, credo che basti continuare ad assegnare pAus all'elemento successivo a quello in esame.

Ciao!