Estructuras de Datos y Algoritmos Básicos
Antes de explorar las estructuras de datos y sus algoritmos
específicos, necesitamos examinar tres cuestiones básicas: ¿Qué es
una estructura de datos? ¿Qué es un algoritmo? ¿Cómo se representa
un algoritmo? El conocimiento de estos conceptos ayudará a entender
este tutorial
¿Qué es una Estructura de Datos?
Las estructuras de datos nos han estado rodeando desde la era de
la programación estructurada. Una definición de esa era: una
estructura de datos es un conjunto de tipos, un tipo diseñado
partiendo de ese conjunto de tipos, un conjunto de funciones, y un
conjunto de axiomas. Esta definición implica que una estructura
de datos es un tipo con implementación. En nuestra era de la
programación orientads a objetos, tipo con implementación
significa clase.
La definición una estructura de datos es una clase es
demasiado amplia porque supone que Empleado,
Vehículo, Cuenta, y otras muchas clases
específicas de entidades del mundo real son estructuras de datos.
Aunque esas clases estructuran varios ítems de datos, describen
entidades del munto real (en la forma de objetos) en lugar de
describir contenedores de objetos para otras entidades objetos (y
posiblemente otro contenedor). Esta idea de contenido da una
definición más apropiada para una estructura de datos: una
estructura de datos es una clase contenedora que proporciona
almacenamiento para ítems de datos, y capacidades para almacenar y
recuperar estos datos. Algunos ejemplos de estructuras de datos
son los arrays, las listas enlazadas, las pilas y las colas.
¿Qué es un Algoritmo?
Normalmante los algoritmos se asocian con estructuras de datos.
Un algoritmo es una secuencia de instrucciones que realizan
una tarea en un periodo de tiempo finito. El algoritmo recibe cero o
más entradas, produce al menos una salida, consiste en instrucciones
claras y poco ambiguas, termina después de un número finito de
pasos, y es lo suficientemente básico que una persona puede llevar a
cabo el algoritmo utilizando lápiz y papel. Por el contrario, un
programa no es necesariamente finito: el programa, como un servidor
Web, podría no terminar nunca si no hay intervención externa.
Algunos ejemplos de algoritmos asociados con estructuras de datos
son: búqueda-lineal, ordenación-de-burbuja,
búsqueda-binaria, concatenación-de-listas-enlazadas,
etc.
¿Cómo se Representa un Algoritmo?
La representación más obvia: código fuente Java. Sin embargo
escribir código fuente antes de entender completamente un algoritmo
normalmente acaba con bugs difíciles de encontrar. Una técnica para
evitar estos bus es utilizar un flowchart (diagrama de
flujo).
Flowchart
Un flowchart es una representación visual del flujo de control de
un algoritmo. Esta representación ilustra las sentencias que se
tienen que ejecutar, las decisiones que hay que tomar, el flujo
lógico (para iteracciones y otros propósitos), y terminaciones que
indican los puntos de entrada y salida. En la siguiente figura puede
ver los distintos símbolos que puede utilizar en un flowchart:
¿Cuál es el aspecto de un flowchart? Supongamos que usted tiene
un sencillo algoritmo que inicializa un contador a 0, lee caracteres
hasta que ve un caracter de nueva línea (\n), incrementa el contador
por cada caracter dígito leído, e imprime el valor del contador
depsués de que haya leído el caracter de nueva línea. En la
siguiente figura puede ver el flowchart que ilustra el flujo de
control de este algoritmo:
Entre las ventajas de un flowchart se incluye su simplicidad y su
habilidad para representar visualmente el flujo de control del
algoritmo. Los flowcharts también tienen desventajas:
- Los flowcharts altamente detallados pueden generar errores o
imprecisiones.
- Se requiere algo de tiempo extra para posicionar, etiquetar y
conectar los símbolos del flowchart, aunque algunas herramientas
aceleran este proceso, Este retardo podría relentizar su
entendimiento de un algoritmo.
- Como los flowcharts son herramientas de la era de la
programación estructurada, no son tan útiles en un contexto
orientado a objetos. Unified Modeling Language (UML) es más
apropiado para proporcionar representaciones visuales orientadas a
objetos.
Pseudocódigo
Una alternativa al flowchart es el pseudocódigo: una
representación en modo texto de un algorirmo que se aproxima al
código fuente final. El pseudocódigo es útil para una escritura
rápida de representaciones de algoritmos. Como la síntaxis no es lo
más importante, no hay reglas definidas para escribir pseudocódigo.
Considere el siguiente ejemplo:
DECLARE CHARACTER ch
DECLARE INTEGER count = 0
DO
READ ch
IF ch IS '0' THROUGH '9' THEN
count++
END IF
UNTIL ch IS '\n'
PRINT count
END
Este ejemplo representa el pseudocódigo equivalente al flowchart
de la figura anterior. Aunque localizar el flujo de control en
pseudocódigo puede costar un poco más que en un flowchart,
normalmente, escribir pseudocódigo lleva menos tiempo que dibujar un
flowchart.
| Nota: |
| En este tutorial se utiliza pseudocódigo para representar
algoritmos. |
Tutoriales
