Pascal: Liste

[gokan]

PROBLEMA 1


type
puntatore=^elemento;
elemento= record
info: integer;
next: puntatore;
end;


var
lis: puntatore; //puntatore alla testa della lista

Salve a tutti, sto lavorando con le liste, ho qualche difficoltà ad implementare una procedura che cancelli il massimo da una lista. Ipotizziamo che la lista sia lis->7->2->15->8->NIL
Io avevo pensato di inizializzare fuori dalla procedura:

massimo:= -MAXINT-1;

La procedura pensavo potesse funzionare così: Confronto il primo elemento della lista con il massimo (lis^.info > massimo), nella figura significa che 7 è sicuramente maggiore di -MAXINT-1, dovrei memorizzare da qualche parte che adesso il nuovo max è 7 e passare avanti scandendo la lista, il nuovo elemento è 2, minore dell'attuale max (quindi non si fa nulla e si passa avanti), adesso il nuovo elemento ha il campo info etichettato con 15 che è maggiore di 7 (dunque il nuovo max è 15)...Andiamo avanti fino all'ultimo elemento (cioè 8<15).
Alla fine la nuova lista dovrebbe essere lis->7->2->8->NIL. Abbiamo eliminato il max. Il problema è implementare questa procedura in pascal ;) Dovrei utilizzare 2 puntatori, uno che mi scandisca la lista ed uno che mi punti al max attuale e che si aggiorni ogni volta che scoprimo un nuovo max?
Mi date una mano?

PROBLEMA 2


type
puntatore=^elemento;
elemento= record
info: char;
next: puntatore;
end;


Ho implementato in questo modo una procedura che cancelli tutte le vocali da una lista di lettere. Esempio:
INPUT: ls->F->O->R->U->M->NIL
OUTPUT:ls->F->R->M->NIL


Procedure CancellaTutteVocali(var p_testa:puntatore);
var
paux: puntatore;
warning:string;
begin
if p_testa=NIL then warning:='Lista vuota'
else
if p_testa<>NIL then
if (p_testa^.info='a')OR(p_testa^.info='e')OR(p_testa^.info='i')OR
(p_testa^.info='o')OR(p_testa^.info='u') then
begin
paux:=p_testa;
p_testa:=p_testa^.next;
dispose(paux);
CancellaTutteVocali(p_testa);
end
else CancellaTutteVocali(p_testa^.next);
end;


Ho tentato di sostituire quel poco elegante controllo dato da tutti quegli OR con qualcosa di simile
if p_testa^.info in [a,e,i,o,u] then ...

dove volevo fare
type
vocali= set of(a,e,i,o,u)

Mi viene dato l'errore di tipi incompatibili (char e set). Come potrei eliminare quella serie di OR, è mettere qualcosa di più compatto ed elegante?
Grazie

[cisc]

Originariamente inviato da gokan
PROBLEMA 1


type
puntatore=^elemento;
elemento= record
info: integer;
next: puntatore;
end;


var
lis: puntatore; //puntatore alla testa della lista

Salve a tutti, sto lavorando con le liste, ho qualche difficoltà ad implementare una procedura che cancelli il massimo da una lista. Ipotizziamo che la lista sia lis->7->2->15->8->NIL
Io avevo pensato di inizializzare fuori dalla procedura:

massimo:= -MAXINT-1;

La procedura pensavo potesse funzionare così: Confronto il primo elemento della lista con il massimo (lis^.info > massimo), nella figura significa che 7 è sicuramente maggiore di -MAXINT-1, dovrei memorizzare da qualche parte che adesso il nuovo max è 7 e passare avanti scandendo la lista, il nuovo elemento è 2, minore dell'attuale max (quindi non si fa nulla e si passa avanti), adesso il nuovo elemento ha il campo info etichettato con 15 che è maggiore di 7 (dunque il nuovo max è 15)...Andiamo avanti fino all'ultimo elemento (cioè 8<15).
Alla fine la nuova lista dovrebbe essere lis->7->2->8->NIL. Abbiamo eliminato il max. Il problema è implementare questa procedura in pascal ;) Dovrei utilizzare 2 puntatori, uno che mi scandisca la lista ed uno che mi punti al max attuale e che si aggiorni ogni volta che scoprimo un nuovo max?
Mi date una mano?



per cancellarlo non ti basta, devi aggiornare un puntatore al massimo attuale e al nodo precedente.



PROBLEMA 2


type
puntatore=^elemento;
elemento= record
info: char;
next: puntatore;
end;


Ho implementato in questo modo una procedura che cancelli tutte le vocali da una lista di lettere. Esempio:
INPUT: ls->F->O->R->U->M->NIL
OUTPUT:ls->F->R->M->NIL


