09/02/2018

1

Facultad de Informática Culiacán

CURSO: Estructura de Datos

Instructor: MC. Gerardo Gálvez Gámez

Febrero de 2018

UNIVERSIDAD AUTÓNOMA DE SINALOA

Aprendiendo a construir soluciones a problemas del mundo

real, aplicando las Estructuras de Datos.

Unidad I• FIC-UAS

Unidad I.- ESTRUCTURAS FUNDAMENTALES DE DATOS

▫ Tipos de datos. Tipos de datos simples.

Tipos de datos abstractos.

Representación.

▫ Estructuras de datos. Definición.

Clasificación.

Lineales y no lineales.

Dinámicas y estáticas.

09/02/2018

2

Unidad I• FIC-UAS

DATO

• Información en bruto, no procesado y sin ningúnsignificado.

• Dado un enunciado, evento o acción, los datos▫ Permiten representar sus actores o participantes

▫ Analizándolos, se podrá obtener resultados deseados

• Analicemos el siguiente hecho:▫ La estudiante de nombre: Judith Pérez de 22 años, tiene unpromedio de 7.5

• Podemos tomar los siguientes datos▫ Nombre: Judith Pérez -> Cadena

▫ Edad: 22 -> Entero

▫ Promedio: 7.5 -> Real

Unidad I• FIC-UAS

INFORMACIÓN

• Es el resultado deseado luego de procesar losdatos.

• Los datos, al ser procesados, se convierten eninformación útil o resultados.

Procesamiento:

Calcular salarios

Juan, Perez $320

Pedro, Rodriguez $310

Luis, Pozo $240

Datos de salida(se muestran en el monitor)

Datos de entrada(ingresados x teclado)

Juan, Perez

Pedro, Rodriguez

Luis, Pozo

160

155

120

Empleado Horas

Valor por hora = $2

09/02/2018

3

Unidad I• FIC-UAS

¿Cómo representar los datos?

• Los seres humanos:▫ Usamos lenguaje natural o símbolos

▫ Ejemplo: Para representar números, usamos el sistema decimal

Para representar palabras, usamos el abecedario

• La computadora:▫ Usa conjuntos de 1s y 0s

▫ El dato más pequeño en la computadora es Un 1 ó un 0 -> bit

▫ El conjunto de 8 bits -> 1 byte

Unidad I• FIC-UAS

TIPOS DE DATOS

• Los datos se clasifican en TIPOS

• Son de diferentes dominios. Ejemplo:

▫ Edad, Año de Nacimiento, Número de multas Tienen dominio numérico

▫ Nombre, Dirección, Número de Cedula, Caen en el dominio de la información tipo texto

• Y las operaciones permitidas para dicho dominio:

Un conjunto de valores y operaciones definidas sólo para esos valores

09/02/2018

4

Unidad I• FIC-UAS

TIPOS DE DATOS

• Un tipo de dato es el conjunto de valores: ▫ Al que puede pertenecer una constante

▫ Que puede asumir una variable o expresión

▫ Que puede ser generado por un Método

• De una constante, variable o expresión:▫ Se puede deducir su tipo de dato

▫ Ya sea de su forma o de su declaración

▫ Sin necesidad que se ejecute ningún proceso

• Las operaciones entre datos:▫ Necesitan participantes (argumentos) de determinado tipo

▫ Producen resultados de otro o el mismo tipo

Unidad I• FIC-UAS

Tipo de Dato

• Es un atributo de una parte de los datos queindica a la computadora (y/o al programador)algo sobre la clase de datos, sobre lo que se va aprocesar.

• Esto incluye imponer restricciones en los datos,como qué valores pueden tomar y quéoperaciones se pueden realizar.

Tipos de Datos Maquina (0-1)

Tipos de Datos Primitivos

•Numéricos

•Lógicos

•Alfanuméricos

Tipos de Datos Abstractos

09/02/2018

5

Unidad I• FIC-UAS

TIPOS DE DATOS SIMPLES(Básicos)

Los podemos distinguir fácilmente, están en el diario vivir:

El Sr. Vera de 63 años tiene cedula No. 0908815533, y paga $120 de impuestos

Son tipos de datos simples:

Que permiten representar información numérica, Alfanumérico (caracteres) ó

lógicos.

NOMBRE CONJUNTO DE VALORES OPERACIONES

Enteros Negativos y positivos sin decimal Sumar, restar, dividir, multiplicar,

residuo

Reales Negativos y positivos, con decimal Sumar, restar, dividir, multiplicar

Lógicos Verdadero o Falso(1 o 0) And, Or, Not

Alfanuméricos Letras, números, especiales, juntos

forman una cadena

Sumar carácter + entero restar,

multiplicar por entero

Unidad I• FIC-UAS

Tipos de Datos Abstractos

• Abstracción.- Proceso mental mediante el cual se

extraen los rasgos esenciales de algo para representarlosmediante un lenguaje gráfico o escrito.

• Proceso de simplificar un problema complejo enfocándosetan sólo en los aspectos relevantes para la solución.

• En el desarrollo de software esto significa centrarse en loque es y hace un objeto, antes de decidir cómo debería serimplementado.

09/02/2018

6

Unidad I• FIC-UAS

Abstracción de Datos

• Técnica o metodología que permite diseñarestructuras de datos.

• Consiste en representar bajo ciertos lineamientosde formato, las características esenciales de unaestructura de datos.

