Resumen Estructuras De Datos

Resumen Estructuras de Datos y Algoritmos



Unidad 1





Diseño y análisis de algoritmos. Estrategias de diseño.
En la figura se representa el proceso de programación.












Etapas:
1. La primera etapa es la modelación, mediante un modelo matemático apropiado, como un grafo. En esta etapa la solución del problema es un algoritmo muy informal.
2. Enla siguiente etapa, el algoritmo se escribe en seudo lenguaje, una mezcla entre el lenguaje de programación y el español. En el proceso que se llama Refinamiento por Pasos se sustituye al español por secuencias mas detalladas. En algún punto del proceso el programa va a estar lo suficientemente detallado para que las operaciones que deba hacer estén bien determinadas. Entonces se crean los tiposde datos abstractos para cada tipo de datos dando un nombre de procedimiento a cada operación.
3. En la tercera etapa, se reemplazará por código del lenguaje que se utilice toda proposición informal que quede en el seudo lenguaje. El resultado va a ser un programa ejecutable.



Tipos de datos abstractos (TDA), tipos de datos y estructuras de datos.
El tipo de datos de una variablees el conjunto de valores que ésta puede tomar (Por ejemplo, un int o un char).
Un tipo de dato abstracto es un modelo matemático, junto con varias operaciones definidas sobre ese modelo. Para representar el modelo matemático básico de un TDA, se emplean estructuras de datos, que son conjuntos de variables, quizá de tipos distintos, conectadas entre sí de diferentes formas.
El componentebásico de una estructura de datos es la celda. Se puede representar una celda como una caja que puede almacenar un valor tomado de algún tipo de dato. Las estructuras de datos se crean dando nombres a agregados de celdas.
El mecanismo de agregación más sencillo es el arreglo, que es una sucesión de celdas de un tipo dado.
Ej. int arregloEntero[10] = {0};
Otro mecanismo habitual es laestructura de registro. Un registro es una celda constituida por un conjunto de celdas llamadas campos, que puede ser de tipos distintos. Los registros suelen agruparse en arreglos.
Ej. struct alumno {
int matricula;
char nombre[30];
int edad;
};
Un tercer método de agrupación es el archivo. Un archivo es una sucesión de valores de un tipo particular que sólo sonaccesibles en el orden en que aparecen en el archivo. Tanto el arreglo como el registro son estructuras de acceso aleatorio, lo cual significa que el tiempo necesario para acceder a un componente de un arreglo o de un registro es independiente del valor del índice del arreglo. La ventaja de agrupar por archivos en lugar de hacerlo por arreglos es que el número de elemento de un archivo puede serilimitado y variable con el tiempo.

Punteros y cursores.
Además de las características de agrupación-celdas de un lenguaje de programación es posible representar relaciones entre celdas mediante punteros y cursores. Un puntero es una celda cuyo valor indica o señala a otra.
Un cursor es una celda de valor entero que se utiliza como puntero a un arreglo. Como métodos de conexión,cursores y punteros son lo mismo, con la diferencia de que un cursor se puede utilizar en lenguajes que carece de los punteros explícitos.

Tiempo de ejecución de un programa.
Cuando se resuelve un problema, con frecuencia hay necesidad de elegir entre varios algoritmos. Hay dos objetivos que se suelen contradecir:
1. Que el algoritmo sea fácil de entender, codificar y depurar.
2. Queel algoritmo sea eficiente y se ejecute con la mayor rapidez
Cuando se escribe un programa que se va a usar una o pocas veces, el primer objetivo es el más importante. En este caso es probable que el costo de tiempo de programación sea mucho mayor al costo de ejecución del programa, de modo que el costo a optimizar es el de escritura del programa.
Si se va a utilizar muchas veces, el...