Presentacin de PowerPoint

Anlisis de AlgoritmosIntegrantes: Jos Soto PrezMorales Lpez WaldoHernndez Surez GabrielProfesora: Beatriz Dolores Guardin SotoEstructuras de datos linealesINSTITUTO POLITCNICO NACIONALEscuela Superior de Ingeniera Mecnica y ElctricaUnidad Culhuacn7 de febrero, 2013, Revisin 021Estructuras de DatosEstructuras de DatosLinealesNo linealesAlmacenamiento ContiguoAlmacenamiento No ContiguoOperaciones Bsicas en Estructuras LinealesRecorrido: Procesa c/elemento de la estructura.Bsqueda: Recupera la posicin de un elemento especfico.Insercin: Adiciona un nuevo elemento a la estructura.Borrado: Elimina un elemento de la estructura.Ordenacin: Ordena los elementos de la estructura de acuerdo a los valores que contiene.Mezcla: Combina 2 estructuras en una sola.PILASDefinicin:Estructura de datos lineal donde los elementos pueden ser aadidos o removidos solo por un extremo. Trabajan con filosofa LIFO (Last In- First Out ).

Ejemplos:Pila de platosPila de discosPila de llamadas a funcionesPila de recursionPila de resultados parciales de formulas aritmticas, etc.OPERACIONES BASICAS CON PILASPUSH (insertar).- Agrega un elementos a la pila en el extremo llamado tope.POP (remover).- Remueve el elemento de la pila que se encuentra en el extremo llamado tope.VACIA.- Indica si la pila contiene o no contiene elementos.LLENA.- Indica si es posible o no agregar nuevos elementos a la pila. REPRESENTACIN DE PILAS:

Usando arreglos: Define un arreglo de una dimensin (vector) donde se almacenan los elementos.

0 1 2 3 4 5TOPE: Apunta hacia el elemento que se encuentra en el extremo de la pila. (inicialmente es -1).Inicio:Insertar A:Tope-1Insertar B:Insertar C:Eliminar elementoTopeAABTopeABTopeCABTopeEjemploLas pilas pueden ser usadas para implementar la recursin en programas.Una funcin o procedimiento recursivo es aquel que se llama a si mismo.Ejemplos:FactorialNmeros de FibonacciTorres de HanoiAlgoritmos de Ordenamiento de datosEtc.Aplicaciones de PilasFunciones RecursivasCOLASDefinicin. Es una lista lineal de elementos en la que las operaciones de insertar y eliminar se realizan en diferentes extremos de la cola. Trabajan con filosofa FIFO (First In - First out), el primer elemento en entrar es el primer elemento en salir.Ejemplos:

*Cola de automviles esperando servicio en una gasolinera*Cola de clientes en una ventanilla del banco para pagar un servicio*Cola de programas en espera de ser ejecutados por una computadora.TIPOS DE COLAS:

*Cola simple: Estructura lineal donde los elementos salen en el mismo orden en que llegan.

*Cola circular: Representacin lgica de una cola simple en un arreglo.

*Cola de Prioridades: Estructura lineal en la cual los elementos se insertan en cualquier posicin de la cola y se remueven solamente por el frente.

*Cola Doble (Bicola): Estructura lineal en la que los elementos se pueden aadir o quitar por cualquier extremo de la cola (cola bidireccional).Operaciones bsicas en Colas Simples*Insertar.- Almacena al final de la cola el elemento que se recibe como paramtro.*Eliminar.- Saca de la cola el elemento que se encuentra al frente.*Vaca.- Regresa un valor booleano indicando si la cola tiene o no elementos (true si la cola esta vacia, false si la cola tiene al menos un elemento).*Llena.- Regresa un valor booleano indicando si la cola tiene espacio disponible para insertar nuevos elementos ( true si esta llena y false si existen espacios disponibles).Operaciones:ABAABCBCBCDCD1.- Insertar A2.- Insertar B3.- Insertar C4.- Remover Elemento5.- Insertar D6.- Remover ElementoEstado de la cola: Inicio Cola VacaLISTAS Una lista es una coleccin lineal de elementos llamados nodos donde el orden de los mismos se establece mediante punteros o referencias y existe un puntero/referencia especial llamado inicio para localizar al primer elemento.

Ejemplo:

inicio inicio* Lista enlazada de 4 elementosInformacin enlaceLos nodos de las listasUn nodo se divide en 2 partes:Informacin: Contiene la informacin del elemento.Enlace: Contiene la direccin del siguiente nodo de la lista.

informacin enlaceNodo*Arreglos: La relacin lineal esta implcita en la relacin fsica de los elementos. Desventaja: Almacenamiento esttico y tamao fijo.

*Elementos enlazados: Agrega a cada elemento un campo de enlace, no requieren almacenamiento contiguo en memoria, se pueden aadir y borrar elementos fcilmente.Almacenamiento de datos:Listas Simples*Coleccin lineal de elementos llamados nodos.*Existe un elemento llamado inicio que apunta al primer elemento de la lista.*Cada nodo contiene un campo de enlace que apunta al siguiente elemento.*El ltimo elemento de la lista en su campo enlace apunta a nulo.*Al principio el apuntador inicio apunta a nulo.*Insertar: Agrega un elemento a la lista.*Eliminar: Retira un elemento de la lista.*Buscar: Busca un elemento en la lista.*Recorrer: Visita todos los elementos de la lista.*Vaca: Indica si la lista contiene o no elementos.*Tamao: Indica el nmero de elementos de la lista.Operaciones con listas simplesLISTAS DOBLESUna lista doble es una estructura lineal de elementos llamados nodos los cuales contienen dos campos de enlace: uno al elemento anterior y otro al elemento siguiente de la lista. El primer nodo de la lista contiene nulo en su enlace al elemento anterior y el ltimo nodo de la lista contiene nulo en su enlace al elemento siguiente.

Estructura del Nodo:Anterior Informacin SiguienteEjemplos:inicio = fin =Lista VacaLista de un solo elementoinicioABCLista de tres elementosinicioAfinfin*Insertar: Agrega un elemento a la lista.*Eliminar: Retira un elemento de la lista.*Buscar: Busca un elemento en la lista.*Recorrer hacia adelante: Visita todos los elementos de la lista desde el inicio hasta el final. *Recorrer hacia atrs: Visita todos los elementos de la lista desde el final hasta el inicio. *Vaca: Indica si la lista contiene o no elementos.*Tamao: Indica el nmero de elementos de la lista.Operaciones con listas dobles