Procedure CancellaTutteVocali(var p_testa:puntatore);
var
paux: puntatore;
warning:string;
begin
if p_testa=NIL then warning:='Lista vuota'
else
{if p_testa<>NIL then //inutile, se non è uguale, vuol dire che è diverso!}
if (p_testa^.info='a')OR(p_testa^.info='e')OR(p_testa^.info='i')OR
(p_testa^.info='o')OR(p_testa^.info='u') then
begin
paux:=p_testa;
p_testa:=p_testa^.next;
dispose(paux);
CancellaTutteVocali(p_testa);
end
else CancellaTutteVocali(p_testa^.next);
end;


Ho tentato di sostituire quel poco elegante controllo dato da tutti quegli OR con qualcosa di simile
if p_testa^.info in [a,e,i,o,u] then ...

dove volevo fare
type
vocali= set of(a,e,i,o,u)

Mi viene dato l'errore di tipi incompatibili (char e set). Come potrei eliminare quella serie di OR, è mettere qualcosa di più compatto ed elegante?
Grazie

nota il commento che ho aggiunto al codice della funzione....
per usare gli insiemo, devi dichiararli così:
type vocali= set of char;
e poi puoi fare così:
vocali=['a','e','i','o','u'];

io ti consiglio di non usare l'insieme vocali predichiarato ma di fare così:

if p_testa^.info in ['a','e','i','o','u'] then ...
e non if p_testa^.info in [a,e,i,o,u] then ...

[gokan]

Cisc disse: per cancellarlo non ti basta, devi aggiornare un puntatore al massimo attuale e al nodo precedente.
----------------------------------------------------------------------------

:D
Come faccio a tenere un puntatore collegato all'attuale max, e poi ad esempio farlo collegare ad un nuovo massimo (che ad esempio si trova 3 elementi più avanti)...La difficoltà è questa.

if p_testa^.info in ['a','e','i','o','u'] then esatto, mi interessava proprio questo, pensavo che gli apici no ci andassero.
Grazie

[cisc]

allora tu confronti massimo con il nodo attuale così:

if massimo^.info<p^.info then massimo:=p;

dato che devi mantenere un puntatore al massimo e a quello precedente, quando scorri la lista devi avere altri due puntatori, uno che punta al nodo precedente del nodo attuale e uno che punta al nodo precedetne del massimo, se vuoi risparmiarti un puntatore, invece di mantenerti un puntatore al massimo e uno al precedente, ti mantienti solo quello al precedente così:

if massimo^.next^.info<p^.info then massimo:=prec;

dove prec è il nodo precedente al nodo attuale e massimo punta al nodo precedente di quello effettivamente massimo.
per cancellare ti basta fare così:

c=massimo^.next;
massimo:=massimo^.next^.next;
dispose(c);

dove c è un puntatore allo stesso tipo.

ciao.

[gokan]

Sono riuscito a risolvere il problema in questo modo, la mia intenzione è però non fare uso della funzione locale. Vediamo che posso fare grazie alle tue indicazioni, ciao


Procedure EliminaMax(var lis1: puntatore; max: integer);
var
paux: puntatore; //globale ad EliminaMax

(*TrovaMax è una funzione locale ad EliminaMax*)
Function TrovaMax(lis1: puntatore; max: integer):integer;
begin
if lis1<>NIL then
begin
if lis1^.info > max then max:=lis1^.info;
max:=TrovaMax(lis1^.next, max);
end;
TrovaMax:=Max;
end;{Fine della funzione TrovaMax}

(*Da qui in poi implementiamo EliminaMax*)
begin
if lis1<>NIL then
if lis1^.info=TrovaMax(lis1,max) then
begin
paux:=lis1;
lis1:=lis1^.next;
dispose(paux);
end
else
EliminaMax(lis1^.next,TrovaMax(lis1,max));
end;

[cisc]

la tua funzione è poco efficiente:nono: :nonsifa:

fai così:


procedure EliminaMax (var lista:puntatore);
var max,prec,p:puntatore;


begin
new (max);
max^.info:=0;
max^.next:=lista;
prec:=max;
if lista<>nil then begin
p:=lista;
repeat
if p^.info>max^.next^.info then max:=prec;
prec:=p;
p:=p^.next;
until p=nil;
if max^.next^.info=lista^.info then begin
prec:=lista;
lista:=lista^.next;
dispose (prec);
end
else begin
prec:=max^.next;
max^.next:=max^.next^.next;
dispose (prec);
end;
end;
end;

[gokan]

Grazie:sofico:
Hai ragione, la mia versione era poco efficente, certo, tu però nella tua usi 4 puntatori....:D ;) :p
Credo che tu mi debba aiutare in qualche altra cosetta.

[gokan]

Ciao Cisc, devo essere sincero, non credo che sarei riuscito a scrivere quel codice (quello di EliminaMax), ieri sera mi sono preso carta e penna ed ho fatto tutti i passaggi (con relativi disegni), pensa che per una lista del tipo:
lis->2->7->5->NIL ho contato 20 passaggi (è interessante come hai trattato il caso in cui il max coincideva con il primo elemento della lista,non prima di essersi controllati gli elementi del resto della lista). Ti volevo chiedere qualcosa:

1)Come agisci quando ti si viene proposto un problema? Prendi carta e penna e cominci da un esempio oppure cominci a buttare giù del codice per poi migliorarlo?

2)Hai costruito una procedura iterativa, io avevo pensato ad una procedura ricorsiva, secondo te, nel caso di EliminaMax si poteva usare la ricorsione? Ho notato che in alcuni casi (ho già fatto tanti esercizietti) che costruire una procedura ricorsiva è addirittura più semplice ma nel caso di EliminaMax non ho saputo metter mano.

E' interessante sapere come agisce un vero programmatore (sia in problemi relativamente facili, sia in quelli più difficili).
Oltre all'esercizio di eliminare il max da una lista, ho avuto problemi particolari con questa funzione:

function SubLista( lis1, lis2: puntatore):boolean;
Siano lis1 ed lis2 due liste, voglio vedere se lis1 è sottolista di lis2. Ad esempio lis1->7->3->21->NIL è sottolista di
lis2->5->7->3->21->4->NIL.
Questo problema, penso, si debba risolvere in maniera ricorsiva (proprio per definizione di sottolista). Pensavo così:
Controllo il primo elemento di lis1 e vedo se è uguale al primo elemento di lis2, se non è uguale controllo il successivo:

