Definido el concepto de array, en este post se verán algunos algoritmos de las operaciones comunes sobre tablas, tales como inserción de un elemento, búsqueda, ordenación… El objetivo es generar una idea clara de cómo se trabaja con tablas, independientemente del lenguaje, por ello esta vez codificaré en pseudocódigo, teniendo en cuenta que:

- Llamaré N al número de elementos presentes en la tabla.

- Llamaré T al número máximo de elementos en la tabla, el declarado con la tabla. tabla(T) es tabla de…

- El rango irá de 1 a T, siendo tabla[1] el primer elemento y tabla[T] el último. (Si codificas en C, ten en cuenta que el índice de los arrays comienza en cero y no en uno)

Lectura y escritura

Como se vió en la primera parte, se puede hacer a un elemento de forma directa, indicando su indice, sin necesidad de recorrer toda la tabla. (tabla[indice]=4; ó variable=tabla[indice]).

Actualización del array

Cuando trabajemos con arrays, no siempre lo tendremos “completo”. Es decir, podemos tener un vector de 5 elementos en el que la mayor parte del tiempo sólo los elementos con índice 1, 2 y 3 tienen algo significativo. A lo largo del programa, puede darse el caso que prescindamos del tercer elemento o añadamos un dato al elemento con índice 4. Por ello, de algún modo debemos llevar cuenta del número de elementos que nos valen, almacenandolos en las primeras posiciones. Respecto al N comentado al principio del post, diremos que los elementos con datos significativos estarán en el rango 1-N. (tabla[1] primer elemento con dato significativo, tabla[N] último elemento con dato significativo). A medida que vayamos considerando elementos o despreciandolos, iremos actualizando el valor de N.

Adicción a continuación del último elemento

Insertaremos en el último lugar (N+1) si el array no está lleno.

Si N < T
tabla[n+1]=valor
N=N+1
Sino
Escribir “tabla llena”
Fin Si

Inserción en una posición P

En este caso, además de comprobar que la tabla no esta llena, moveremos todos los elementos desde P a N al elemento con índice siguiente, para dejar hueco en la posición P y así poder meter el nuevo valor sin perder ningún dato.

Si N < T
Para j de N a P con incremento -1
tabla[j+1]=tabla[j]
Fin Para
tabla[p]=valor
N=N+1
Sino
Escribir “tabla llena”
Fin Si.

También podríamos haberlo hecho con un bucle mientras en lugar de un para y de P a N en lugar de N a P, pero la filosofía seguiría siendo la misma.

Borrado de un elemento situado en una posición P

En este caso dará lo mismo que el array esté lleno o no, pero no si está vacío. Tras comprobar esto, moveremos hacia la izquierda todos los elementos posteriores a la posición P.

Si N>0
Para j de P a N-1 con incremento 1
tabla[j]=tabla[j]+1
Fin Para
N=N-1
Sino
Escribir “tabla llena”
Fin Si

Búsqueda de un valor x y la posición que ocupa

Aquí debemos tener en cuenta varias cosillas. En primer lugar, consideramos que tenemos una tabla de enteros, ordenada de menor a mayor. La cosa sería

j=1;
Mientras tabla[j]<x y j<N
j=j+1
Fin Mientras
Si tabla[j]=x Escribir “encontrado x en la posicion j”
Sino Escribir “No encontrado”.

Si la tabla no estuviese ordenada, bastaría cambiar el menor por diferente, en la primera condición del mientras. (Mientras tabla[j]<>x y j<N). Otra forma de hacer esto es utilizar un interruptor: lo inicializamos a false, ponemos la condicion en el mientras de mientras interruptor sea igual a false, si en algún momento del bucle lo encuentra hacemos interruptor=true y fuera del bucle preguntamos por qué condición se ha salido. Pero de la forma mostrada queda más eficiente.

Si la tabla contiene valores repetidos, queremos mostrarlos todos y su posición, haremos algo como:

