Estructura de datos

INTITUTO TECNOLOGICO SUPERIOR DE CAJEME

Manual de Referencia

Estructura de Datos
Orientado a Objetos

MANUAL DE REFERENCIA

Estructura de Datos
Orientado a Objetos

© Carretera Internacional a Nogales Km. 2 CD. Obregón, Sonora, México Teléfono (644) 4151915 • Fax (644) 4151914

i

ii

T abla de contenido
4.5 Recursividad en el diseño.

CAPÍTULO 1
ANÁLISIS DE ALGORITMOS.1.1 Concepto de Complejidad de algoritmos. 1.2 Aritmética de la notación O. 1.3 Complejidad. 1.3.1 Tiempo de ejecución de un algoritmo. 1.3.2 Complejidad en espacio. 1.4 Selección de un algoritmo.

4.6 Complejidad de los algoritmos recursivos.

CAPÍTULO 5
ESTRUCTURAS NO LINEALES ESTÁTICAS Y DINÁMICAS. 5.1 Concepto de árbol. 5.1.1 Clasificación de árboles. 5.2 Operaciones Básicas sobreárboles binarios. 5.2.1 Creación. 5.2.2 Inserción. 5.2.3 Eliminación. 5.2.4 Recorridos sistemáticos. 5.2.5 Balanceo.

CAPÍTULO 2
MANEJO DE MEMORIA. 2.1 Manejo de memoria estática. 2.2 Manejo de memoria dinámica.

CAPÍTULO 3
ESTRUCTURAS LINEALES ESTÁTICA Y DINÁMICAS. 3.1 Pilas. 3.2 Colas. 3.3 Listas enlazadas. 3.3.1 Simples. 3.3.2 Dobles.

CAPÍTULO 6
ESTRUCTURAS NO LINEALES ESTÁTICAS Y DINÁMICAS.6.1 Algoritmos de Ordenamiento por Intercambio. 6.1.1 Burbuja. 6.1.2 Quicksort. 6.1.3 ShellSort. 6.2 Algoritmos de ordenamiento por Distribución. 6.2.1 Radix.

CAPÍTULO 4
RECURSIVIDAD. 4.1 Definición. 4.2 Procedimientos recursivos. 4.3 Mecánica de reexcursión. 4.4 Transformación de algoritmos recursivos a iterativos.

CAPÍTULO 7
ORDENACIÓN EXTERNA. 7.1 Algoritmos de ordenación externa.7.1.1 Intercalación directa.

7.1.2 Mezcla natural.

CAPÍTULO 8
MÉTODOS DE BÚSQUEDA. 8.1 Algoritmos de ordenación externa. 8.1.1 Secuencial. 8.1.2 Binaria. 8.1.3 Hash. 8.2 Búsqueda externa. 8.2.1 Secuencial. 8.2.2 Binaria. 8.2.3 Hash.

1
Análisis de Algoritmos
1. 1 Concepto de Complejidad de algoritmos.
1.1.1. CONCEPTOS BÁSICOS

Capítulo

Una posible definición de algoritmo es unconjunto de reglas que permiten obtener un resultado determinado apartir de ciertas reglas definidas. Otra definición sería, algoritmo es una secuencia finita de instrucciones, cada una de las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en un tiempo finito. Ha de tener las siguientes características: Legible, correcto, modular, eficiente, estructurado, noambiguo y a ser posible se ha de desarrollar en el menor tiempo posible. Características de un algoritmo de computador: Ser algoritmo: Tiene que consistir en una secuencia de instrucciones claras y finitas. Ser correcto: El algoritmo ha de resolver el problema planteado en todas sus facetas. Ser legible: El Algoritmo debe de se entendible por cualquier persona que conozca el lenguaje. Sereficiente: Es relativa porque depende de la maquinas en la que lo ejecutemos. Existen ejemplos de algoritmos eficientes que ocupan demasiado espacio para ser aplicados sin almacenamiento secundario lento, lo cual puede anular la eficiencia. Un algoritmo eficiente pero complicado puede ser inapropiado porque posteriormente puede tener que darle mantenimiento otra persona distinta del escritor. 1.1.2.DISEÑO DE ALGORITMOS. Fases de diseño de algoritmos. 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.

A. TOP-DOWN se alcanza el programa sustituyendo las palabrasdel palabras del pseudocódigo por secuencias de proposiciones cada vez mas detalladas, en un llamado refinamiento progresivo. B. BOTTON-UP parte de las herramientas mas primitivas hasta que se llega al programa. C. TAD'S modularización dependiendo de los recursos.Tenemos unas estructuras abstractas implementadas, y una serie de conocimientos asociados a esos recursos. Pruebas: Es un material...