Presentación

1. Conceptos principales y definiciones

a. Simplificar las variables

Hasta ahora, los tipos de datos que ha encontrado son escalares, excepto las cadenas de caracteres. Como recordatorio, un escalar es un tipo de datos que representa sólo una variable a la vez. Un entero, un carácter, un real, un booleano, etc., son escalares. Una cadena de caracteres no lo es: es una secuencia o lista de caracteres, uno detrás de otro. Por tanto, una cadena es una lista ordenada de escalares. Los lenguajes suelen proponer un tipo para las cadenas de caracteres, pero es una facilidad que ofrecen. Un lenguaje como C no lo hace. En algoritmos, se utiliza el tipo "alfanumérico", por lo que hay que tener cuidado al convertir a C.

Pero, ¿cómo se representa una cadena de caracteres con un tipo escalar? Debemos recordar cómo se almacena la información en la memoria. La memoria del ordenador está formada por celdas que pueden contener determinados tipos de información. Estas celdas están numeradas (lo que se conoce como dirección de celda) y contienen datos. Estos datos representan lo que se desee, dependiendo del contexto en el que se utilicen.

Por ejemplo, puede suponer que contienen escalares. Si una celda de memoria contiene el número 65, podría ser el valor entero 65 o el código ASCII del carácter "A". Una celda de memoria puede contener perfectamente la dirección de otra celda de memoria: es un poco más complicado de lo que parece y será objeto de una presentación más extensa más adelante en este libro.

Por tanto, una cadena de caracteres es una serie de escalares de tipo Carácter, uno tras otro en celdas de memoria, en principio, contiguas. Utilizando el mismo principio, si tomamos el ejemplo de la introducción de las notas de los alumnos, ¿no cree que sería más práctico poder conservar estas notas durante el resto del programa? Así sería posible reutilizarlas a voluntad para nuevos cálculos o incluso guardarlas en un fichero, imprimirlas, consultarlas, etc. Hasta ahora, la única forma de hacerlo era hacer un bucle en el que introducía las notas y luego intentaba hacer los cálculos sobre la marcha. La otra posibilidad era hacer la misma pregunta n veces y colocar los resultados en n variables diferentes. Imagínese...

Operaciones sencillas

1. Buscar un elemento

Tiene una tabla de n elementos que corresponden a los nombres de pila de sus amigos y quiere saber si uno de ellos está presente en su tabla. Para ello, tiene que buscarlo. La idea es recorrer toda la tabla utilizando una estructura iterativa y salir del bucle en cuanto se haya encontrado el elemento o se haya superado el número máximo de índices. Al salir del bucle, tendrá que comprobar de nuevo si se ha encontrado o no el elemento: puede que se haya escaneado toda la tabla y que ésta sea la razón para salir del bucle.

PROGRAMA BUSCAR  
VAR  
  Tabla nombres:tabla[1..10] de cadenas  
  busq:cadena  
  i:entero  
INICIO  
  i1  
  MientrasQue i<=10 y nombres[i]<> busq Hacer  
    ii+1  
  FinMientrasQue  
  ii-1  
  Si nombre[i]=Busq Entonces  
    Visualizar "Encontrado"  
  Sino 
    Visualizar "Ausente"  
  FinSi  
FIN

Con una bandera se pueden hacer las cosas de otra manera:

PROGRAMA BUSCAR2  
VAR  
  Tabla nombres:tabla[1..10] de cadenas  
  Busq:cadena  
  i:entero  
  encontrado:booleano  
INICIO  
  i1  
  encontradoFALSO  
  MientrasQue i<=10 y encontrado=FALSO Hacer  
    Si nombre[1]=busq Entonces  
      encontradoVERDADERO  
    FinSi  
    ii+1  
  FinMientrasQue  
  Si encontrado Entonces  
    Visualiza "Encontrado"  
  Sino  
    Visualiza "Ausente"  
  FinSi  
FIN

En PHP:

<html>  
  <head><meta/>  
    <title>Buscar</title>  
  </head>  
  <body>  
  <?php  
  
  $t=array(10,20,14,25,17,8,10,12,15,5,41,19,2,6,21);  ...

Algoritmos avanzados

1. Algoritmos de ordenación

a. Conceptos principales

En los ejemplos anteriores ha visto lo útiles que son las tablas para almacenar múltiples valores. Pero dependiendo del caso, puede necesitar obtener una lista ordenada de valores en orden ascendente o descendente. En otras palabras, quiere ordenar el contenido de la tabla. Tomemos el caso de un profesor que quiere ordenar las notas de sus alumnos de menor a mayor o los resultados de un sorteo de lotería para hacerlo más legible.