while lis1^.info <> lis2^.info do lis2:=lis2^.next;
p2Aux:=lis2;

Adesso, affinchè lis1 sia sottolista di lis2, (tutti) gli elementi (di lis1) che seguono (lis1^.next^.info,etc) devono essere uguali ai successivi elementi di lis2, questo controllo si dovrebbe bloccare non appena lis1 (o qualche puntatore ausiliario) giunga a NIL.In quel momento se nella lis2 ci dovessero essere altri elementi poco importa (ormai abbiamo visto che nell'esempio, sia 7,3,21 sono nella lis2). Avrai notato che in questo modo la mia funzione è tutt'altro che ricorsiva, penso che il problema sia nel valore di ritorno alla funzione:


while p2Aux^.next^.info = lis1^.next^.info do
begin
p1Aux:=lis1^.next;
p2Aux:=p2Aux^.next;
lis1:=lis1^.next;
//Qui dentro penso che debba andare qualche controllo che mi faccia restituire SubLista:=TRUE
end;
//SubLista:=FALSE ?


Pensi che come ragionamento generale possa andare oppure mi consigli di muovermi in maniera diversa?
Tante Grazie per la tua disponibilità.
Ciao

[cisc]

Originariamente inviato da gokan
Ciao Cisc, devo essere sincero, non credo che sarei riuscito a scrivere quel codice (quello di EliminaMax), ieri sera mi sono preso carta e penna ed ho fatto tutti i passaggi (con relativi disegni), pensa che per una lista del tipo:
lis->2->7->5->NIL ho contato 20 passaggi (è interessante come hai trattato il caso in cui il max coincideva con il primo elemento della lista,non prima di essersi controllati gli elementi del resto della lista). Ti volevo chiedere qualcosa:

1)Come agisci quando ti si viene proposto un problema? Prendi carta e penna e cominci da un esempio oppure cominci a buttare giù del codice per poi migliorarlo?


la 2nd




2)Hai costruito una procedura iterativa, io avevo pensato ad una procedura ricorsiva, secondo te, nel caso di EliminaMax si poteva usare la ricorsione? Ho notato che in alcuni casi (ho già fatto tanti esercizietti) che costruire una procedura ricorsiva è addirittura più semplice ma nel caso di EliminaMax non ho saputo metter mano.



la prima idea è stata usare la ricorsione, perchè è più semplice (anche se in questo caso per me è più semplice usare il ciclo), ma in genere la prima idea non è quasi mai la migliore...



E' interessante sapere come agisce un vero programmatore (sia in problemi relativamente facili, sia in quelli più difficili).


non sono un vero programmatore, sono uno studente che si appresta a diplomarsi (ancora un anno :muro: :muro: )


Oltre all'esercizio di eliminare il max da una lista, ho avuto problemi particolari con questa funzione:

function SubLista( lis1, lis2: puntatore):boolean;
Siano lis1 ed lis2 due liste, voglio vedere se lis1 è sottolista di lis2. Ad esempio lis1->7->3->21->NIL è sottolista di
lis2->5->7->3->21->4->NIL.
Questo problema, penso, si debba risolvere in maniera ricorsiva (proprio per definizione di sottolista). Pensavo così:
Controllo il primo elemento di lis1 e vedo se è uguale al primo elemento di lis2, se non è uguale controllo il successivo:

while lis1^.info <> lis2^.info do lis2:=lis2^.next;
p2Aux:=lis2;

