AnteriorPosterior

Tema 13: Variables dinámicas (1b: lista ordenada)

  Curso: Curso de Pascal, por Nacho Cabanes

Aquí va un programilla de ejemplo, que ordena los elementos que va insertando... y poco más }:-) :

{--------------------------}
{  Ejemplo en Pascal:      }
{                          }
{    Ejemplo de listas     }
{    dinámicas enlazadas   }
{    LISTAS.PAS            }
{                          }
{  Este fuente procede de  }
{  CUPAS, curso de Pascal  }
{  por Nacho Cabanes       }
{                          }
{  Comprobado con:         }
{    - Free Pascal 2.2.0w  }
{    - Turbo Pascal 7.0    }
{    - Tmt Pascal Lt 1.20  }
{--------------------------}
 
program EjemploDeListas;
 
type
  puntero = ^TipoDatos;
  TipoDatos = record
    numero: integer;
    sig:    puntero
  end;
 
 
function CrearLista(valor: integer): puntero;  {Crea la lista, claro}
var
  r: puntero;                 { Variable auxiliar }
begin
  new(r);                     { Reserva memoria }
  r^.numero := valor;         { Guarda el valor }
  r^.sig := nil;              { No hay siguiente }
  CrearLista := r             { Crea el puntero }
end;
 
 
procedure MuestraLista ( lista: puntero );
begin
  if lista <> nil then               { Si realmente hay lista }
    begin
    writeln(lista^.numero);          { Escribe el valor }
    MuestraLista (lista^.sig )       { Y mira el siguiente }
    end;
end;
 
 
procedure InsertaLista( var lista: puntero; valor: integer);
var
  r: puntero;                         { Variable auxiliar }
begin
  if lista <> nil then                { Si hay lista }
    if lista^.numero<valor            {   y todavía no es su sitio }
      then                            {   hace una llamada recursiva: }
      InsertaLista(lista^.sig,valor)  {   mira la siguiente posición }
    else                              { Caso contrario: si hay lista }
      begin                           {   pero hay que insertar ya: }
      new(r);                         {   Reserva espacio, }
      r^.numero := valor;             {   guarda el dato }
      r^.sig := lista;                {   pone la lista a continuac. }
      lista := r                      {   Y hace que comience en }
      end                             {     el nuevo dato: r }
  else                                { Si no hay lista }
    begin                             {   deberá crearla }
    new(r);                           {   reserva espacio }
    r^.numero := valor;               {   guarda el dato }
    r^.sig := nil;                    {   no hay nada detrás y }
    lista := r                        {   hace que la lista comience }
    end                               {     en el dato: r }
end;
 
 
var
  l: puntero;             { Variables globales: la lista }
 
begin
  l := CrearLista(5);     { Crea una lista e introduce un 5 }
  InsertaLista(l, 3);     { Inserta un 3 }
  InsertaLista(l, 2);     { Inserta un 2 }
  InsertaLista(l, 6);     { Inserta un 6 }
  MuestraLista(l)         { Muestra la lista resultante }
end.
 

Ejercicio propuesto: ¿Se podría quitar de alguna forma el segundo "else" de InsertaLista?
Ejercicio propuesto: ¿Cómo sería un procedimiento que borrase toda la lista?
Ejercicio propuesto: ¿Cómo sería un procedimiento de búsqueda, que devolviera la posición en la que está un dato, o NIL si el dato no existe?
Ejercicio propuesto: ¿Cómo se haría una lista "doblemente enlazada", que se pueda recorrer hacia adelante y hacia atrás?


Pues eso es todo por hoy... ;-)

Actualizado el: 19-08-2012 22:19

AnteriorPosterior