Hemos llegado al tema final de la primera parte de este curso. No me extenderé mucho más, sino que haré una presentación con ejemplos como siempre, algún caso típico de error y luego les dejaré los ejercicios prácticos más dos proyectos: Una actualización del Base de Productos y dos proyectos nuevos que proponen cada uno un videojuego de lógica, muy interesante. Estos proyectos son de una dificultad muy alta, tienen programada una interfaz gráfica sencilla que ya está lista para usar.

Estos proyectos son tanto o más importantes que todo lo que ya les he propuesto, por tanto vuelvo a pedirles por favor que tomen la iniciativa de hacer uno de ellos, de chocarse contra un muro enorme y duro, que tengan que pedirme ayuda para poder seguir, etc, etc. De este modo, si han logrado hacer esto, estarán saliendo de este curso online con un nivel medio en programación estructurada, listos para aprender un lenguaje potente. Si hacen esto ya pueden llamarse programadores, solo que aún hay mucho más por aprender.

El curso que estoy escribiendo como continuación de este pretenderá introducirlos a nuevas técnicas de programación que serán más difíciles de asimilar, por ejemplo, la recursión. En ese curso asumiré en todo momento que han aprendido lo que he enseñado en todas las lecciones que componen esta entrega, de modo que podamos seguir adelante en las nuevas técnicas sin perder tiempo en entender como funciona un IF, un REPEAT o qué significa invocar a un PROCEDIMIENTO.
Espero que muchos de ustedes a estas alturas puedan mirar hacia atrás y comparar lo que sabían antes de empezar este curso con lo que saben hoy y sentirse contentos por darse cuenta de que han aprendido mucho, ese es mi cometido. Claro está que muchos de ustedes tendrán que repasar muchas lecciones varias veces para terminar de aprender, y eso es justamente lo que quiero.
Bien, vallamos a lo que nos concierne ahora:

Listas encadenadas simples:

Es aquí donde utilizaremos el verdadero potencial de los punteros. No aprenderemos en sí nada nuevo ya que en lo que a lenguaje refiere hemos aprendido todo a lo que apunta este curso, esto es simplemente una implementación de una herramienta ya conocida, una implementación que probablemente no se les ocurriría por sí mismos y es por esto que en las universidades y cursos de programación se enseña de forma específica.

Dando una definición sencilla, una lista encadenada simple es un listado (valga la redundancia) de varios elementos de un mismo tipo donde existe uno que es el primero y uno que es el último, tal como en los arreglos. La diferencia es que las listas son dinámicas y pueden aumentar o disminuir de tamaño llegando incluso a ser vacías, ocupando solo la memoria que necesitan para existir en un momento preciso. A forma de esquema, tenemos un primer elemento que, además de contener todos los datos que sean, nos dirá donde está el segundo elemento. Este elemento nos dirá donde está el tercero, que nos dirá donde esta el cuarto, y así sucesivamente hasta llegar a uno que nos diga “Ya no hay más elementos después de mí”.



Allí pueden ver un dibujo sencillo de lo que sería una lista encadenada. Cada elemento puede contener muchos datos y, además, nos dice donde está el elemento siguiente a él en la lista, hasta que algún elemento nos diga que ya no existe nada más después de él con lo cual diremos que estamos al final de la lista.

Veamos como aplicar este concepto en PASCAL. Para empezar diremos que cada elemento de una lista es un nodo, por lo tanto una lista puede ser vacía (cuando no existe nodo alguno), contener un nodo o varios. La gracia de esto será poder modificar los nodos, quitarlos, agregarlos y moverlos. En este primer ejemplo definiremos lo que es un nodo de lo que será un alista de números enteros. Pongan mucha atención para comprender esto porque causa confusión y a veces cuesta entender lo que se está escribiendo. Este tema en particular es el que causa que muchos estudiantes pierdan los cursos de programación como el que yo les he dado aquí y es por eso el que necesita más trabajo, tanto de ustedes para asimilarlo como mío para transmitirlo.

Antes de ir directo a la definición de lo que es una lista, veamos un ejemplo donde tenemos un puntero hacia un registro que guarda varios datos de una persona, tales como el Nombre, Apellido, Edad, Sexo y Documento.