sw=false
Para j de 1 a N con incremento de 1
Si tabla[j]=x
Escribir “encontrado en posicion j”
sw=true;
Fin Si
Fin Para
Si sw=false
Escribir “No encontrado”
Fin Si

Otro método de búsqueda es la búsqueda binaria o dicotomía, válido sólamente para tablas ordenadas. Se comienza comparando el elemento central de la tabla y, si no es el valor buscado, en función de que sea menor o mayor que el elemento buscado, se coge la mitad inferior o superior y se procede de la misma forma. En tablas muy grandes, es una buena opción, debido a su eficiencia respecto a la búsqueda secuencial.

izq=1
der=N
c=(izq+der)/2
Mientras tabla[c]<>x y izq<der
Si tabla[c]> x entonces der=c-1
Sino izq=c+1
Fin Si
c=(izq+der)/2
Fin Mientras

Si tabla[c]=x entonces Escribir “encontrado en la posicion c”
Sino Escribir “No encontrado”
Fin Si

Observa que izq va estrechando el cerco por la izquierda o principio del array y la variable der, lo mismo, pero por la derecha o fin del array. Si te fijas en la segunda condición del mientras, paramos cuando izq y der se mezclan o superponen, o lo que es lo mismo, el cerco se convierte en cero. Dentro del bucle, indicamos la nueva zona del array en la que buscar y finalmente preguntamos si coincide la variable buscada. La esencia de este algoritmo, como puedes intuir, es recursiva. (Bastaría con ir pasando a la función la porción de la tabla a evaluar, siguiendo la misma filosofía. Cuando llegue a recursividad, lo retomaremos)

El siguiente tema en esta serie de artículos serán las tablas, también llamadas arrays ó matrices, estructura fundamental para el programador. Constantemente haremos uso de ellas; cuanto más soltura se tenga con ellas, menos disgustos nos ahorraremos.

¿Qué es un array?

Un array es un conjunto de datos del mismo tipo. Un conjunto de enteros, un conjunto de chars… Llevan asociados un mismo nombre y para diferenciarlos tienen un índice. LLamaremos elemento a cada dato que compone el conjunto de datos, es decir, el array.

Vectores

Un vector es un array de una dimensión, o lo que es lo mismo, un array de una fila y N columnas.

int miTabla[5];

Con eso tendríamos un array, “vacío”, de enteros, de 5 elementos, en lenguaje C. El índice del primer elemento sería el cero, accediendo a él a través de miTabla[0]. El elemento 2, siguiendo la misma pauta, sería accesible mediante miTabla[1] y el último elemento, por miTabla[4].

En pascal, podemos especificar nosotros el rango del índice… de modo que…

Var MiTabla : Array [1..5] of Integer

En este caso el índice iría de 1 a 5, correspondiendo el 1 al primer elemento y el 5 al último.

Cada elemento del array, se comportará como cualquier otra variable. Es decir, podremos hacer un miTabla[3]=5; y asignaremos al elemento 3 del array miTabla el valor 5; también podremos hacer un miTabla[3]=miTabla[3]+2; con lo que tendremos que en ese elemento de miTabla ahora hay un 7.

Por supuesto, cuando accedamos a los elementos del array, debemos asegurarnos que el elemento con el índice que indicamos, existe. Es decir, si en el ejemplo anterior, intentamos acceder a un elemento miTabla[7];, nos daría un error de overflow, pues el índice pasado no coincide con el rango indicado (de 1 a 5). Esto hay que tenerlo en cuenta de forma especial cuando en lugar de una constante, accedamos por una variable, el típico miTabla[i]; metido en un bucle. Si i en algún momento se pasa del rango, el programa cascará. (En tiempo de ejecucción, además, pues el compilador no daría error al compilar).