Adesso, affinchè lis1 sia sottolista di lis2, (tutti) gli elementi (di lis1) che seguono (lis1^.next^.info,etc) devono essere uguali ai successivi elementi di lis2, questo controllo si dovrebbe bloccare non appena lis1 (o qualche puntatore ausiliario) giunga a NIL.In quel momento se nella lis2 ci dovessero essere altri elementi poco importa (ormai abbiamo visto che nell'esempio, sia 7,3,21 sono nella lis2). Avrai notato che in questo modo la mia funzione è tutt'altro che ricorsiva, penso che il problema sia nel valore di ritorno alla funzione:


while p2Aux^.next^.info = lis1^.next^.info do
begin
p1Aux:=lis1^.next;
p2Aux:=p2Aux^.next;
lis1:=lis1^.next;
//Qui dentro penso che debba andare qualche controllo che mi faccia restituire SubLista:=TRUE
end;
//SubLista:=FALSE ?


Pensi che come ragionamento generale possa andare oppure mi consigli di muovermi in maniera diversa?
Tante Grazie per la tua disponibilità.
Ciao

più o meno farei così(è la prima idea che mi è venuta e non tiene conto dei casi in cui l1 o l2 siano nil):


function substringa (l1,l2:puntatore):boolean;
var p1:puntatore;

begin
p1:=l1;
while (l2<>nil) and (p1<>nil) do
begin
if p1^.info=l2^.info then p1:=p1^.next
else p1:=l1;
l2:=l2^.next;
end;
if p1=nil then substringa:=true
else substringa:=false;
end;

[cisc]

update:

function substringa (l1,l2:puntatore):boolean;
var p1,p2:puntatore;

begin
p1:=l1;
while (l2<>nil) and (p1<>nil) do
begin
p1:=l1;
p2:=l2;
while (p1^.info=p2^.info) and (p1<>nil) do
begin
p1:=p1^.next;
p2:=p2^.next;
end;
end;
if p1=nil then substringa:=true
else substringa:=false;
end;

[gokan]

Ciao Cisc, ho risolto cosi:

function SubLista(lis1, lis2: puntatore):boolean;
begin
while (lis1<>NIL) AND (lis2<>NIL) do
if lis2^.info<>lis1^.info then lis2:=lis2^.next
else
lis1:=lis1^.next;

if (lis1=NIL) then SubLista:=TRUE
else SubLista:=FALSE;
end;


Adesso ti chiedo un piccolo l'ultimo aiutino per quanto riguarda le liste (infatti dalla prossima settimana comincio a lavorare con gli alberi, ahimè). Devo costruire una procedura che elimini le occorrenze di posto pari. Ad esempio sia la lista:
lista->3->5->4->9->12->NIL In questa lista devo eliminare quindi il 5 ed il 9 (rispettivamente di posto 2 e 4 in questo esempio). Sono riuscito ad implementare tale procedura così:

Procedure EliminaPostoPari(p_testa:puntatore);
var
paux,paux2: puntatore;
warning:string;
begin
if p_testa=NIL then warning:='Lista vuota'
else
begin
paux:=p_testa^.next;
paux2:=p_testa;
paux2:=paux^.next;
dispose(paux);
p_testa^.next:=paux2;
EliminaPostoPari(paux2);
end;
end;

Questa procedura funziona bene fino a quando inserisco in lista 2,4,6,8... (un numero pari di elementi). Se ad esempio prendo la lista di sopra (cioè con un numero dispari di elementi) non funziona. Sicuramente in questo ultimo caso perdo il riferimento all'ultimo elemento e la lista si perde. Vuoi dare tu un' occhiata?
Ti allego tutto il programmino così vedi tu stesso (non so se tu hai/usi Delphi come compilatore di pascal)

[cisc]

Originariamente inviato da gokan
Ciao Cisc, ho risolto cosi:

function SubLista(lis1, lis2: puntatore):boolean;
begin
while (lis1<>NIL) AND (lis2<>NIL) do
if lis2^.info<>lis1^.info then lis2:=lis2^.next
else
lis1:=lis1^.next;

if (lis1=NIL) then SubLista:=TRUE
else SubLista:=FALSE;
end;



sei sicuro che questa funzione sia corretta??
scusami, se lis1^.info è uguale a lis2^.info, perchè porti solo lis2 al prossimo nodo??

la mia funzione non va bene solo perchè uso una funzionalità aggiuntiva del Turbo Pascal 7 che mi permette di fare un controllo del tipo (if (a<>nil) and (a^.info>0)) senza ricevere errori.
se si vuole adottare un pascal più rigido, la mia funzione diventa:

function substringa (l1,l2: puntatore):boolean;
var p1,p2: puntatore;
b:boolean;

begin
p1:=l1;
while (l2<>nil) and (p1<>nil) do
begin
p1:=l1;
p2:=l2;

while (p1^.info=p2^.info) and (p1<>nil) do
begin
p1:=p1^.next;
p2:=p2^.next;
end;
end;
if p1=nil then substringa:=true
else substringa:=false;
end;




Adesso ti chiedo un piccolo l'ultimo aiutino per quanto riguarda le liste (infatti dalla prossima settimana comincio a lavorare con gli alberi, ahimè). Devo costruire una procedura che elimini le occorrenze di posto pari. Ad esempio sia la lista:
lista->3->5->4->9->12->NIL In questa lista devo eliminare quindi il 5 ed il 9 (rispettivamente di posto 2 e 4 in questo esempio). Sono riuscito ad implementare tale procedura così:

Procedure EliminaPostoPari(p_testa:puntatore);
var
paux,paux2: puntatore;
warning:string;
begin
if p_testa=NIL then warning:='Lista vuota'
else
begin
paux:=p_testa^.next;
paux2:=p_testa;
paux2:=paux^.next;
dispose(paux);
p_testa^.next:=paux2;
EliminaPostoPari(paux2);
end;
end;

Questa procedura funziona bene fino a quando inserisco in lista 2,4,6,8... (un numero pari di elementi). Se ad esempio prendo la lista di sopra (cioè con un numero dispari di elementi) non funziona. Sicuramente in questo ultimo caso perdo il riferimento all'ultimo elemento e la lista si perde. Vuoi dare tu un' occhiata?
Ti allego tutto il programmino così vedi tu stesso (non so se tu hai/usi Delphi come compilatore di pascal)

[cisc]

Originariamente inviato da gokan
Ciao Cisc, ho risolto cosi:

function SubLista(lis1, lis2: puntatore):boolean;
begin
while (lis1<>NIL) AND (lis2<>NIL) do
if lis2^.info<>lis1^.info then lis2:=lis2^.next
else
lis1:=lis1^.next;

if (lis1=NIL) then SubLista:=TRUE
else SubLista:=FALSE;
end;



sei sicuro che questa funzione sia corretta??
scusami, se lis1^.info è uguale a lis2^.info, perchè porti solo lis2 al prossimo nodo??

la mia funzione non va bene solo perchè uso una funzionalità aggiuntiva del Turbo Pascal 7 che mi permette di fare un controllo del tipo (if (a<>nil) and (a^.info>0)) senza ricevere errori.
se si vuole adottare un pascal più rigido, la mia funzione diventa:

function substringa (l1,l2: puntatore):boolean;
var p1,p2: puntatore;
b:boolean;

begin
p1:=l1;
while (l2<>nil) and (p1<>nil) do
begin
p1:=l1;
p2:=l2;
if (p1=nil) b:=false;
else b:=true;
while (p1^.info=p2^.info) and b do
begin
p1:=p1^.next;
p2:=p2^.next;
if (p=nil) b:=false;
end;
end;
if p1=nil then substringa:=true
else substringa:=false;
end;




Adesso ti chiedo un piccolo l'ultimo aiutino per quanto riguarda le liste (infatti dalla prossima settimana comincio a lavorare con gli alberi, ahimè). Devo costruire una procedura che elimini le occorrenze di posto pari. Ad esempio sia la lista:
lista->3->5->4->9->12->NIL In questa lista devo eliminare quindi il 5 ed il 9 (rispettivamente di posto 2 e 4 in questo esempio). Sono riuscito ad implementare tale procedura così:

Procedure EliminaPostoPari(p_testa:puntatore);
var
paux,paux2: puntatore;
warning:string;
begin
if p_testa=NIL then warning:='Lista vuota'
else
begin
paux:=p_testa^.next;
paux2:=p_testa;
paux2:=paux^.next;
dispose(paux);
p_testa^.next:=paux2;
EliminaPostoPari(paux2);
end;
end;

Questa procedura funziona bene fino a quando inserisco in lista 2,4,6,8... (un numero pari di elementi). Se ad esempio prendo la lista di sopra (cioè con un numero dispari di elementi) non funziona. Sicuramente in questo ultimo caso perdo il riferimento all'ultimo elemento e la lista si perde. Vuoi dare tu un' occhiata?
Ti allego tutto il programmino così vedi tu stesso (non so se tu hai/usi Delphi come compilatore di pascal)

così dovrebbe funzionare (non lìho testato, quindi!!)

Procedure EliminaPostoPari(p_testa:puntatore);
var
paux: puntatore;
b:boolean;
begin
b:=true;
while (p_testa<>nil) do
begin
paux:=p_testa^.next;
if paux<>nil then
begin
p_testa^.next:=p_testa^.next^.next;
dispose (paux);
end;
p_testa:=p_testa^.next;
end;
end;

[gokan]

La funzione SubLista che ho scritto funziona :D
Quando lis1^.info è diverso da lis2^.info faccio puntare lis2 al successivo elemento altrimenti porto avanti lis1.
Per quanto riguarda la particolarità di Borland Pascal 7, non penso sia questo il problema (Delphi non è altro che una versione evoluta di un Pascal ad oggetti, mantiene ed aggiunge molte caratteristiche del vecchio pascal (sempre borland)). Doma ti faccio sapere per l'altra procedura (EliminaPostoPari), adesso sono un pò stanco...
ti ringrazio ancora per la tua grande disponibiltà:)
Ciao

