{ *************************************************** }

{ *      Estructuras de datos para Pilas y Colas    * }

{ *      para problemas de búsqueda en IA           * }

{ *               Jacinto Ruiz Catalán              * }

{ *               jacinruiz@hotmail.com             * }

{ *         http://www.geocities.com/jacinruiz/     * }

{ *************************************************** }

 

unit Listas;

 

interface

 

{Tipo de dato base de un estado del problema a resolver

En este caso se trata de un tablero de ajedrez represen-

tado por una fila , una columna y la profundidad en el

árbol de búsqueda}

 

type TipoValor=record

                     Fila,Columna:Integer;

                     Profundidad:Integer

               end;

 

{Tipo nodo para contener cada estado y un puntero al siguiente nodo}

 

type TipoPuntero=^TipoNodo;

     TipoNodo=record

                 Valor:TipoValor;

                 Puntero:TipoPuntero

           end;

 

{Procedimientos básicos para cargar y comparar estados}

 

{Carga un estado }

procedure CargarRegistro(var Registro:TipoValor;Dato:Tipovalor);

{Compara dos estados pero sólo su posición}

function CompararRegistrosPosicion(Registro,Dato:TipoValor):Boolean;

{Compara dos estados tanto en posición como en profundidad}

function CompararRegistros(Registro,Dato:TipoValor):Boolean;

 

{Procedimientos para la creación y manipulación de listas de nodos}

 

{Inicializa una lista}

procedure Iniciar(var Lista:TipoPuntero);

{Devuelve true si la lista está vacía y false si no lo está}

function Vacio(Lista:TipoPuntero):Boolean;

{Añade un elemento al principio de la lista}

procedure AnadirPrincipio(var Lista:TipoPuntero;Dato:TipoValor);

{Lee un elemento del principio de la lista}

function LeerPrincipio(Lista:TipoPuntero):TipoValor;

{Elimina el primer elemento de la lista}

procedure EliminarPrincipio(var Lista:TipoPuntero);

{Añade un elemento al final de la lista}

procedure AnadirFinal(var Lista:TipoPuntero;Dato:TipoValor);

{Lee un elemento del final de la lista}

function LeerFinal(Lista:TipoPuntero):TipoValor;

{Elimina un elemento del final de la lista}

procedure EliminarFinal(var Lista:TipoPuntero);

{Devuelve true si existe un elemento en la lista y false si no}

function Existe(Lista:TipoPuntero;Dato:TipoValor):Boolean;

{Devuelve true y elimina un elemento de una lista si existe}

function ExisteElimina(var Lista:TipoPuntero;Dato:TipoValor):Boolean;

{Devuelve el número de elementos de la lista}

function Longitud(Lista:TipoPuntero):Integer;

 

{Acciones sobre una pila}

 

{La inicializa}

procedure IniciarPila(var Pila:TipoPuntero);

{¿está vacía?}

function PilaVacia(Pila:TipoPuntero):Boolean;

{Inserta}

procedure InsertarPila(var Pila:TipoPuntero;Dato:TipoValor);

{Saca}

function SacarPila(var Pila:TipoPuntero):TipoValor;

{Lee sin sacar}

function LeerPila(Pila:TipoPuntero):TipoValor;

{Obtiene el número de elementos}

function LongitudPila(Pila:TipoPuntero):Integer;

{¿Existe un elemento en la pila?}

function ExisteEnPila(Pila:TipoPuntero;Dato:TipoValor):Boolean;

{Devuelve la posición de un elemnto en la pila ( desde 1 en adelante)

Devuelve 0 si no lo encuentra}

function BuscaPosicionEnPila(Pila:TipoPuntero;Dato:TipoValor):Integer;

{Lee el elemento en una cierta posición de la pila . P.e. el octavo}

function LeePosicionEnPila(Pila:TipoPuntero;Posicion:Integer):TipoValor;

 

{Las mismas acciones para las colas}

 

procedure IniciarCola(var Cola:TipoPuntero);

function ColaVacia(Cola:TipoPuntero):Boolean;

procedure InsertarCola(var Cola:TipoPuntero;Dato:TipoValor);

function SacarCola(var Cola:TipoPuntero):TipoValor;

function LeerCola(Cola:TipoPuntero):TipoValor;

function LongitudCola(Cola:TipoPuntero):Integer;

function ExisteEnCola(Cola:TipoPuntero;Dato:TipoValor):Boolean;

function BuscaPosicionEnCola(Cola:TipoPuntero;Dato:TipoValor):Integer;

function LeePosicionEnCola(Cola:TipoPuntero;Posicion:Integer):TipoValor;

 

implementation

 

procedure CargarRegistro(var Registro:TipoValor;Dato:Tipovalor);

begin

  Registro.Fila:=Dato.Fila;

  Registro.Columna:=Dato.Columna;

  Registro.Profundidad:=Dato.Profundidad

end;

 

function CompararRegistrosPosicion(Registro,Dato:TipoValor):Boolean;

begin

  if (Registro.Fila=Dato.Fila) and

     (Registro.Columna=Dato.Columna)

  then Result:=True else Result:=False

end;

 

function CompararRegistros(Registro,Dato:TipoValor):Boolean;

begin

  if (Registro.Profundidad=Dato.Profundidad) and

     (CompararRegistrosPosicion(Registro,Dato)=true)

  then Result:=True else Result:=False

end;

 

procedure Iniciar(var Lista:TipoPuntero);

begin

  Lista:=nil

end;

 

function Vacio(Lista:TipoPuntero):Boolean;

begin

  if Lista=nil then Result:=True else Result:=False

end;

 

procedure AnadirPrincipio(var Lista:TipoPuntero;Dato:TipoValor);

var Caminante:TipoPuntero;

begin

  New(Caminante);

  CargarRegistro(Caminante^.Valor,Dato);

  Caminante^.Puntero:=Lista;

  Lista:=Caminante

end;

 

function LeerPrincipio(Lista:TipoPuntero):TipoValor;

begin

  if Lista<>nil then Result:=Lista^.Valor

end;

 

procedure EliminarPrincipio(var Lista:TipoPuntero);

begin

  if Lista<>nil then Lista:=Lista^.Puntero;

end;

 

procedure AnadirFinal(var Lista:TipoPuntero;Dato:TipoValor);

var Caminante,Auxiliar:TipoPuntero;

begin

  New(Auxiliar);

  if Lista=nil then begin

    CargarRegistro(Auxiliar^.Valor,Dato);

    Auxiliar^.Puntero:=nil;

    Lista:=Auxiliar

  end

  else begin

    New(Caminante);

    Caminante:=Lista;

    while Caminante^.Puntero<>nil do Caminante:=Caminante^.Puntero;

    CargarRegistro(Auxiliar^.Valor,Dato);

    Auxiliar^.Puntero:=nil;

    Caminante^.Puntero:=Auxiliar

  end

end;

 

function LeerFinal(Lista:TipoPuntero):TipoValor;

var Caminante:TipoPuntero;

begin

  if Lista<>nil then begin

    New(Caminante);

    Caminante:=Lista;

    while Caminante^.Puntero<>nil do Caminante:=Caminante^.Puntero;

    Result:=Caminante^.Valor

  End

end;

 

procedure EliminarFinal(var Lista:TipoPuntero);

var Caminante:TipoPuntero;

begin

  New(Caminante);

  Caminante:=Lista;

  if Caminante<>nil then

    if Caminante^.Puntero^.Puntero=nil then Lista:=nil

    else begin

      while Caminante^.Puntero^.Puntero<>nil do Caminante:=Caminante^.Puntero;

      Caminante^.Puntero:=nil

    end

end;

 

function Existe(Lista:TipoPuntero;Dato:TipoValor):Boolean;

var Caminante:TipoPuntero;

begin

  New(Caminante);

  Result:=False;

  Caminante:=Lista;

  while Caminante<>nil do

    If CompararRegistrosPosicion(Caminante^.Valor,Dato) then begin

      Result:=True;

      Break

    end

    else Caminante:=Caminante^.Puntero

end;

 

function ExisteElimina(var Lista:TipoPuntero;Dato:TipoValor):Boolean;

var Caminante:TipoPuntero;

begin

  Result:=False;

  if Lista<>nil then

    if CompararRegistrosPosicion(Lista^.Valor,Dato) then begin

      Lista:=Lista^.Puntero;

      Result:=True

    end

    else begin

      New(Caminante);

      Caminante:=Lista;

      while Caminante^.Puntero^.Puntero<>nil do

        if CompararRegistrosPosicion(Caminante^.Puntero^.Valor,Dato) then begin

          Caminante^.Puntero:=Caminante^.Puntero^.Puntero;

          Result:=True;

          Break

        end

        else Caminante:=Caminante^.Puntero;

      if Caminante^.Puntero^.Puntero=nil then

        if CompararRegistrosPosicion(Caminante^.Puntero^.Valor,Dato) then begin

          Caminante^.Puntero:=nil;

          Result:=True

        end

    end

end;

 

function Longitud(Lista:TipoPuntero):Integer;

var Caminante:TipoPuntero;p:Integer;

begin

  If Lista=nil then p:=0 else p:=1;

  Caminante:=Lista;

  while Caminante^.Puntero<>nil do begin

    Caminante:=Caminante^.Puntero;

    p:=p+1

  end;

  Result:=p

end;

 

procedure IniciarPila(var Pila:TipoPuntero);

begin

  Iniciar(Pila)

end;

 

function PilaVacia(Pila:TipoPuntero):Boolean;

begin

  Result:=Vacio(Pila)

end;

 

procedure InsertarPila(var Pila:TipoPuntero;Dato:TipoValor);

begin

  AnadirPrincipio(Pila,Dato)

end;

 

function SacarPila(var Pila:TipoPuntero):TipoValor;

begin

  Result:=LeerPrincipio(Pila);

  EliminarPrincipio(Pila)

end;

 

function LeerPila(Pila:TipoPuntero):TipoValor;

begin

  Result:=LeerPrincipio(Pila)

end;

 

function LongitudPila(Pila:TipoPuntero):Integer;

begin

  Result:=Longitud(Pila)

end;

 

function ExisteEnPila(Pila:TipoPuntero;Dato:TipoValor):Boolean;

begin

  Result:=Existe(Pila,Dato)

end;

 

function BuscaPosicionEnPila(Pila:TipoPuntero;Dato:TipoValor):Integer;

var p:Integer;Caminante:TipoPuntero;

begin

  Result:=0;

  If Existe(Pila,Dato) then begin

    New(Caminante);

    p:=1;

    Caminante:=Pila;

    while Caminante<>nil do

      if CompararRegistrosPosicion(Caminante^.Valor,Dato) then Break

      else begin

        Caminante:=Caminante^.Puntero;

        p:=p+1

      end;

    Result:=p

  end

end;

 

function LeePosicionEnPila(Pila:TipoPuntero;Posicion:Integer):TipoValor;

var Caminante:TipoPuntero;x:Integer;

begin

  New(Caminante);

  Caminante:=Pila;

  For x:=1 to Posicion-1 do Caminante:=Caminante^.Puntero;

  Result:=Caminante^.Valor

end;

 

procedure IniciarCola(var Cola:TipoPuntero);

begin

  Iniciar(Cola)

end;

 

function ColaVacia(Cola:TipoPuntero):Boolean;

begin

  Result:=Vacio(Cola)

end;

 

procedure InsertarCola(var Cola:TipoPuntero;Dato:TipoValor);

begin

  AnadirFinal(Cola,Dato)

end;

 

function SacarCola(var Cola:TipoPuntero):TipoValor;

begin

  Result:=LeerPrincipio(Cola);

  EliminarPrincipio(Cola)

end;

 

function LeerCola(Cola:TipoPuntero):TipoValor;

begin

  Result:=LeerPrincipio(Cola)

end;

 

function LongitudCola(Cola:TipoPuntero):Integer;

begin

  Result:=Longitud(Cola)

end;

 

function ExisteEnCola(Cola:TipoPuntero;Dato:TipoValor):Boolean;

begin

  Result:=Existe(Cola,Dato)

end;

 

function BuscaPosicionEnCola(Cola:TipoPuntero;Dato:TipoValor):Integer;

var p:Integer;Caminante:TipoPuntero;

begin

  Result:=0;

  If Existe(Cola,Dato) then begin

    New(Caminante);

    p:=1;

    Caminante:=Cola;

    while Caminante<>nil do

      if CompararRegistrosPosicion(Caminante^.Valor,Dato) then Break

      else begin

        Caminante:=Caminante^.Puntero;

        p:=p+1

      end;

    Result:=p

  end

end;

 

function LeePosicionEnCola(Cola:TipoPuntero;Posicion:Integer):TipoValor;

var Caminante:TipoPuntero;x:Integer;

begin

  New(Caminante);

  Caminante:=Cola;

  For x:=1 to Posicion-1 do Caminante:=Caminante^.Puntero;

  Result:=Caminante^.Valor

end;

 

end.