Código:
PROGRAM PunteroARegistro;

TYPE
   TSexo= (Masculino,Femenino);

   TPersona= RECORD
      Nombre, Apellido: String;
      Edad: Integer;
      Sexo: TSexo;
      Documento: Integer;
   End;

   TPunteroPersona= ^TPersona;

VAR
   Persona: TPunteroPersona;
   auxSexo: String; //Para leer el sexo y luego asignar el valor al enumerado.

BEGIN
   //Pedimos la memoria para guardar el registro de nuestra persona.
   NEW(Persona);

   {Ahora mi puntero Persona apunta a algún lugar de la memoria que contiene basura}
   //Leemos los datos desde la entrada estándar.
   Write('Ingresa el nombre: ');
   ReadLn(Persona^.Nombre);
   Write('Ingresa el apellido: ');
   ReadLn(Persona^.Apellido);
   Write('Ingresa la edad: ');
   ReadLn(Persona^.Edad);
   Write('Ingresa el sexo (Masculino/Femenino): ');
   ReadLn(auxSexo);
   If auxSexo= 'Masculino' then
      Persona^.Sexo:= Masculino
   else if auxSexo='Femenino' then
      Persona^.Sexo:= Femenino;
   Write('Ingresa el documento: ');
   ReadLn(Persona^.Documento);

   {Ahora mi registro está cargado de datos.}
   //Mostraremos los datos ingresados.
   WriteLn(Persona^.Nombre);
   WriteLn(Persona^.Apellido);
   WriteLn(Persona^.Edad);
   If Persona^.Sexo=Masculino then
      WriteLn('Masculino')
   else if Persona^.Sexo=Femenino then
      WriteLn('Femenino');
   WriteLn(Persona^.Edad);

   //Ahora elminamos los datos guardados.
   DISPOSE(Persona);

   //Esto ha liberado la memoria de toda la información contenida en el registro.
   //Podríamos pedir memoria nuevamente para cargar nuevos datos.
END.
Dado este ejemplo, iremos a la declaración de un "Tipo Lista". La única diferencia es que incluimos en el registro un campo que contiene un puntero hacia un registro del mismo tipo. Veremos el ejemplo creando una lista que contenga solo números enteros:

Código:
TYPE
   Lista= ^NodoLista;

   NodoLista= Record
      numero: integer;
      siguiente: Lista;
   End;
¡¡¡¿¿¿QUÉ ES ESOOOOOOOOOOOO???!!!

Veamos: Definimos el tipo Lista como puntero hacia el tipo NodoLista, el cual declaramos más abajo como un registro de dos campos, uno del tipo entero que será nuestra información, y otro con un puntero del tipo Lista, o sea, un puntero que apuntará a elementos del tipo NodoLista. Al tener un puntero del tipo Lista, estaremos apuntando a un registro que dentro de él tendrá, además de un número entero, otro puntero del tipo Lista, y así por cada uno. Cada elemento del tipo Lista podrá apuntar a otro con la misma estructura. Veamos esto en un dibujo:



Como ven, cada elemento del tipo Lista tiene, además de un número entero, un puntero que apunta a una estructura del tipo Lista por lo cual podemos ir repitiendo esa estructura tanto como queramos, donde cada elemento tiene el puntero hacia el siguiente quedando todos encadenados. Esta definición de un tipo para crear una lista encadenada es recursiva. Se entenderá mejor qué quiero decir cuando tratemos recursión en el curso siguiente, mientras tanto traten de comprender esta estructura tal como se las he dado.

De este modo, para tener una lista simplemente necesito el puntero hacia el primer elemento ya que a partir de este podré obtener el siguiente y, recorriendo uno a uno, puedo ver la lista completa. Siempre para dar una lista debe darse el puntero hacia el primer elemento.

Dado este sistema, debemos recorrer siempre las listas de forma secuencial, elemento a elemento, ya que no podemos ir directamente a un nodo específico. Por ejemplo, en una lista de 10 elementos no puedo ir al elemento número 5 sin antes recorrer los 4 anteriores. Esto deriva en problemas de eficiencia y metodologías del uso de listas para solucionarlos, pero no los veremos aquí ya que lo importante ahora es saber trabajar con ellas en su forma más sencilla.

