program prog_lista;
uses crt;

{$ifdef LINUX}
const FLECHA = #226#148#128#226#150#186;
const AACUTE = #195#161;
const IACUTE = #195#173;
const OACUTE = #195#179;
const UACUTE = #195#186;
const AACUTE_= #195#129;
const NTILDE = #195#177;
{$else}
const FLECHA = #196#16;
const AACUTE = #160;
const IACUTE = #161;
const OACUTE = #162;
const UACUTE = #163;
const AACUTE_= #181;
const NTILDE = #164;
{$endif}

type Lista = ^TDALista;
TDALista = object
    liga : Lista;
    dato : integer;
end;

function lista_insertar (cabecera : Lista; dato : integer) : Lista;
var nodo : Lista;
begin
    new (nodo);
    nodo^.liga := cabecera;
    nodo^.dato := dato;
    lista_insertar := nodo;
end;

function lista_quitar_ultimo (nodo : Lista) : Lista;
var liga : Lista;
begin
    if nodo <> nil then
    begin
        liga := nodo^.liga;
        dispose (nodo);
        lista_quitar_ultimo := liga;
    end
    else
        lista_quitar_ultimo := nil;
end;

function lista_quitar (nodo : Lista; dato : integer) : Lista;
begin
    if nodo <> nil then
    begin
        if nodo^.dato = dato then
        begin
            lista_quitar := lista_quitar_ultimo (nodo);
            exit;
        end;
        nodo^.liga := lista_quitar (nodo^.liga, dato);
    end;
    lista_quitar := nodo;
end;

function lista_contiene (nodo : Lista; dato : integer) : boolean;
begin
    lista_contiene := (nodo <> nil) and ((nodo^.dato = dato) or lista_contiene (nodo^.liga, dato));
end;

procedure lista_listar (nodo : Lista);
begin
    if nodo <> nil then
    begin
        lista_listar (nodo^.liga);
        writeln (nodo^.dato);
    end;
end;

function lista_ordenar (nodo : Lista) : boolean;
var dato : integer;
var cambio : boolean;
begin
    cambio := false;
    if (nodo <> nil) and (nodo^.liga <> nil) then
    begin
        if nodo^.dato < nodo^.liga^.dato then
        begin
            dato := nodo^.dato;
            nodo^.dato := nodo^.liga^.dato;
            nodo^.liga^.dato := dato;
            cambio := true;
        end;
        cambio := cambio or lista_ordenar (nodo^.liga);
        if cambio then
        begin
            cambio := lista_ordenar (nodo);
            cambio := true;
        end;
    end;
    lista_ordenar := cambio;
end;