[gokan]

La tua ultima procedura è ok ;)
Mi sembra che con le liste per il momento può bastare (se dovessi avere altri problemi riesumo questo post).Adesso mi aspettano gli alberi e se ho problemi stai sicuro che mi faccio risentire :oink:
Ciao

[cisc]

non per cercare sempre il pelo nell'uovo, ma hai controllato la tua procedura sublista con questo input??:
lis1: 2->3->4->nil
lis2: 2->2->8->3->4->5->6->nil





Per quanto riguarda la particolarità di Borland Pascal 7, non penso sia questo il problema (Delphi non è altro che una versione evoluta di un Pascal ad oggetti, mantiene ed aggiunge molte caratteristiche del vecchio pascal (sempre borland)).

lo so che delphi è un'evoluzione del Turbo Pascal 7, ma la funzionalità aggiuntiva bisogna attivarla nelle opzioni del compilatore, cmq nella versione che usava questa funzionalità, ho sbagliato l'ordine dei controlli (bisogna prima controllare se il puntatore è nil, e poi il resto)

ciao.

[gokan]

Originariamente inviato da cisc
non per cercare sempre il pelo nell'uovo, ma hai controllato la tua procedura sublista con questo input??:
lis1: 2->3->4->nil
lis2: 2->2->8->3->4->5->6->nil

E' vero, la procedura restituisce un TRUE che non dovrebbe, mi piace la gente precisa come te, mi hai fatto notare un piccolo bug della mia procedura, mi adeguerò alla tua o tenterò di modificarla.
Ciao ;)

[gokan]

function substringa (l1,l2: puntatore):boolean;
var p1,p2: puntatore;
b:boolean;

begin
p1:=l1;
while (l2<>nil) and (p1<>nil) do
begin
p1:=l1;
p2:=l2;
if (p1=nil) b:=false; //err
else b:=true;
while (p1^.info=p2^.info) and b do
begin
p1:=p1^.next;
p2:=p2^.next;
if (p=nil) b:=false; //err
end;
end;
if p1=nil then substringa:=true
else substringa:=false;
end;

C'è qualcosina che non va in questa funzione, l'hai provata? Il problema è che non restituisce alcun valore. Se dovessi sistemarla mi faccio vivo :)

[cisc]