Crearemos, dada la estructura anterior, una lista de tres nodos, guardando el número 10 den cada uno:

Código:
1 PROGRAM   PrimeraLista;
2
3   TYPE
4      Lista= ^NodoLista;
5
6      NodoLista= Record
7         numero: integer;
8         siguiente: Lista;
9      End;
10
11 VAR
12    MiLista, i: Lista;
13
14 BEGIN
15 New(MiLista); //Creo el primer elemento de la lista.
16 i:= MiLista; //Utilizo un puntero alternativo como alias para iterar.
16 i^.numero:= 10;
17
18 New(i^.siguiente); //Creo el segundo elemento de la lista.
19 i:= i^.siguiente; //Ahora i apunta al segundo elemento de la lista.
20 i^.numero:= 10;
21
22 New(i^.siguiente); //Creo el tercer elemento de la lista.
23 i:= i^.siguiente; //Ahora i apunta al tercer elemento de la lista.
24 i^.numero:= 10;
25 END.
Analicemos este código un poco; tengan en cuenta que lo he hecho así para que vean todo, luego lo haré de la forma correcta.

En la línea 15 invocamos a NEW para que la variable puntero MiLista obtenga un lugar de memoria para almacenar a un registro NodoLista:



MiLista obtiene la dirección de un registro NodoLista y apunta hacia allí. Dicho registro tendrá a priori un número entero cualquiera en su campo numero y un puntero no inicializado en su campo siguiente.

En la línea 16 utilizo un puntero adicional i para apuntar también al primer elemento de la lista transformando a MiLista y a i en alias:



En la línea 18 solicito el espacio necesario para alojar a un nuevo elemento. El puntero i^.siguiente es del tipo Lista, por lo tanto la sentencia New(i^.siguiente) creará un nuevo registro y nos dará su dirección de memoria:



En la línea 19 hago que i apunte al elemento creado recientemente:



En la línea 20 asigno el valor 10 al nuevo elemento:



En la línea 22 creo el tercer elemento del mismo modo que fue hecho para crear el segundo. Luego hago que i apunte hacia dicho elemento para asignarle el valor 10 tal como hice anteriormente:



De este modo he logrado construir una lista de tres nodos, cada uno con el valor 10, donde el puntero MiLista apunta siempre al primero de ellos y todos están encadenados; así, solo obteniendo la dirección de MiLista puedo recorrer todos los nodos uno por uno.

Veamos ahora un código que hace lo mismo pero mediante un FOR que iterará tres veces. Este código es el más correcto ya que será igual de largo para crear tres nodos que para crear cien ¿comprenden?:

Código:
1   PROGRAM PrimeraLista;
2
3   TYPE
4      Lista= ^NodoLista;
5
6      NodoLista= Record
7         numero: integer;
8         siguiente: Lista;
9      End;
10 VAR
11    MiLista, i: Lista;
12    j: integer; //Un iterador entero para el FOR.
13
14 BEGIN
15 New(MiLista);
16 For j:= 1 to 3 do //Crearé tres nodos.
17 begin
18    If j=1 then
19       i:=MiLista
20    else
21       new(i^.siguiente);
22
23    If j<>1 then
24       i:= i^.siguiente;
25
26    i^.numero:= 10;
27 end;
28 END.
El análisis de este código les queda de tarea para ustedes.

-------------------------------------------------------------------------------

Fin de lista:

En la primera lista que hemos visto aquí creamos tres nodos. Ahora haremos un pequeño programa que cree tantos nodos como el usuario quiera y a cada uno le asigne el número que el usuario quiere. Al terminar nos dirá cuantos nodos hemos creado. Asumimos en todo momento que el usuario siempre ingresa información correcta:

Código:
PROGRAM PrimeraLista;

USES crt;

TYPE
   Lista= ^NodoLista;
   NodoLista= Record
      numero: integer;
      siguiente: Lista;
   End;

VAR
   MiLista, i: Lista;
   j: integer; //Un iterador entero para el FOR.
   opcion: char; //Para leer opciones de teclado.

