Newsgroup: it.comp.lang.pascal
Titolo: inserire in lista

come faccio ad inserire un elemento in una lista a puntatori ordinata
mantenendo l'ordine? grazie, ciao...
steve

 steve
Scorri tutta la lista fin che non trovi la posizione giusta, ma ti devi
ricordare sempre il precedente nodo in modo da poter inserire
Ciao Re Di Cuori

 - rimuovi XXX  x  rispondere  ICQ	#8814554
 
Fare l'eunuco non e' da tutti: bisogna essere tagliati.
		-- Da it.hobby.umorismo

bye!
ecco qua un programmino che contiene tutte le procedure più usate per
manipolare liste semplici concatenate.
program ListaSempliceConcatenata;
uses crt;
type PREC = ^REC;
     REC  = record
          dato : integer;
          next : PREC;
          end;
var INIZIO,I1,I2,ELEM,FINE : PREC;
    i : integer;
procedure InsInTesta;
var i:integer;
begin
INIZIO:=nil;
i:=0;
repeat
    i:=i+1;
    new(ELEM);
    ELEM^.DATO := i;
    ELEM^.next := INIZIO;
    INIZIO := ELEM;
until i=10;
end;
procedure InsInCoda;
var p : PREC;
    i : integer;
begin
INIZIO:=nil;
i:=0;
repeat
    i:=i+1;
    new(ELEM);
    ELEM^.DATO := i;
    ELEM^.next := nil;
    if INIZIO<>nil then begin
       p:=INIZIO;
       while p^.next<>nil do
          p:=p^.next;
       p^.next:=ELEM
       end
    else
       INIZIO:=ELEM;
until i=10;
end;
procedure InsInCoda2;
var i : integer;
begin
INIZIO:=nil;
FINE:=nil;
i:=10;
repeat
    i:=i+1;
    new(ELEM);
    ELEM^.DATO := i;
    ELEM^.next := nil;
    if INIZIO=nil then begin
       INIZIO:=ELEM;
       FINE:=ELEM;
       end
    else begin
       FINE^.next:=ELEM;
       FINE:=ELEM;
    end;
until i=20;
end;
procedure InsInCodaRic(var p,q :prec);
begin
if q=nil then
   q:=p
else
   InsInCodaRic(p,q^.next);
end;
procedure InsOrdinato;
var p,q : PREC;
    i,k : integer;
begin
INIZIO:=nil;
randomize;
i:=0;
repeat
    k:=random(30)+1;
    i:=i+1;
    new(ELEM);
    ELEM^.DATO := k;
    ELEM^.next := nil;
(* caso 1: lista vuota *)
    if INIZIO=nil then
       INIZIO:=ELEM
    else begin
(* caso 2.1: lista non vuota ed inserimento in testa *)
       if INIZIO^.dato >= ELEM^.dato then begin
          ELEM^.next:=INIZIO;
          INIZIO:=ELEM;
          end
       else begin
(* caso 2.2: lista non vuota ed inserimento in posizione
   diversa dalla prima                                            *)
          p:=INIZIO;
          q:=INIZIO^.next;
(* p punta l'elemento A il cui dato precede quello dell'elemento
   da inserire, mentre q punta l'elemento B, successivo ad A     *)
          while q<>nil do
             if q^.dato<ELEM^.dato then begin
(* Se anche l'elemento B precede nell'ordinamento l'elemento da
   inserire, allora scorro in avanti di una posizione             *)
                p:=q;
                q:=q^.next;
                end
             else
                q:=nil;
(* In uscita dal ciclo l'elemento puntato da p PRECEDE
nell'ordinamento
   quello nuovo, mentre quello seguente a p puo'
          a) SEGUIRE nell'ordinamento quello da inserire
          o
          b) non esistere (inserimento in coda)                     *)
          ELEM^.next:=p^.next;
          p^.next:=ELEM;
       end;
    end;
