Estructuras de datos básicas
Toda la información que se maneja dentro de un computador se encuentra
almacenada en su memoria, que en términos simples es una secuencia de
caracteres (bytes) en donde se encuentran las instrucciones y datos a los que
se accede directamente a través del procesador del computador.
Los sistemas o métodos de organización de datos que permiten un
almacenamiento eficiente de la información en la memoria del computador son
conocidos como estructuras de datos. Estos métodos de organización
constituyen las piezas básicas para la construcción de algoritmos complejos, y
permiten implementarlos de manera eficiente.
En el presente capítulo se presentan las estructuras de datos básicas como
son arreglos, listas enlazadas y árboles, con las cuales se implementarán
posteriormente los tipos de datos abstractos.
Características
- Correcto
- Legible
- eficiente
- Diseño de algoritmo
Diseño: se dan las especificaciones en lenguaje
natural y se crea un primer modelo matemático apropiado. La solución en esta
etapa es un algoritmo expresado de manera muy informal.
Implementación: El
programador convierte el algoritmo en código,
siguiendo alguna de estas 3 metodologías.
* TOP-DOWN se alcanza el programa
sustituyendo las palabras del pseudocódigo por secuencias de proposiciones cada
vez mas detalladas, en un llamado refinamiento progresivo.
* BOTTON-UP
parte de las herramientas
mas primitivas hasta que se llega al programa.
Pruebas:
Es un material que se pasa al programa para detectar posibles errores. Esto no
quiere decir que el diseño no tenga errores, puede tenerlos para otros
datos.
Árbol binarios.
Los árboles de grado 2 tienen una especial importancia. Se les conoce con el
nombre de árboles binarios. Se define un árbol binario como un conjunto finito
de elementos (nodos) que bien está vació o está formado por una raíz con dos
árboles binarios disjuntos, llamados subárbol izquierdo y derecho de la
raíz.
En los apartados que siguen se considerarán únicamente árboles
binarios y, por lo tanto, se utilizará la palabra árbol para referirse a árbol
binario. Los árboles de grado superior a 2 reciben el nombre de árboles
multica mino.
Árbol binario de búsqueda.- Los árboles binarios se utilizan
frecuentemente para representar conjuntos de datos cuyos elementos se
identifican por una clave única. Si el árbol está organizado de tal manera que
la clave de cada nodo es mayor que todas las claves su subárbol izquierdo, y
menor que todas las claves del subárbol derecho se dice que este árbol es un
árbol binario de búsqueda.
CONCEPTO DE CLASE
UNA CLASE ES UNA AGRUPACIÓN DE DATOS (VARIABLES O
CAMPOS) Y DE FUNCIONES(MÉTODOS) QUE OPERAN SOBRE ESOS DATOS. A ESTOS DATOS
Y FUNCIONES PERTENECIENTESA UNA CLASE SE LES DENOMINA VARIABLES, MÉTODOS O
FUNCIONES MIEMBRO. LAPROGRAMACIÓN ORIENTADA A OBJETOS SE BASA EN LA
PROGRAMACIÓN DE CLASES. UNPROGRAMA SE CONSTRUYE A PARTIR DE UN CONJUNTO DE
CLASES.UNA VEZ DEFINIDA E IMPLEMENTADA UNA CLASE, ES POSIBLE DECLARAR
ELEMENTOS DE ESTA CLASE DE MODO SIMILAR A COMO SE DECLARAN LAS
VARIABLES DEL LENGUAJE (INT,DOUBLE, STRING). LOS ELEMENTOS DECLARADOS
DE UNA CLASE SE DENOMINAN OBJETOS DE LA CLASE. DE UNA ÚNICA CLASE SE PUEDEN DECLARAR O CREAR NUMEROSOS OBJETOS. LACLASE ES LO GENÉRICO: ES EL PATRÓN O MODELO PARA CREAR OBJETOS. CADA OBJETOTIENE SUS PROPIAS COPIAS DE
LAS VARIABLES MIEMBRO, CON SUS PROPIOS VALORES, ENGENERAL DISTINTOS DE LOS
DEMÁS OBJETOS DE LA CLASE. LAS CLASES PUEDEN TENER VARIABLES STATIC,
QUE SON PROPIAS DE LA CLASE Y NO DE CADA OBJETO
HERENCIA
LA HERENCIA
PERMITE QUE SE PUEDEN DEFINIR NUEVAS CLASES BASADAS EN CLASESEXISTENTES, LO CUAL FACILITA RE-UTILIZAR CÓDIGO PREVIAMENTE DESARROLLADO. SI UNACLASE DERIVA DE OTRA (EXTENDS) HEREDA TODAS SUS VARIABLES Y MÉTODOS. LA CLASE DERIVADA PUEDE AÑADIR NUEVAS VARIABLES Y MÉTODOS Y/O REDEFINIR LAS VARIABLES Y MÉTODOS HEREDADOS. EN JAVA, A DIFERENCIA DE OTROS LENGUAJES ORIENTADOS AOBJETOS, UNA CLASE SÓLO PUEDE DERIVAR DE UNA ÚNICA CLASE, CON LO CUAL NO ESPOSIBLE REALIZAR HERENCIA MÚLTIPLE EN BASE A CLASES. SIN EMBARGO ES POSIBLE “SIMULAR” LA
HERENCIA MÚLTIPLE EN BASE A LAS INTERFACES.
PACKAGE
UN PACKAGE ES UNA AGRUPACIÓN DE CLASES. EXISTEN UNA SERIE DE PACKAGES INCLUIDOSEN EL LENGUAJE (VER JERARQUÍA DE CLASES QUE APARECE EN EL API DE JAVA).ADEMÁS EL USUARIO PUEDE CREAR SUS PROPIOS PACKAGES. LO HABITUAL ES JUNTAR ENPACKAGES LAS CLASES QUE ESTÉN RELACIONADAS. TODAS LAS CLASES QUE FORMEN PARTE DE UN PACKAGE DEBEN ESTAR EN EL MISMO DIRECTORIO.
UNA CLASE ES UNA AGRUPACIÓN DE DATOS (VARIABLES O
CAMPOS) Y DE FUNCIONES(MÉTODOS) QUE OPERAN SOBRE ESOS DATOS. A ESTOS DATOS
Y FUNCIONES PERTENECIENTESA UNA CLASE SE LES DENOMINA VARIABLES, MÉTODOS O
FUNCIONES MIEMBRO. LAPROGRAMACIÓN ORIENTADA A OBJETOS SE BASA EN LA
PROGRAMACIÓN DE CLASES. UNPROGRAMA SE CONSTRUYE A PARTIR DE UN CONJUNTO DE
CLASES.UNA VEZ DEFINIDA E IMPLEMENTADA UNA CLASE, ES POSIBLE DECLARAR
ELEMENTOS DE ESTA CLASE DE MODO SIMILAR A COMO SE DECLARAN LAS
VARIABLES DEL LENGUAJE (INT,DOUBLE, STRING). LOS ELEMENTOS DECLARADOS
DE UNA CLASE SE DENOMINAN OBJETOS DE LA CLASE. DE UNA ÚNICA CLASE SE PUEDEN DECLARAR O CREAR NUMEROSOS OBJETOS. LACLASE ES LO GENÉRICO: ES EL PATRÓN O MODELO PARA CREAR OBJETOS. CADA OBJETOTIENE SUS PROPIAS COPIAS DE
LAS VARIABLES MIEMBRO, CON SUS PROPIOS VALORES, ENGENERAL DISTINTOS DE LOS
DEMÁS OBJETOS DE LA CLASE. LAS CLASES PUEDEN TENER VARIABLES STATIC,
QUE SON PROPIAS DE LA CLASE Y NO DE CADA OBJETO
HERENCIA
LA HERENCIA
PERMITE QUE SE PUEDEN DEFINIR NUEVAS CLASES BASADAS EN CLASESEXISTENTES, LO CUAL FACILITA RE-UTILIZAR CÓDIGO PREVIAMENTE DESARROLLADO. SI UNACLASE DERIVA DE OTRA (EXTENDS) HEREDA TODAS SUS VARIABLES Y MÉTODOS. LA CLASE DERIVADA PUEDE AÑADIR NUEVAS VARIABLES Y MÉTODOS Y/O REDEFINIR LAS VARIABLES Y MÉTODOS HEREDADOS. EN JAVA, A DIFERENCIA DE OTROS LENGUAJES ORIENTADOS AOBJETOS, UNA CLASE SÓLO PUEDE DERIVAR DE UNA ÚNICA CLASE, CON LO CUAL NO ESPOSIBLE REALIZAR HERENCIA MÚLTIPLE EN BASE A CLASES. SIN EMBARGO ES POSIBLE “SIMULAR” LA
HERENCIA MÚLTIPLE EN BASE A LAS INTERFACES.
PACKAGE
UN PACKAGE ES UNA AGRUPACIÓN DE CLASES. EXISTEN UNA SERIE DE PACKAGES INCLUIDOSEN EL LENGUAJE (VER JERARQUÍA DE CLASES QUE APARECE EN EL API DE JAVA).ADEMÁS EL USUARIO PUEDE CREAR SUS PROPIOS PACKAGES. LO HABITUAL ES JUNTAR ENPACKAGES LAS CLASES QUE ESTÉN RELACIONADAS. TODAS LAS CLASES QUE FORMEN PARTE DE UN PACKAGE DEBEN ESTAR EN EL MISMO DIRECTORIO.