procedure lista_imprimir (nodo : Lista);
begin
    if nodo <> nil then
    begin
        write (nodo^.dato, ' ', FLECHA, ' ');
        lista_imprimir (nodo^.liga);
    end
    else
        writeln ('nil'#10#13);
end;

function lista_tamano (nodo : Lista) : integer;
begin
    if nodo = nil then
        lista_tamano := 0
    else
        lista_tamano := 1 + lista_tamano (nodo^.liga);
end;

function lista_invertir (nodo : Lista; inversa : Lista) : Lista;
begin
    if nodo <> nil then
    begin
        inversa := lista_invertir (nodo^.liga, lista_insertar (inversa, nodo^.dato));
        dispose (nodo);
    end;
    lista_invertir := inversa;
end;

function lista_insertar_primero (nodo : Lista; dato : integer) : Lista;
begin
    if nodo = nil then
        lista_insertar_primero := lista_insertar (nil, dato)
    else
    begin
        nodo^.liga := lista_insertar_primero (nodo^.liga, dato);
        lista_insertar_primero := nodo;
    end;
end;

function lista_quitar_primero (nodo : Lista) : Lista;
begin
    if nodo <> nil then
    begin
        if nodo^.liga = nil then
        begin
            lista_quitar_primero := lista_quitar_ultimo (nodo);
            exit;
        end;
        nodo^.liga := lista_quitar_primero (nodo^.liga);
    end;
    lista_quitar_primero := nodo;
end;

function leer_entero (mensaje : string) : integer;
var entero : integer;
begin
    write ('Ingrese ', mensaje, ': ');
    readln (entero);
    writeln;
    leer_entero := entero;
end;

var cabecera : Lista;
var dato : integer;
var opcion, tecla : char;
var cambio : boolean;
begin
    cabecera := nil;
    randomize;
    repeat
        clrscr;
        writeln ('OPERACIONES B', AACUTE_, 'SICAS DE LISTAS LIGADAS');
        writeln ('a) Insertar un n', UACUTE, 'mero al final');
        writeln ('b) Quitar el ', UACUTE, 'ltimo n', UACUTE, 'mero');
        writeln ('c) Listar n', UACUTE, 'meros');
        writeln ('d) Tama', NTILDE, 'o de la lista');
        writeln ('e) Vaciar lista');
        writeln ('OPERACIONES COMPLEMENTARIAS');
        writeln ('f) Insertar n', UACUTE, 'meros aleatorios');
        writeln ('g) Insertar un n', UACUTE, 'mero al principio');
        writeln ('h) Consular si contiene un n', UACUTE, 'mero');
        writeln ('i) Quitar un n', UACUTE, 'mero a buscar');
        writeln ('j) Quitar el primer n', UACUTE, 'mero');
        writeln ('k) Ordenar lista');
        writeln ('l) Ivertir lista');
        writeln ('m) Salir'#10#13);
        write ('Seleccione una opci', OACUTE, 'n: ');
        repeat
            opcion := upcase (readkey);
        until (opcion >= 'A') and (opcion <= 'M');
        opcion := chr(ord(opcion) + 32);
        if opcion <> 'm' then
        begin
            writeln (opcion + #10#13);
            if (cabecera = nil) and (opcion <> 'a') and (opcion <> 'd') and (opcion <> 'f') and (opcion <> 'g') then
                writeln ('La lista est', AACUTE, ' vac', IACUTE, 'a.'#10#13)
            else
            begin
                if (opcion <> 'c') and (opcion <> 'd') and (opcion <> 'h') then
                begin
                    writeln ('Lista original:');
                    lista_imprimir (cabecera);
                end;
                case opcion of
                    'a': { Insertar un numero al final }
                        cabecera := lista_insertar (cabecera, leer_entero ('el n' + UACUTE + 'mero a insertar'));
                    'b': { Quitar el ultimo numero }
                        cabecera := lista_quitar_ultimo (cabecera);
                    'c': { Listar numeros }
                        begin
                            lista_listar (cabecera);
                            writeln;
                        end;
                    'd': { Tamano de la lista }
                        writeln ('Tama', NTILDE, 'o de la lista: ', lista_tamano (cabecera), '.'#10#13);
                    'e': { Vaciar lista }
                        while cabecera <> nil do
                            cabecera := lista_quitar_ultimo (cabecera);
                    'f': { Insertar numeros aleatorios }
                        begin
                            dato := leer_entero ('la cantidad de n' + UACUTE + 'meros aleatorios a insertar');
                            while dato>0 do
                            begin
                                cabecera := lista_insertar (cabecera, random (1000));
                                dec (dato);
                            end;
                        end;
                    'g': { Insertar un numero al principio }
                        begin
                            dato := leer_entero ('el n' + UACUTE + 'mero a insertar');
                            cabecera := lista_insertar_primero (cabecera, dato);
                        end;
                    'h': { Consular si existe un numero }
                        begin
                            dato := leer_entero ('el n' + UACUTE + 'mero a consultar');
                            if lista_contiene (cabecera, dato) then
                                writeln ('El n', UACUTE, 'mero ', dato, ' s', IACUTE, ' est', AACUTE,
                                    ' en la lista.'#10#13)
                            else
                                writeln ('El n', UACUTE, 'mero ', dato, ' no est', AACUTE, ' en la lista.'#10#13);
                        end;
                    'i': { Quitar un numero a buscar }
                        cabecera := lista_quitar (cabecera, leer_entero ('el n' + UACUTE + 'mero a quitar'));
                    'j': { Quitar el primer numero }
                        cabecera := lista_quitar_primero (cabecera);
                    'k': { Ordenar lista }
                        cambio := lista_ordenar (cabecera);
                    'l': { Ivertir lista }
                        cabecera := lista_invertir (cabecera, nil);
                end;
                if (opcion <> 'c') and (opcion <> 'd') and (opcion <> 'h') then
                begin
                    writeln ('Lista actualizada:');
                    lista_imprimir (cabecera);
                end;
            end;
            write ('Presione una tecla para continuar . . . ');
            tecla := readkey;
        end;
    until opcion = 'm';
end.