11.4.2 Búsqueda secuencial
Para buscar un elemento dentro de una formación es necesario recorrerla, pero no siempre en su totalidad. El recorrido se debe detener en cuanto se encuentre el elemento buscado, y por tanto sólo será completo cuando no se encuentre el elemento buscado dentro de la formación. Este planteamiento del problema indica que no se puede utilizar una sentencia FOR para la operación de búsqueda.
Para establecer un esquema general de búsqueda es necesario fijar la condición o condiciones que determinan las características del elemento buscado. Además se debe tener en cuenta el tamaño y estructura de la formación para controlar cuándo se da por finalizada una búsqueda infructuosa. En algunos casos es posible incluso que el tamaño de la formación sea nulo y no contenga ningún elemento. Todos estos condicionantes apuntan en el sentido de emplear una sentencia WHILE para realizar la búsqueda. Como esquema general se puede plantear el siguiente:
Iniciar búsqueda
WHILE ( NOT Encontrado ) AND ( NOT Final ) DO
Pasar al siguiente elemento;
Verificar encuentro
END
Este esquema se puede emplear, por ejemplo, para la búsqueda del contenido de la variable elemento en la formación vectorUno. Para ello se necesitan las siguientes declaraciones previas:
VAR
elemento: INTEGER;
posicion: Dimension;
visto: BOOLEAN;
el fragmento de programa que realiza la búsqueda sería el siguiente:
visto := FALSE;
posicion := 0;
WHILE ( NOT visto ) AND ( posicion < Ultimo ) DO
posicion := posicion + 1;
visto := elemento = vectorUno[ posicion ]
END
El valor final de la variable booleana visto indica si ha sido encontrado elemento y el valor de la variable posicion apunta la posición en la que ha sido encontrado. El empleo de dos variables tiene el incoveniente de que ambas deben ser analizadas al finalizar la búsqueda para conocer el resultado. Para evitar esto se puede dar a la variable posicion un valor fuera del rango de las posiciones posibles (normalmente la posición cero), para indicar que elemento no ha sido encontrado. Para concluir la búsqueda infructuosa apuntado a la posición cero se puede realizar el recorrido hacia atrás, empezando por Ultimo. Con este planteamiento el resultado es el siguiente:
visto := FALSE;
posicion := Ultimo;
WHILE ( NOT visto ) AND (poisicon > 0) DO
IF elemento <> vectorUno[ posicion ] THEN
posicion := posicion -1
ELSE
visto := TRUE
END
END
Cuando se sabe que el vector tiene al menos un elemento, es posible emplear la sentencia REPEAT de la siguiente forma:
visto := FALSE;
posicin := Ultimo;
REPEAT
IF elemento <> vectorUno[ posicion ] THEN
posicion := posicion – 1
ELSE
visto := TRUE
END
UNTIL visto OR ( posicion = 0 )
También se puede utilizar la sentencia LOOP, incluso con un vector vacío. En este caso el esquema a emplear es el siguiente:
Iniciar la búsqueda;
LOOP
IF Final THEN EXIT END
Verificar encuentro;
IF Encontrado THEN EXIT END;
Pasar al siguiente elemento
END
La búsqueda en vectoUno sería de la siguiente forma:
posicion := Ultimo;
LOOP
IF posicion = 0 THEN EXIT END;
IF ( elemento = vectorUno[ posicion ] ) THEN EXIT END;
posicion := posicion – 1
END
La elección del esquema más adecuado depende de la complejidad de las operaciones Verificar encuentro y Pasar al siguiente elemento, y de las posibles simplificaciones que se puedan introducir en ambas empleando uno u otro esquema.
11.4.3 Inserción
Cuando los elementos de un vector se van incorporando al mismo de una forma paulatina, uno detrás de otro, se puede aprovechar esta circunstancia para insertar el nuevo elemento en la posición que le corresponda. De esta forma, los datos del vector podrían estar siempre ordenados, lo que supone grandes ventajas.
En general, una operación de inserción de un nuevo elemento en una formación supone desplazar algunos de sus datos actuales para conseguir el hueco que le corresponde al nuevo elemento y después insertarlo en el hueco. Un posible esquema sería:
Iniciar inserción;
WHILE ( NOT Encontrado hueco ) AND ( NOT Final ) DO
Desplazar elemento;
Pasar al siguiente elemento
END
Insertar nuevo elemento
Este esquema, para la inserción de elemento dentro de los N primeros elementos de vectorUno, que ya están ordenados, se convierte en el siguiente fragmento de programa:
j := N;
WHILE ( elemento < vectorUno[ j ] ) AND ( j >= 1 ) DO
vectorUno[ j + 1 ] := vectorUno[ j ];
j := j – 1
END;
vectorUno[ j + 1 ] := elemento;
Evidentemente, después de la inserción, el vector tiene un elemento más. Por tanto, el valor de N siempre deberá ser menor que Ultimo.
11.4.4 Ordenación por inserción directa
En este apartado se aborda una solución para la ordenación de un número indeterminado de datos dentro de un vector. Existen diversos métodos de ordenación de vectores cuyo estudio cae fuera del alcance de es libro (entradas de blog). El método de ordenación por inserción directa es uno de los más sencillos y está basado en el esquema de inserción mostrado en el apartado anterior. Por ejemplo, se trata de ordenar vectorUno definido como vector de diez elementos y que inicialmente está desordenado, tal como se muestra en la Figura 11.3.
Figura 11.3. Vector Inicial
Para comenzar, el primer elemento ( 21 ) se supone ordenado. A continuación, extraemos el segundo elemento ( 5 ) y se genera un hueco, que se puede utilizar para ampliar el vector ya ordenado. El método de ordenación consiste en insertar el elemento extraído en su lugar correspondiente entre los elementos ya ordenados. Este proceso se repite con el tercero, cuarto, quinto, … y décimo elemento hasta quedar ordenado todo el vector. La secuencia de inserciones de los sucesivos elementos del vector es la siguiente:
En la secuencia se muestra la posición del hueco inmediatamente antes de la inserción del siguiente elemento. La línea quebrada indica hasta qué punto se amplía el vector ordenado con cada nueva inserción. La inserción se realiza desde la posición anterior a la del elemento extraído. La variable elemento guarda el elemento extraído de la posición i. La ordenación total del vector se consigue mediante el recorrido de todos sus elementos, desde el segundo, para buscarles su hueco e insertarlos en él. Así, el fragmento de programa de ordenación es el siguiente:
FOR i := 2 TO Ultimo DO
elemento := vectorUno[ i ]; j := i – 1;
WHILE ( elemento < vectorUno[ j ] ) AND ( j >= 1 ) DO
vectorUno[ j + 1 ] := vectorUno[ j ];
j := j-1
END;
vectorUno[ j + 1 ] := elemento
END
Este programa es válido para cualquier tamaño del vector, ya que sólo depende del valor que tome la constante Ultimo.
11.4.5 Búsqueda por dicotomía
Cuando los datos están ordenados la búsqueda resulta mucho mas rápida. Si comparamos el elemento a buscar con el que está justo en la mitad de los datos ordenados, podemos decidir si es ése el elemento que buscamos o debemos continuar buscando, pero sólo en la mitad derecha o sólo en la mitad izquierda.
El mismo proceso se puede repetir con la mitad elegida, comparando con el elemento que está en el centro de dicha mitad. En cada comparación, la búsqueda se reduce a comprobar si el dato buscado está entre la mitad de los anteriores. La búsqueda finaliza cuando el elemento se encuentra, o bien cuando no es ninguno de los dos datos consecutivos a los que queda reducida la comparación después de sucesivas divisiones en mitades. Esta búsqueda se denomina búsqueda por dicotomía.
Como esquema general de búsqueda sigue siendo válido el mismo utilizado anteriormente. Sin embargo, ahora es necesario cambiar la obtención del siguiente elemento a comparar. Como ejemplo, realizaremos la búsqueda por dicotomía de elemento vectorUno. Se necesitan dos variables para acotar el trozo de vector que todavía queda por comprobar y otra variable para señalar el punto medio de ambas. Estas variables las denominaremos izq, dch y mitad. Sus declaraciones serán:
VAR izq, dch, mitad: Dimension;
El fragmento de programa sería como sigue:
posicion := 0; izq := 1; dch := Ultimo;
WHILE ( posicion = 0 ) AND ( izq <= dch ) DO
mitad := ( izq + dch ) DIV 2;
IF Elemento = VectorUn[ mitad ] THEN
posicion := mitad
ELSIF Elemento < VectorUno[ mitad ] THEN
dch := mitad – 1
ELSIF
izq := mitad + 1
END
END
En este caso la variable posicion se utiliza para conocer si ha sido encontrado Elemento y se inicializa a cero (no encontrado). Este valor sólo se modifica cuando se consigue encontrar el elemento buscado. La búsqueda por dicotomía se puede aplicar también, por ejemplo, en el esquema de ordenación por inserción, para localizar el lugar en que hay que insertar el nuevo elemento.
11.4.6 Simplificación de las condiciones de contorno
La programación de operaciones con vectores, realizadas elemento a elemento, exige con frecuencia realizar un tratamiento especial de los elementos extremos del vector o, en general, de los elementos del contorno de una formación. A continuación veremos algunas técnicas particulares para evitar la necesidad de detectar de manera explícita si se ha llegado a un elemento del contorno, o realizar con él un tratamiento especial.
Por ejemplo, en el procedimiento general de búsqueda es necesario comprobar con cada iteración si no se ha alcanzado todavía el Final del vector. Esto complica la condición del bucle de iteración y supone un tiempo adicional en la ejecución de cada iteración. Si el dato que se trata de buscar está dentro del vector, antes o después se termina encontrando y nunca se intenta buscar fuera de los límites del mismo. En este caso la condición Final resulta innecesaria. Por tanto, se podrá prescindir de la condición Final cuando se puede asegurar que cualquier dato que se busque estará en el vector. La manera de asegurar esto es incluir el dato en el vecor antes de comenzar la búsqueda. El vector se amplía, según se muestra en la Figura 11.4, en un elemento más de índice 0. En él se copia el dato a buscar antes de iniciar la búsqueda para que actúe como centinela (C) y asegure que la búsqueda nunca acaba de forma infructuosa.
Figura 11.4. Vector con centinela
Ahora, el esquema general de búsqueda se simplifica de la siguiente forma:
Iniciar centinela;
Iniciar búsqueda;
WHILE ( NOT Encontrado ) DO
Pasar al siguiente elemento
END
Este esquema para la búsqueda del contenido de la variable elemento en el vectorUno requiere modificar la declaración de la dimensión del vector de la siguiente forma:
TYPE Dimension = [ 0..Ultimo ];
TipoVector = ARRAY Dimension OF INTEGER;
y se tiene que redifinir la variable:
VAR vectorUno: TipoVector;
La posición cero del vector estará destinada a situar el centinela y la búsqueda se simplificaría de la siguiente forma:
vectorUno[ 0 ] := elemento;
posicion := Ultimo;
WHILE elemento <> vectorUno[ posicion ] DO
posicion := posicion – 1
END
Igual que antes, si al final de la búsqueda, la variable posición tiene un valor igual a cero, quiere decir que la búsqueda ha sido infructuosa: el elemento encontrado ha sido el centinela.
La misma técnica del centinela se puede emplear en la inserción, lo que simplifica el algoritmo de ordenación. La nueva redacción del programa es la siguiente:
FOR i := 2 TO Ultimo DO
elemento := vectorUno[ i ];
vectorUno[ 0 ] := elemento; j := i – 1;
WHILE elemento < vectorUno[ j ] DO
vectorUno[ j + 1 ] := vectorUno[ j ];
j := j – 1
END;
vectorUno[ j + 1 ] := elemento
END
Como se puede observar, la técnica del centinela simplifica las condiciones de contorno para cualquier operación que se realice con un vector y el programa resulta más simple y fácil de entender.
Cuando se trabaja con matrices, también se pueden simplificar las condiciones de contorno utilizando matrices orladas. Estas matrices se dimensionan con dos filas y dos columnas más de las necesarias tal como se muestra en la Figura 11.5.
Figura 11.5. Matriz Orlada
En esa matriz se inicializa todo su contorno (filas y columnas extras) con un valor tal que permita identificar dicho contorno (C). Si se elige adecuadamente el valor C, cualquier operación que se realice con la matriz no necesita tener en cuenta sus límites declarados. Además, en algunos casos el contorno puede jugar un papel fundamental en la operación con la matriz.
Para ilustrar el uso de una matriz orlada, supongamos que tenemos una imagen en blanco y negro digitalizada dentro de una matriz definida de la siguiente forma:
CONST Puntos = 20;
Blanco = 0;
Negro = 5;
TYPE Grises = [ Blanco .. Negro ];
Indice = [ 1 .. Puntos ];
VAR imagen: ARRAY Indice, Indice OF Grises;
Cada elemento de la matriz guarda el nivel de grises del correspondiente punto de la imagen. Para tratar cada punto de la imagen individualmente basta con hacer un recorrido completo, sin ninguna complicación. Por ejemplo, para contrastar la imagen y reducir todos los puntos gris claro a blanco y todos los grises oscuro a negro, bastará escribir:
FOR i := 1 TO Puntos DO
FOR j := 1 TO Puntos DO
IF imagen [ i, j ] <= Nivel THEN
imagen [ i, j ] := Blanco
ELSE
imagen [ i, j ] := Negro
END
END
END;
Supongamos ahora que queremos recortar la imagen, esto es, eliminar aquellos puntos externos de la imagen que están en blanco, pero dejando los puntos blancos que son interiores y están rodeados de puntos negros. El tratamiento de cada punto exige examinar al mismo tiempo los puntos contiguos. El programa se simplifica si se garantiza que todo punto útil de la imagen tiene puntos contiguos en todas las direcciones, es decir, no hay situaciones excepcionales en los bordes.
Para ello lo mejor es que la matriz de la imagen sea una matriz orlada, por lo que se redefine de la siguiente forma:
TYPE Indice = [ 0 .. Puntos + 1 ];
TipoImagen = ARRAY Indice, Indice OF Grises;
Para establecer el nivel de contorno se declara un valor de borde y se redefine la escala de grises de la siguiente forma:
CONST Borde = -1;
TYPE Grises = [ Borde .. Negro ];
Suponiendo que imagen está ya contrastada anteriormente y que su contorno (es decir, la orla) está inicializado al valor de Borde, el recorte se realizaría mediante sucesivos recorridos de toda la matriz en los que los puntos blancos que tienen algún punto Borde alrededor deben pasar también a puntos de Borde. El proceso de recorte se termina cuando en un recorrido completo de toda la imagen no hay ningún punto que cambie. Esta forma de operar se denomina de fuerza bruta, y puede ser poco eficiente, pero es muy sencilla de programar. El fragmento de programa que realiza ésto es el siguiente:
REPEAT
fin := TRUE;
FOR i := 1 TO Puntos DO
FOR j := 1 TO Puntos DO
IF ( imagen [ i, j ] = Blanco ) AND (( imagen [ i-1, j ] = Borde )
OR ( imagen [ i, j-1 ] = Borde )
OR ( imagen [ i, j+1 ] = Borde )
OR ( imagen [ i+1, j ] = Borde )
THEN
imagen [ i, j ] := Borde; fin := FALSE
END
END
END
UNTIL fin
Este ejemplo es un fragmento de uno de los programas completos que figura como ejemplo al final del Tema.
11.5 Vector de caracteres: Ristra (String)
Debido a su frecuente uso, en el Tema 2 fueron ya presentadas las constantes de tipo ristra. Sin embargo, hasta ahora no hemos podido utilizar variables de este tipo. Esto se debe a que en realidad las ristras son vectores de caracteres y los vectores no han sido estudiados hasta este Tema. Sin embargo, en todos los lenguajes es habitual que las ristras tengan ciertas peculiaridades que no tienen el resto de los vectores y por esta razón son objeto de este apartado específico.
En Modula-2 cualquier vector cuya declaración sea de la forma:
ARRAY [ 0 .. N ] OF CHAR
se considera una ristra o string, con independencia de su longitud particular, esto es, del valor de N. Las características peculiares de las ristras son:
a) El primer elemento de una ristra siempre es el índice igual a cero.
b) En un vector de esta clase se pueden almacenar ristras de diferentes longitudes (si caben). Para distinguir la longitud útil en cada momento se reserva siempre espacio para un carácter más, y se hace que toda ristra termine con un carácter nulo (0C) situado al final.
Por tanto, para declarar una ristra de veinte caracteres se debe hacer de la siguiente forma:
TYPE
Ristra20 = ARRAY [ 0 .. 20 ] OF CHAR;
La declaración de variables de este tipo se hace de la forma habitual:
VAR
nombre, apellido: Ristra20;
direccion: ARRAY [ 0 .. 40 ] OF CHAR;
La asignación de un valor a una variable de tipo ristra se realiza de la siguiente forma:
apellido := "Gonzalez";
direccion := "Paseo de la Castellana 345 – 6º";
Como se puede observar, no es necesario asignar una ristra con los veinte o cuarenta caracteres. Cuando el número de caracteres asignados es menor que los declarados, a continuación del último se sitúa el carácter nulo (0C) de final de ristra. Este carácter es especial y no se puede escribir. Lo que nunca se puede hacer es asignar más caracteres de los declarados pues se rebasarían los límites previstos y se provocaría un error. Al igual que con cualquier otro tipo de vector, para poder realizar asignaciones entre variables de tipo ristra es necesario que ambas sean del mismo tipo. Por ejemplo:
nombre := apellido;
Estas variables se pueden utilizar como argumento del procedimiento de escritura de ristras. Por ejemplo:
WriteString( "APELLIDO : " ); WriteString( apellido );
produce el siguiente resultado:
APELLIDO : Gonzalez
El procedimiento de escritura sólo escribe el contenido de la variable hasta el primer carácter nulo, aunque en versiones antiguas del lenguaje puede que se escriba el vector completo.
También es posible utilizar variables de tipo ristra con el procedimiento de lectura de ristras que suele estar disponible en el módulo InOut. Por ejemplo:
ReadString( nombre );
Las características y funcionamiento de este procedimiento dependen del compilador concreto y por tanto se debe consultar el manual correspondiente. En cualquier caso, el procedimiento guardará en la variable la ristra introducida por teclado.
11.6 Argumentos de tipo vector abierto
Una de las operaciones que se puede realizar con los vectores es pasarlos como argumento de un procedimiento o función. En su definición se tienen que indicar la estructura y tamaño del vector que se puede pasar como argumento. Por ejemplo:
TYPE TipoVector = ARRAY [ 1 .. 10 ] OF INTEGER;
. . . .
PROCEDURE LeerVector( VAR v: Vector )
Este procedimiento sólo permite operar con vectores de diez elementos de tipo INTEGER. Si dentro del mismo programa se necesita realizar un procedimiento idéntico para vectores de once elementos también de tipo INTEGER, sería necesario realizar un nuevo procedimiento para once elementos. En general, sería necesario realizar una versión distinta del procedimiento para cada tamaño diferente del vector con el que se quiera trabajar. Evidentemente ésto no es la solución más adecuada.
Una forma de trabajar con vectores de diferentes tamaños es definir un tipo único con capacidad para el mayor de todos los que se necesiten. Cuando no se utiliza todo el tamaño, es necesario indicar de alguna forma qué elementos se están empleando realmente. Esto se puede hacer, por ejemplo, almacenando en alguna parte el número de elementos en uso, o marcando el final con un valor nulo como sucede con las ristras. Esto se deberá tener en cuenta en la programación del procedimiento. Con esta solución todos los vectores que se pasen como argumento deben tener el mismo tamaño máximo, lo que supone un despilfarro de memoria en la mayoría de los casos.
Otra solución permitida en Modula-2 es emplear vectores abiertos como argumentos en la definición del procedimiento o función. Un vector abierto es aquél del que sólo se define el tipo de sus elementos, pero no el rango del índice. El tipo implícito de su índice es siempre un subrango comprendido entre 0 y un valor máximo. En Modula-2 se expresa en la forma:
PROCEDURE Muestra( X: ARRAY OF TipoElemento )
Esta definición indica que es posible pasar en la llamada cualquier vector con una estructura tal como la siguiente:
ARRAY [ P .. Q ] OF TipoElemento;
Por ejemplo, si tenemos la siguiente declaración de función:
PROCEDURE Simetrico( texto: ARRAY OF CHAR ): BOOLEAN;
es válido realizar cualquiera de las siguientes llamadas:
VAR nombre: ARRAY [0..20] OF CHAR;
rotulo: ARRAY [1..10] OF CHAR;
(1) IF Simetrico( rotulo ) THEN …
…
(2) IF Simetrico( nombre ) THEN …
…
(3) IF Simetrico( "abracadabra" ) THEN …
Para hacer referencia dentro de la función al tamaño del vector utilizado en cada llamada, se puede usar la función predefinida siguiente;
HIGH( X )
Esta función devuelve como resultado el valor superior del índice del vector pasado como argumento X en la llamada. Por ejemplo, HIGH( texto ) vale 9 en la llamada (1) del ejemplo anterior, 20 en la llamada (2), y 11 en la llamada (3). Nótese que internamente el rango del índice siempre se cuenta como si empezase en cero.
Un ejemplo típico de la utilidad de los vectores abiertos es el procedimiento predefinido WriteString. Este procedimiento se puede utilizar con ristras constantes o variables de cualquier tamaño. Su funcionamiento puede describirse basándose en el procedimiento Write para escribir un carácter, de la manera siguiente:
PROCEDURE WriteString( s: ARRAY OF CHAR );
CONST Nulo = 0C;
VAR k: INTEGER;
BEGIN
k := 0;
LOOP
IF k > HIGH( s ) THEN EXIT END;
IF s[ k ] = Nulo THEN EXIT END;
Write( s[ k ] );
INC( k )
END
END WriteString;
De la misma forma, es posible definir un procedimiento para ordenar vectores de cualquier tamaño. Este era el problema que se planteaba al comenzar este tema. Por ejemplo, para ordenar vectores de enteros se puede definir un procedimiento con un argumento del tipo vector abierto, que aplique el método de ordenación por inserción. El vector pasado como argumento debe tener la primera posición reservada para usarla como centinela. El código sería:
PROCEDURE Ordenar( VAR v: ARRAY OF INTEGER );
VAR i, j: Dimension;
elemento: INTEGER;
BEGIN
FOR := 2 TO HIGH( v ) DO
elemento := v[ i ];
v[ 0 ] := elemento;
j := i – 1;
WHILE elemento < v[ j ] DO
v[ j + 1 ] := v[ j ];
j := j – 1
END
v[ j + 1 ] := elemento
END
END Ordenar;
Finalmente, es importante resaltar que no se pueden utilizar matrices abiertas.
Fraternidad-Igualdad-Libertad 