Software

A continuación, mostraremos los esquemas básicos de recorrido y búsqueda sobre tablas, tratadas éstas como estructuras secuenciales. Para simplificar la notación, tomaremos como conjunto de índices el intervalo [1..N]

Esquema de recorrido

var y : enter fvar
y := 1;
  incializar tratamiento
Mientras y ≠ N + 1 hacer
  tratar i - ésimo elemento
  y : = y + 1;
fMientras
tratamiento final

Como el recorrido de tablas es una tarea muy frecuente, es útil definir una instrucción más simple para utilizarla en casos como éste. Es la instrucción por, que tiene la sintaxis

por variable : = valor inicial hasta valor final paso incremento hacer
    S
fpor

Cuando el incremento sea igual a 1 podemos obviar su mención en la instrucción.

Hay que hacer notar que al final de cada instrucción, excepto en la última, se añade automáticamente el valor incremento en la variable que sirve de índice. La expresión valor final se evalúa al principio de cada iteración y por tanto las instrucciones del cuerpo del bucle no deberían modificar las variables que aparezcan.

Con esta nueva instrucción, el esquema de recorrido puede escribirse así:

var y : enter fvar
inicializar tratamiento
Por y : = 1 hasta N hacer
  tratar i - ésimo elemento
fpor
tratamiento final

Estructura iterativa for

Esta estructura iterativa no presenta un formato fijo, sino que admite numerosas variantes. Su función consiste en ejecutar un número determinar a veces una secuencia de instrucciones.

La sintaxis general (en C) de la sentencia for es la siguiente:

for (expresión 1; expresión 2; expresión 3)
{ grupo de sentencias ;}

La primera expresión de la construcción for acostumbra (pero no es obligatorio) a ser una sentencia de asignación donde se inicializa alguna variable que controla el número de veces que se debe ejecutar el bucle. Esta sentencia se ejecuta una sola vez antes de entrar por primera vez en el bucle.

La segunda expresión corresponde a la condición que indica al finalizar el bucle. La condición se evalúa antes de ejecutar el cuerpo del bucle, y por tanto al igual que la construcción mientras, el cuerpo del bucle puede ejecutarse entre 0 y N veces, donde N depende de la condición.

La tercera expresión corresponde normalmente a una sentencia de incremento o decremento sobre la variable de control del bucle. Esta sentencia se ejecuta siempre después de la ejecución del bucle.

Ejemplo

for (i = 0; i < 10; i++) 
{ ........ }

Las tres partes del for son opcionales, por lo que es posible omitir alguna o todas ellas. En cualquier caso, los puntos y comas son siempre necesarios. Por ejemplo:

for ( ; ; ) 
{ }

crearía un bucle infinito.

C permite la utilización de más de una sentencia en la primera y tercera parte de la construcción for así como más de una condición en la segunda parte. En este caso la coma está haciendo la función de un "&&". También se puede utilizar un “||”.

La construcción siguiente sería correcta en C:

for (i = 0, j = 0; y < 10, j > 0; i++, j = j-2 )
{ ..... }

Búsqueda secuencial

Supongamos una lista de elementos almacenados en un vector. El método más sencillo de buscar un elemento en un vector es recorrer el vector desde el primer hasta el último. La búsqueda secuencial compara cada elemento del vector con el valor deseado, hasta que lo encuentra o acaba de leer el vector entero.

var y : entero; encontrado : booleano; fvar
  encontrado : = falso;
  y:=1;
  Mientras (y <= N) y no encontrado hacer
si v[i] = x entonces
  encontrado:=cierto;
sino
  y:=i+1;
fsi
fmientras

Búsqueda secuencial en un vector ordenado

Básicamente el algoritmo es lo mismo de antes. Pero ahora podemos poner más restricciones. Dado que el vector está ordenado, en el momento en que encontramos un mayor valor que el que buscamos, ya estamos seguros de que no encontraremos el elemento deseado.

var y: entero; encontrado, terminar: booleano;
encontrado := falso;
terminar := falso
y := 1;
  Mientras (y <= N) y (no encontrado) y (no terminar) hacer
    si v[i] = x entonces
    encontrado := cierto;
    sino // Si v[i] > x, todos los elementos a la derecha del vector son > x.
       si v[i] > x semillas
           terminar := cierto;
       sino
           y := i + 1 ;
       fsi
    fsi
  fmientras

Tweet

Whatsapp