scusami, ma, non avendo più tempo, queste procedure le sto scrivendo di getto sul forum, e qualche volta si possono scrivere ca....te, prova questa (non l'ho testata, e, considerando l'ora e il fatto che l'ho scritta direttamente sul forum, è facile che ci scappi qualche errorino.......)


function substringa (l1,l2: puntatore):boolean;
var p1,p2: puntatore;
b:boolean;

begin
p1:=l1;
p2:=l2;
while (p2<>nil) and (p1<>nil) do
begin
p1:=l1;
b:=true;
while b do
begin
if (p1^.info<>p2^.info) then b:=false;
p1:=p1^.next;
p2:=p2^.next;
if ((p1=nil) or (p2=nil)) then b:=false;
end;
end;
if ((p1=nil) and (l1<>nil)) then substringa:=true
else substringa:=false;
end;

[gokan]

Originariamente inviato da cisc
scusami, ma, non avendo più tempo, queste procedure le sto scrivendo di getto sul forum, e qualche volta si possono scrivere ca....te, prova questa (non l'ho testata, e, considerando l'ora e il fatto che l'ho scritta direttamente sul forum, è facile che ci scappi qualche errorino.......)


function substringa (l1,l2: puntatore):boolean;
var p1,p2: puntatore;
b:boolean;

begin
p1:=l1;
p2:=l2;
while (p2<>nil) and (p1<>nil) do
begin
p1:=l1;
b:=true;
while b do
begin
if (p1^.info<>p2^.info) then b:=false;
p1:=p1^.next;
p2:=p2^.next;
if ((p1=nil) or (p2=nil)) then b:=false;
end;
end;
if ((p1=nil) and (l1<>nil)) then substringa:=true
else substringa:=false;
end;



Tranquillo:D Ti ringrazio tanto per l'aiuto che mi hai già dato. ti faccio sapere.
ciao

[gokan]

Purtroppo il problema è quello che se nella lista2 ritroviamo anche in ordine sparso gli elementi della lista1 il risultato è sempre TRUE.Ho testato la procedura con un insieme di dati tale da metterla in difficoltà.
Guarda l'output :wtf:

[cisc]

azzz, scusami, con una piccola modifica dovrebbe funzionare..........


function substringa (l1,l2: puntatore):boolean;
var p1,p2: puntatore;
b:boolean;

begin
p1:=l1;
p2:=l2;
while (p2<>nil) and (p1<>nil) do
begin
p1:=l1;
b:=true;
while b do
begin
if (p1^.info<>p2^.info) then b:=false
else begin
p1:=p1^.next;
p2:=p2^.next;
end;
if ((p1=nil) or (p2=nil)) then b:=false;
end;
end;
if ((p1=nil) and (l1<>nil)) then substringa:=true
else substringa:=false;
end;

[gokan]

Non restituisce alcun risultato:(

[cisc]

come??????:eh:
non è possibile che con una modifica del genere non funziona più, sei sicuro????

[bsummer]

Posso suggerire una implementazione per il problema di eliminazione di nodi di posto pari?


funzione toglinodo(p: puntatore, togli:booleano) : puntatore

var p2: puntatore

inizio

se p==NIL allora p2 = p
altrimenti
se togli = true allora
inzio
p2 = toglinodo(p^.next,false)
libera p
fine
altrimenti p^.next = toglinodo (p^.next,true)
fine 1°altrimenti
return p2
fine


Versione ricorsiva, mi pare semplice e credo possa funzionare.

Aloha!

[gokan]

Originariamente inviato da cisc
come??????:eh:
non è possibile che con una modifica del genere non funziona più, sei sicuro????
Purtroppo si, sono così perso tra alberi, delphi e liste che mi sto rincoglionendo, non so più cosa fare prima!!

[cisc]

x bsummer:

a me viene in mente sempre questa procedura ricorsiva per quel problema, ma bisogna passargli p^.next e nn p come parametro.

procedure eliminapari (var p: puntatore;);
var pa: puntatore;

begin
if (p<>nil) begin
pa:=p;
p:=p^.next;
dispose (pa);
eliminapari (p^.next^.next);
end;
end;



la tua procedura mi sembra a prima vista ottimizzabile........


x gokan:
la proceura substringa che ho scritto eve per forza restituire o vero o falso, controlla di averla trascritta correttamente

[bsummer]

Originariamente inviato da cisc
x bsummer:


procedure eliminapari (var p: puntatore;);
var pa: puntatore;

begin
if (p<>nil) begin
pa:=p;
p:=p^.next;
dispose (pa);
eliminapari (p^.next^.next);
end;
end;



la tua procedura mi sembra a prima vista ottimizzabile........



La procedura che hai scritto è compatta, chiara e va benissimo...se non per un piccolo caso ;)

Infatti se p è diverso da nil, ma p^.next è nil, cosa succede se passi alla funzione p^.next^.next ? :eek: ;)
Bisognerebbe fare un piccolo controllo.

Per quanto riguarda la mia procedura, si, penso sia ottimizzabile.

Aloha!

[gokan]

Originariamente inviato da cisc
x gokan:
la proceura substringa che ho scritto eve per forza restituire o vero o falso, controlla di averla trascritta correttamente
Ho fatto copia ed incolla, restituisce un risultato solo se la lista1 e 2 non superano 2,3 elementi.
Ciao :confused:

[gokan]

Mi dareste una mano a migliorare questa funzione (possibilmente deve essere ricorsiva). Essa confronta due liste e restituisce TRUE se sono uguali, FALSE altrimenti.

Function Uguali(lis,lis2:puntatore):boolean;
begin
if (lis<>NIL) AND (lis2<>NIL) then
if lis^.info<>lis2^.info then Uguali:=FALSE
else
Uguali:=Uguali(lis^.next,lis2^.next);
end;

Il problema è che se le due liste sono di lunghezza diverse ma molto simili, la funz mi da sempre TRUE. Ad esempio
lis->c->a->r->NIL
lis2->c->a->r->n->e->NIL
Fanno restituire True, dovrei mettere un controllo dove c'è 'else', prima di fare eseguire Uguali:=Uguali(lis^.next,lis2^.next);

[bsummer]

Prova questo:

Function Uguali(lis,lis2untatore):boolean;

var a, b :boolean;
begin

if lis<>nil then a:= true
else a:=false;
if lis2<>nil then b:= true
else b:=false;

a = (a and b);

if a = true then
begin
if lis.info <> lis2.info then uguali:=false
else Uguali:=Uguali(lis^.next,lis2^.next);
end else uguali:=false;
end;


Aloha!

[cisc]

prima cosa, così funziona:

function substringa (l1,l2: puntatore):boolean;
var p1,p2: puntatore;
b:boolean;

begin
p1:=l1;
p2:=l2;
while (p2<>nil) and (p1<>nil) do
begin
p1:=l1;
b:=true;
while b do
begin
if (p1^.info<>p2^.info) then begin
b:=false;
p1:=p1^.next;
p2:=p2^.next;
end
else begin
p1:=p1^.next;
p2:=p2^.next;
end;
if ((p1=nil) or (p2=nil)) then b:=false;
end;
end;
if ((p1=nil) and (l1<>nil)) then substringa:=true
else substringa:=false;
end;



per la funzione uguali sono d'accordo con bsummer.

per eliminapari, hai ragione :D , diventerebbe così:


procedure eliminapari (var p: puntatore;
var pa: puntatore;

begin
if p<>nil begin
pa:=p;
p:=p^.next;
dispose (pa);
if p^.next<>nil then eliminapari (p^.next^.next);
end;
end;

[gokan]

La procedure subStringa non funziona ancora perfettamente (vedi output),la funzione UgualiListe non funziona bene, restituisce sempre false!!
Doma vi faccio sapere se riesco a migliorare qualcosa!!
Ciao e grazie ancora a tutti e due!!

Ah, la procedura eliminapari (dovrebbe eliminare gli elementi di posto pari di una lista) non funziona, elimina tutti gli elementi tranne l'ultimo.
Perchè passare la testa della lista per riferimento? La testa non verrà mai eliminata (essendo di posto uno, cioè dispari)?
:)

[bsummer]

Originariamente inviato da gokan
la funzione UgualiListe non funziona bene, restituisce sempre false!!


Perchè sono un coglione! E' ovvio che gli ultimi 2 nodi sono NIL e quindi se entrambi sono NIL la funzione deve restituire true!
Invece com'è fatta ora questo caso non lo prende in considerazione...ci vuole una modica...

[cisc]

function substringa (l1,l2: puntatore):boolean;
var p1,p2: puntatore;
b:boolean;

begin
p1:=l1;
p2:=l2;
while (p2<>nil) and (p1<>nil) do
begin
p1:=l1;
b:=true;
while b do
begin
if p1^.info<>p2^.info then b:=false
else p1:=p1^.next;
p2:=p2^.next;
if ((p1=nil) or (p2=nil)) then b:=false;
end;
end;
if ((p1=nil) and (l1<>nil)) then substringa:=true
else substringa:=false;
end;

[gokan]

Originariamente inviato da cisc

function substringa (l1,l2: puntatore):boolean;
var p1,p2: puntatore;
b:boolean;

begin
p1:=l1;
p2:=l2;
while (p2<>nil) and (p1<>nil) do
begin
p1:=l1;
b:=true;
while b do
begin
if p1^.info<>p2^.info then b:=false
else p1:=p1^.next;
p2:=p2^.next;
if ((p1=nil) or (p2=nil)) then b:=false;
end;
end;
if ((p1=nil) and (l1<>nil)) then substringa:=true
else substringa:=false;
end;


Adesso funziona alla grande :p

[gokan]

Ecco come deve essere la funzione di Uguaglianza Liste

Function Uguali(lis,lis2:puntatore):boolean;
begin
if (lis<>NIL) AND (lis2<>NIL) then
begin
if lis^.info<>lis2^.info then Uguali:=FALSE
else //if lis^.info=lis2^.info then
Uguali:=Uguali(lis^.next,lis2^.next)
end
else if ((lis=NIL)AND(lis2<>NIL))OR((lis<>NIL)AND(lis2=NIL)) then
Uguali:=False;
end;

[gokan]

Salve a tutti ho un problemino apparentemente stupido. Dovrei costruire una lista che mi consenta di scegliere quale elelento iinserire e dopo quale inserirlo.
Esempio
lis->6->2->9->NIL

Voglio inserire l'elemento 5 dopo l'elemento 2. Dovrebbe essere così lis->6->2->5->9->NIL.
Ho costruito tale procedura, che ha il difetto di eliminare tutti i valori che seguono quello inserito, ad esempio l'output sarebbe stato:lis->6->2->5->NIL (ho perso il 9).
Dateci un'occhiata e datemi qualche consiglio:

Procedure InsDopo(var lis1:puntatore; dopoValore,qualeValore: integer);
var
pNuovo:puntatore;
begin
if lis1<>NIL then
begin
if lis1^.info=dopoValore then
begin
new(pNuovo);
lis1^.next:=pNuovo;
pNuovo^.info:=qualeValore;
pNuovo^.next:=lis1^.next^.next;
end
else
InsDopo(lis1^.next,dopoValore,qualeValore);
end;
end;

[bsummer]

PRIMA

pnuovo^.next := list1^.next;

e DOPO

list1^.next:=pnuovo;


Altrimenti si che perdi la coda... ;)

