c++ datos

7/17/2019 C++ Datos

http://slidepdf.com/reader/full/c-datos 1/41

Oscar Bedoya.

[email protected]

http://eisc.univalle.edu.co/~oscarbed/Estruct

uras/Edifcio 331, 2º piso, E.I.S.C.

Estructuras de datos yEstructuras de datos yalgoritmosalgoritmos

7/17/2019 C++ Datos


CONTENIDO

• !u" es un tipo de dato#• !u" es un tipos de dato abstracto $TD%&#

• Cu'l es el ciclo de vida de un TD%#

• E(e)plos de TD%

7/17/2019 C++ Datos


Tipos de datos

Algunos tipos de datos que se encuentran en loslenguajes de programación son:

• int

• foat

• double

• char

• cadena de caracteres(String)• arreglos.

7/17/2019 C++ Datos


Tipos de datos

Considere el tipo de datos int • Cu'les n*)eros pertenecen a este tipo de

dato

• Cu'ntos ele)entos tiene

• !u" operaciones se pueden reali+ar sobreenteros

7/17/2019 C++ Datos


Tipos de datos

El tipo de datos int es un subconjunto de losnmeros enteros. Son !nitos.

int ⊂ "

Algunas de las operaciones que est#n permitidassobre enteros son:

$: int % int & int

' : int % int & int

* : int % int & int

: int % int & double

%: int % int & double

7/17/2019 C++ Datos


Tipos de datos

El tipo de datos oat es un subconjunto de losnmeros reales. Son !nitos.

oat ⊂

Algunas de las operaciones que est#n permitidassobre fotantes son:

$: oat % oat & oat

': oat % oat & oat

*: oat % oat & oat

: oat % oat & oat

7/17/2019 C++ Datos


Tipos de datos

El tipo de datos String (cadena de caracteres)cadena + ,car#cter-car#cter/ 0 car#ctern'/1

Algunas de las operaciones que est#n permitidassobre cadenas de caracteres son:

strlen : cadena & int

$ : cadena % cadena & cadena

7/17/2019 C++ Datos


Tipos de datos

2esde un en3oque orientado a objetos considere eltipo uto!"#il de!nido de la siguiente manera

Automo4il + (motor baul areapasajeros chasiscarroceria)

Automo4il ∈5ehiculo

Algunas de las operaciones que est#n permitidassobre un Automo4il

encender : uto!o#il % $la#e & uto!o#il

acelerar : uto!o#il % Intensidad & uto!o#il

7/17/2019 C++ Datos


Tipos de datos

En todos los tipos de!nidos consideradosanteriormente se tienen en cuenta dos aspectos

• roposiciones l"gicas &ue indican &u'ele!entos pertenecen, o no, al tipo

• Con(unto de operaciones o acciones &ue se pueden reali)ar sobre los ele!entos deltipo

7/17/2019 C++ Datos


Tipos de datos

Un tipo de datos defne el conjunto de valoresválidos del tipo y las operaciones que se puedenaplicar al tipo.

7/17/2019 C++ Datos


Tipos de datos

,n Tipo de Dato %bstracto debe de-nir dos

partes:

• El in4ariante

• 6n conjunto de operaciones.

7/17/2019 C++ Datos


Tipos de datos

• El invariante.

El in#ariante es una proposición que e%presa elconjunto de 4alores 4#lidos del 72A. 8ermite saberqu9 elementos pertenecen al 72A qu9 elementos

no.

6n in4ariante tambi9n e%presa la estructuraabstracta del 72A.

7/17/2019 C++ Datos


Tipos de datos

Se dice que la estructura es abstracta porque se

trata de que el 72A tenga un nivel alto degeneralidad

6na de las 3ormas para que esto se cumpla es que

el 72A debe ser lo m#s independiente posible de suimplementación

7/17/2019 C++ Datos


Tipos de datos

