Pascal: Liste

gokan · 09-08-2003, 09:36

PROBLEMA 1

Codice:

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

Codice:

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

Codice:

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 · 09-08-2003, 15:13

Quote:

Originariamente inviato da gokan
PROBLEMA 1

Codice:

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.

Quote:

PROBLEMA 2

Codice:

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

Codice:

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 · 09-08-2003, 15:31

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

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 · 11-08-2003, 00:52

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 · 11-08-2003, 14:12

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

Codice:

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 · 11-08-2003, 19:18

la tua funzione è poco efficiente

fai così:

Codice:

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 · 11-08-2003, 19:41

Grazie

Hai ragione, la mia versione era poco efficente, certo, tu però nella tua usi 4 puntatori....

Credo che tu mi debba aiutare in qualche altra cosetta.

gokan · 12-08-2003, 10:04

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:

Codice:

 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:

Codice:

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 · 13-08-2003, 00:56

Quote:

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

Quote:

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...

Quote:

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

)

Quote:

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:

Codice:

 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:

Codice:

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):

Codice:

 
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 · 13-08-2003, 17:05

update:

Codice:

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 · 14-08-2003, 11:27

Ciao Cisc, ho risolto cosi:

Codice:

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ì:

Codice:

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 · 15-08-2003, 20:12

Quote:

Originariamente inviato da gokan
Ciao Cisc, ho risolto cosi:

Codice:

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;

Quote:

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:

Codice:

 
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ì:

Codice:

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 · 15-08-2003, 20:24

Quote:

Originariamente inviato da gokan
Ciao Cisc, ho risolto cosi:

Codice:

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;

Quote:

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:

Codice:

 
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ì:

Codice:

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!!)

Codice:

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 · 15-08-2003, 23:09

La funzione SubLista che ho scritto funziona

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 · 16-08-2003, 11:49

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

Ciao

cisc · 17-08-2003, 18:07

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

Quote:

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 · 17-08-2003, 20:55

Quote:

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 · 17-08-2003, 21:54

Codice:

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 · 20-08-2003, 01:59

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.......)

Codice:

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 · 20-08-2003, 13:43

Quote:

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.......)

Codice:

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

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

09-08-2003, 09:36	#1
gokan Senior Member Iscritto dal: Apr 2002 Città: Palermo Messaggi: 4913	Pascal: Liste PROBLEMA 1 Codice: 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 Codice: 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 Codice: 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 __________________ Sun Certified Java Programmer - Sun Certified Web Component Developer - Sun Certified Business Component Developer

09-08-2003, 15:31	#3
gokan Senior Member Iscritto dal: Apr 2002 Città: Palermo Messaggi: 4913	Cisc disse: per cancellarlo non ti basta, devi aggiornare un puntatore al massimo attuale e al nodo precedente. ---------------------------------------------------------------------------- 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 __________________ Sun Certified Java Programmer - Sun Certified Web Component Developer - Sun Certified Business Component Developer

11-08-2003, 00:52	#4
cisc Senior Member Iscritto dal: Nov 2002 Città: Cosenza --> Roma Messaggi: 853	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. __________________ GNU MyServer Wants YOU!! We live thinking we will never die. We die thinking we had never lived. Jason Becker

11-08-2003, 19:41	#7
gokan Senior Member Iscritto dal: Apr 2002 Città: Palermo Messaggi: 4913	Grazie Hai ragione, la mia versione era poco efficente, certo, tu però nella tua usi 4 puntatori.... Credo che tu mi debba aiutare in qualche altra cosetta. __________________ Sun Certified Java Programmer - Sun Certified Web Component Developer - Sun Certified Business Component Developer

12-08-2003, 10:04	#8
gokan Senior Member Iscritto dal: Apr 2002 Città: Palermo Messaggi: 4913	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: Codice: 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: Codice: 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 __________________ Sun Certified Java Programmer - Sun Certified Web Component Developer - Sun Certified Business Component Developer

15-08-2003, 23:09	#14
gokan Senior Member Iscritto dal: Apr 2002 Città: Palermo Messaggi: 4913	La funzione SubLista che ho scritto funziona 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 __________________ Sun Certified Java Programmer - Sun Certified Web Component Developer - Sun Certified Business Component Developer

16-08-2003, 11:49	#15
gokan Senior Member Iscritto dal: Apr 2002 Città: Palermo Messaggi: 4913	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 Ciao __________________ Sun Certified Java Programmer - Sun Certified Web Component Developer - Sun Certified Business Component Developer

17-08-2003, 21:54	#18
gokan Senior Member Iscritto dal: Apr 2002 Città: Palermo Messaggi: 4913	Codice: 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 __________________ Sun Certified Java Programmer - Sun Certified Web Component Developer - Sun Certified Business Component Developer Ultima modifica di gokan : 17-08-2003 alle 22:13.

20-08-2003, 01:59	#19
cisc Senior Member Iscritto dal: Nov 2002 Città: Cosenza --> Roma Messaggi: 853	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.......) Codice: 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; __________________ GNU MyServer Wants YOU!! We live thinking we will never die. We die thinking we had never lived. Jason Becker Ultima modifica di cisc : 20-08-2003 alle 02:08.

Strumenti
Mostra una versione stampabile Invia questa pagina per email