[gokan]

Originariamente inviato da bsummer
PRIMA

pnuovo^.next := list1^.next;

e DOPO

list1^.next:=pnuovo;


Altrimenti si che perdi la coda... ;)
azz.. mi sono rimbambito, hai ragione, come facevo a non accorgemene
:muro: :mc: :eek: :cry:

[gokan]

Altro problemino con le liste.
Cisc ha risolto il problema dell'eliminazione degli elementi di posto pari così:

Procedure EliminaPostoPari(p_testa:puntatore);
var
paux: puntatore;
begin
while (p_testa<>nil) do
begin
paux:=p_testa^.next;
if paux<>nil then
begin
p_testa^.next:=p_testa^.next^.next;
dispose (paux);
end;
p_testa:=p_testa^.next;
end;
end;


Adesso volevo implementare una procedura che mi consenta di eliminare gli elementi di posto dispari. Questa volta è più complicato perchè dobbiamo eliminare anche la testa della lista (essendo l'elemento di posto 1). Pensavo a qualcosa di simile:

//Versione ricorsiva da migliorare
Procedure EliminaPostoDispari(var p_testa:puntatore);
var
paux: puntatore;
begin
if p_testa<>NIL then
begin
paux:=p_testa;
p_testa:=p_testa^.next;
dispose(paux);
if p_testa^.next<>NIL then EliminaPostoDispari(p_testa^.next) //il prob sta qui
end;
end;


Il problema è che se la lista di numeri è pari tutto ok cioè: lis->1->2->3->4->NIL diventa lis->2-->4->NIL
Invece se il numero è dispari non funziona (questo perchè il controllo non funziona adeguatamente se p_testa=NIL). Mi date un mano a migliorare tale controllo?

[bsummer]

E che ne diresti di una procedura generica che elimini a seconda del parametro passato i nodi di posto pari e quelli di posto dispari?


procedure elimina_nodo (var p: puntatore,elimino: boolean);

var p2 :puntatore

begin
if p <> nil then
begin
if elimino = true then
begin
p2 := p;
p := p^.next;
dispose(p2);
elimina_nodo(p, not(elimino));
end else
begin
elimina_nodo(p^.next, not(elimino));
end
end
end


Se vuoi eliminare i posti dispari :

elimina_nodo(p,true);

Per i pari:

elimina_nodo(p,false);


Dovrebbe funzionare, provala e dimmi :)

