{ Terreno Antonio mat.9714216 }
unit
   listeric;

interface

type
   tipo_elemento=integer;
   tipo_lista=^cella;
   cella= record
             element:tipo_elemento;
        next:tipo_lista
          end;

   procedure crea_lista(var L:tipo_lista);
   procedure leggi_da_tastiera_lista(var L:tipo_lista);
   procedure inserisci_in_testa(x:tipo_elemento;var L:tipo_lista);
   procedure inserisci_ord(x:tipo_elemento;var L:tipo_lista);
   procedure inserisci_in_coda(x:tipo_elemento;var L:tipo_lista);
   procedure inserisci_prima(x,y:tipo_elemento;var L:tipo_lista);
   procedure inserisci_dopo(x,y:tipo_elemento;var L:tipo_lista);
   procedure cancella_tutti(x:tipo_elemento;var L:tipo_lista);
   procedure cancella_prima(x:tipo_elemento;var L:tipo_lista);
   procedure cancella_dopo(x:tipo_elemento;var L:tipo_lista);
   procedure estrai_el(var elem: tipo_elemento;pos: integer; var L: tipo_lista);
   function cerca_elemento(x:tipo_elemento;L:tipo_lista):boolean;
   function primo_elemento(L:tipo_lista): tipo_elemento;
   function ultimo_elemento(L:tipo_lista):tipo_elemento;
   function posizione_elemento(x: tipo_elemento;L:tipo_lista): integer;
   function lunghezza_lista(L:tipo_lista):integer;
   function lista_vuota(L:tipo_lista): boolean;
   procedure stampa_lista(L:tipo_lista);
   function concatena(L,M:tipo_lista):tipo_lista;
   function fondi(L,M:tipo_lista):tipo_lista;

implementation

procedure crea_lista(var L:tipo_lista);
{ crea una lista vuota }
begin
   new(L);
   L:=nil
end;

procedure inserisci_in_testa(x:tipo_elemento;var L:tipo_lista);
{ inserisce in testa ad L x }
var
   M:tipo_lista;
begin
   new(M);
   M^.element:=x;
   M^.next:=L;
   L:=M;
end;


procedure inserisci_ord(x:tipo_elemento;var L:tipo_lista);
{ inserisc x in una lista ordinata }
begin
   if (L=nil) then
      inserisci_in_testa(x,L)
   else if(x<L^.element)then
      inserisci_in_testa(x,L)
   else if(x>L^.element)then
      inserisci_ord(x,L^.next)
end;

procedure inserisci_in_coda(x:tipo_elemento;var L:tipo_lista);
{ inserisce x in coda a L }
begin
   if (L=nil) then
      begin
         new(L);
    L^.element:=x;
    L^.next:=nil;
      end
   else
      inserisci_in_coda(x,L^.next)
end;

procedure inserisci_prima(x,y:tipo_elemento;var L:tipo_lista);
{ inserisce y prima di x }
begin
   if (L=nil) or (L^.element = x) then
      inserisci_in_testa(y,L)
   else if (L^.element <> x ) then
      inserisci_prima(x,y,L^.next)
end;

procedure inserisci_dopo(x,y: tipo_elemento; var L:tipo_lista);
{ inserisc dopo x y }
begin
   if (L=nil) then
      inserisci_in_testa(y,L)
   else if (L^.element = x) then
      inserisci_in_testa(y,L^.next)
   else if (L^.element <> x ) then
      inserisci_dopo(x,y,L^.next)
end;


procedure cancella_tutti(x:tipo_elemento;var L:tipo_lista);
{ cancella ogi occorenza di x da L }
begin
  if (L<>nil) then
     if (L^.element=x) then
        begin
      L:=L^.next;
      cancella_tutti(x,L)
   end
     else
        cancella_tutti(x,L^.next)
end;

procedure cancella_prima(x:tipo_elemento;var L:tipo_lista);
{ cancella l'elemento che precede x }
begin
   if (L<>nil) then
      if (L^.next <> nil) then
         if (L^.next^.element = x) then
       L:=L^.next
    else
       cancella_prima(x,L^.next)
end;

procedure cancella_dopo(x:tipo_elemento;var L:tipo_lista);
{ cancella l'elemento che segue x }
var
   tmp: tipo_lista;
begin
   if (L<>nil) then
      if (L^.next <> nil) and (L^.element=x)then
         begin
       tmp:=L^.next;
       L^.next:=L^.next^.next;
       dispose(tmp)
    end
      else
         cancella_dopo(x,L^.next)
end;

procedure estrai_el(var elem: tipo_elemento;pos: integer; var L: tipo_lista);
{ primo elemento-> pos=0}
{ estrae l'elemento in posizione i-esima}
var
   tmp: tipo_lista;
begin
   if (L<>nil) then
      if (pos>0) then
         estrai_el(elem,pos-1,L^.next)
      else
         begin
       elem:=L^.element;
       tmp:=L;
       L:=L^.next;
       dispose(tmp)
    end;
end;

function cerca_elemento(x:tipo_elemento;L:tipo_lista):boolean;
{ true se x e' in L }
begin
   if (L=nil) then
      cerca_elemento:=false
      else if (L^.element=x) then
         cerca_elemento:=true
      else
         cerca_elemento:=cerca_elemento(x,L^.next)
end;

function primo_elemento(L:tipo_lista): tipo_elemento;
{ ritorna il primo elemento di L }
begin
   if (L<>nil) then
      primo_elemento:=L^.element;
end;

function ultimo_elemento(L:tipo_lista):tipo_elemento;
{ ritorna l'ultiomo elemento di L }
begin
   if (L<>nil) then
      begin
         while (L^.next <> nil) do
       L:=L^.next;
       ultimo_elemento:=L^.element
    end
end;

function posizione_elemento(x: tipo_elemento;L:tipo_lista): integer;
{ ritorna la posizione di x nella lista }
{ -1 -> x non e' presente }
{ 0 x e' nella prima cella }
var
   i:integer;
begin
   if (L=nil) then
      posizione_elemento:=-1
   else if (L^.element=x) then
      posizione_elemento:=0
   else
      posizione_elemento:=1+posizione_elemento(x,L^.next)
end;

function lunghezza_lista(L:tipo_lista):integer;

begin
   if(L=nil)then
      lunghezza_lista:=0
   else
      lunghezza_lista:=lunghezza_lista(L^.next)+1
end;

function lista_vuota(L:tipo_lista): boolean;

begin
   lista_vuota:= (L=nil);
end;

procedure leggi_da_tastiera_lista(var L:tipo_lista);

var
   x:tipo_elemento;
begin
   if (eoln) then
      L:=nil
   else

begin
   read(x);
   inserisci_in_coda(x,L);
   leggi_da_tastiera_lista(L^.next)
end

end;

procedure stampa_lista(L:tipo_lista);

begin
  if (L=nil) then
     writeln('nil')
  else
     begin
        write(L^.element,' ');
   stampa_lista(L^.next)
     end
end;

function concatena(L,M:tipo_lista):tipo_lista;

begin
  if (L=nil) then
    concatena:=M
  else if (L^.next=nil) then
     L^.next:=M
  else
     concatena:=concatena(L^.next,M);
  concatena:=L;
end;

function fondi(L,M:tipo_lista):tipo_lista;

begin
   if (L=nil) then
     fondi:=M
   else if (M=nil) then
     fondi:=L
   else if (L^.element<=M^.element) then
      begin
         L^.next:=fondi(L^.next,M);
    fondi:=L
      end
   else
      begin
         M^.next:=fondi(L,M^.next);
    fondi:=M
      end
end;

end.