Otro aspecto que se ha de tener en cuenta, al igual que con las variables, es comprobar qué tiene el elemento en cada momento. Tras crear el array, en el primer ejemplo, en C, puse un vacío entre comillas. Y, es que, al declarar el array no lo estamos inicializando… y sus elementos pueden contener cualquier cosa, y no necesareamente ceros como se podría pensar. Aprovechando esto para ver cómo sería el recorrido completo de un vector y suponiendo que nuestro programa necesita inicializar todos los elementos del vector a cero…

for(i=0;i<5;i++) miTabla[ i ]=0;

En un algoritmo genérico, la 0 del i=0 sería el comienzo del índice del vector y el i<5, el último. Visto desde pascal, con el ejemplo anterior,

for i=1 to i<=5 do miTabla[ i ]:=0;

Si no recuerdo mal, esa sería la sintaxis para pascal. Pero más allá del código en concreto, hay que coger la filosofía.

Matrices

Por matriz se entiende un array bidimensional. En este caso, tendremos un array de N filas por M columnas, es decir, de tamaño NxM, por ejemplo, int Matrix[5][5]; ó int Matrix[10][2]. Lo dicho anteriormente se aplica aquí, teniendo en cuenta la segunda dimensión.

Para recorrer la matriz, necesitaremos dos bucles anidados, con dos contadores, i y j, una para las filas (i) y otra para las columnas (j).

// Código en C
for(i=0;i<10;i++)
for(i=0;i<2;i++)
Matrix[ i ][ j ]=0;

Arrays multidimensionales

También podemos crear arrays de más de dos dimensiones, 3, 4.. N dimensiones. Pasando de 3, la cosa se complicaría mucho y no merecería la pena, optando por otra opción de implementación. En el caso de tres, tendríamos algo como int arrayM[5][6][7]; y recorriendolo con tres bucles for y tres variables, i, j y k.

Seguimos con el cursete de programación. Según vaya avanzando, me meteré más en profundidad en algoritmos genéricos, ejemplos y demás… pues el anterior post del curso igual me parecía muy básico para extenderme demasiado…

Programación estructural, modular y orientada a objetos

Estos tres conceptos hacen referencia a una serie de principios o pautas que definen la filosofía a seguir en los programas.

La programación estructural es la que se compone de las 3 estructuras básicas ya vistas: secuencial (las instrucciones se ejecutan una detrás de otra, en orden descendente), alternativa (los if) e iterativa (los bucles), teniendo en cuenta que todo programa comienza en un sitio y termina en otro o, dicho de otro modo, tiene un principio y un final. (Todo principio, tiene un final, que decía Morpheus)

La programación modular consiste en dividir un programa en partes bien diferenciadas, llamadas módulos (o subprogramas), que pueden ser analizadas y programadas por separado. Existe un algoritmo o programa principal, que cede el control al resto de módulos y, una vez éstos se han ejecutado, vuelve a tomar el control, continuando la ejecución del programa por dónde los llamó.

Entre las reglas principales para programar de forma modular (práctica más que conveniente), están:

- Cada módulo tiene que tener un punto de entrada y otro de salida. (Es decir, el módulo una vez haya realizado su tarea, debe devolver el control al programa principal desde donde fue llamado).

- En el programa principal, se debe definir todos los módulos que se van a utilizar y definirlos en consecuencia.

- Los módulos deben tener independencia, en la medida de lo posible, respecto del programa principal. La idea es que los módulos realicen una tarea de forma genérica, para poder reutilizar código si fuese necesario en otro programa, sin tener que tocar el código del módulo.

- Los datos del programa principal que el módulo necesite, serán pasados desde allí. (Evitar las variables globales).

De la POO ó OOP, programación orientada objetos, hablaré más adelante, pues primero conviene tener soltura con las “programaciones” anteriores, para pillar bien ciertos conceptos.

Funciones y procedimientos

Para no cambiar de tema y después retomarlo, seguiré hablando de subprogramación o programación modular. Las funciones y los procedimientos forman parte de ello.