[gokan]

Originariamente inviato da bsummer
E che ne diresti di una procedura generica che elimini a seconda del parametro passato i nodi di posto pari e quelli di posto dispari?


procedure elimina_nodo (var p: puntatore,elimino: boolean);

var p2 :puntatore

begin
if p <> nil then
begin
if elimino = true then
begin
p2 := p;
p := p^.next;
dispose(p2);
elimina_nodo(p, not(elimino));
end else
begin
elimina_nodo(p^.next, not(elimino));
end
end
end


Se vuoi eliminare i posti dispari :

elimina_nodo(p,true);

Per i pari:

elimina_nodo(p,false);


Dovrebbe funzionare, provala e dimmi :)

Funziona!!! Ingegnosa la tua procedura!!
Il valore booleano elimino cambia continuamente ed in questo modo si passa sempre il giusto puntatore!!!
Grazie, ho imparato una cosa nuova!!

[gokan]

Dato che sono testardo, voglio perfezionare questa procedura. Avevo pensato che si potesse procedere così:
Elimino il primo elemento (che ovviamente è di posto dispari) e poi tratto i successivi elementi alla stregua di quelli di ordine pari della precedente procedura. Purtroppo non mi funziona, perchè vengono eliminati tutti gli elementi della lista?

Procedure EliminaPostoDisp(var p_testa:puntatore);
var
paux:puntatore;
begin
if (p_testa<>NIL) then
begin
paux:=p_testa;
p_testa:=p_testa^.next;
dispose(paux);
end;
while (p_testa<>NIL) do
begin
paux:=p_testa^.next;
if paux<>nil then
begin
p_testa^.next:=p_testa^.next^.next;
dispose (paux);
end;
p_testa:=p_testa^.next;
end;
end;

[bsummer]

Intanto prova a togliere quel "var" dal parametro passato alla procedura ;)

[gokan]

Originariamente inviato da bsummer
Intanto prova a togliere quel "var" dal parametro passato alla procedura ;)
Ok ma adesso funziona peggio di prima
:(

[bsummer]

Dunque...quando ti ho suggerito di togliere il var l'ho fatto perchè ogni volta che fai un'operazione del tipo

p_testa:=p_testa^.next

sposti la testa della lista avanti di un nodo. Visto che il var passa la variabile per riferimento e visto che la tua procedura si ferma sul NIL allora è ovvia conseguenza che alla fine la lista ti risulti vuota...in realtà la lista è ancora allocata in memoria ma tu hai perso il reference alla testa :(

Omettendo il "var" non perdi il reference alla testa ma il risultato è lo stesso di prima perchè il primo nodo lo deallochi sempre (purchè non sia già NIL).

Per risolvere questo problema puoi procedere come segue


Procedure EliminaPostoDisp(var p_testa: puntatore);
var
paux: puntatore;
p: puntatore;

begin
if (p_testa<>NIL) then
begin
paux:=p_testa;
p_testa:=p_testa^.next;
dispose(paux);
end;
p := p_testa;
while (p<>NIL) do
begin
paux:=p^.next;
if paux<>nil then
begin
p^.next:=p^.next^.next;
dispose (paux);
end;
p :=p^.next;
end;
end;


In questo modo usi p per scorrere la lista e mantiene inalterato p_testa, mantenendo così il reference al nodo di testa. Con queste modifiche non dovresti più avere il problema della lista vuota, ma non so se effettivamente la procedura funzioni perchè non ho provato la casistica...quello spetta a te ;)

Aloha!

[gokan]

Hai ragione, mi ero perso in un bicchiere d'acqua. :rolleyes:
Grazie