• No se considera los detalles específicos deimplementación

Unidad I• FIC-UAS

Estructura de Datos

• Es cualquier colección o grupo de datosorganizados de tal forma que tenganasociados un conjunto de operaciones parapoder manipularlos.

• Ejemplo los Arreglos:

▫ Son un conjunto de datos del mismo tipo.▫ Con métodos claros de acceso.▫ Con diversas operaciones.

09/02/2018

7

Unidad I• FIC-UAS

Unidad I• FIC-UAS

Tipo de Dato Abstracto (TDA)

• Es la creación o diseño de una nuevaestructura de datos aplicando la técnica ymetodología de la abstracción, que podráimplementarse en cualquier lenguaje yaplicarse en cualquier concepto.

09/02/2018

8

Unidad I• FIC-UAS

Tipo de Dato Abstracto (TDA)

• Es un conjunto de valoresy operaciones asociadasque se especifican demanera precisa,independientes dealguna implementación enparticular.

• El TDA define la interface ala abstracción de datos sinespecificar detalles de laimplementación.

Unidad I• FIC-UAS

Tipo de Dato Abstracto (TDA)

• Es un tipo de dato definido por el programadorque se puede manipular de un modo similar alos tipos de datos definidos por el sistema.

• Está formado por un conjunto válido deelementos y un número de operacionesprimitivas que se pueden realizar sobre ellos.

• Una vez definido se podrán declarar variablesde ese tipo y operar con ellas utilizando lasoperaciones que aporta el tipo.

09/02/2018

9

Unidad I• FIC-UAS

Una clase que modela los atributos y el

comportamiento de una colección de objetos,

define un tipo de dato.

Si en el modelo se encapsula la representación de

los atributos y la implementación de las

operaciones, el tipo de dato es abstracto.

La interface describe qué pueden hacer los

objetos de una clase, la implementación establece

cómo lo hacen.

Tipo de Dato Abstracto

Unidad I• FIC-UAS

Para construir un tipo abstracto debemos

Exponer una definición del tipo.

2. Definir las operaciones (funciones yprocedimientos) que permitan operar coninstancias de ese tipo.

3. Ocultar la representación de los elementosdel tipo de modo que sólo se pueda actuarsobre ellos con las operacionesproporcionadas.

4. Poder hacer instancias múltiples del tipo.

09/02/2018

10

Unidad I• FIC-UAS

Representación de TDA

• Un TDA es representado por su interfaz, lacual sirve como cubierta a lacorrespondiente implementación.

• La idea es que los usuarios de un TDAtengan que preocuparse sólo por lainterfaz, pero no por la implementación,ya que esta puede ir cambiando con eltiempo

Unidad I• FIC-UAS

Representación

• La solidez de un TDA reposa en la idea de que la implementación está escondida al usuario. Solo la interfaz es pública.

• Lo anterior significa que el TDA puede serimplementado de diferentes formas, peromientras se mantenga consistente con lainterfaz, los programas que lo usan no se venafectados.

09/02/2018

11

Unidad I• FIC-UAS

Implementación

• Una vez definido el TAD se escoge unarepresentación interna utilizando los tiposque proporciona el lenguaje y/o otros TAD yadefinidos previamente.

• La representación deberá ocultarse utilizandolos mecanismos que nos proporcione ellenguaje. Ocultamiento de Información.

• Normalmente la implementación del tipo serealiza en un módulo aparte que seráenlazado al programa principal.

Unidad I• FIC-UAS

Clasificación de las Estructuras de Datos

09/02/2018

12

Unidad I• FIC-UAS

Estructuras de Datos Lineales y No Lineales.

Estructuras de datos lineales: Cada componente

tiene un único sucesor y un único predecesor con excepción del último y el primero.

Estructura de datos no lineal.-Cada componente

puede tener varios sucesores y varios predecesores.

Unidad I• FIC-UAS

Estructuras de Datos Estáticas y Dinámicas

• Las estructuras de datos estáticas:

▫ Son aquellas en las que el tamaño ocupado enmemoria se define antes que el programa seejecute y el mismo no puede ser modificadodurante la ejecución. Ejemplo: Arreglo, cadenas,estructuras.

• Las estructuras de datos dinámicas:

▫ No tienen limitaciones en cuanto al tamaño dememoria ocupada. Para utilizar este tipo deestructuras necesitamos usar un tipo de datoespecífico llamado puntero. Ejemplo: Pilas, colas,Lista, árbol, grafo.

09/02/2018

13

Unidad I• FIC-UAS

FIN Unidad I

¿Preguntas?

Unidad I• FIC-UAS

Ejemplificación de los elementos teóricos abordados, en un

lenguaje de programación. Pág. 29 libro Cairo, ejemplo 1.11.

09/02/2018

14

Unidad I• FIC-UAS

Unidad I• FIC-UAS

Actividad #1

• Aplicando la abstracción de datos,diseñe la estructura de dato, quepermita representar lascaracterísticas esenciales de unalumno, si se requiriera el guardar sunúmero de cuenta y nombre, asícomo también, las calificaciones desus tres parciales correspondientes,en la materia de Estructura deDatos.

09/02/2018

15

Unidad I• FIC-UAS

Actividad #2

• Tomando como referencia el tipodato obtenido en la actividadanterior, diseñe una aplicación(interfaz) que permita registrar losdatos de más de un alumno.

Unidad I• FIC-UAS

FIN Ejercicios

¿Preguntas?