BEGIN
//En esta sección de código solo mostramos opciones al usuario, creando
//la lista vacía si el usuario dice que SI.
//
//-----------------------------------------------------------------------
clrscr;
write('¿Desea crear una lista de números enteros? S/N: ');
readln(opcion);
j:= 0;

//Simplemente damos opciones de inicio al usuario.
Case opcion of
   'S': begin
           MiLista:= NIL;
           writeln('Hemos creado una lista vacía.');
           writeln;
        end;
   'N': begin
           write('Presione ENTER para salir...');
           readln;
           exit;
        end;
End;//Fin del CASE OF.

{Crearemos tantos nodos como quiera el usuario. Cada vez que elija la opción 1 crearemos un nuevo nodo y leeremos un número de la entrada estándar. Terminaremos cuando el usuario lo desee.
De este modo la lista será de un largo totalmente aleatorio en cada ejecución}
//-----------------------------------------------------------------------

Repeat
   //Mostramos las opciones al usuario
   clrscr;
   writeln('LISTA DE NÚMEROS: ');
   writeln;
   writeln('1) Agregar nuevo número a la lista');
   writeln('2) No agregar más números');
   writeln;
   write('Opción: ');
   readln(opcion);
   {Si la opción leída es 1 creo el nodo correspondiente y hago que i apunte a dicho nodo. Vean que discrimino mediante un IF si la lista es vacía y si no lo es. Al final leo el número directo sobre el nodo para luego sumar 1 a mi contador j.}

   Case opcion of
      '1': begin
              clrscr;
              write('Número: ');
              If MiLista=NIL then
              begin
                 New(MiLista);
                 i:= MiLista;
              end
              else
              begin
                 new(i^.siguiente);
                 i:= i^.siguiente;
             end;
                readln(i^.numero);
                j:= j+1;
            end;
      '2': writeln('No se ingresarán más números.');
   end;
Until opcion='2';
//Terminado el bucle del REPEAT mostramos la información al usuario y ya.

clrscr;
writeln('Se han agregado ',j,' números.');
write('Presione ENTER para salir.');
END.
No he numerado las líneas de este código porque no lo analizare, los comentarios son lo suficientemente descriptivos como para que ustedes puedan comprender lo que se está haciendo, además de que todo ha sido explicado con anterioridad. No continúen hasta no comprender este código.

¿Para qué este programa? ¿Qué tiene que ver con el fin de una lista? Bueno, lo que hemos hecho aquí es crear una lista de largo aleatorio, o sea, crearemos tantos nodos como el usuario quiera en el momento, por lo tanto nunca es posible saber cuantos elementos tendremos. Entonces, ¿qué pasa si ahora queremos mostrar los elementos de la lista? Debemos recorrer uno a uno hasta llegar al final de la misma, pero no sabemos hasta donde recorrer. Es cierto que en este caso hemos contabilizado los nodos creados por lo cual podríamos iterar tantas veces como diga nuestra variable j, sin embargo esa no es la forma correcta de hacerlo porque en general, los programas que trabajan listas no van contabilizando lo que crean ya que la complejidad a la que se enfrentan no lo permite y traería muchísimos problemas, sobretodo al tener que utilizar herramientas como la recursión, que, aunque en este curso no la aprenderemos, es importante que aprendan a trabajar de forma correcta desde el principio. No puedo explicitarles aquí la importancia de esto ya que no es a lo que apunta este curso. Normalmente los programas trabajan con módulos independientes, o sea, partes de código independientes entre sí donde cada una está en archivos diferentes, y luego existe un archivo principal que se encarga de enlazar (hacer link o linkear) todos los archivos independientes. De este modo el paso de información entre un módulo y otro se vuelve complejo y cuanto menos variables y estructuras existan en este pasaje hacen que la programación sea más sencilla, así como el mantenimiento y la actualización de los programas. En nuestro próximo manual, donde pasaremos al lenguaje MODULA-2, que es un PASCAL un tanto más avanzado y orientado a la modularización de programas, muy cerca de lo que es la programación orientada a objetos, aprenderán estas cosas y podrán hacer programas mucho más complejos, como pequeños editores de texto y demás.

