Es muy habitual trabajar con datos ordenados. En estructuras estáticas, como un array, habitualmente añadimos los datos nuevos al final y ordenamos en un paso posterior, pero usando estructuras dinámicas podemos avanzar en cada inserción sólo hasta donde sea necesario, de modo que cada dato quede colocado directamente en su posición correcta.
Vamos a partir de la lista dinámica anterior, para crear las siguientes operaciones: añadir un dato, obtener un dato, borrar un dato. Esta vez no indicaremos la posición de ese dato cuando añadimos, porque no es necesario, ya que la lista está ordenada: cada dato se insertará de modo automático en la posición que le corresponda. Sí podremos obtener un dato por posición (por ejemplo, el segundo dato), para poder obtener el segundo. También podríamos borrar el dato que se encuentra en una posición específica. Podemos enriquecer la lista con una función para saber si existe un cierto valor (ya no será necesario recorrer toda la lista: si encontramos un número mayor, es que no existía ese dato), igual que podríamos incorporar una que permita borrar por valor (además de hacerlo por posición).
Con estos cambios, la versión estática (basada en un array) podría ser así:
(* LISTAOE.PAS, Ejemplo de lista ordenada estática *)
(* No incluye ninguna comprobacion de errores *)
(* Parte de CUPAS5, por Nacho Cabanes *)
program listaOrdenadaEstatica;
var
datos: array[1..10] of integer;
cantidad: integer;
procedure InicializarLista;
begin
cantidad := 0;
end;
procedure Anadir(nuevoDato: integer);
var
i: integer;
posicion: integer;
begin
{ Tenemos un dato mas }
cantidad := cantidad + 1;
posicion := cantidad;
{ Primero buscamos la posicion en que debe acabar }
for i := 1 to cantidad do
if datos[i] > nuevoDato then
begin
posicion := i;
break;
end;
{ Si la posicion no es la ultima, hay que desplazar todos }
if posicion <= cantidad then
for i := cantidad+1 downto posicion+1 do
datos[i] := datos[i-1];
{ Y finalmente guardamos }
datos[posicion] := nuevoDato;
end;
function Obtener(posicion: integer): integer;
begin
Obtener := datos[posicion];
end;
procedure Borrar(posicion: integer);
var
i: integer;
begin
for i := posicion to cantidad do
datos[i] := datos[i+1];
cantidad := cantidad - 1;
end;
function Existe(valor: integer): boolean;
var
i: integer;
begin
{ Presupongo que no esta }
Existe := false;
{ Y reviso todos, cortando si aparece }
i := 1;
for i := 1 to cantidad do
if datos[i] = valor then
begin
Existe := true;
break;
end
else if datos[i] > valor then
break;
end;
function CantidadDatos: integer;
begin
CantidadDatos := cantidad;
end;
{ --- Programa de prueba --- }
var
i, n: integer;
begin
InicializarLista;
WriteLn('Guardando 3 y 2...');
Anadir(3);
Anadir(2);
WriteLn('Los datos por ahora son:');
for i := 1 to CantidadDatos do
WriteLn( Obtener(i) );
WriteLn('Ahora 6 y 4...');
Anadir(6);
Anadir(4);
WriteLn('Y ahora son:');
for i := 1 to CantidadDatos do
WriteLn( Obtener(i) );
WriteLn('Y al reves:');
for i := CantidadDatos downto 1 do
WriteLn( Obtener(i) );
WriteLn('Vamos a borrar el segundo dato...');
Borrar(2);
WriteLn('Ahora tenemos:');
for i := 1 to CantidadDatos do
WriteLn( Obtener(i) );
WriteLn('Ahora introduce nuevos datos, 0 para terminar...');
repeat
Write('Dato? ');
ReadLn( n );
if n <> 0 then
Anadir(n);
until n = 0;
WriteLn('Ahora los datos en orden eran:');
for i := 1 to CantidadDatos do
WriteLn( Obtener(i) );
WriteLn('Y al reves:');
for i := CantidadDatos downto 1 do
WriteLn( Obtener(i) );
end.
Y en pantalla mostraría algo como:
Su resultado serÃa
Guardando 3 y 2...
Los datos por ahora son:
2
3
Ahora 6 y 4...
Y ahora son:
2
3
4
6
Y al reves:
6
4
3
2
Vamos a borrar el segundo dato...
Ahora tenemos:
2
4
6
Ahora introduce nuevos datos, 0 para terminar...
Dato? 8
Dato? 1
Dato? 0
Ahora los datos en orden eran:
1
2
4
6
8
Y al reves:
8
6
4
2
1Y la versión dinámica, no es mucho más compleja que antes:
La implementación real podría ser algo como...
(* LISTAOD.PAS, Ejemplo de lista ordenada dinamica *)
(* No incluye ninguna comprobacion de errores *)
(* Parte de CUPAS5, por Nacho Cabanes *)
program listaOrdenadaDinamica;
type
puntero = ^ nodo;
nodo = record
dato: integer;
siguiente: puntero
end;
var
comienzoLista: puntero;
contadorDeDatos: integer;
procedure InicializarLista;
begin
comienzoLista := nil;
contadorDeDatos := 0;
end;
procedure InsertarEnLista( var nodoInicial: puntero; valor: integer);
var
nuevoNodo: puntero; { Variable auxiliar }
begin
{ Si hay lista }
if nodoInicial <> nil then
begin
{ Si no hemos llegado a su sitio }
if nodoInicial^.dato < valor
then
{ Miramos la siguiente posición, de forma recursiva }
InsertarEnLista(nodoInicial^.siguiente, valor)
else
begin
{ Caso contrario: si hay lista pero hay que insertar ya }
{ Reservamos espacio, }
new(nuevoNodo);
{ guardamos el dato }
nuevoNodo^.dato := valor;
{ ponemos el resto de la lista a continuación }
nuevoNodo^.siguiente := nodoInicial;
{ y hacemos que el nuevo dato sea el punto de partida }
nodoInicial := nuevoNodo
end
end
{ Si no hay lista, deberemos crearla }
else
begin
{ Reservamos espacio, }
new(nuevoNodo);
{ guardamos el dato }
nuevoNodo^.dato := valor;
{ no habrá nada a continuación }
nuevoNodo^.siguiente := nil;
{ y hacemos que la lista comience en el nuevo dato }
nodoInicial := nuevoNodo
end
end;
procedure Anadir(nuevoDato: integer);
begin
{ Tenemos un dato mas }
contadorDeDatos := contadorDeDatos + 1;
{ Y llamamos a la función auxiliar recursiva }
InsertarEnLista(comienzoLista, nuevoDato);
end;
function Obtener(posicion: integer): integer;
var
punteroActual: puntero;
i: integer;
begin
punteroActual := comienzoLista;
{ "Saltamos" tantas veces como corresponda }
for i := 1 to posicion-1 do
punteroActual := punteroActual^.siguiente;
{ Y devolvemos el valor de esa posición }
Obtener := punteroActual^.dato;
end;
procedure Borrar(posicion: integer);
var
punteroActual: puntero;
siguienteNodo: puntero;
nodoABorrar: puntero;
i: integer;
begin
{ Caso facil, al principio }
if posicion = 1 then
begin
nodoABorrar := comienzoLista;
comienzoLista := nodoABorrar;
end
{ Si es mas adelante, hay que recorrer }
else
begin
punteroActual := comienzoLista;
{ "Saltamos" tantas veces como corresponda para llegar al anterior }
for i := 1 to posicion-2 do
punteroActual := punteroActual^.siguiente;
{ Memorizamos el enlace al siguiente }
siguienteNodo := punteroActual^.siguiente;
{ Enlazamos el anterior con el nuevo }
punteroActual^.siguiente := siguienteNodo^.siguiente;
{ Y el nuevo con el que antes era el siguiente }
nodoABorrar := siguienteNodo;
end;
contadorDeDatos := contadorDeDatos - 1;
dispose(nodoABorrar);
end;
function CantidadDatos: integer;
begin
CantidadDatos := contadorDeDatos;
end;
procedure MostrarListaDesde ( comienzo: puntero );
begin
{ Si realmente hay lista }
if comienzo <> nil then
begin
{ Escribimos el valor }
writeln(comienzo^.dato);
{ Y miramos desde el siguiente }
MostrarListaDesde (comienzo^.siguiente )
end
end;
{ --- Programa de prueba --- }
var
i, n: integer;
begin
InicializarLista;
WriteLn('Guardando 3 y 2...');
Anadir(3);
Anadir(2);
WriteLn('Los datos por ahora son:');
for i := 1 to CantidadDatos do
WriteLn( Obtener(i) );
WriteLn('Ahora 6 y 4...');
Anadir(6);
Anadir(4);
WriteLn('Y ahora son:');
for i := 1 to CantidadDatos do
WriteLn( Obtener(i) );
WriteLn('Y al reves:');
for i := CantidadDatos downto 1 do
WriteLn( Obtener(i) );
WriteLn('Vamos a borrar el segundo dato...');
Borrar(2);
WriteLn('Ahora tenemos:');
for i := 1 to CantidadDatos do
WriteLn( Obtener(i) );
WriteLn('Ahora introduce nuevos datos, 0 para terminar...');
repeat
Write('Dato? ');
ReadLn( n );
if n <> 0 then
Anadir(n);
until n = 0;
WriteLn('Ahora los datos en orden eran:');
for i := 1 to CantidadDatos do
WriteLn( Obtener(i) );
WriteLn('Y al reves:');
for i := CantidadDatos downto 1 do
WriteLn( Obtener(i) );
end.
Ejercicio propuesto 9.5.1: Crea un programa que permita guardar una lista ordenada de números reales. El usuario introducirá tantos datos como desee (usando 99999 para terminar), y en ese momento se le mostrarán los datos ordenados.
Ejercicio propuesto 9.5.2: Crea un programa que permita guardar una lista ilimitada ordenada de nombres (cadenas de texto). El usuario introducirá tantos datos como desee (hasta terminar con una cadena vacía). A continuación se le preguntará qué nombres quiere buscar, y se le dirá si esa frase aparece como una de las cadenas de texto originales o no (no se debe revisar todos los datos, sino interrumpir la búsqueda cuando se sepa que el dato no existe, aprovechando que están ordenados). Esta fase de búsqueda acabará también cuando el usuario introduzca una cadena vacía.
Ejercicio propuesto 9.5.3: Crea una "lista de cadenas de texto". Utilízala para mostrar ordenado el contenido de un fichero de texto cuyo nombre indicará el usuario.