• ,n con(unto de operaciones

6na operación es algo que se le puede hacer al 72A.

El conjunto de las operaciones de!ne elcomportamiento del 72A esto es de!ne lo que sepuede hacer o no con el 72A.

7/17/2019 C++ Datos


Tipos de datos

6n 72A puede estar compuesto por otros 72As.

En t9rminos 3ormales un 72A se de!ne como el par$invariante operaciones& donde in4ariante es

una proposición (que tiene un 4alor 4erdadero o3also) operaciones es el conjunto de lasoperaciones del 72A.

7/17/2019 C++ Datos


Tipos de datos

!ue es una instancia de TD%#

6na instancia de 72A o simplemente instancia esun elemento que pertenece al 72A.

El 72A es abstracto mientras que la instancia esconcreta

7/17/2019 C++ Datos


Tipos de datos

!ue es una instancia de TD%#

6n 72A es como un molde o un sello que de!necomo ser# la 3orma comportamiento de loselementos que le pertenecen.

6na instancia por su parte es la impresión delsello o molde.

7/17/2019 C++ Datos


Tipos de datos

Considere el 72A Automó4il. A partir de este 72Apodemos de!nir cualquier cantidad de instancias.Cada una con 4alores concretos que permitendi3erenciar una instancia de otra

7/17/2019 C++ Datos


Tipos de datos

El ciclo de vida de un TD% se compone de tresetapas:

• 2ise;o

• <mplementación• 6so.

DISEÑO IMPLEMENTACION USO

7/17/2019 C++ Datos


Tipos de datos

DIE0O

Se describe cómo 4a a ser el 72A su in4ariante sus operaciones.

Es en esta etapa cuando el 72A es 4erdaderamenteabstracto en las otras etapas comien=a a ser real.

>a etapa de dise;o del 72A responde a laspreguntas:

¿Cómo es el TDA?.¿Cómo es la estructura del TDA?¿Cuál es el conjunto de valores válidos?¿Cuáles son sus operaciones?

7/17/2019 C++ Datos


Tipos de datos

DIE0O

• 8roposiciones lógicas que indican qu9 elementospertenecen o no al tipo

• Conjunto de operaciones o acciones que sepueden reali=ar sobre los elementos del tipo8or cada operación se debe establecer eldominio el codominio

7/17/2019 C++ Datos


Tipos de datos

DIE0O $Docu)ento 1or)al&

1. Nombre: La letra inicial en mayúscula el resto en minúsculas.2. Descripción del TDA: Una frase en lenua!e natural

"escri#ien"o el TDA.3. Invariante de TDA: Una $ro$osici%n l%ica &ue e'$resa el

con!unto "e (alores ()li"os "el TDA.*. as operaciones

!.1 Nombre de operación: To"as las letras en minúscula ae'ce$ci%n "e las

o$eraciones constructoras &ue tienen el mismo nom#re "elTDA.

!.1.1 Descripción: Una frase en lenua!e natural"escri#ien"o la o$eraci%n.

!.1.2 Descripción operacional: La "escri$ci%n en t+rminos"el "ominio y

7/17/2019 C++ Datos


Tipos de datos

I234E2ENT%CION

>a implementación consiste en tomar el dise;o del 72A con4ertirlo en algo real en nuestro caso eslle4arlo a un lenguaje de programación.

>a implementación de un 72A no es nica? dado undise;o de un 72A es posible implementarlo dedi4ersas 3ormas

7/17/2019 C++ Datos


Tipos de datos

I234E2ENT%CION

DISEÑO IMPLEMENTACION , USO

IMPLEMENTACION -

IMPLEMENTACION

IMPLEMENTACION *

Diferentes

implementacionespuedenrepresentarel mismoTDA

7/17/2019 C++ Datos


Tipos de datos

,O

El uso de un 72A se re!ere a cuando se utili=a enuna aplicación para resol4er una problemaespeci!co.

>os di4ersos usos de un 72A es una prueba de lageneralidad de este.

7ener un conjunto de 72As reutili=ables hace muchom#s 3#cil construir un so3t@are complejo. 8arahacer esto es solo unir las implementaciones quenecesitemos de la 3orma adecuada se tiene laaplicación.

7/17/2019 C++ Datos


Tipos de datos

,O

En el caso en que se presenten errores en laimplementación de un 72A es m#s 3#cil corregir unerror pues es solo corregir en este

autom#ticamente quedar# corregido en todo elso3t@are que lo utilice a que los errores est#nmodulari=ados.

>a reutili=ación la modularidad hacen lasimplementaciones de los 72A una herramientapoderosa para el desarrollo de so3t@are de calidad.

7/17/2019 C++ Datos


Tipos de datos

I234E2ENT%CION

IMPLEMENTACION USO ,

USO -

USO

USO *

Diversos usos