until i=10;
end;
function InsOrdRic(var p,q:prec):prec;
begin
if q=nil then
   InsOrdRic:=p
else
   if q^.dato<p^.dato then begin
      InsOrdRic:=q;
      q^.next:=InsOrdRic(p,q^.next);
      end
   else begin
      p^.next:=q;
      InsOrdRic:=p;
   end;
end;
procedure InvertiLista;
var p,q,r:PREC;
begin
p:=nil;
q:=INIZIO;
r:=INIZIO;
repeat
   q:=q^.next;
   r^.next:=p;
   p:=r;
   r:=q;
until q=nil;
INIZIO:=p;
end;
procedure VisualizzaLista;
begin
ELEM := INIZIO;
repeat
    write(ELEM^.dato);
    write(' -> ');
    ELEM := ELEM^.next;
until ELEM = nil;
write('NIL');
writeln;
end;
procedure VisualizzaListaRicorsiva(p:prec);
begin
if p<>nil then begin
   write(p^.dato);
   write(' -> ');
   VisualizzaListaRicorsiva(p^.next);
   end
else
   write('NIL');
end;
procedure aggiungi(k:integer);
var p:prec;
begin
new(p);
p^.dato:=k;
p^.next:=nil;
InsInCodaRic(p,INIZIO);
end;
procedure aggiungiord(i:integer;var punt:prec);
var p:prec;
    k:integer;
begin
new(p);
k:=random(30)+1;
p^.dato:=k;
p^.next:=nil;
punt:=InsOrdRic(p,punt);
end;
procedure fondi(var r,p,q : prec);
var paus : prec;
begin
r:=nil;
while (p<>nil) and (q<>nil) do begin
   if p^.dato < q^.dato then begin
      paus:= p^.next;
      p^.next:=r;
      r:=p;
      p:=paus;
      end
   else begin
      paus:= q^.next;
      q^.next:=r;
      r:=q;
      q:=paus;
      end;
   end;
if p=nil then
   repeat
      paus:= q^.next;
      q^.next:=r;
      r:=q;
      q:=paus;
   until q=nil
else
   repeat
      paus:= p^.next;
      p^.next:=r;
      r:=p;
      p:=paus;
   until p=nil;
end;
begin
clrscr;
writeln('Inserimento in testa ripetuto di 10 elementi');
InsInTesta;
VisualizzaLista;
writeln('Inserimento in coda ripetuto di 10 elementi (con punt.
ausiliario)');
InsInCoda;
VisualizzaLista;
writeln('Inserimento in coda ripetuto di 10 elementi (con punt. di
fine lista)');
InsInCoda2;
VisualizzaLista;
writeln('Inserimento ordinato ripetuto di 10 elementi casuali');
InsOrdinato;
VisualizzaLista;
writeln('Inversione dell''ultima lista creata');
InvertiLista;
VisualizzaLista;
writeln('Visualizzazione ricorsiva ');
VisualizzaListaRicorsiva(INIZIO);
writeln;
writeln('Aggiunta di 3 elementi con procedura di inserimento in coda
ricorsiva');
for i:=3 downto 1 do
    aggiungi(i);
VisualizzaListaRicorsiva(INIZIO);
writeln;
writeln('Creazione di una lista ordinata con funzione ricorsiva');
INIZIO:=nil;
randomize;
for i:=1 to 12 do
    aggiungiord(i,inizio);
VisualizzaListaRicorsiva(INIZIO);
writeln;
I1:=nil;
I2:=nil;
randomize;
for i:=1 to 5 do aggiungiord(i,i1);
for i:=1 to 5 do aggiungiord(i,i2);
VisualizzaListaRicorsiva(i1);
writeln;
VisualizzaListaRicorsiva(i2);
writeln;
fondi(inizio,i1,i2);
VisualizzaListaRicorsiva(inizio);
repeat until keypressed;
readln;
end.