Veamos entonces cómo marcar el final de una lista de manera correcta. Es simple. Cada nodo tiene un puntero que apunta al siguiente elemento de la lista, el último elemento simplemente apuntará a NIL y ya, con eso diremos que la lista terminó y con eso podremos crear algoritmos muy eficientes en el tratamiento de listas encadenadas.



---------------------------------------------------------------------------------

Trabajos comunes con listas

Veamos, de forma genérica, ejemplos de códigos para el trabajo habitual con listas encadenadas, o sea, contabilizar sus elementos, agregar un elemento al principio, agregar un elemento al final, buscar un elemento dentro de la lista, borrar el primero, borrar la lista completa:

Largo de una lista:
Código:
function largo(l: lista): integer;
var
   contador: integer;
   p: lista;
begin
   contador:= 0;
   p:= l;
   while p <> nil do
   begin
      contador:= contador + 1;
      p:= p^.siguiente; (* avanzar a la siguiente celda *)
   end;
   largo:= contador;
end;
----------------------------------------------------------

Búsqueda de un elemento:

Código:
function pertenece(elem: T; l: lista): boolean;
var
   p: lista;
begin
   p:= l;
   (* notar: evaluación por circuito corto *)
   while (p <> nil) and (p^.elemento <> elem) do
      p:= p^.siguiente;
   pertenece:= (p <> nil);
end;
Como ven en los comentarios, notar la evaluación por circuito corto. Si no lo recuerdan, significa que en una condición AND, la parte de la izquierda se cumple entonces verificamos la parte de la derecha y en caso de que ambas sean ciertas el AND es cierto (TRUE). Si la condición de la izquierda es falsa entonces ni siquiera verificamos la de la derecha. En este caso, si la condición de la derecha es falsa significa que p=NIL por lo tanto, si quisiéramos verificar la segunda parte tendríamos que acceder a p^, lo cual es un error porque un puntero NIL no apunta a nada.

---------------------------------------------------------


Agregar elemento al principio:

Código:
procedure agregar_al_principio(var l: lista; elem: T);
var p : lista;
begin
   new(p); (*crear nueva celda*)
   p^.elemento:= elem; (*cargar el elemento*)
   (* ajuste de punteros *)
   p^.siguiente:= l;
   l:= p;
end;
----------------------------------------------------------

Agregar elemento al final:

Código:
procedure agregar_al_final(var l: lista; elem: T);
var p,q : lista;
begin
   new(p); (*crear nueva celda*)
   p^.elemento:= elem; (*cargar el elemento*)
   p^.siguiente:= nil; (*es el último*)
   if l = nil then
       l:= p
   else
   begin
      (*busco el último de l*)
      q:= l;
      while q^.siguiente <> nil do
         q:= q^.siguiente;
      (*engancho p a continuacion del último*)
      q^.siguiente:= p;
   end;
end;
----------------------------------------------------------

Borrar el primer elemento de una lista no vacía:

Código:
procedure borrar_primero(var l: lista);
var
   p: lista;
begin
   p:= l;
   l:= l^.siguiente;
   dispose(p);
end;
----------------------------------------------------------

Borrar una lista completa:

Para liberar todo el espacio ocupado por una lista es necesario liberar celda por celda.

Código:
procedure borrar_lista(l: lista);
var
   p: lista;
begin
   while l <> nil do
   begin
      p:= l;
      l:= l^.siguiente;
      dispose(p);
   end;
end;
-----------------------------------------------------------------

¿Qué pasa si, teniendo una lista de N cantidad de elementos hago DISPOSE del primero?

Pues se borrará el primer elemento y todos los demás nodos quedarán colgados en la memoria. Si no tenemos algún puntero apuntando a alguno entonces ya no podremos acceder a ellos.

Del mismo modo, si modificamos el puntero inicial de la lista para que apunte a otro nodo pues ya no podremos volver para atrás y por tanto nos quedarán cosas colgadas.

Todo esto se tratará en los ejercicios.

----------------------------------------------------------------------------

