PA2 RESUEMEN DATOS AABSTRACTOS

 

 

INGENIERÍA EN SISTEMAS COMPUTACIONALES

 

ALUMNO:

 

JONY ALEJANDRO LÓPEZ JIMÉNEZ (17700168)

 

DOCENTE:

ING. MÓNICA LAURENT LEON JUÁREZ

 

SEMESTRE:

3 B

 

TRABAJO:

RESUMEN

 

 

 

 

 

 

 

 

 

 Para empezar un tipo de dato abstracto se representa con las siglas TDA, esto es un conjunto de datos o objetos que se encuentran socializados entre sí, esto con la finalidad de poder realizar múltiples funcionalidades. Un TDA se puede utilizar con una o mas distintas estructuras de datos ya que tendrá la misma funcionalidad, alguno de los TDA básicos esta lo que es TDA LISTA una lista nos dice que es una serie de N elementos que se encuentran ordenadas de manera consecutiva y también un dato importante es de que si la lista contiene 0 elementos se le conoce como lista vacía, las operaciones que se pueden realizar en la lista es insertar un elemento en la posición N, borrar el N-ésimo elemento, buscar un elemento dentro de la lista y preguntar si la lista está vacía al igual una manera de implementar una lista es utilizando un arreglo, aquí algunos ejemplos de implementación del TDA en listas enlazadas y sus operaciones asociadas.

EstaVacia (): devuelve verdadero si la lista está vacía, falso en caso contrario.

Insertar (x, k): inserta el elemento x en la k-ésima posición de la lista.

Buscar(x): devuelve la posición en la lista del elemento x.

BuscarK (k): devuelve el k-ésimo elemento de la lista.

Eliminar (x): elimina de la lista el elemento x        

 

También tenemos el TDA PILA una pila es una lista de N elementos en lo cual solo se puede extraer el ultimo elemento insertado nos dice que la posición donde se allá ubicado el elemento se le denomina tope de fila y también se le conoce como LIFO (LAST IN – FIRST OUT) en español el ultimo en entrar es el primero en salir. Existen dos maneras de implementar una pila una de ellas es utilizando una lista enlazada o por lo otro utilizando un arreglo.

Para implementar una pila utilizando un arreglo, basta con definir el arreglo del tipo de dato que se almacenará en la pila. Una variable de instancia indicará la posición del tope de la pila, lo cual permitirá realizar las operaciones de inserción y borrado, y también permitirá saber si la pila está vacía, definiendo que dicha variable vale -1 cuando no hay elementos en el arreglo.  Para listas enlazadas no existe el problema de tener que fijar el tamaño máximo de la pila, aunque siempre se está acotado por la cantidad de memoria disponible. La implementación es bastante simple los elementos siempre se insertan al principio de la lista (apilar) y siempre se extrae el primer elemento de la lista (desapilar y tope), por lo que basta con tener una referencia al principio de la lista enlazada. Si dicha referencia es null, entonces la pila está vacía.

El TDA COLA nos dice que es una lista de N elementos donde siempre se inserta nuevos elementos al final de la lista y se extraen elementos desde el inicio de la lista también se les conoce como listas FIFO el primero que entra es el primero que sale Al igual que con el TDA pila, una cola se puede implementar tanto con arreglos como con listas enlazadas.

Igual esta TDA COLA DE PRIORIDAD una cola de prioridad tipo de datos abstracto que almacena un conjunto de datos que poseen una llave perteneciente a algún conjunto ordenado, y permite insertar nuevos elementos y extraer el máximo (o el mínimo, en caso de que la estructura se organice con un criterio de orden inverso).

En este están 2 formas de poder implementarlas que son:

Una lista ordenada:

    Inserción: O (n)

    Extracción de máximo: O (1)

Una lista desordenada:

    Inserción: O (1)

    Extracción

con lo cual la estructura permite insertar elementos de prioridad cualquiera, y extraer el de mejor prioridad.