Imaginemos un sorteo de lotería de cinco números, todos diferentes, por supuesto, con valores comprendidos entre 1 y 49. Este es el estado inicial de la mesa después del sorteo:

48	17	25	9	34

Existen varios métodos para clasificar estos distintos valores. Todos tienen sus puntos fuertes y débiles. Un método será lento, otro requerirá más memoria y así sucesivamente. Es su complejidad lo que determina su uso, sobre todo para grandes rangos de valores.

En los algoritmos siguientes, la variable Cnt contiene el número de elementos de la tabla inicial y t[] es la tabla.

Es interesante tener en cuenta la complejidad de estos distintos algoritmos, aunque esta noción, presentada en el primer capítulo, no se suele abordar (o apenas) en los primeros años de los estudios de informática. Los algoritmos suelen tener una complejidad similar. Sin embargo, en la práctica, el uso de una ordenación Shell es más rápida que una ordenación por selección, dependiendo del número de elementos y de su orden inicial.

b. La ordenación por creación

La clasificación por creación sólo se tratará desde un punto de vista teórico. Aunque este método parece sencillo, en realidad es engorroso y complicado. Si pregunta a un principiante en programación cómo ordenar una tabla, casi seguro que le sugerirá que cree una segunda tabla en la que los elementos de la primera se coloquen en orden ascendente.

Es una muy mala idea por varias razones:

Si se añade una segunda tabla, se duplica la memoria necesaria.
La búsqueda del elemento más pequeño es más complicada de lo que se piensa, porque cada vez que se hace una pasada, no hay que volver a los elementos que ya se han sacado y eso no es fácil....

Estructuras y registros

1. Aspectos principales

Las tablas son sin duda muy prácticas, pero no siempre ofrecen una solución eficaz a todas las necesidades de almacenamiento. Una tabla es una estructura de datos en la que todos los elementos son del mismo tipo. ¿Qué hacer cuando es necesario colocar registros de distintos tipos en una estructura de tabla?

Como ejemplo concreto, consideremos un catálogo de productos en una tienda especializada. Un artículo se describe mediante una referencia, un nombre (etiqueta) y un precio. Los dos primeros son cadenas de caracteres, el último un número real. ¿Cómo representarlo mediante tablas? Necesitaríamos tres tablas: una para las referencias, otra para las descripciones y una tercera para los precios. El índice del artículo debe ser idéntico para las tres tablas.

Es posible y factible, pero en la práctica es totalmente inmanejable cuando se trata de algo más que tratamientos sencillos. ¿Y la ordenación? ¿Y la búsqueda? Se hacen difíciles. Así que lo que necesitamos es un tipo especial de metatipo que pueda reunir variables de distintos tipos en un único conjunto.

Estos metatipos existen. Se denominan estructuras o tipos estructurados y se utilizan para describir registros. Los registros son, de hecho, estructuras de datos compuestas por elementos de tipos diferentes o distintos. Estas estructuras, compuestas por varios elementos, forman una entidad única que se denomina tipo estructurado.

En otras palabras, puede crear sus propios tipos de datos combinando otros elementos de tipos distintos o diferentes y crear variables de este nuevo tipo, denominadas registros. Los distintos elementos contenidos en un tipo estructurado se denominan campos.

2. Declaración

a. Tipo estructurado

El tipo estructurado se puede contrastar con los llamados tipos primitivos vistos hasta ahora. Un tipo estructurado puede contener elementos de tipos primitivos (enteros, reales, cadenas, caracteres), tablas, pero también elementos de otros tipos estructurados. Esto permite crear un número infinito de nuevos tipos, para todo tipo de situaciones.

Un tipo estructurado se debe declarar y definir antes que las variables, para que se pueda utilizar para definir registros. Por lo tanto, el tipo estructurado se declara entre las constantes y las variables....

Ejercicios

Ejercicio 1

Cree una tabla que contenga los números del 1 al 10 y otra tabla que contenga los números del 11 al 20. A continuación, cree una tercera tabla que contenga la suma de las dos primeras tablas y muestre sus valores. Necesita utilizar bucles para crear estas tablas.

Escriba el programa PHP equivalente.

Ejercicio 2

Dos tablas:

La tabla 1 está formada por los elementos 6, 25, 35 y 61.
La tabla 2 está formado por los elementos 12, 24 y 46.

Escriba el algoritmo para calcular un valor representativo de estas dos tablas, S. El valor S se calcula multiplicando cada valor de la tabla1 por el valor de la tabla2 y sumándolos a continuación.

En este ejemplo, el valor S será igual a:

12*6+12*25+12*35+12*61+24*6+24*25+24*35+24*61+46*6+46*25+46*35+46*61

Por supuesto, tiene que utilizar bucles para hacer este ejercicio.