de laimplementación de un TDA.

7/17/2019 C++ Datos


Tipos de datos

TD% Co)ple(o

6n nmero complejo es un objeto matem#tico quese puede representar como una pareja ordenadapor ejemplo (B) o como el polinomio $ Bi

donde i es la unidad b#sica de los nmerosimaginarios.

>os nmeros complejos tienen operaciones comolas de suma resta multiplicación. Si tenemos doscomplejos c1+r 1 ,i 1 - c2+r 2 ,i 2& las operaciones

se pueden de!nir de la siguiente manera:C5 6 C7 8 $r5 6 r7 i5 6 i7&C5 9 C7 8 $r5 9 r7 i5 9 i7&

7/17/2019 C++ Datos


Tipos de datos

TD% Co)ple(o$Invariante&

8ara establecer el in4ariante debemos responder alas dos preguntas:

C"!o es la estructura del /0

El 72A Complejo contiene dos partes: la real laimaginaria.

7/17/2019 C++ Datos


Tipos de datos

TD% Co)ple(o$Invariante&

Cu'l es el con(unto de valores v'lidos#

Se puede e%presar en t9rminos del conjunto de

4alores 4#lidos de cada una de las partes del 72Aes decir la primera parte de un Complejo es unnmero que pertenece al conjunto de los nmerosreales las segunda es un nmero imaginario.ormalmente se puede e%presar como:

Co)ple(o8$real i)ainario& real ∈ D imaginario∈ <

7/17/2019 C++ Datos


Tipos de datos

TD% Co)ple(o$Operaciones&

Cu'les son sus operaciones#

sumar: Co)ple(o % Co)ple(o & Co)ple(o

restar: Co)ple(o % Co)ple(o & Co)ple(o

obtenereal: Co)ple(o &

obtener<maginario: Co)ple(o & I

Complejo R % I & Co)ple(o (Operación deconstrucción)

Las operaciones sumar y restar tienen comodominio el roducto cartesiano de Com le os

7/17/2019 C++ Datos


Tipos de datos

TD% Co)ple(o $Docu)ento -nal&

TDAComplejo

Descripción: El TDA Complejo representa al conceptomatemático de número complejo, es decir,un número que tiene una parte real y otraimaginaria.

Inariante: Complejo!" real# imaginario #, real ∈ R ! imainario ∈

7/17/2019 C++ Datos


Tipos de datos


Operación! Complejo

Descripción:

Construye un n"mero complejo con #ase en unreal real y un imaginario imainario.

Descripción operacional: Complejo! R ' I / Com$le!o

%recondición:real ∈ R ! imainario ∈

%oscondición:Complejo $ ( real0 imainario )

7/17/2019 C++ Datos


Tipos de datos


Operación! %umar

Descripción:

%uma dos n"meros complejos. Descripción operacional: sumar1 $omple%o ' $omple%o / $omple%o

%recondición:otro ∈ Complejo

%oscondición:sumar $ ( real 2 otro.real0 imainario 2

otro.imainario )

7/17/2019 C++ Datos


Tipos de datos


Operación! O#tenerReal

Descripción:

Retorna la parte real del n"mero complejo. Descripción operacional: o#tenerReal1 $omple%o / 3

%recondición:

%oscondición:o#tenerReal $ real

7/17/2019 C++ Datos


Tipos de datos

I234E2ENT%CION

7/17/2019 C++ Datos


Tipos de datos

public class Complejo {

double real;

double imaginario;

public Complejo (double r, double i)

{

real = r;

imaginario = i;

}

7/17/2019 C++ Datos


Tipos de datos

public Complejo sumar (Complejo C1, Complejo C2){

Complejo C3 = new Complejo(0,0);

C3.real = C1.real C2.real; C3.imaginario = C1.imaginario C2.imaginario;

re!urn C3;

}

i d d

7/17/2019 C++ Datos


Tipos de datos

public double obtenerReal(Complejo C1) {

re!urn C1.real;

}

Ti d d

7/17/2019 C++ Datos


Tipos de datos

,O

Ti d d t

7/17/2019 C++ Datos


Tipos de datos

TD% ;%CION%4

TDA &acional

Descripción: El TDA &acional representa al conceptomatemático de número racional, es decir,un número que tiene un numerador y undenominador, am'os alores de'en ser detipo entero.

Inariante:

c++ datos

Documents