¿Qué es un procedimiento? Teniendo en cuenta lo anterior, se definiría como un módulo. Concretamente, como un módulo que no retorna ningún valor, ejecuta lo que tenga que ejecutar y devuelve el control al programa que lo llamó.

¿Qué es una función Un módulo que retorna un valor.

La llamada de ambas desde un programa, se hace de forma diferente, atendiendo a su definición. Cuando trabajemos con una función, al llamarla no podremos llamarla sin más, si no que deberemos hacerlo en alguna parte en el que el valor devuelto sea evaluable. Imagina que tenemos una función llamada EsNumero, de tipo booleano (devuelve un valor de tipo bool, true o false, según la cadena pasada esté compuesta toda de números o haya otros caracteres). Si la llamamos como

Sentencia 1
Sentencia 2
EsNumero(cadena)
Sentencia 3

A dónde iría el valor devuelto por la función? A ninguna parte. Y tampoco sería evaluable de ningún modo. La llamada correcta sería en un if, o igualando a una variable. (if EsNumero(cadena) then writeln(”es numero”); ó miVar=EsNumero(cadena), donde miVar es una variable de tipo boolean).

Observa la diferencia. También al margen, observa que en el if no he puesto EsNumero(cadena)=true. En un if, cuando la evaluación de la condición da true, verdadero, es cuando se ejecuta las instrucciones que hay dentro de él. Al retornar nuestra función un valor booleano, si devuelve true, en el if habrá algo como if true then… puesto que true, es true…. entrará. Si retorna false, if false then.. como la evaluación de false no es verdadero, no entrará. Por supuesto puedes ponerlo de forma completa con EsNumero=true, pero estos detalles muestran la soltura de un programador.

Por el contrario, la llamada a un procedimiento se hace en “solitario”, como en el ejemplo primero de EsNumero (el que está en el recuadro).

Dentro de una función, deberemos tener una sentencia que indique el retorno de un valor. En pascal, tomaremos el nombre de la función y le asignaremos el valor. (EsNumero:=true). En C, se hará mediante return valor; Para no olvidar este retorno, una buena práctica es declarar una variable del tipo de la función, en este caso bool. Es decir, al principio de la función, haremos var retorno: bool; En el código de la función, iremos asignando a esa variable el valor que proceda en cada caso y al final de la misma, asignaremos esa variable a la función, EsNumero:=retorno. Así, la lógica de la función podrá fallar, pero siempre devolveremos un valor de forma clara.

Paso de parámetros

Los parámetros son los datos que pasaremos a los subprogramas, cuando necesiten trabajar con datos ajenos a ellos. Hay dos formas de pasar estos parámetros, por valor o por referencia. Tanto las funciones como los procedimientos, aceptan ambas formas.

Paso por valor. Se pasa una copia de la variable. Los cambios que hagamos a esa variable, sólo tendrán efecto en el subprograma, pues al tratarse de una copia, en el programa principal tendremos el valor original.

Paso por refencia. En este caso se pasa la dirección de memoria en dónde está la variable, una referencia a su ubicación. (de ahí el nombre). Por tanto, cualquier cambio que hagamos en ella, quedará modificado en el resto del programa, pues se trata de la misma variable.

Y… ¿qué sistema es mejor? Depende de lo que queramos hacer. Es cuestión de valorar cada caso y decidir. (Cuando se trabaje con TAD´s, tipos abstractos de datos, los pasaremos siempre por referencia, pues por valor carecería de sentido por concepto).

Parámetros formales / parámetros actuales. Cuando hablamos de parámetros formales, nos referimos a los parámetros presentes en la declaración de un subprograma. Por parámetros actuales entendemos los parámetros pasados al subprograma en cada llamada. Los parámetros formales y actuales han de coincidir en número y en tipo. De forma opcional, también pueden coincidir en el nombre.