Ejercicios Estos son una continuación de los ejercicios de punteros, solo que orientados al trabajo con listas, por eso comienzan desde el número 5:

Ejercicio 5: Dado el siguiente código que permite crear una lista encadenada:
Código:
TYPE
   apuntador = ^registro;
   registro = RECORD
      dato : ...; (* integer, char, real, ... *)
      sigreg : apuntador;
   END;

VAR
   apuntaInic : apuntador;
   apuntaActual : apuntador;
   indice : integer;

BEGIN
new(apuntaInic);
apuntaActual := apuntaInic;
FOR indice := 1 TO 3 DO
BEGIN
   new(apuntaActual^.sigreg);
   apuntaActual := apuntaActual^.sigreg
END;
apuntaActual^.sigreg := NIL;
END.
¿Cómo modificarían el código anterior si se desea, mediante la inclusión de una tercera variable de tipo apuntador, apuntar al último registro de la lista? Suponiendo que el tipo del campo ‘dato’ en el registro definido anteriormente es de tipo char, escriban un procedimiento en Pascal llamado Buscar que exhiba un mensaje que indique si un valor de tipo char se encuentra o no en la lista.
El cabezal del procedimiento es el siguiente:

Código:
procedure Buscar(c : char; apuntaInic : apuntador)
donde c es el char a buscar y apuntaInic es la referencia del comienzo de la lista.

--------------------------------------------------------------------------------

Ejercicio 6:
1.Definan un tipo llamado ListEnt, el cual representa una lista encadenada de enteros.

2. Escribir un procedimiento en Pascal que permita insertar un entero al principio de la lista encadenada. El cabezal del procedimiento es el siguiente:

Código:
Procedure InsertarPrincipio(valor: integer; VAR lista: ListEnt);
3. Escribir un procedimiento en Pascal que permita eliminar el primer elemento de una lista encadenada. El cabezal del procedimiento es el siguiente:

Código:
procedure EliminarPrincipio (VAR lista: ListEnt);
--------------------------------------------------------------------------------

Ejercicio 7: Dada la siguiente definición:
Código:
Type
   ListChar = ^registro;
   registro = RECORD
      campo: char;
      siguiente : ListChar
   END;
1. Escribir una función en Pascal que permita insertar un carácter al final de una lista encadenada de caracteres.
Ponga especial atención en no modificar la lista con la cual se invoca a la función, sino que se debe copiar toda la lista, y operar sobre la copia.
El cabezal de la función es el siguiente:

Código:
function InsertarUltimo (valor :char; lista: ListChar):ListChar;
2. Escribir un procedimiento en Pascal que permita eliminar los primeros cant caracteres (siendo cant una variable dada, mayor o igual a cero) de una lista encadenada de caracteres. El cabezal del procedimiento es el siguiente:

Código:
procedure DescartarComienzo(cant : integer; VAR lista: ListChar);
3. Escribir una función en Pascal que permita obtener, a partir de una lista de caracteres, otra lista con los caracteres que se encuentran entre la posición “indBase” e “indSup” de la lista original (siendo “indBase“ e “indSup” números enteros mayores o iguales a cero). El cabezal de dicha función es el siguiente:

Código:
function SubCadena (indBase, indSup : integer; lista : ListChar) : ListChar;
--------------------------------------------------------------------------------

BASE PRODUCTOS – Parte 3

Nuestro programa seguirá haciendo las mismas cosas que en su segunda parte solo que esta vez utilizará la estructura de listas encadenadas para almacenar los elementos de modo que solo utilizará la memoria necesaria para la cantidad de productos almacenados en el momento.
Será tarea de ustedes modificar los cabezales de los procedimientos y las funciones que utilizaban la estructura del arreglo con tope para trabajar con la lista de elementos así como es tarea de ustedes modificar la declaración de los tipos principales del programa. No necesitan trabajar con listas para corregir errores de la entrada estándar, solo quiero que lo hagan con la lista de productos.

Si necesitaran que yo les envíe los cabezales de todos los subprogramas no tendré problema en hacerlo ya que por lo general es lo que se hace, sin embargo será un buen ejercicio para ustedes el tener que pensarlos.

Saludos a todos.