Vida y visibilidad de variables

De vuelta a las variables, comentar una cosilla en relación a la última frase del apartado anterior. Las variables globales, a evitar, son aquellas que son accesibles en cualquier lugar del programa principal y de los subprogramas. En cambio, las locales sólo son accesibles desde el subprograma donde fueron creadas. (Si se crean en el programa principal, sólo serán visibles en el programa principal, no así en los módulos). Por este motivo, si tenemos dos subprogramas y en cada uno de ellos declaramos una variable con el mismo nombre, el programa no daría error, pues se trataría de dos variables diferentes (no se ven entre sí y por tanto, no influyen entre ellas, y tampoco pasaría nada por tener una variable llamada i en el programa principal y en dos subprogramas). La vida de esas variables, terminará (se liberará el espacio en memoria destinado a esa variable), cuando se finalice el subprograma… por ello hay que tener en cuenta que las variables locales de cada subprograma no son accesibles desde el resto de subprogramas o programa principal… si nos hace falta un dato procesado en el subprograma, lo enviaremos por medio de una función, retornando un valor.

Comenzando con la recopilación de apuntes o tutorial de introducción a la programación….

Introducción

¿Qué es un programa? Podríamos definirlo como una secuencia lógica de instrucciones que manipulan unos datos para obtener unos resultados. En esa secuencia podemos distinguir dos partes: una declarativa, donde se definen / especifican los datos a tratar y otra operacional, donde van las instrucciones que procesarán la información.

Cuando se comienza a aprender a programar, antes de comenzar en algún lenguaje concreto, suele verse la llamada metodología, que no es más que desarrollar los programas en papel, de forma genérica, en pseudocódigo. Resolviendo problemas de esta manera y posteriormente pasándolos a un lenguaje concreto es una buena manera de aprender a programar.

Aquí haré un poco mezcla de todo… pseudocódigo, pascal y c… éste ultimo para que veais que una vez sepais resolver problemas (programar), pasar de un lenguaje a otro no es difícil. En el aspecto léxico no me meteré mucho, pues se puede mirar en cualquier tutorial especializado en el lenguaje concreto.

Comenzando

Cuando nos enfrentemos al desarrollo de un programa, debemos tener presente de principio dos cosas: los datos que van a entrar y los que van a salir. Haciendo valoración de ambas, pensaremos en el algoritmo que solucionará nuestro problema. (Los pasos a efectuar para conseguir nuestro objetivo).

Para ello haremos uso de todo lo que veremos a continuación…

Tipos de datos

Hemos hablado de datos, pero no del tipo que son esos datos. Y, esto es importante, pues no trataremos de igual modo un número entero que un número decimal o que una cadena de caracteres. Por lo general, hablaremos de integer (entero), float (decimales de simple precisión), double (decimales de doble precisión), bool (true/false) y char (caracter). Actualmente los lenguajes soportan el tipo string o cadena de caracteres, pero no lo usaremos. (Creando las susodichas cadenas a partir de arrays de char).

También podremos crearnos nuestro propio tipo de dato, a través del type y registros de pascal o las estructuras de C.

Variables

Las variables son contenedores de información. Como su nombre indica, cambian de valor a lo largo de la ejecución del programa. (O mejor dicho, las asignamos nosotros valores diferentes según convenga). Lo explicado sobre los tipos de datos, quedará patente en este apartado. Si queremos meter un 5 en una variable, por ejemplo, esa variable deberá ser de tipo integer, haciendo

var num: integer; num:=5; (* en pascal *)
int num=5; // en C

Con ello, en la variable num tendremos un 5 almacenado para su posterior uso. Hay que poner atención al rango del tipo de datos, pues por ejemplo, si en un entero intentamos meter un número que no está en su rango, dará un error de overflow.

Constantes

En muchos programas, usaremos datos que se mantendrán invariables en todo el programa. Hablamos entonces de constantes. Realmente, también lo podríamos meter en una variable, pero no estaría bien visto, por así decirlo. Poniendo un ejemplo, imaginemos que por algún motivo necesitamos el número pi, 3.14, en muchos puntos del programa. Una solución sería poner en cada uno de sus puntos el número tal cual… pero… imagina que en un momento dado, quieres poner dos decimales más: tendrías que cambiarlo en todos los sitios.

Lo suyo sería definirnos una constante, antes de todo procedimiento, incluso de la función principal.

(* Pascal *)
Const
PI = 3.14

// C
# define PI 3.14

En cualquier punto del programa, podremos hacer referencia a la constante escribiendo su nombre. Las constantes no tienen un tipo específico y se suelen nombrar con todos sus caracteres en mayúscula.

Operadores

Con los datos podemos hacer una serie de operaciones, concretamente, en pascal:

Aritméticas: +, -, *, /, div (división entera), mod (resto)
Relacionales: =,<,>,<=,>=, <>
Lógicas: and, or, not
Asignación: :=

Sentencias de control

If. Sentencia condicional. El código que esté dentro se ejecutará sólo si la condición se cumple. De lo contrario, pasará de largo, ejecutando el resto de código que esté después.

Un if puede contener otros if dentro de él, llamados anidados. Además, puede seguirle una instrucción else, con la que indicaremos el código a ejecutar si la condición no se cumple.

if a>5 then writeln(”a es mayor que 5″)
else writeln(”a es menor o igual a 5″);

En pascal, si dentro de un if y, en general de cualquier bloque, va más de una instrucción, debe llevar un begin al principio y un end al final del bloque. En C, el contenido iría entre llaves. { }

Bucles. Un bucle hace posible que determinado código se ejecute una y otra vez, un número finito de veces. Ese número finito queda definido por una condición.

En pascal, tenemos los bucles for, while y repeat. Algo a tener en cuenta es la diferencia de concepto entre los tres. En el for, se ejecutarán las instrucciones tantas veces como se cumpla la condición, sin poder salir antes del bucle. En el while, se ejecutarán mientras se cumpla la condición (si desde el principio no se cumple, no se ejecutarán) y en el repeat, como el while, pero se ejecutarán al menos una vez, pues la condición va al final.

Y cuando se usa uno u otro? Sabiendo lo anterior y valorando. En una búsqueda, usaremos un while, pues saldremos del bucle en cuanto encontremos lo que buscamos, para recorrer una matriz de principio a fin, usaremos un for… a base de hacer ejercicios y de ir pensando, se va cogiendo soltura… Manejando bucles de forma correcta, ireis por el buen camino, pues son el pan diario del programador.

Más sobre variables

Para terminar la primera parte, un pequeño matiz sobre variables. Según el uso que las demos, podemos hablar de contadores, interruptores, auxiliares… en esencia no dejaremos de hablar de variables, pero por cumplir una misión específica, se las llama de un modo especial.

Contador: es la variable que usamos, como su nombre indica, para llevar alguna cuenta. Por ejemplo, en los bucles. Se suelen llamar i, j, k… y su incremento o decremento suele ser de uno. Si es de más, también se le llama acumulador. (Por ejemplo, suma=suma+lo leido por teclado).

Interruptores: también llamadas switch. Nos indican el estado de algo concreto en un punto del programa. Se llaman así porque funcionan como el botón de encendido, tomando sólo dos valores, true o false. Por ejemplo, la variable booleana en el típico algoritmo de búsqueda con while.

Auxiliares: las anteriores son clasificadas como auxiliares, pero nos referiremos con este nombre a aquellas que nos sirven para almacenar un valor mientras hacemos otras operaciones. Por ejemplo, en el intercambio de valores en los algoritmos de ordenación, en los que para no perder un dato, debemos guardarlo en un sitio auxiliar, para reubicarlo en su sitio adecuado después.