Download - Teoria Parcial 1 ED
![Page 1: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/1.jpg)
Programación Orientada a Objetos (POO) en Python
Classes y Tipos de Datos Abstractos
Tema 2
Petia Ivanova Radeva 1
![Page 2: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/2.jpg)
Petia Ivanova Radeva
Índice
Clases y objetos
Clases y atributos ◦ Datos
◦ Métodos
◦ Constructor
Objetos encrustados
Clases mutables y copias
Tema 2 POO en Python 2
![Page 3: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/3.jpg)
Petia Ivanova Radeva
Casi todo en Python es objeto…
Cada variable en Python es de hecho un objeto. ◦ Hemos visto ejemplos de objetos ya ...
>>> hello .upper() >>>list3.append( a ) >>>dict2.keys()
◦ Estos comandos parecen a llamadas a métodos en Java o C ++ .
◦ Además de estos tipos de datos incorporados, podemos también diseñar nuestros propios objetos ...?
De hecho, la programación en Python se realiza normalmente de forma orientada a objetos.
![Page 4: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/4.jpg)
Petia Ivanova Radeva
Clases y objetos: definición de nuevos tipos
◦ Consideremos que hemos de representar un punto:
x,y=1,0
◦ ¿Cómo representamos muchos puntos?
, , , = , , , …
xy= [[ , ],[ , ]…]
◦ Creamos un nuevo tipo: Punto
# Fichero Point.py:
class Point:
“””represents a point in 2-D space””” …. ¿Cómo comprobamos si entre dos puntos cuál es el que está más lejos del centro de coordenadas?
Tema 2 POO en Python 4
Df: Los tipos definidos por el usuario se llaman clases.
![Page 5: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/5.jpg)
Petia Ivanova Radeva
Definición de una clase
Una clase es un tipo de datos especial que define cómo construir un cierto tipo de objeto.
La "clase" también almacena parte de los datos que son compartidos por todas las instancias de esta clase.
"Instancias" son objetos que se crean que siguen la definición dada en el interior de la clase.
Python no utiliza definiciones de interfaz de clases separadas. Directamente definimos la clase y ya la podemos usar.
![Page 6: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/6.jpg)
Petia Ivanova Radeva
Clases y objetos: Instanciación
class Point:
“””represents a point in 2-D space””” …. >>>pnt=Point() #creamos un objeto de tipo Point
Df: Una instancia de una clase se llama objeto. El proceso se llama instanciación.
Ejemplo: Lassy vs. perro, class Point, pnt=Point()
>>> pnt2=Point()
>>>pnt3=Point() # creamos tantos objetos como necesitamos
Los objetos están referenciados por variables de tipo igual al nombre de la classe.
Tema 2 POO en Python
6
![Page 7: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/7.jpg)
Petia Ivanova Radeva
Clases y objetos:
Tema 2 POO en Python 7
Definición de la clase:
class Point: #código...
b=Point()
La varia le a contiene referencia que apunta a:
Objeto de tipo Point e.d. instancia de la clase Point en
dirección 0x0F45
La varia le contiene referencia que apunta a:
Objeto de tipo Point e.d. instancia de la clase Point en
dirección 0x6F48
La varia le contiene referencia que apunta a:
Objeto de tipo Point e.d. instancia de la clase Point en
dirección 0xFF25
![Page 8: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/8.jpg)
Petia Ivanova Radeva
Clases y objetos: Tipo de Datos Abstracto (clase)
Tipo de Datos Abstracto (TDA) – descripción lógica sobre:
◦ El estado del objeto (sus datos)
◦ Los métodos del objeto (qué puede hacer).
◦ Se implementa a través de las clases.
Una clase es un tipo de datos abstracto que contiene algo y define qué se
puede operar con este algo . 1. Una colección de información relevante.
2. Un conjunto de operaciones para manipular esta información.
La información está guardada en variables objetos (instancias de las clases).
Definimos la clase como: class <class-name>: <method-definitions>
![Page 9: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/9.jpg)
Petia Ivanova Radeva
Índice
Clases y objetos
Clases y atributos ◦ Datos
◦ Métodos
◦ Constructor
Objetos encrustados
Clases mutables y copias
Tema 2 POO en Python 9
![Page 10: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/10.jpg)
Petia Ivanova Radeva
Clases y atributos: Datos
Python permite asignar valores y crear atributos usando el operador . :
>>>blank=Point() # crea objeto de tipo Point
>>> blank.x = 3.0 # crea los datos del objeto,
>>> blank.y = 4.0
Df. Diagrama del objeto – diagrama del estado que indica los valores de los atributos del objeto:
Tema 2 POO en Python 10
![Page 11: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/11.jpg)
Petia Ivanova Radeva
Clases y atributos: Datos y su acceso
Leemos los valores de los datos usando la misma sintaxis:
>>>blank=Point()
>>>print blank.y
4.0
>>> x = blank.x
>>> print x
3.0
>>> print ’(’ + str(blank.x) + ’, ’ + str(blank.y) + ’)’
>>> distanceSquared = blank.x * blank.x + blank.y * blank.y
Tema 2 POO en Python 11
![Page 12: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/12.jpg)
Petia Ivanova Radeva
Índice
Clases y objetos
Clases y atributos ◦ Datos
◦ Métodos
◦ Constructor
Objetos incrustados
Clases mutables y copias
Tema 2 POO en Python 12
![Page 13: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/13.jpg)
Petia Ivanova Radeva
Clases y atributos: métodos (funciones)
Vamos a definir la clase Tiempo:
class Time(object):
"""represents the time of day.
attributes: hour, minute, second""“
>>>time = Time()
>>>time.hour = 11
>>>time.minute = 59
>>>time.second = 30
Tema 2 POO en Python 13
![Page 14: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/14.jpg)
Petia Ivanova Radeva
Clases y atributos: métodos (funciones)
Definir un método que imprime los valores del objeto de la clase: class Time:
"""represents the time of day.
attributes: hour, minute, second"""
def print_time(time): # función global
print '%.2d:%.2d:%.2d' % (time.hour, time.minute, time.second)
>>> start = Time() # creamos el objeto
>>> start.hour = 9
>>> start.minute = 45
>>> start.second = 00
>>> print_time(start)
09:45:00
¿Ha de ser una función global? ¿Cómo definir una función de una clase? Tema 2 POO en Python 14
![Page 15: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/15.jpg)
Petia Ivanova Radeva
Clases y atributos: métodos (funciones)
Tema 2 POO en Python 15
¿Cómo definir una función de una clase?: • Podemos definir un método en una clase mediante la inclusión de la definición de
funciones dentro del ámbito del bloque de clases.
class Time(object): def print_time(self): #método de la clase print '%.2d:%.2d:%.2d’ % (self.hour, self.minute, self.second)
Definimos el método de la clase como una función (usando def) dentro de la clase
• ¿Cuál es el primer argumento de los métodos de una clase?
• self permite distinguir los atributos de la clase de los datos globales.
•¿Por qué es importante?
![Page 16: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/16.jpg)
Petia Ivanova Radeva
Clases y atributos: métodos (funciones)
Tema 2 POO en Python 16
class Time: def print_time(self): #método de la clase print '%.2d:%.2d:%.2d’ % (self.hour, self.minute, self.second) >>> start=Time() >>>start.hour=9 >>>start.minute=45 >>>start.second=00 >>> print start.hour # imprimimos el dato hour de 9 >>>start.print_time() #llamamos el método de la clase con el objeto (start) 09:45:00 >>>start2=Time() ….
Llamamos los métodos y los datos desde fuera de la clase: • con el nombre del objeto de la clase. ¿Por qué?
![Page 17: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/17.jpg)
Petia Ivanova Radeva
Clases y atributos: métodos (funciones)
Tema 2 POO en Python 17
class Time(object): def print_time(self):… def increment(self, seconds): #método de la clase seconds += self.time_to_int() #llamamos los métodos de la clase con self return self.int_to_time(seconds) def time_to_int(self):
self.minutes = self.hour * 60 + self.minute self.seconds = self.minutes * 60 + self.second # recuperamos los datos del
objeto con self return self.seconds
def int_to_time(self,seconds):…
>>> start=Time() >>>start.print_time() #llamamos el método de la clase con el objeto (start) 09:45:00 >>> end = start.increment(1337) >>> end.print_time() 10:07:17 • Llamamos los métodos y los datos desde dentro de la clase:
• Con la lave self !
• Dónde se declaran los datos? Pueden declararse en cualquier método?
![Page 18: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/18.jpg)
Petia Ivanova Radeva
Clases y atributos: métodos (funciones)
class Time (object):
# inside class Time:
def is_after(self, other):
return self.time_to_int() > other.time_to_int()
>>> start.print_time()
09:15:00
>>> end.print_time()
09:45:00
>>>end.is_after(start)
True
¿Por qué la llamada de la función tiene sólo un argumento?
Tema 2 POO en Python 18
Usando dos objetos:
![Page 19: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/19.jpg)
Petia Ivanova Radeva
Clases y atributos: métodos puros
def add_time(t1, t2): #t1, t2 objetos de tipo Time sum = Time()
sum.hour = t1.hour + t2.hour
sum.minute = t1.minute + t2.minute
sum.second = t1.second + t2.second
if sum.second >= 60: sum.second -= 60
sum.minute += 1
if sum.minute >= 60: sum.minute -= 60
sum.hour += 1
return sum
Df: Las funciones puras no modifican los valores de los objetos.
Tema 2 POO en Python
19
![Page 20: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/20.jpg)
Petia Ivanova Radeva
Clases y atributos: métodos puros class Time(object):
def getHour(self):
return self.hour
def setHour(self,hour):
self.hour=hour
def add_time(t1, t2): #t1, t2 objetos de tipo Time
sum = Time()
sum.setHour(t1.getHour() + t2.getHour())
sum.setMinute(t1.getMinute() + t2.getMinute())
sum.setSecond(t1.getSecond() + t2.getSecond())
if sum.getSecond() >= 60:
sum.setSecond(sum.getSecond() – 60) sum.setMinute(sum.getMinute + 1)
if sum.getMinute() >= 60:
sum.setMinute(sum.getMinute() – 60) sum.setHour(sum.getHour() + 1)
return sum
La forma correcta para acceder a los valores de las clases es a través de los métodos getValor().
Tema 2 POO en Python
20
![Page 21: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/21.jpg)
Petia Ivanova Radeva
Clases y atributos: métodos modificadores
Df. Funciones modificadoras – modifican los valores de sus parámetros
def increment(time, seconds):
time.setSecond(time.getSecond() + seconds)
if time.getSecond() >= 60:
time.setSecond(time.getSecond() – 60) time.setMinute(time.getMinute() + 1)
if time.getMinute() >= 60: #sustituir el if con while!
time.setMinute(time.getMinute() – 60) time.setHour(time.getHour() + 1)
Estilo de programación funcional: siempre que se pueda, utilizar funciones puras.
◦ Hace ejecutar más rápido los programas.
◦ Se obtienen menos errores de la ejecución.
Tema 2 POO en Python 21
La forma correcta para modificar a los valores de las clases es a través de los métodos setValor().
![Page 22: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/22.jpg)
Petia Ivanova Radeva
Clases y atributos: métodos modificadores Df. Funciones modificadores – modifican los valores de sus parámetros
def increment(self, seconds):
self.setSecond(self.getSecond() + seconds)
if self.getSecond() >= 60:
self.setSecond(self.getSecond() – 60) self.setMinute(self.getMinute() + 1)
if self.getMinute() >= 60: #sustituir el if con while!
self.setMinute(self.getMinute() – 60) self.setHour(self.getHour() + 1)
◦ Las funciones modificadores definirlas como métodos de la clase.
Tema 2 POO en Python 22
![Page 23: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/23.jpg)
Petia Ivanova Radeva
Clases y atributos
Python – lenguaje de Programación orientada a objetos
◦ Programas compuestos por definiciones de clases y funciones donde la parte más importante de computación -> las operaciones de los objetos.
◦ Cada definición de clase corresponde a un concepto del mundo real y las funciones de las clases corresponden a la interacción de los objetos.
Df. Un método es una función asociada con una clase (p.e. concatenación de cadenas).
Diferencia entre funciones globales y métodos:
◦ Están definidos dentro de una clase para explicitar la relación entre la clase y el método.
◦ Tiene sintaxis diferente de las funciones globales.
Tema 2 POO en Python 23
![Page 24: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/24.jpg)
Petia Ivanova Radeva
Clases y atributos: cómo instanciamos un objeto?
Constructor: Método especial que construye e inicializa un objeto al declararlo de una clase.
class Time(object):
def __init__(self, hour=0, minute=0, second=0): #coincidencia de los nombres
self.hour = hour # define los atributos de la clase
self.minute = minute
self.second = second
>>>t1=Time(1,2,3)
Al crear un objeto, donde se llama el constructor e.d. se usa explicitamente __init__()?!
Tema 2 POO en Python
24
![Page 25: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/25.jpg)
Petia Ivanova Radeva
Constructor: __init__
El método __init__ puede tomar cualquier número de argumentos.
◦ Al igual que otras funciones o métodos, los argumentos pueden ser definidos con valores
por defecto.
◦ Sin embargo, el primer argumento en la definición de __init__ es especial ...
En __init__, self se refiere al objeto que se está creando actualmente; mientras, en los otros métodos de la clase, se refiere a la instancia cuyo método fue llamado.
◦ De manera similar a la palabra clave this' en Java o C ++.
![Page 26: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/26.jpg)
Petia Ivanova Radeva
Clases y atributos: métodos (funciones)
Tema 2 POO en Python 26
class Time(object): def print_time(self):… def increment(self, seconds): #método de la clase seconds += self.time_to_int() #llamamos los métodos de la clase con self return self.int_to_time(seconds) def time_to_int(self):
self.minutes = self.hour * 60 + self.minute self.seconds = self.minutes * 60 + self.second # recuperamos los
datos del objeto con self return self.seconds
def int_to_time(self,seconds):…
>>> start=Time() >>>start.print_time() #llamamos el método de la clase con el objeto (start) 09:45:00 >>> end = start.increment(1337) >>> end.print_time() 10:07:17 • Llamamos los métodos y los datos desde dentro de la clase:
• Con la lave self !
• Dónde se declaran los datos? Pueden declararse en cualquier método?
![Page 27: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/27.jpg)
Petia Ivanova Radeva
Self
Recordar:
Aunque se debe especificar self de forma explícita en la definición del método, no es necesario incluirla en la llamada al método.
Python lo pasa de forma automática.
Definición del método: Llamada al método: (este código va dentro de la definición de la clase)
def setMinute(self, num): >>> x.setMinute(23) self.minutes = num
![Page 28: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/28.jpg)
Petia Ivanova Radeva
No hace falta liberar espacio ( free ) Cuando hayamos terminado con un objeto, no hace falta
eliminar o liberar explícitamente la memoria.
◦ Python tiene el garbage collection automático (recolección de basura
automática).
◦ Python detectará automáticamente cuando todas las referencias a una parte de memoria han sido fuera de alcance. Y liberará automáticamente la memoria.
◦ Trabaja generalmente bien, pocas pérdidas de memoria.
◦ No hay ningún método "destructor" para las clases.
![Page 29: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/29.jpg)
Petia Ivanova Radeva
Clases y atributos: el constructor
¿Cómo definir los atributos – datos de la clase? class Time(object):
def __init__(self, hour=0, minute=0, second=0): #coincidencia de los nombres
self.hour = hour # define los atributos de la clase
self.minute = minute
self.second = second
def time_to_int(self):
self.minutes = self.hour * 60 + self.minute
self.seconds = self.minutes * 60 + self.second
# recuperamos los datos del objeto con self
return self.seconds
>>> print t1.seconds
Al declarar un dato dentro de un método con self, automáticamente lo convertimos en atributo de la clase.
Se desanconseja inicializar los datos fuera de la clase!
Tema 2 POO en Python
29
![Page 30: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/30.jpg)
Petia Ivanova Radeva
Clases y atributos: el constructor
class Time(object):
pass
>>>t1=Time()
>>>t1.hour=1 #evitar
>>>t1.minute=15
>>>t1.second=20
NO!!!
Tema 2 POO en Python 30
class Time(object):
def __init__(self, hour=0, minute=0, second=0): #coincidencia de los nombres
self.hour = hour self.minute = minute
self.second = second
def time_to_int(self)….
>>>t1=Time(1,2,3)
Df: El proceso de separar los detalles de implementación y organizar los atributos (datos y métodos) dentro de las clases se llama encapsulamiento.
![Page 31: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/31.jpg)
Petia Ivanova Radeva
Clases y atributos: el constructor
Valores opcionales del constructor >>> time = Time() # se llama el constructor __init__(self,…)
>>> time.print_time() # con los valores por defecto/opcionales
00:00:00
>>> time = Time (9)
>>> time.print_time()
09:00:00 # no se aplican los valores opcionales
>>> time = Time(9, 45) # van por orden
>>> time.print_time()
09:45:00
Tema 2 POO en Python 31
![Page 32: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/32.jpg)
Acceso a los atributos y los métodos
![Page 33: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/33.jpg)
Petia Ivanova Radeva
Definimos la clase student
class student: A class representing a student.
def __init__(self,n,a): self.full_name = n self.age = a def get_age(self): return self.age
![Page 34: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/34.jpg)
Petia Ivanova Radeva
Sintáxis tradicional de acceso
>>> f = student ( Bob Smith , 23)
>>> f.full_name # Access an attribute.
Bob Smith
>>> f.get_age() # Access a method.
23
![Page 35: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/35.jpg)
Petia Ivanova Radeva
Accediendo atributos desconocidos
¿Qué pasa si no sabemos el nombre del atributo o método de una clase que deseamos acceder hasta el tiempo de ejecución ...
¿Hay una manera de tomar una cadena que contiene el nombre de un atributo o método de una clase y obtener una referencia a él (para que pueda usarlo)?
![Page 36: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/36.jpg)
Petia Ivanova Radeva
getattr(object_instance, string)
>>> f = student( Bob Smith , 23) >>> getattr(f, full_name ) Bob Smith >>> getattr(f, get_age ) <method get_age of class studentClass at 010B3C2> >>> getattr(f, get_age )() # We can call this. 23 >>> getattr(f, get_birthday ) # Raises AttributeError – No method exists.
![Page 37: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/37.jpg)
Petia Ivanova Radeva
hasattr(object_instance,string)
>>> f = student( Bob Smith , 23) >>> hasattr(f, full_name ) True >>> hasattr(f, get_age ) True >>> hasattr(f, get_birthday ) False
![Page 38: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/38.jpg)
Atributos
![Page 39: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/39.jpg)
Petia Ivanova Radeva
Dos tipos de atributos
Los datos (que no son métodos) almacenado por objetos se denominan atributos. Hay dos tipos:
Atributo de datos: Variable propiedad de un caso particular de una clase ◦ Cada instancia puede tener su propio valor diferente para ella Estos
son el tipo más común de atributo.
Los atributos de clase: Propiedad de la clase en su conjunto. ◦ Todas las instancias de la clase comparten el mismo valor para él. ◦ Llamado variables "estáticas" en algunos lenguajes? ◦ Útil para constantes en toda la clase o para la construcción de contador
de cuántas instancias de una clase se han hecho.
![Page 40: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/40.jpg)
Petia Ivanova Radeva
Atributos de datos
Se crean e inicializan los atributo de datos dentro del método __init __ (). ◦ Recuerde la asignación se utiliza para crear las variables en Python; ◦ así, la asignación de un nombre crea el atributo.
Dentro de la clase, los atributos de datos se obtienen via self: p.e., self.full_name
class teacher: A class representing teachers. def __init__(self,n): self.full_name = n def print_name(self): print self.full_name
![Page 41: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/41.jpg)
Petia Ivanova Radeva
Atributos de la clase Todas las instancias de una clase comparten una copia de un atributo
de clase, por lo que cuando cualquiera de las instancias lo cambia, entonces el valor se cambia para todos ellos.
Definimos los atributos de clase fuera de cualquier método.
Puesto que no es uno de estos atributos por clase y no una por ejemplo, utilizamos una notación diferente: accedemos a través del nomber de la clase: self.__class__.name.
class sample: >>> a = sample() x = 23 >>> a.increment() def increment(self): >>> a.__class__.x
self.__class__.x += 1 24
![Page 42: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/42.jpg)
Petia Ivanova Radeva
Datos vs. atributos de la clase
class counter: overall_total = 0 # class attribute def __init__(self): self.my_total = 0 # data attribute def increment(self): counter.overall_total = \ counter.overall_total + 1 self.my_total = \ self.my_total + 1
>>> a = counter() >>> b = counter() >>> a.increment() >>> b.increment() >>> b.increment() >>> a.my_total 1 >>> a.__class__.overall_total 3 >>> b.my_total 2 >>> b.__class__.overall_total 3
![Page 43: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/43.jpg)
Petia Ivanova Radeva
Índice
Clases y objetos
Clases y atributos ◦ Datos
◦ Métodos
◦ Constructor
Objetos encrustados
Clases mutables y copias
Tema 2 POO en Python 43
![Page 44: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/44.jpg)
Petia Ivanova Radeva
Objetos encrustados ¿Cómo definir la clase Rectángulo? ◦ A través de un punto, anchura y altura
class Point(object):
def __init__(self,x,y):
self.x, self,y=x, y
class Rectangle(object):
"""represent a rectangle. attr: width, height, corner"””
def __init__(self, width, height, cornerx, cornery):
self.width, self.height=width, height
self.corner=Point(cornerx,cornery)
Df. Un objeto que es un atributo de otro objeto se llama encrustado (embedded).
Tema 2 POO en Python 44
![Page 45: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/45.jpg)
Petia Ivanova Radeva
Objetos incrustados: Instancias de objetos como valores de retorno # En la clase Rectangle:
def find_center(self):
return Point(self.corner.x + self.width/2.0, self.corner.y + self.height/2.0)
>>> mibox = Rectangle(100,200,0,0)
>>> center=mibox.find_center()
>>> print center
(50.0, 100.0)
>>>a=[]
>>>a.append(Point(10,4))
Tema 2 POO en Python 45
¿Qué sucede con el objeto que retorna la función find_center()?
![Page 46: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/46.jpg)
Petia Ivanova Radeva
Índice
Clases y objetos
Clases y atributos ◦ Datos
◦ Métodos
◦ Constructor
Objetos encrustados
Clases mutables y copias
Tema 2 POO en Python 46
![Page 47: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/47.jpg)
Petia Ivanova Radeva
Clases mutables y copias: los objetos son mutables!
class Rectangle(object):
…. def grow_rectangle(self, dwidth, dheight) :
self.width += dwidth
self.height += dheight
>>> print mibox
100 200
>>>mibox2=mibox
>>> mibox2.grow_rectangle(50, 100)
>>> print mibox
¿Habrán cambiado los valores de los atributos?
Tema 2 POO en Python 47
![Page 48: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/48.jpg)
Petia Ivanova Radeva
Clases mutables y copias: los objetos son mutables!
Utilizar el aliasing puede ser confuso, no darnos cuenta de los cambios de valores de los objetos.
¿Cuál sería la alternativa? >>> mibox2 = mibox
>>> print mibox2 is mibox
True
>>> print mibox2==mibox
True
¿Comprueba la identidad o la equivalencia?
Tema 2 POO en Python 48
>>> mibox2 = copy.copy(mibox) >>> print mibox2 is mibox False >>> print mibox2==mibox False
![Page 49: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/49.jpg)
Petia Ivanova Radeva
Clases mutables y copias: los objetos son mutables!
>>> mibox2 = copy.copy(mibox)
>>> mibox2 is mibox
False
>>> mibox2.corner is mibox.corner
True
copy.copy copia los valores simples pero no los atributos encrustados! Copia débil (shallow copy)
Tema 2 POO en Python 49
![Page 50: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/50.jpg)
Petia Ivanova Radeva
Clases mutables y copias: los objetos son mutables!
>>> mibox2 = copy.deepcopy(mibox)
>>> mibox2 is mibox
False
>>> mibox2.corner is mibox.corner
False
¿Se puede decir que mibox2 y mibox son completamente objetos diferentes?
Df. La copia profunda (deep copy) copia recursivamente todos los atributos encrustados.
Tema 2 POO en Python 50
![Page 51: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/51.jpg)
Petia Ivanova Radeva
Conclusiones Python es un lenguaje orientado a objetos, potente y fácil de programar.
Las classes permiten implementar tipos de datos abstractos.
El encapsulamiento de los datos y los métodos es un proceso de organizarlos en clases donde se separa la interfaz de la clase de la implementación de sus métodos.
Los constructores son métodos de las clases que tienen el objetivo de crear los objetos e inicializar sus valores. ◦ Se ha de evitar inicializar los datos de la clase fuera de los constructores.
La forma correcta para acceder a los valores de las clases es a través de funciones getValor() y setValor(). ◦ Por defecto, intentar definir los métodos como métodos puros.
Se pueden incrustar objetos dentro de objetos.
Las clases son tipos de datos mutables ◦ Una solución es copiar los objetos usando la copia simple o la copia profunda.
Tema 2 POO en Python 51
![Page 52: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/52.jpg)
Programación Orientada a Objetos (POO) en Python
Polimorfismo, encapsulamiento y
herencia Tema 3
Petia Ivanova Radeva Última corrección: 19/02/2015
1
Pictures and some slides from: Matt Huenerfauth University of Pennsylvania
![Page 53: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/53.jpg)
Petia Ivanova Radeva
Índice Acceso a los atributos y los métodos
Tipos de atributos
Objetos incrustados
Clases mutables y copias
Encapsulamiento
Polimorfismo y sobrecarga
Herencia
Tema 2 POO en Python
2
![Page 54: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/54.jpg)
Petia Ivanova Radeva
Consideremos la siguiente lista de estudiantes
class Student: A class representing a student.
def __init__(self,n,a): self.full_name = n self.age = a
students=[[ Bob Smith , 23],[“Anna Kournikova”, 25], [“Andy Roddick”, 28]]
¿Cómo convertirla en una lista de objetos?
>>>f = Student( Bob Smith , 23) # Crea el objeto >>>print f.full_name # Acceso a un atributo. Bob Smith
# No recomendable! ?
![Page 55: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/55.jpg)
Petia Ivanova Radeva
Consideremos la siguiente lista de estudiantes
class Student: A class representing a
student. def __init__(self,n,a): self.full_name = n self.age = a def get_name(self): return self.full_name
def get_age(self): return self.age
>>>f = Student( Bob Smith , 23) # Crea el objeto >>>print f.full_name # Acceso a un atributo. Bob Smith
>>>f.get_name() # Acceso a método. ‘Bob Smith’ >>>f.get_age() # Acceso a método. 23
>>> lista=[] >>> lista.append(Student( Bob Smith , 23)) >>> lista.append(Student(“Anna Kournikova”, 25)) …
![Page 56: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/56.jpg)
Petia Ivanova Radeva
Accediendo atributos desconocidos
¿Qué pasa si no sabemos el nombre del atributo o método de una clase que deseamos acceder hasta el tiempo de ejecución ?...
¿Hay una manera de tomar una cadena que contiene el nombre de un atributo o método de una clase y obtener una referencia a él (para que pueda usarlo)?
![Page 57: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/57.jpg)
Petia Ivanova Radeva
getattr(object_instance, string)
>>> f = Student( Bob Smith , 23) >>> getattr(f, full_name ) Bob Smith >>> getattr(f, get_age ) <method get_age of class studentClass at 010B3C2> >>> getattr(f, get_age )() # We can call this. 23 >>> getattr(f, get_birthday ) # Raises AttributeError – No method exists.
![Page 58: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/58.jpg)
Petia Ivanova Radeva
hasattr(object_instance,string)
>>> f = Student( Bob Smith , 23) >>> hasattr(f, full_name ) True >>> hasattr(f, get_age ) True >>> hasattr(f, get_birthday ) False
![Page 59: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/59.jpg)
Petia Ivanova Radeva
Índice Acceso a los atributos y los métodos
Tipos de atributos
Objetos incrustados
Clases mutables y copias
Encapsulamiento
Polimorfismo y sobrecarga
Herencia
Tema 2 POO en Python
8
![Page 60: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/60.jpg)
Petia Ivanova Radeva
Dos tipos de atributos
Los datos (que no son métodos) almacenados en los objetos se denominan atributos. Hay dos tipos:
Atributos de objetos: Variable propiedad de un objeto particular de una clase ◦ Cada instancia puede tener su propio valor diferente para ella, el tipo más
común de atributo. ◦ Ejemplo: Student name -> Ba y Bo ds
Atributos de clases: Propiedad de la clase en su conjunto. ◦ Todas las instancias de la clase comparten el mismo valor para él. ◦ Llamado variables "estáticas" en algunos lenguajes. ◦ Útil para constantes en toda la clase o para la construcción de contador de
cuántas instancias de una clase se han hecho. ◦ Ejemplo: Student edad de selectividad -> 18
![Page 61: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/61.jpg)
Petia Ivanova Radeva
Atributos de datos
Se crean e inicializan los atributo de objetos dentro del método __init __ (). ◦ Recuerde la asignación se utiliza para crear las variables en Python; ◦ así, la asignación de un nombre crea el atributo. (p=Student(..))
Dentro de la clase, los atributos de objetos se obtienen via self: p.e., self.full_name
class Teacher: A class representing teachers. def __init__(self,n): self.full_name = n def print_name(self): print self.full_name
![Page 62: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/62.jpg)
Petia Ivanova Radeva
Atributos de la clase Todas las instancias de una clase comparten una copia de un atributo
de clase, por lo que cuando cualquiera de las instancias lo cambia, entonces el valor se cambia para todos ellos.
Definimos los atributos de clase fuera de cualquier método.
Puesto que es un atributo para toda la clase y no de un objeto: accedemos a través de: self.__class__.name o a través del nombre de la clase.
class Sample: >>> a = Sample() x = 23 >>> a.increment() def increment(self): >>> print a.__class__.x
self.__class__.x += 1 24
Sample.x+=1 >>> print Sample.x
24
![Page 63: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/63.jpg)
Petia Ivanova Radeva
Atributos de objetos vs de la clase
class Counter: overall_total = 0 # class attribute def __init__(self): self.my_total = 0 # data attribute def increment(self): Counter.overall_total = \ Counter.overall_total + 1 self.my_total = \ self.my_total + 1
>>> a = Counter() >>> b = Counter()
>>> Counter.overall_total 0
>>> a.increment() >>> b.increment() >>> b.increment() >>> a.my_total 1 >>> a.__class__.overall_total 3 >>> b.my_total 2 >>> b.__class__.overall_total 3
Útil para constantes en toda la clase o para la construcción de contador de cuántas instancias de una clase se han hecho.
![Page 64: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/64.jpg)
Petia Ivanova Radeva
Índice Acceso a los atributos y los métodos
Tipos de atributos
Objetos incrustados
Clases mutables y copias
Encapsulamiento
Polimorfismo y sobrecarga
Herencia
Tema 2 POO en Python
13
![Page 65: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/65.jpg)
Petia Ivanova Radeva
Objetos incrustados ¿Cómo definir la clase Rectángulo?
◦ A través de un punto, anchura y altura
class Point:
"""represents a point in a plane"”” def __init__(self,x,y):
self.x, self.y=x, y
class Rectangle:
"""represents a rectangle. attr: width, height, corner"””
def __init__(self, width, height, cornerx, cornery):
self.width, self.height=width, height
self.corner=Point(cornerx,cornery)
Df. Un objeto que es un atributo de otro objeto se llama incrustado (embedded).
Tema 2 POO en Python 14
![Page 66: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/66.jpg)
Petia Ivanova Radeva
Objetos incrustados: Instancias de objetos como valores de retorno
# En la clase Rectangle:
def find_center(self):
return Point(self.corner.x + self.width/2.0, self.corner.y + self.height/2.0)
>>> box = Rectangle(100,200,0,0)
>>> center=box.find_center()
>>> print center
(50.0, 100.0)
Tema 2 POO en Python 15
![Page 67: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/67.jpg)
Petia Ivanova Radeva
Objetos incrustados: Instancias de objetos como valores de retorno # En la clase Rectangle:
def find_center(self):
return Point(self.corner.x + self.width/2.0, self.corner.y + self.height/2.0)
>>>a=[]
>>>a.append(Point(10,4))
>>>a.append(center)
Tema 2 POO en Python 16
¿Qué sucede con el objeto que retorna la función find_center()?
![Page 68: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/68.jpg)
Petia Ivanova Radeva
Índice Acceso a los atributos y los métodos
Tipos de atributos
Objetos incrustados
Clases mutables y copias
Encapsulamiento
Polimorfismo y sobrecarga
Herencia
Tema 2 POO en Python
17
![Page 69: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/69.jpg)
Petia Ivanova Radeva
Clases mutables y copias: los objetos son mutables!
¿Qué significa que un objeto es mutable?
Ejemplos?!
class Rectangle:
def grow_rectangle(self, width, height):
#función pura o modificadora?
self.width += width
self.height += height
>>> print box
100 200
>>> box2=box
>>> box2.grow_rectangle(50, 100)
>>> print box
¿Habrán cambiado los valores de los atributos del objeto box?
Tema 2 POO en Python 18
![Page 70: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/70.jpg)
Petia Ivanova Radeva
Clases mutables y copias: los objetos son mutables!
Utilizar el aliasing puede ser confuso, no darnos cuenta de los cambios de valores de los objetos.
¿Cuál sería la alternativa?
>>> box2 = box
>>> print box2 is box
True
>>> print box2==box
True
¿Comprueba la identidad o la equivalencia?
Tema 2 POO en Python 19
>>> import copy >>> box2 = copy.copy(box) >>> print box2 is box False >>> print box2==box False
![Page 71: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/71.jpg)
Petia Ivanova Radeva
Clases mutables y copias: los objetos son mutables!
>>> box2 = copy.copy(box)
>>> box2 is box
False
>>> box2.corner is box.corner
True
copy.copy copia los valores simples, pero no los atributos incrustados! Copia débil (shallow copy)
Tema 2 POO en Python 20
![Page 72: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/72.jpg)
Petia Ivanova Radeva
¿Qué ocurre cuando hacemos box2=copy.copy(box)?
Tema 2 POO en Python 21
![Page 73: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/73.jpg)
Petia Ivanova Radeva
Clases mutables y copias: los objetos son mutables!
>>> box2 = copy.deepcopy(box)
>>> box2 is box
False
>>> box2.corner is box.corner
False
¿Se puede decir que box2 y box son completamente objetos diferentes?
Df. La copia profunda (deep copy) copia recursivamente todos los atributos incrustados.
Tema 2 POO en Python 22
![Page 74: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/74.jpg)
Petia Ivanova Radeva
Índice Acceso a los atributos y los métodos
Tipos de atributos
Objetos incrustados
Clases mutables y copias
Encapsulamiento
Polimorfismo y sobrecarga
Herencia
Tema 2 POO en Python
23
![Page 75: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/75.jpg)
Petia Ivanova Radeva
Datos públicos y privados
class Fraction:
….
Construimos el objeto:
>>>myfraction=Fraction(3,5)
>>>print myfraction.den
# llamamos un dato de la clase
No recomendable! La forma correcta será:
>>>myfraction.imprimir()
# llamamos un método de la clase
Tema 2 POO en Python
24
¿Y ó o pode os p ohi i el a eso a los at i utos?
![Page 76: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/76.jpg)
Petia Ivanova Radeva
Datos públicos y privados
class Fraction:
def __init__(self,top,bottom): # el constructor
self.__num = top # self.__num – dato del objeto self.__den = bottom
Datos privados: de uso sólo por los atributos de la clase (empiezan con el p efijo: __ .
Al llamar desde fuera:
>>> f=Fraction(3,4) #se llama al constructor de la clase.
>>> f.__init__(2,2) #llamada equivalente
Tema 2 POO en Python 25
![Page 77: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/77.jpg)
Petia Ivanova Radeva
Datos públicos y privados class Fraction:
…. def imprimir(self): #método de la clase
print self.__num # datos de la clase
print self.__den
self.__auxiliar() # It’s OK
def __auxiliar(self):
print “This is an auxiliar function”
>> f=Fraction(1,2)
>>print f.__num -> Error!
>>f.__auxiliar() -> Error! Tema 2 POO en Python
26
![Page 78: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/78.jpg)
Petia Ivanova Radeva
Datos públicos y privados class Fraction:
def __show(self):
print self.__num # self.num – # dato del objeto
print self.__den
def test(self):
self.__num=0 #variable de la clase
x=100 #variable local
self.__show()
¿Qué líneas darán error?
>>>f=Fraction()
>>>f.test()
>>>print f.__den
>>>print x
Tema 2 POO en Python
27
![Page 79: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/79.jpg)
Petia Ivanova Radeva
Encapsulamiento
Tema 2 POO en Python 28
– Significa tratar los datos que pertenecen a un objeto de forma prediseñada. – Podemos ir más allá y ocultar los datos de un objeto a cualquier otro objeto o código que trate de hacer uso de ellos. • Serían sólo accesibles al propio objeto y, en algunos
casos, a objetos de sus clases descendientes.
![Page 80: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/80.jpg)
Petia Ivanova Radeva
Encapsulamiento
Tema 2 POO en Python 29
• Hay muchos datos que no tiene porque conocerlo aquel que esté usando la clase; ya que son inherentes al objeto y sólo controlan su funcionamiento interno • cuando alguien nos ve puede saber inmediatamente si eres hombre o mujer
(propiedad) o puede hablarte y obtener una respuesta procesada (metodo); tambien puede conocer el color de tu cabello y ojos.
• pero jamás sabra qué cantidad de energía exacta tienes, o cuántas neuronas te quedan, ni siquiera preguntándote ya que ninguna de tus propiedades externas visibles o funciones de comunicación al publico tienen acceso a esos datos.
El encapsulamiento u ocultación: hacer privadas (ocultas) las variables que son innecesarias para el tratamiento del objeto pero necesarias para su funcionamiento privado
• asi como las funciones que no necesitan interacción del usuario o que sólo pueden ser llamadas por otras funciones del mismo objeto.
![Page 81: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/81.jpg)
Petia Ivanova Radeva
Encapsulamiento
Para proteger a las variables de modificaciones no deseadas se introduce el concepto del encapsulamiento.
Los miembros de una clase se pueden dividir en públicos y privados.
◦ Los miembros públicos se pueden acceder libremente desde fuera de la clase.
◦ Los miembros privados solamente pueden ser accedidos por los métodos de la propia clase.
El acceso a un atributo o a los métodos viene determinado por su nombre. ◦ Si el nombre comienza con dos guiones bajos p.e. self.__denum (y no termina
con dos guiones bajos, p.e. __init__) es un atributo o método privado.
◦ En cualquier otro caso, es público.
Tema 2 POO en Python 30
![Page 82: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/82.jpg)
Petia Ivanova Radeva
Encapsulamiento
Tema 2 POO en Python 31
El encapsulamiento es muy conveniente y nos permite colocar nuestro objeto en funcionamiento en cualquier tipo de sistema, de una manera modular y escalable (algunas de las reglas de la ingenieria del software). Formas de encapsular definiendo los atributos como: 1. Públicos: Hace que el miembro de la clase pueda ser accedido desde el exterior de la Clase y cualquier parte del programa. 2. Privados: Sólo es accesible desde los métodos de la misma Clase. En el encapsulamiento hay analizadores que pueden ser semánticos y sintácticos.
![Page 83: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/83.jpg)
Petia Ivanova Radeva
Encapsulamiento
Tema 2 POO en Python 32
Porción visible: interfaz (protocolo) – Contrato público de comportamiento. – Descripción de operaciones: información de entrada y de salida. Porción oculta: implementación – Estructura de datos para almacenar la información. – Código que se ejecuta para realizar las operaciones.
![Page 84: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/84.jpg)
Petia Ivanova Radeva
Índice Acceso a los atributos y los métodos
Tipos de atributos
Objetos incrustados
Clases mutables y copias
Encapsulamiento
Polimorfismo y sobrecarga
Herencia
Tema 2 POO en Python
33
![Page 85: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/85.jpg)
Petia Ivanova Radeva
Implementación del comportamiento de la clase
>>myf=Fraction(3,5)
>>print myf # print espera una cadena para imprimir
<__main__.Fraction instance at 0x409b1acc>
Solución a):
class Fraction:
……. def show(self):
print self.__num,"/",
self.__den
Tema 2 POO en Python 34
>>myf=Fraction(3,5)
>>print myf
<__main__.Fraction instance at 0x409b1acc>
>>myf.show()
3/5
![Page 86: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/86.jpg)
Petia Ivanova Radeva
Sobrecarga al imprimir objetos
Cuando se hace un print <algo>, no queremos imprimir la referencia del objeto, sino su contenido.
Esto se puede hacer redifiendo el método str dentro de la nueva clase.
Recordamos que str convierte a una representación el forma de cadena cualquier tipo de objeto.
Si una clase ofrece un método llamado __str__, éste se impone al comportamiento de la función interna str de Python.
Tema 2 POO en Python 35
![Page 87: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/87.jpg)
Petia Ivanova Radeva
Métodos estandard en Python class Fraction:
def __str__(self): # por defecto convierte en string el objeto
return str(self.__num)+"/"+str(self.__den)
>>myf=Fraction(3,5)
>>print myf
3/5
>>print “I ate ”, myf, “ of the pizza” I ate 3/5 of the pizza
>>myf.__str__()
‘3/5’ >>str(myf)
‘3/5’
Tema 2 POO en Python 36
![Page 88: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/88.jpg)
Petia Ivanova Radeva
Polimorfismo
Definición: El concepto de polimorfismo (del griego muchas formas) implica que si en una porción de código se invoca un determinado método de un objeto, podrán obtenerse distintos resultados según la clase del objeto.
◦ Esto se debe a que distintos objetos pueden tener un método con un mismo nombre, pero que realice distintas operaciones según el tipo del objeto (p.e. la suma de los flotantes vs. la suma de las fracciones).
Llamamos redefinición a la acción de definir un método con el mismo nombre en distintas clases, de forma tal que provea una interfaz.
Un bloque de código será polimórfico cuando dentro de ese código se realicen llamadas a métodos que puedan estar redefinidos en distintas clases (p.e. __str__).
Tema 2 POO en Python
37
![Page 89: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/89.jpg)
Petia Ivanova Radeva
Polimorfismo y sobrecarga
El término sobrecarga viene de un posible uso de polimorfismo:
◦ En ciertos lenguajes de POO, existe la posibilidad de tener, dentro de una misma clase, dos métodos que se llamen igual pero reciban parámetros de distintos tipos.
◦ En Python al no ser necesario especificar explícitamente el tipo de los parámetros que recibe una función, las funciones son naturalmente polimórficas.
Python, al encontrar un operador, llamará a distintos métodos según el tipo de las variables que se quieran manipular (sumar, restar, multiplicar, etc.).
Tema 2 POO en Python 38
![Page 90: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/90.jpg)
Petia Ivanova Radeva
Sobrecarga de métodos >>f1=Fraction(1,4)
>>f2=Fraction(1,2)
>>f1+f2
Traceback(most recent call last): …TypeError: unsupported operand…
def __add__(self,otherfraction):
newnum = self.__num*otherfraction.__den + \
self.__den*otherfraction.__num
newden = self.__den * otherfraction.__den
return Fraction(newnum,newden)
>>f3=f1+f2 # equivalente a: f3=f1.__add__(f2)
>>print f3
6/8
Tema 2 POO en Python
39
![Page 91: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/91.jpg)
Petia Ivanova Radeva
Comparación de dos objetos
>>f1=Fraction(1,2)
>>f2=Fraction(1,2)
>>f1==f2
False # the “sameness” problem
Es lo mismo decir?:
Mi a to favo ito y su a to favo ito so el is o
Mi pizza y la suya so la is a
Recordatorio: Los objetos de las clases definidas por el usuario son mutables!
Tema 2 POO en Python 40
![Page 92: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/92.jpg)
Petia Ivanova Radeva
Comparación de dos objetos >>f1=Fraction(1,2)
>>f2=Fraction(1,2)
>>f3=f1
>>f3==f1
True
Tema 2 POO en Python 41
def __cmp__(self,otherfraction):
num1 = self.__num*otherfraction.__den
num2 = self.__den*otherfraction.__num
if num1 < num2:
return -1
else:
if num1 == num2:
return 0
else:
return 1
![Page 93: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/93.jpg)
Petia Ivanova Radeva
La clase completa Fraction
class Fraction:
def __init__(self,top,bottom):
self.__num = top
self.__den = bottom
def __str__(self):
return str(self.__num)
+"/"+str(self.__den)
def show(self):
print self.__num,"/",self.__den
Tema 2 POO en Python 42
def __add__(self,otherfraction):
newnum =self.__num*otherfraction.__den + \ self.__den*otherfraction.__num
newden = self.__den*otherfraction.__den
com = gcd(newnum,newden)
return Fraction(newnum/com,newden/com)
def __cmp__(self,otherfraction):
num1 = self.__num*otherfraction.__den
num2 = self.__den*otherfraction.__num
if num1 < num2:
return -1
else:
if num1 == num2:
return 0
else: return 1
¿En qué se expresa el polimorfismo y el encapsulamiento en esta implementación?
![Page 94: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/94.jpg)
Petia Ivanova Radeva
Sobrecarga de operadores
La sobrecarga de operadores permite redefinir ciertos operadores, como + o - , para usarlos con las clases que hemos definido.
Se llama sobrecarga de operadores porque estamos reutilizando el mismo oeprador con un número de usos diferentes.
El compilador decide cómo usar este operador dependiendo sobre qué objetos opera.
Tema 2 POO en Python 43
![Page 95: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/95.jpg)
Petia Ivanova Radeva
¿Qué operadores sobrecargar?
Las clases contienen muchos métodos y atributos que se incluyen de Python incluso si no se definen explícitamente.
La mayoría de estos métodos definen la funcionalidad automática provocada por los operadores o el uso de la clase especial.
Los atributos incorporados definen la información que deben ser almacenados para todas las clases.
Todos los miembros integrados tienen dobles guiones bajos alrededor de sus nombres:__init__ __doc__
![Page 96: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/96.jpg)
Petia Ivanova Radeva
Métodos especiales Por ejemplo, existe el método __repr__ para todas las clases, y
siempre se puede redefinir. ◦ La definición de este método especifica cómo convertir una instancia de la clase en
una cadena.
Si escribimos f en la línea de comandos, estamos llamando __repr__.
class Student: ... def __repr__(self): return I’m named + self.__full_name
# Note: we changed the full_name to __full_name …
>>> f = Student( Bob Smith , 23)
>>> f I’m named Bob Smith
![Page 97: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/97.jpg)
Petia Ivanova Radeva
Métodos especiales
Podemos sobrecargar: __init__ : El constructor de la clase.
__cmp__ : Define como aplicar == para la clase.
__len__ : Define len( obj ).
__copy__ : Define cómo copiar un objeto de la clase.
__getitem__ : Define el operador [].
__doc__ : Variable que guarda la documentación de la clase.
>>> f = Student( Bob Smith , 23) >>> print f.__doc__ A class representing a student.
Consultar qué otros métodos se pueden sobrecargar!
![Page 98: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/98.jpg)
Petia Ivanova Radeva
Sobrecarga de los métodos de los operadores
__add__(self, other) # operación de suma
__sub__(self, other) # operación de resta
__mul__(self, other) # operación de multiplicación
__floordiv__(self, other) # operación de división redondeo
__mod__(self, other) # operación de modulo
__divmod__(self, other) # operación de división
__pow__(self, other) # operación de potencia
__and__(self, other) # operación de and
__or__(self, other) # operación de or
__xor__(self, other) # operación de xor
Tema 2 POO en Python 47
![Page 99: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/99.jpg)
Petia Ivanova Radeva
Índice Acceso a los atributos y los métodos
Tipos de atributos
Objetos incrustados
Clases mutables y copias
Encapsulamiento
Polimorfismo y sobrecarga
Herencia
Tema 2 POO en Python
48
![Page 100: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/100.jpg)
Petia Ivanova Radeva
Subclases
Una clase puede extender la definición de otra clase con el fin de utilizar (o reaprovechar) métodos y atributos ya definidos en la anterior. ◦ Llamamos la nueva clase: "subclase o clase derivada . ◦ La clase original es: clase base" o "ancestro".
Al definir una subclase, se pone el nombre de la clase base en
paréntesis después del nombre de la subclase en la primera línea de la definición.
class AI_Student(Student):
![Page 101: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/101.jpg)
Petia Ivanova Radeva
Derivative
__qq f2()
getqq()
Ejercicio class Main:
def __init__(self,p):
self._pp=p
def f(self):
print self._pp
def getpp(self):
return self._pp
class Derivative (Main):
def __init__(self,p,q):
Main.__init__(self,p)
self.__qq=q
def f2(self):
print self.__qq,self._pp
def getqq(self):
return self.__qq
Tema 2 POO en Python
50
Main _pp f()
getpp()
>>>o1=Main(3)
>>>o2=Derivative(5,4)
>>>print o2.getpp(),o2.getqq()
>>>o2.f()
>>>o2.f2()
![Page 102: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/102.jpg)
Petia Ivanova Radeva
Definición de la clase Student
class Student: “””A class representing a student.”””
def __init__(self,n,a): self.__full_name = n self.__age = a
def get_age(self): print "Student age: "+str(self.__age) return self.__age def get_name(self): return self.__full_name >>>p=Student("John", 24) >>>print p.get_name() John >>>p.get_age() Student age: 24
![Page 103: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/103.jpg)
Petia Ivanova Radeva
Definición de la clase AI_Student class AI_Student (Student):
‘’’A class extending student.’’’ def __init__(self,n,a,s): Student.__init__(self,n,a) self.__section_num = s def get_age(self): # es obligatoria?
print AI Student age: +str(self.__age)
return self.__age
>>>s=AI_Student("Ann", 34, 23)
>>>print s.get_name()
Ann
>>>s.get_age()
AI Student age: 34
![Page 104: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/104.jpg)
Petia Ivanova Radeva
Redefinición de los métodos
Cuando creamos una clase derivada a partir de una clase base y tenemos que la clase derivada proporciona o requiere su propio método __init__, este método de la clase derivada debe llamar explícitamente el método __init__ de la clase base
Lo interesante de la herencia es que las clases derivadas pueden definir métodos propios, y también redefinir métodos que sí existen en la clase base ◦ Si quieremos que la clase derivada redefina un método de la clase base (para que haga algo
diferente), podemos simplemente escribir una nueva definición para el nombre de este método en la subclase.
◦ El código anterior no quede ejecutado.
◦ Si deseamos que el viejo código se ejecutara, además del nuevo código del método, debemos llamarlo explícitamente con el nombre de la clase base:
parentClass.methodName(self, a, b, c)
![Page 105: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/105.jpg)
Petia Ivanova Radeva
Propiedades de la herencia
Evita repeticiones de código.
Facilita el reuso de código.
Código compacto y claro.
A veces los datos pueden quedar demasiado escondidos.
Tema 2 POO en Python 54
La herencia es la posibilidad de definir una clase como especificación de otra (relación is_a). • ¿Cómo implementar la relación has_a?
![Page 106: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/106.jpg)
Petia Ivanova Radeva
Herencia
La herencia nos permite crear nuevas clases a partir de clases ya existentes, convervando las propiedades de la clase original y añadiendo otras nuevas.
Además, las clases derivadas pueden ser base de otras clases derivadas.
◦ Se pueden montar jerarquías de clases.
En la herencia, las clases derivadas heredan todos los métodos y atributos de la clase base.
◦ La visibilidad de los métodos de las clases bases depende de la repetición de los
nombres.
Tema 2 POO en Python
55
![Page 107: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/107.jpg)
Petia Ivanova Radeva
Definimos una herencia simple
class Instrumento:
#Clase Base
pass
class Guitarra(Instrumento):
#Clase Derivada
pass
class Bajo(Instrumento):
#Clase Derivada
pass
Tema 2 POO en Python 56
![Page 108: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/108.jpg)
Petia Ivanova Radeva
Ejemplo
class Instrumento:
def __init__(self, precio):
self.__precio = precio
def tocar (self):
print "Estamos tocando musica” def romper (self):
print "Esto lo pagas tu"
print "Son”,self.__precio,” euros ” class Guitarra (Instrumento):
def __init__ (self, cuerdas, precio):
Instrumento.__init__(self, precio)
self.__cuerdas = cuerdas
def tocar(self):
print "Estamos tocando la
guitarra de ", self.__cuerdas,
" cuerdas"
Tema 2 POO en Python 57
def main():
instru = Instrumento(20)
guitar = Guitarra(5, 100)
instru.romper()
guitar.romper()
instru.tocar()
guitar.tocar()
main()
![Page 109: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/109.jpg)
Petia Ivanova Radeva
Ejemplo – redifinición de métodos
class Instrumento:
def __init__(self, precio):
self.__precio = precio
def tocar (self):
print "Estamos tocando musica” def romper (self):
print "Esto lo pagas tu"
print "Son”,self.__precio,” euros ” class Guitarra (Instrumento):
def __init__ (self, cuerdas, precio):
Instrumento.__init__(self,
precio)
self.__cuerdas = cuerdas
def tocar(self):
print "Estamos tocando la
guitarra de ", self.__cuerdas,
" cuerdas"
Tema 2 POO en Python 58
def main():
instru = Instrumento(20)
guitar = Guitarra(5, 100)
instru.romper()
guitar.romper()
instru.tocar()
guitar.tocar()
main()
![Page 110: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/110.jpg)
Petia Ivanova Radeva
Conclusiones
La forma correcta para acceder a los valores de las clases es a través de funciones getValor() y setValor(). ◦ Por defecto, intentar definir los métodos como métodos puros.
Se pueden incrustar objetos dentro de objetos.
Las clases son tipos de datos mutables ◦ Una solución es copiar los objetos usando la copia simple o la copia profunda.
La encapsulación de los datos y los métodos es un proceso de organizarlos en clases donde se separa la interfaz de la clase de la implementación de sus métodos
Se pueden sobrecargar métodos implementados.
El polimorfismo es la capacidad de definir operaciones básicas de los tipos (métodos de las clases) que tiene el mismo objetivo aunque puedan tener diferente implementación.
Las clases se pueden organizar en jerarquías. Las jerarquias permiten realizar herencia de métodos y datos de las clases bases por las clases derivadas
◦ Es una forma muy eficiente de reaprovechar el código, escribir de forma compacta y concisa y minimizar los errores.
Tema 2 POO en Python
59
![Page 111: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/111.jpg)
Petia Ivanova Radeva
Material adicional
Tema 2 POO en Python 60
![Page 112: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/112.jpg)
Petia Ivanova Radeva
Ejemplo 1: Juego de Poker ◦ Tenemos: Suit (palo): Espadas, Corazones, Diamantes, y
Tréboles,
◦ Rank (número): As, 2, 3, 4, 5, 6, 7, 8, 9, 10, comodí, reina, y el rey
◦ Consideramos : “pades →
Hea ts →
Dia o ds →
Clu s → 0
class Card:
"""represents a standard playing card."""
def __init__(self, suit=0, rank=2):
self._suit = suit
self._rank = rank
Tema 2 POO en Python 61
Jack 7→ 11 Queen 7→ 12 King 7→ 13
![Page 113: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/113.jpg)
Petia Ivanova Radeva
Atributos de la clase
# inside class Card:
_suit_names = ['Clubs', 'Diamonds', 'Hearts', 'Spades']
_rank_names = [None, 'Ace', '2', '3', '4', '5', '6', ' ‘,' ', '9', '10', 'Jack', 'Queen', 'King']
def __str__(self):
return '%s of %s' % (Card._rank_names[self._rank],
Card._suit_names[self._suit])
>>> card1 = Card(2, 11)
>>> print card1
Jack of Hearts
Tema 2 POO en Python 62
![Page 114: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/114.jpg)
Petia Ivanova Radeva
Comparar las cartas
Tema 2 POO en Python 63
La clase Card y una instancia
Podemos sobrecargar el operador __comp__() para comparar las cartas: toma dos parámetros – self y uno más y retorna -1, 0, o 1 si el primero es más pequeño, igual o más grande que el segundo. Consideremos un ranking de los palos (p.e. Espadas, Corazones, Diamantes, y Tréboles): # inside class Card: def __cmp__(self, other):
# check the suits if self._suit > other.getSuit(): return 1 if self._suit < other.getSuit(): return -1 # suits are the same... check ranks if self._rank > other.getRank(): return 1 if self._rank < other.getRank(): return -1 # ranks are the same... it's a tie return 0
![Page 115: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/115.jpg)
Petia Ivanova Radeva
El juego de cartas
# inside class Card:
# implementación compacta
def __cmp__(self, other):
t1 = self._suit, self._rank
t2 = other.getSuit(), other.getRank()
return cmp(t1, t2)
Utilizamos la definición preimplementada del operador cmp!
Tema 2 POO en Python 64
![Page 116: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/116.jpg)
Petia Ivanova Radeva
Baraja
class Deck(object):
def __init__(self):
self._cards = []
for suit in range(4):
for rank in range(1, 14):
card = Card(suit, rank)
self._cards.append(card)
Tema 2 POO en Python 65
![Page 117: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/117.jpg)
Petia Ivanova Radeva
Imprimiendo la baraja
#inside class Deck:
def __str__(self):
res = []
for card in self._cards:
res.append(str(card))
return '\n'.join(res)
Tema 2 POO en Python 66
>>> deck = Deck() >>> print deck Ace of Clubs 2 of Clubs 3 of Clubs ... 10 of Spades Jack of Spades Queen of Spades King of Spades
![Page 118: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/118.jpg)
Petia Ivanova Radeva
Jugando con las cartas
Necesitamos una función para sacar y añadir carta a la barraja
#inside class Deck:
def pop_card(self):
return self._cards.pop()
#inside class Deck:
def add_card(self, card):
self._cards.append(card)
# inside class Deck:
def shuffle(self):
random.shuffle(self._cards)
Tema 2 POO en Python 67
![Page 119: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/119.jpg)
Petia Ivanova Radeva
La herencia en el caso de las cartas ◦ Las cartas de un jugador tienen mucho en común con la baraja entera:
basados en un conjunto de cartas que se pueden manipular: sacar, añadir cartas.
◦ Además puede tener sus propias operaciones – comparar, calcular la puntuación, etc.
La herencia es la posibilidad de definir una clase como especificación de otra (relación is_a): ◦ Clase base
◦ Clase derivada
class Hand (Deck):
def __init__(self, label=''):
self._cards, self._label = [], label
Tema 2 POO en Python 68
![Page 120: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/120.jpg)
Petia Ivanova Radeva
Las clases (casi)completas
class Card(object): """represents a standard playing card.""“ def __init__(self, suit=0, rank=2): self._suit, self._rank = suit, rank self._suit_names = ['Clubs', 'Diamonds', Hearts', 'Spades'] self._rank_names = [None, 'Ace', ' ', ' ', ' ', ' ', ' ', ' ‘,' ', ' ', ' ',\ 'Jack', 'Queen', 'King'] def __str__(self): return '%s of %s' %\ (self._rank_names[self._rank], self._suit_names[self._suit]) def __cmp__(self, other): t1 = self._suit, self._rank t2 = other.getSuit(), other.getRank() return cmp(t1, t2)
![Page 121: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/121.jpg)
Petia Ivanova Radeva
Las clases (casi)completas class Deck(object):
def __init__(self):
self._cards = []
for suit in range(4):
for rank in range(1, 14):
card = Card(suit, rank)
self._cards.append(card)
def __str__(self):
res = []
for card in self._cards:
res.append(str(card))
return '\n'.join(res)
def pop_card(self):
return self._cards.pop()
def add_card(self, card):
self._cards.append(card)
def shuffle(self):
random.shuffle(self._cards)
def len(self):
return len(self._cards)
class Hand(object):
def __init__(self, label=''):
self._cards = []
self._label = label
def __str__(self):
res = []
for card in self._cards:
res.append(str(card))
return '\n'.join(res)
def pop_card(self):
return self._cards.pop()
def add_card(self, card):
self._cards.append(card)
def len(self):
return len(self._cards)
![Page 122: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/122.jpg)
Petia Ivanova Radeva
Las clases (casi)completas
class Deck(object):
def __init__(self):
self._cards = []
for suit in range(4):
for rank in range(1, 14):
card = Card(suit, rank)
self._cards.append(card)
def __str__(self):
res = []
for card in self._cards:
res.append(str(card))
return '\n'.join(res)
def pop_card(self):
return self._cards.pop()
def add_card(self, card):
self._cards.append(card)
def shuffle(self):
random.shuffle(self._cards)
def len(self):
return len(self._cards)
class Hand(Deck):
def __init__(self, label=''):
self._cards = []
self._label = label
IS-A HAS-A
![Page 123: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/123.jpg)
Petia Ivanova Radeva
Las clases (casi)completas
class Card(object):
"""represents a standard playing card.""“
def __init__(self, suit=0, rank=2):
self._suit = suit
self._rank = rank
def __str__(self): ...
def __cmp__(self, other):...
class Deck(object):
def __init__(self):
self._cards = ...
def __str__(self):...
def pop_card(self):....
def add_card(self, card): ...
def shuffle(self): ...
class Hand(Deck):
def __init__(self, label=''):
self._cards = ...
self._label = ...
>>>h=Hand()
>>> deck = Deck()
>>> c1=Card()
>>> card1 = Card(2, 11)
>>> print card1
Jack of Hearts
>>> hand = Hand('new hand')
>>> print hand.cards
[]
>>> print hand.label
new hand
>>> deck = Deck()
Los otros métodos se heredan de la clase Deck así que podemos utilizar pop_card y add_card:
>>> card = deck.pop_card()
>>> hand.add_card(card)
>>> print hand
King of Spades
![Page 124: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/124.jpg)
Petia Ivanova Radeva
Jugar
¿En qué clase pondrías el siguiente
método? def move_cards(self, hand, num):
for i in range(num):
hand.add_card(self.pop_card())
Tema 2 POO en Python 73
IS-A
HAS-A
![Page 125: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/125.jpg)
Petia Ivanova Radeva
El juego
Implementar un juego que:
1. Mezcla las cartas y las reparte entre 2 jugadores.
2. Se juega hasta que alguno de los jugadores se quede sin cartas.
3. A cada iteración, cada uno saca una carta. ◦ Si la carta del primero es más grande, el segundo se lleva las dos
cartas y viceversa.
4. El ganador es el que primero se quede sin cartas.
Tema 2 POO en Python 74
![Page 126: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/126.jpg)
Petia Ivanova Radeva
El juego
# Crear la baraja y mezclar las cartas
deck=Deck()
deck.shuffle()
#Declarar los dos jugadores
hand1=Hand()
hand2=Hand()
#repartir todas las cartas
for i in range(26):
hand1.add_card(deck.pop_card())
hand2.add_card(deck.pop_card())
print deck.len()
Tema 2 POO en Python 75
#jugar
while(hand1.len()>0 and hand2.len()>0):
card1=hand1.pop_card()
card2=hand2.pop_card()
if card1<card2:
hand1.add_card(card1)
hand1.add_card(card2)
else:
hand2.add_card(card1)
hand2.add_card(card2)
print hand1.len()
print hand2.len()
#determinar el ganador
if (hand1.len()>0):
print "The winner is: Hand1"
else: print "The winner is: Hand2"
![Page 127: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/127.jpg)
Petia Ivanova Radeva
Ejemplo 2: Implementar un juego para tirar dados (Material adicional)
Implementar un juego que consiste en tirar dos dados:
Definimos la clase MSDie: 1. ¿Cuántas caras tiene?
2. ¿Cuál es su valor actual?
¿Dónde han de estar estos valores y cuándo se han de crear?
Definiremos los métodos: a) roll() b) setValue(), c) getValue().
![Page 128: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/128.jpg)
Petia Ivanova Radeva
Ejemplo >>> die1 = MSDie(6) #definimos un dado de 6 puntos >>> die1.getValue() 1 >>> die1.roll() >>> die1.getValue() 4 >>> die2 = MSDie(13) #definimos un dado de 13 puntos >>> die2.getValue() 1 >>> die2.roll() >>> die2.getValue() 12 >>> die2.setValue(8) >>> die2.getValue() 8
![Page 129: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/129.jpg)
Petia Ivanova Radeva
¿Cómo implementamos la clase MSDie? # msdie.py # Class definition for an n-sided die. from random import randrange class MSDie:
def __init__(self, sides): self.sides = sides self.value = 1
def roll(self): self.value = randrange(1,self.sides+1)
def getValue(self): return self.value def setValue(self, value): self.value = value
![Page 130: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/130.jpg)
Petia Ivanova Radeva
¿Cómo implementamos la clase MSDie?
class MSDie:
...
def setValue(self,value):
self.value = value
def main(): die1 = MSDie(12)
die1.setValue(8)
print die1.getValue()
<self=die1; self.value=8>
![Page 131: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/131.jpg)
Petia Ivanova Radeva
Definir los objetos gráficos necesarios para dibujar la interfaz del juego
Puntos
Rectángulos (dados, botones)
…. Cuadrados, rombos, romboides
Polígonos
Círculos
Formas ovales
Lineas
…
Textos
Imágenes
Tema 2 POO en Python 80
![Page 132: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/132.jpg)
Petia Ivanova Radeva
Jerarquía de los objetos/clases gráficos
Tema 2 POO en Python 81
Punto
Línea Rectángulo
Forma Oval
Círculo
BoundingBox
Texto
Imagen
ObjetoGráfico
Herencia – la posibilidad de una clase de recibir sus métodos y datos de otras clases
![Page 133: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/133.jpg)
Petia Ivanova Radeva
La clase genérica GraphicsObject class GraphicsObject:
"""Generic base class for all of the drawable objects"""
def __init__(self, options):
# options is a list of strings indicating which
# options are legal for this object.
def setFill(self, color):
"""Set interior color to color"""
def setOutline(self, color):
"""“et outli e olo to olo ""
def setWidth(self, width):
"""Set line weight to width"""
def draw(self, graphwin):
"""Draw the object in graphwin, which should be a GraphWin object """
Tema 2 POO en Python 82
def undraw(self): """Undraw the object (i.e. hide it). Returns silently if the object is not currently drawn.""" def move(self, dx, dy): """move object dx units in x direction and dy units in y direction""" def _draw(self, canvas, options): """draws appropriate figure on canvas with options provided Returns Tk id of item drawn""" # must override in subclass def _move(self, dx, dy): """updates internal state of object to move it dx,dy units""" # must override in subclass
![Page 134: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/134.jpg)
Petia Ivanova Radeva
La clase Punto
Tema 2 POO en Python 83
class Point(GraphicsObject): def __init__(self, x, y): GraphicsObject.__init__(self, ["outline", "fill"]) self.setFill = self.setOutline self.x = x self.y = y def _draw(self, canvas, options): x,y = canvas.toScreen(self.x,self.y) return \ canvas.create_rectangle(x,y,x+1,y+1,options)
def _move(self, dx, dy): self.x = self.x + dx self.y = self.y + dy def clone(self): other = Point(self.x,self.y) other.config = self.config.copy() return other def getX(self): return self.x def getY(self): return self.y
![Page 135: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/135.jpg)
Petia Ivanova Radeva
La clase BoundingBox class _BBox(GraphicsObject):
# Internal base class for objects represented by bounding box
# (opposite corners) Line segment is a degenerate case.
def __init__(self, p1, p2, options=["outline","width","fill"]):
def _move(self, dx, dy):
def getP1(self):
def getP2(self):
def getCenter(self):
Tema 2 POO en Python
84
![Page 136: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/136.jpg)
Petia Ivanova Radeva
La clase Rectángulo
class Rectangle(_BBox):
def __init__(self, p1, p2):
def _draw(self, canvas, options):
def clone(self):
Tema 2 POO en Python 85
![Page 137: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/137.jpg)
Petia Ivanova Radeva
La clase Figura Oval
class Oval(_BBox):
def __init__(self, p1, p2):
def clone(self):
def _draw(self, canvas, options):
Tema 2 POO en Python 86
![Page 138: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/138.jpg)
Petia Ivanova Radeva
La clase Círculo
class Circle(Oval):
def __init__(self, center, radius):
def clone(self):
def getRadius(self):
Tema 2 POO en Python 87
![Page 139: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/139.jpg)
Petia Ivanova Radeva
Constructor
myCircle = Circle(Point(0,0), 20) # se llama al constructor
class Circle(Oval):
def __init__(self, center, radius):
p1 = Point(center.x-radius, center.y-radius)
p2 = Point(center.x+radius, center.y+radius)
Oval.__init__(self, p1, p2)
self.radius = radius
![Page 140: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/140.jpg)
Petia Ivanova Radeva
La clase Línea
class Line(_BBox):
def __init__(self, p1, p2):
def clone(self):
def _draw(self, canvas, options):
def setArrow(self, option):
Tema 2 POO en Python 89
![Page 141: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/141.jpg)
Petia Ivanova Radeva
La clase Polígono
class Polygon(GraphicsObject):
def __init__(self, *points):
# if points passed as a list, extract it
def clone(self):
def getPoints(self):
def _move(self, dx, dy):
def _draw(self, canvas, options):
Tema 2 POO en Python
90
![Page 142: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/142.jpg)
Petia Ivanova Radeva
La clase Imagen class Image(GraphicsObject):
def __init__(self, p, pixmap):
def _draw(self, canvas, options):
def _move(self, dx, dy):
def undraw(self):
def getAnchor(self):
def clone(self):
Tema 2 POO en Python
91
![Page 143: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/143.jpg)
Petia Ivanova Radeva
La clase Texto
class Text(GraphicsObject):
def __init__(self, p, text):
def _draw(self, canvas, options):
def _move(self, dx, dy):
def clone(self):
def setText(self,text):
Tema 2 POO en Python
92
def getText(self): def getAnchor(self): def setFace(self, face): def setSize(self, size): def setStyle(self, style): def setTextColor(self, color):
![Page 144: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/144.jpg)
Petia Ivanova Radeva
Uso from graphics import *
win = GraphWin()
win.setCoords(0,0,10,10)
p=Point(3,4)
p.draw(win)
win = GraphWin()
win.setCoords(0,0,10,10)
t = Text(Point(5,5), "Centered Text")
t.draw(win)
p = Polygon(Point(1,1), Point(5,3), Point(2,7))
p.draw(win)
e = Entry(Point(5,6), 10)
e.draw(win)
win.getMouse()
p.setFill("red")
p.setOutline("blue")
p.setWidth(2)
s = "
for pt in p.getPoints():
s = s + "(%0.1f,%0.1f) " % (pt.getX(), pt.getY())
Tema 2 POO en Python
93
![Page 145: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/145.jpg)
Petia Ivanova Radeva
Métodos públicos y privados
Tema 2 POO en Python 94
t.setText(e.getText()) e.setFill("green") e.setText("Spam!") e.move(2,0) win.getMouse() p.move(2,3) s = "" for pt in p.getPoints(): s = s + "(%0.1f,%0.1f) " %\ (pt.getX(), pt.getY()) t.setText(s) win.getMouse() p.undraw() e.undraw() t.setStyle("bold") win.getMouse() t.setStyle("normal") win.getMouse() t.setStyle("italic") win.getMouse() t.setStyle("bold italic") win.getMouse() t.setSize(14) win.getMouse() t.setFace("arial") t.setSize(20) win.getMouse() win.close()
![Page 146: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/146.jpg)
Petia Ivanova Radeva
Ejercicio sobre POO en Python: I ple e tar la aplicació Dice Roller segú las or as:
Al iniciar la roleta se tiran los dados y se visualiza la puntuación obtenida
Cada vez ue se haga u li k so e el otó Roll Di e se vuelven a tirar los dados y se actualiza la visualización de los dados
Al ap eta el otó Quit se ie a la aplicación
Tema 2 POO en Python 95
![Page 147: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/147.jpg)
Petia Ivanova Radeva
Usando widgets
La clase botón
Métodos de la clase botón ◦ constructor
◦ activate
◦ deactivate
◦ clicked
◦ getLabel
def activate(self): "Sets this button to ’active’." self.label.setFill(’black’) self.rect.setWidth(2) self.active = 1
![Page 148: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/148.jpg)
Petia Ivanova Radeva
La clase botón
def deactivate(self): "“ets this utto to ’i a tive’."
self.la el.setFill ’da kg ey’
self.rect.setWidth(1)
self.active = 0
![Page 149: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/149.jpg)
Petia Ivanova Radeva
La clase botón
def clicked(self, p): "RETURNS true if button is active and p is inside"
return self.active and \
self.xmin <= p.getX() <= self.xmax and \
self.ymin <= p.getY() <= self.ymax
pt = win.getMouse() if button1.clicked(pt): # Do button1 stuff elif button2.clicked(pt): # Do button2 stuff elif button3.clicked(pt) # Do button3 stuff ...
![Page 150: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/150.jpg)
Petia Ivanova Radeva
La clase botón # Button.py from graphics import * class Button: """A button is a labeled rectangle in a window. It is activated or deactivated with the activate() and deactivate() methods. The clicked(p) method returns true if the button is active and p is inside it.""" def __init__(self, win, center, width, height, label):
""" Creates a rectangular button, eg: qb = Button(myWin, Point(30,25), 20, 10, 'Quit') """ w,h = width/2.0, height/2.0 x,y = center.getX(), center.getY() self.xmax, self.xmin = x+w, x-w self.ymax, self.ymin = y+h, y-h p1 = Point(self.xmin, self.ymin) p2 = Point(self.xmax, self.ymax) self.rect = Rectangle(p1,p2) self.rect.setFill('lightgray') self.rect.draw(win) self.label = Text(center, label) self.label.draw(win) self.deactivate()
def clicked(self, p): "RETURNS true if button active and p is inside" return self.active and \ self.xmin <= p.getX() <= self.xmax and \ self.ymin <= p.getY() <= self.ymax def getLabel(self): """RETURNS the label string of this button.""" return self.label.getText() def activate(self): """Sets this button to 'active'.""" self.label.setFill('black') self.rect.setWidth(2) self.active = 1 def deactivate(self): """Sets this button to 'inactive'.""" self.label.setFill('darkgrey') self.rect.setWidth(1) self.active = 0
![Page 151: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/151.jpg)
Petia Ivanova Radeva
La clase DieView y sus métodos
Constructor
setValue()
__makePip(self, x, y) – dibujar un punto ◦ Función privada!
La encapsulación de los datos y los métodos es un proceso de organizarlos en
clases donde se separa la interfaz de la clase de la implementación de sus métodos
![Page 152: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/152.jpg)
Petia Ivanova Radeva
La clase DieView class DieView: """ DieView is a widget that displays a graphical
representation of a standard six-sided die."" def __init__(self, win, center, size): """Create a view of a die, e.g.: d1 = GDie(myWin, Point(40,50), 20) creates a die centered at (40,50) having sides of length 20.""" # first define some standard values self.win = win # save this for drawing pips later self.background = "white" # color of die face self.foreground = "black" # color of the pips self.psize = 0.1 * size # radius of each pip hsize = size / 2.0 # half the size of the die offset = 0.6 * hsize # distance from center to
outer pips
# create a square for the face cx, cy = center.getX(), center.getY() p1 = Point(cx-hsize, cy-hsize) p2 = Point(cx+hsize, cy+hsize) rect = Rectangle(p1,p2) rect.draw(win) rect.setFill(self.background) # Create 7 circles for standard pip locations self.pip1 = self.__makePip(cx-offset, cy-offset) self.pip2 = self.__makePip(cx-offset, cy) self.pip3 = self.__makePip(cx-offset, cy+offset) self.pip4 = self.__makePip(cx, cy) self.pip5 = self.__makePip(cx+offset, cy-offset) self.pip6 = self.__makePip(cx+offset, cy) self.pip7 = self.__makePip(cx+offset, cy+offset) # Draw an initial value self.setValue(1)
![Page 153: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/153.jpg)
Petia Ivanova Radeva
La función __makePip() def __makePip(self, x, y): "Internal helper method to draw a pip at (x,y)" pip = Circle(Point(x,y), self.psize) pip.setFill(self.background) pip.setOutline(self.background) pip.draw(self.win) return pip def setValue(self, value): "Set this die to display value." # turn all pips off self.pip1.setFill(self.background) self.pip2.setFill(self.background) self.pip3.setFill(self.background) self.pip4.setFill(self.background) self.pip5.setFill(self.background) self.pip6.setFill(self.background) self.pip7.setFill(self.background) # turn correct pips on if value == 1: self.pip4.setFill(self.foreground) elif value == 2: self.pip1.setFill(self.foreground) self.pip7.setFill(self.foreground)
elif value == 3: self.pip1.setFill(self.foreground) self.pip7.setFill(self.foreground) self.pip4.setFill(self.foreground) elif value == 4: self.pip1.setFill(self.foreground) self.pip3.setFill(self.foreground) self.pip5.setFill(self.foreground) self.pip7.setFill(self.foreground) elif value == 5: self.pip1.setFill(self.foreground) self.pip3.setFill(self.foreground) self.pip4.setFill(self.foreground) self.pip5.setFill(self.foreground) self.pip7.setFill(self.foreground) else: self.pip1.setFill(self.foreground) self.pip2.setFill(self.foreground) self.pip3.setFill(self.foreground) self.pip5.setFill(self.foreground) self.pip6.setFill(self.foreground) self.pip7.setFill(self.foreground)
![Page 154: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/154.jpg)
Petia Ivanova Radeva
La aplicación final # roller.py # Graphics program to roll a pair of dice. Uses custom
widgets Button and DieView. from random import randrange from graphics import GraphWin, Point, Rectangle from button import Button from dieview import DieView def main(): # create the application window win = GraphWin("Dice Roller") win.setCoords(0, 0, 10, 10) win.setBackground("green2") # Draw the interface widgets die1 = DieView(win, Point(3,7), 2) die2 = DieView(win, Point(7,7), 2) rollButton = Button(win, Point(5,4.5), 6, 1, "Roll
Dice") rollButton.activate() quitButton = Button(win, Point(5,1), 2, 1, "Quit") # Event loop pt = win.getMouse()
while not quitButton.clicked(pt): if rollButton.clicked(pt): value1 = randrange(1,7) die1.setValue(value1) value2 = randrange(1,7) die2.setValue(value2) quitButton.activate() pt = win.getMouse() # close up shop win.close() main()
![Page 155: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/155.jpg)
Estructuras de datos básicas
Tema 5
Tema 3 Pilas y Colas
1
Book: “Problem Solving with Algorithms and Data Structures”
![Page 156: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/156.jpg)
Petia Ivanova Radeva
Objetivos
Entender la lógica de las estructuras básicas: pila, cola, cola de prioridad y deque.
Ser capaces de implementar los tipos de datos abstractos pila, cola, cola de
prioridad y deque.
Considerar ejemplos de uso de las pilas, colas, colas de prioridad y deques.
Ser capaz de reconocer las propiedades de los problemas, donde son apropiadas
las pilas, colas, cola de prioridad y deques.
Pilas y Colas 2
Tema 3
![Page 157: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/157.jpg)
Petia Ivanova Radeva
¿Qué son las estructuras lineales?
Estructuras lineales – estructuras con orden (el elemento
antes y después e.d. estructuras con dos extremos donde se
añaden y borran los elementos).
◦ Top y bottom, inicio y fin.
◦ Tres tipos:
Pila
Cola y colas de prioridad
Deque
Tema 3 Pilas y Colas 3
![Page 158: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/158.jpg)
Petia Ivanova Radeva
Pilas
Definición – una pila es una secuencia de objetos
ordenados donde los objetos se añaden y borran del
mismo extremo ( top ).
◦ El otro extremo se llama bottom .
Es una estructura lineal, una colección secuencial.
Last In First Out (LIFO)
Ejemplos
◦ La pila de objetos en Python
◦ El botón Back del web browser
◦ El comando undo
Tema 3 Pilas y Colas 4
![Page 159: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/159.jpg)
Petia Ivanova Radeva
Pilas
En una pila no sabemos dónde estan los elementos.
◦ La indexación no es posible/eficiente.
◦ Pero sí cuáles han sido introducidos los últimos.
◦ Los elementos no estan físicamente juntos -> apropiada para grandes volúmenes de datos
◦ La pila se expande automáticamente.
La única manera de eliminar los datos de una pila es desde su parte
superior.
◦ Cada vez que retire los datos, la pila se reduce automáticamente.
Pocos lenguajes de programación ofrecen la estructura de datos de la pila
como una estructura preimplementada.
◦ La hemos de crear utilizando otras estructuras de datos, p.e. como una matriz.
◦ La nueva estructura de datos creada es una estructura TDA.
◦ Muchos compiladores de lenguajes de programación vienen con bibliotecas de
subprogramas que ya han creado la estructura de datos de la pila.
Tema 3 Pilas y Colas 5
![Page 160: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/160.jpg)
Petia Ivanova Radeva
El tipo de Datos Abstracto Pila
Datos – secuencia lineal ordenada de elementos heterogéneos que se añaden y borran del
mismo extremo.
Operaciones básicas:
◦ Stack() – crea una pila vacía. No necesita parámetros y retorna una pila vacía.
◦ push(item) – añade un nuevo elemento al top de la pila. Necesita el elemento como parámetro y no
retorna nada.
◦ pop() – borra el elemento del top de la pila. No necesita parámetros y retorna el elemento borrado del
top.
◦ peek() – retorna el primer elemento de la pila sin borrarlo de la pila. La pila no se modifica.
◦ isEmpty() – comprueba si la pila está vacía. No necesita parámetros y retorna un valor booleano.
◦ size() o __len__() – retorna el número de elementos de la pila. No necesita parámetros y retorna un
entero.
Tema 3 Pilas y Colas 6
![Page 161: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/161.jpg)
Petia Ivanova Radeva
Ejemplo de las operaciones básicas de una pila
Operación Contenido de la pila Valor de retorno
s.isEmpty()
s.push(4)
s.push( dog )
s.peek()
s.push(True)
len(s)
s.isEmpty()
s.push(8.4)
s.pop()
s.pop()
len(s)
Tema 3 Pilas y Colas 7
![Page 162: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/162.jpg)
Petia Ivanova Radeva
Ejemplo de las operaciones básicas de una pila
Operación Contenido de la pila Valor de retorno
s.isEmpty() [] True
s.push(4) [4]
s.push( dog ) [4,dog ]
s.peek() [4,dog ] dog
s.push(True) [4,dog ,True]
len(s) [4,dog ,True] 3
s.isEmpty() [4,dog ,True] False
s.push(8.4) [4,dog ,True,8.4]
s.pop() [4,dog ,True] 8.4
s.pop() [4,dog ] True
len(s) [4,dog ] 2
Tema 3 Pilas y Colas 8
![Page 163: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/163.jpg)
Petia Ivanova Radeva
Implementación de la clase pila class Stack:
“””Define un TDA Pila “”” def __init__(self):
def __str__(self):
def isEmpty(self):
def push(self, item):
def pop(self):
def peek(self):
def __len__(self):
Tema 3 Pilas y Colas 9
![Page 164: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/164.jpg)
Petia Ivanova Radeva
Recordad: Operaciones de las listas en Python
Metodo Uso Explicacion
append milista.append(elemento) Añade un elemento al final de la lista
insert milista.insert(i, item) Inserta un elemento a la posición i
pop milista.pop() Borra y retorna el último elemento
pop milista.pop(i) Borra y retorna el i-ésimo elemento
sort milista.sort() Modifica ordenando la lista
reverse milista.reverse() Invierte la lista
del del milista[i] Borra el elemento i
index milista.index(item) Retorna el índice de la primera ocurrencia
count milista.count(item) Retorna el número de ocurrencias del item
remove milista.remove(item) Borra la primera ocurrencia de item
Tema 1 Abstracción de datos
10
![Page 165: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/165.jpg)
Petia Ivanova Radeva
Implementación de la clase pila
class Stack:
“””Define un TDA Pila “”” def __init__(self):
self.__items = []
def __str__(self):
res=""
for i in self.__items: res=res+" "+str(i) #Alternativas?
return res
def isEmpty(self):
return self.__items == []
def push(self, item): # Qué es recomendable: item o __item?
self.__items.append(item)
def pop(self):
return self.__items.pop()
def peek(self):
if len(self)>0: return self.__items[len(self)-1]
else: return None
def __len__(self):
return len(self.__items)
Tema 3 Pilas y Colas
11
![Page 166: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/166.jpg)
Petia Ivanova Radeva
Implementación de la clase pila
class Stack:
“””Define un TDA Pila “”” def __init__(self):
self.__items = []
def __str__(self):
return ''.join(str(elem)+', ' for elem in self.__items)
# Ventajas?
def isEmpty(self):
return self.__items == []
def push(self, item):
self.__items.append(item)
def pop(self):
return self.__items.pop()
def peek(self):
if len(self)>0: return self.__items[len(self)-1]
else: return None
def __len__(self):
return len(self.__items)
Tema 3 Pilas y Colas
12
![Page 167: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/167.jpg)
Petia Ivanova Radeva
Una alternativa para implementar una Pila
class Stack:
“””Define un TDA Pila “”” def __init__(self):
self.__items = []
def __str__(self):
return ''.join(str(elem)+', '
for elem in self.__items)
def isEmpty(self):
return self.__items == []
def push(self, item):
self.__items.append(item)
def pop(self):
return self.__items.pop()
def peek(self):
if len(self)>0:
return self.__items[len(self)-1]
else: return None
def __len__(self):
return len(self.__items)
Tema 3 Pilas y Colas
13
class Stack: “””Define un TDA Pila “”” def __init__(self):
self.__items = []
def __str__(self): return ''.join(str(elem)+', ' for elem in self.__items)
def isEmpty(self):
return self.__items == []
def push(self, item):
self.__items.insert(0,item)
def pop(self):
return self.__items.pop(0)
def peek(self):
if len(self)>0:
return self.__items[0]
else: return None
def __len__(self):
return len(self.__items)
![Page 168: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/168.jpg)
Petia Ivanova Radeva
Test
La posibilidad de definir el operador apropiado para poder
hace p i t , do de es u a pila se lla a ……………………….
Para encapsular correctamente la clase pila, definimos los
datos co o ……………………………..
Para poder ejecutar len(p), donde p es una pila necesitamos
…………………………..
Las fu cio es odificado as de la clase pila so : …………………..
E la clase pila, el étodo gette es: ………………….
Tema 3 Pilas y Colas 14
![Page 169: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/169.jpg)
Petia Ivanova Radeva
Ejemplo: chequear si una expresión contiene
paréntesis balanceados
Tema 3 Pilas y Colas 15
Determinar las expresiones correctas: (()()()) ((()))) ((((((()()()()))))) ()()()() )()()()( Fijémonos que cada paréntesis que cierra corresponde al último paréntesis que abre.
![Page 170: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/170.jpg)
Petia Ivanova Radeva
Implementación def parChecker(symbolString):
s = Stack()
balanced, index = True, 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol == '(': s.push(symbol)
elif symbol==')':
if s.isEmpty(): balanced = False
else: s.pop()
index += 1
if balanced and s.isEmpty(): return True
else: return False
Tema 3 Pilas y Colas 16
>>>print parChecker('(()())()')
![Page 171: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/171.jpg)
Petia Ivanova Radeva
Símbolos balanceados (el caso general)
En el caso general, podemos encontrar (), [], {}
( { [ ] ) { } ) ]
( ( { { [ [ ] ] } { [ ] [ ] } } ( ) ) )
[ { ( ) } { } ]
Tema 3 Pilas y Colas 17
![Page 172: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/172.jpg)
Petia Ivanova Radeva
Implementación
def parCheckerComplete(symbolString):
s = Stack()
balanced,index = True,0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol in '([{': s.push(symbol)
elif symbol in ')]}':
if s.isEmpty():
balanced = False
else:
top = s.pop()
if not matches(top,symbol):
balanced = False
index += 1
if balanced and s.isEmpty(): return True
else: return False
Tema 3 Pilas y Colas
18
Hay acceso a los atributos privados de la clase Stack?
![Page 173: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/173.jpg)
Petia Ivanova Radeva
Implementación
def matches(open,close):
opens = "([{"
closers = ")]}“ return opens.index(open) == closers.index(close)
>>parChecker(‘'()()()()(())()()’) True
¿Puede el algoritmo parsear expresiones de tipo?:
>>parCheckerComplete(‘(a+b)/c*(d+’) False
Tema 3 Pilas y Colas 19
![Page 174: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/174.jpg)
Petia Ivanova Radeva
Aplicaciones
Tema 3 Pilas y Colas 20
• Backtracking
• Evaluación de expresiones y análisis de sintáxis
• Lenguajes de programación basados en pilas
![Page 175: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/175.jpg)
Petia Ivanova Radeva
Relación con la práctica
Dadas las clases: Deck, Discard_Pile y Player , ¿cuál de éstas
se puede considerar como una pila?
Tema 3 Pilas y Colas 21
![Page 176: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/176.jpg)
Petia Ivanova Radeva
Relación con la práctica
Dadas las clases: Deck, Discard_Pile y Player , ¿cuál de éstas
se puede considerar como una pila?
Tema 3 Pilas y Colas 22
Por ejemplo, si consideramos la clase pila (Discard_Pile) - donde amontonamos las cartas, sólo la última carta se puede ver.
a. Datos i. Cards b. Métodos i. Constructor (__init__). ii. show_last_card - retorna la última carta. iii. append –añadir una carta a la pila. iv. len - Comprobar cuántas cartas tiene la pila. v. test – define función de test.
¿Cuáles de los datos y métodos serán definidos y heredados de la clase Pila y cuáles seran específicos para la clase de las cartas?
![Page 177: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/177.jpg)
Petia Ivanova Radeva
Colas
Ejemplos:
◦ La cola de impresión
◦ El buffer de la secuencia de teclas
Tema 3 Pilas y Colas 23
Definición – una colección lineal de elementos
heterogéneos, donde los elementos se añaden por uno de
los lados y se eliminan por el otro.
![Page 178: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/178.jpg)
Petia Ivanova Radeva
Colas
Es una estructura lineal, una colección secuencial.
First In First Out (FIFO) - first-come first-served.
Las colas se pueden expander y contraer automáticamente
según la cantidad de elementos que tienen.
Tema 3 Pilas y Colas 24
![Page 179: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/179.jpg)
Petia Ivanova Radeva
Colas
Una cola permite guardar en un extremo y recuperar por el
otro extremo del contenedor.
La mayoría de los lenguajes de programación no tienen la
cola pre-implementada.
◦ Se ha de crear como TDA.
Pero normalmente existen librerías con la implementación de
la cola como estructura de datos.
Tema 3 Pilas y Colas 25
![Page 180: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/180.jpg)
Petia Ivanova Radeva
El tipo de Datos Abstracto Cola Datos – secuencia ordenada de elementos heterogéneos
Operaciones básicas
◦ Queue() – crea una cola vacía. No necesita argumentos.
◦ enqueue(item) – añade un nuevo elemento item a la cola. Necesita el
elemento como argumento y no retorna nada.
◦ dequeue() – borra el primer elemento de la cola. No necesita parámetros y
retorna el elemento.
◦ isEmpty() – comprueba si la cola está vacía. No necesita parámetros y retorna
un valor booleano.
◦ size() o __len__() – retorna el número de elementos de la cola. No necesita
argumentos y retorna un entero.
Tema 3 Pilas y Colas 26
![Page 181: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/181.jpg)
Petia Ivanova Radeva
Cola
Operación Contenido de la cola Valor de retorno
q.isEmpty()
q.enqueue(4)
q.enqueue( dog )
q.enqueue(True)
len(q)
q.isEmpty()
q.enqueue(8.4)
q.dequeue()
q.dequeue()
len(q)
Tema 3 Pilas y Colas 27
![Page 182: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/182.jpg)
Petia Ivanova Radeva
Cola
Operación Contenido de la cola Valor de retorno
q.isEmpty()
q.enqueue(4)
q.enqueue( dog )
q.enqueue(True)
len(q)
q.isEmpty()
q.enqueue(8.4)
q.dequeue()
q.dequeue()
len(q)
Tema 3 Pilas y Colas 28
[]
[4]
[ dog ,4]
[True,dog ,4]
[True,dog ,4]
[True,dog ,4]
[8.4,True,dog ,4]
[8.4,True,dog ]
[8.4,True]
[8.4,True]
True
3
False
4
dog
2
![Page 183: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/183.jpg)
Petia Ivanova Radeva
Implementación de la Cola en Python
Tema 3 Pilas y Colas 29
class Queue:
“””Define un TDA Cola”””
def __init__(self):
def __str__(self):
def enqueue(self,el):
def dequeue(self):
def isEmpty(self):
def __len__():
![Page 184: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/184.jpg)
Petia Ivanova Radeva
Implementación de la Cola en Python
Tema 3 Pilas y Colas 30
class Queue:
“””Define un TDA Cola”””
def __init__(self):
self.__data=[]
def __str__(self):
return ''.join(str(elem)+', ’ for elem in self.__data) def enqueue(self,el):
self.__data.append(el)
def dequeue(self):
return self.__data.pop(0)
def isEmpty(self):
return self.__data==[]
def __len__():
return len(self.__data)
![Page 185: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/185.jpg)
Petia Ivanova Radeva Tema 3 Pilas y Colas 31
Ejercicio: Dada una lista de números p.e. [1,5,3,4,2,7,5,9,0],
generar sus permutaciones?
[1, 5, 3, 4, 2, 7, 5, 9, 0]
[5, 3, 4, 2, 7, 5, 9, 0, 1]
[3, 4, 2, 7, 5, 9, 0, 1, 5]
[4, 2, 7, 5, 9, 0, 1, 5, 3]
[2, 7, 5, 9, 0, 1, 5, 3, 4]
[7, 5, 9, 0, 1, 5, 3, 4, 2]
[5, 9, 0, 1, 5, 3, 4, 2, 7]
[9, 0, 1, 5, 3, 4, 2, 7, 5]
[0, 1, 5, 3, 4, 2, 7, 5, 9] ¿Relación con la práctica?
![Page 186: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/186.jpg)
Petia Ivanova Radeva
Implementación del juego La patata caliente
Tema 3 Pilas y Colas 32
Flavius Josephus (historiador del s. 1) - El combate de los judios contra los romanos. - Josephus con sus 39 compañeros atrapados en una cueva
![Page 187: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/187.jpg)
Petia Ivanova Radeva
Implementación del juego La patata caliente
def hotPotato(namelist, N):
“””Implementa el juego de la patata caliente””” sim = Queue()
for name in namelist:
while sim.size() > 1:
for i in range(N-1):
return
Tema 3 Pilas y Colas 33
>>>hotPotato(['Bill','David','Susan','Jane','Kent','Brad’], 7) Kent
def hotPotato(namelist, N): “””Implementa el juego de la patata caliente””” sim = Queue()
for name in namelist:
sim.enqueue(name)
while len(sim) > 1:
for i in range(N-1):
sim.enqueue(sim.dequeue())
sim.dequeue()
return sim.dequeue()
![Page 188: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/188.jpg)
Petia Ivanova Radeva
Relación con la práctica
¿Dadas las clases: Deck, Discard_Pile y Player , cuál de éstas
se puede implementar como una cola?
Tema 3 Pilas y Colas 34
![Page 189: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/189.jpg)
Petia Ivanova Radeva
Relación con la práctica
Dadas las clases: Deck, Discard_Pile y Player , ¿cuál de éstas
se puede implementar como una cola?
Tema 3 Pilas y Colas 35
Dada la clase mazo (Deck ) – es el conjunto de cartas de donde sacamos las cartas, a.Datos: i. Mazo de cartas b. Métodos i. Constructor – crea todas las cartas con números de 0 a 9 y colores. ii. Obtener la carta “i” del mazo (__getitem__) – devuelve la carta en la posición “ i” del mazo. iii. Retornar cuántas cartas tiene el mazo (len). iv. Borrar la carta “i” del mazo (remove). v. Repartir una carta a un jugador (deal_one_card). vi. Repartir las cartas (deal) – reparte N cartas a cada uno de los jugadores.
¿Cuáles de los datos y métodos serán definidos y heredados de la clase Cola y cuáles seran específicos para la clase de las cartas?
![Page 190: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/190.jpg)
Petia Ivanova Radeva
Colas de prioridad
A veces necesitamos que los elementos de la cola estén ordenados no por
el orden de llegada, sino por sus características.
◦ Ejemplo: lista de preferencias de música
La cola de prioridad representa una cola donde los elementos estan
ordenados por su prioridad.
◦ Esto hace muy fácil recuperar el elemento con mayor prioridad (tiempo O(1)).
Ejercicio: Dada una estructura de números reales, desarrollar un
algoritmo que en tiempo óptimo O(1) encuentra el número mayor por
valor absoluto.
Tema 3 Pilas y Colas 36
![Page 191: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/191.jpg)
Petia Ivanova Radeva
Y cómo sería una cola de prioridad? class PriorityQueue(Queue):
""" Cola de prioridad""”
def __init__(self):
def …………………(self,el):
¿Qué métodos ha de tener?
¿Podemos reaprovechar alguna clase?
¿Qué métodos redefinir?
¿Qué métodos sobrecargar?
Tema 3 Pilas y Colas 37
![Page 192: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/192.jpg)
Petia Ivanova Radeva
¿Y cómo sería una cola de prioridad? class PriorityQueue(Queue):
""" Cola de prioridad, hereda de una cola pero inserta los elementos en orden, por defecto ascendiente"""
def __init__(self):
Queue.__init__(self)
def enqueue(self,el):
if self.isEmpty(): self.insert(0,el)
elif el<=self.__getitem__(0): self.insert(0,el)
else:
inserted,i=False,0
while i< (len(self)-1) and not(inserted):
if self.__getitem__(i)<el and el<=self.__getitem__(i+1):
self.insert(i+1,el)
inserted=True
i=i+1
if not(inserted): self.insert(len(self),el)
Tema 3 Pilas y Colas 38
![Page 193: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/193.jpg)
Petia Ivanova Radeva
Ejercicio
¿Dado un conjunto de datos ordenado y de gran volumen (p.e.
las películas en un vídeoclub), si tenemos espacio limitado,
en qué estructura guardar el contenido?
Tema 3 Pilas y Colas 39
![Page 194: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/194.jpg)
Petia Ivanova Radeva
Relación con la práctica
Dadas las clases: Deck, Discard_Pile y Player , ¿cuál de éstas
se puede considerar como una cola de prioridad?
Tema 3 Pilas y Colas 40
![Page 195: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/195.jpg)
Petia Ivanova Radeva
Relación con la práctica
Dadas las clases: Deck, Discard_Pile y Player , ¿cuál de éstas
se puede considerar como una cola?
Tema 3 Pilas y Colas 41
¿Cuáles de los datos y métodos serán definidos y heredados de la clase Cola de prioridad y cuáles seran específicos para la clase?
La clase jugador (Player): a.Datos:
i. Nombre (name) ii. Cartas de la mano del jugador b. Métodos
i. Inicializa el nombre del jugador y sus cartas ii. Imprimir el nombre del jugador y sus cartas iii. Comprobar si puede jugar (can_play_card). iv. Jugar carta (play_a_card). v. Seleccionar carta (select_card). vi. Imprimir cuántas cartas tiene en la mano.
![Page 196: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/196.jpg)
Petia Ivanova Radeva
Aplicaciones – programas antivirus
Cada mensaje que viene, el programa antivirus lo guarda en
un extremo y si el mensaje está comprobado que no tiene
virus, se guarda en el otro extremo.
Si tiene virus se rechaza por el primer extremo.
Tema 3 Pilas y Colas 42
![Page 197: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/197.jpg)
Petia Ivanova Radeva
Aplicaciones: Programación multitarea &
multiprocesador (A-Steal job scheduling algorithm).
Tema 3 Pilas y Colas 43
• El algoritmo hace la planificación de tareas de los múltiples
procesadores. • Cada procesador tiene su deque.
• Para ejecutar el siguiente proceso, el procesador saca el primer
elemento.
• Si el proceso se bifurca, se añade al deque por el otro extremo.
• Y se ejecuta la siguiente tarea. • Cuando un procesador vacíe su deque, “roba” un proceso del II
extremo de otro procesador y lo ejecuta.
• Algoritmo usado por la librería de programación paralela de Intel's.
![Page 198: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/198.jpg)
Petia Ivanova Radeva
Deque
Una estructura lineal de elementos ordenados donde se
puede añadir y borrar por los dos lados de la secuencia.
Fijémonos que el prinicipio está a la derecha.
Tema 3 Pilas y Colas 44
![Page 199: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/199.jpg)
Petia Ivanova Radeva
El TAD Deque
Deque() crea un deque nuevo vacío. No necesita parámetros y retorna el deque
vacío.
addFront(item) añade un nuevo item al principio del deque. Necesita como
parámetro el item y no retorna nada.
addRear(item) añade un nuevo item al final del deque. Necesita como parámetro
el item y no retorna nada.
removeFront() borra el primer item del deque. No necesita parámetros y retorna
el item. Modifica el deque.
removeRear() borra el último item del deque. No necesita parámetros y retorna el
item. Modifica el deque.
isEmpty() comprueba si el deque está vacío. No necesita parámetros y retorna un
valor booleano.
__len__() o size() retorna en número de items del deque. No necesita parámetros
y retorna un entero.
Tema 3 Pilas y Colas 45
![Page 200: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/200.jpg)
Petia Ivanova Radeva
Ejemplo de deque
[]
[4]
[ dog ,4]
[ dog ,4,cat ]
[ dog ,4,cat ,True]
[ dog ,4,cat ,True]
[ dog ,4,cat ,True]
[8.4,dog ,4,cat ,True]
[ dog ,4,cat ,True]
[ dog ,4,cat ]
[ dog ,4,cat ]
Tema 3 Pilas y Colas 46
Operación Contenido de la cola Valor de retorno
q.isEmpty()
q.addRear(4)
q.addRear( dog )
q.addFront( cat )
d.addFront(True)
len(q)
q.isEmpty()
q.addRear (8.4)
q.removeRear()
q.removeFront()
len(q)
[]
[4]
[ dog ,4]
[ dog ,4,cat ]
[ dog ,4,cat ,True]
[ dog ,4,cat ,True]
[ dog ,4,cat ,True]
[8.4,dog ,4,cat ,True]
[ dog ,4,cat ,True]
[ dog ,4,cat ]
[ dog ,4,cat ]
True
4
False
8.4
True
3
![Page 201: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/201.jpg)
Petia Ivanova Radeva
Implementación del deque
class Deque:
def __init__(self):
def isEmpty(self):
def addFront(self, item):
def addRear(self, item):
def removeFront(self):
def removeRear(self):
def __len__(self):
def __str__(self):
Tema 3 Pilas y Colas 47
class Deque:
def __init__(self):
self._items = []
def isEmpty(self):
return self._items == []
def addFront(self, item):
self._items.append(item)
def addRear(self, item):
self._items.insert(0,item)
def removeFront(self):
return self._items.pop()
def removeRear(self):
return self._items.pop(0)
def __len__(self):
return len(self._items) def __str__(self):…….
![Page 202: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/202.jpg)
Petia Ivanova Radeva
Ejemplo: chequear si una palabra es palíndromo
Tema 3 Pilas y Colas 48
>>palchecker(‘gjgjhgj’) False
>>palchecker(‘toot’) True
>>palchecker(‘radar’) True
![Page 203: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/203.jpg)
Petia Ivanova Radeva
Ejemplo: chequear si una palabra es palíndromo
def palchecker(aString):
chardeque = Deque()
for ch in aString:
while len(chardeque) > 1
and ……:
if first != last:
return stillEqual
Tema 3 Pilas y Colas 49
Implementar el mismo programa sustituyendo el deque con una pila y una cola.
![Page 204: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/204.jpg)
Petia Ivanova Radeva
Ejemplo: chequear si una palabra es palíndromo
def palchecker(aString):
chardeque = Deque()
for ch in aString:
while len(chardeque) > 1
and ……:
if first != last:
return stillEqual
Tema 3 Pilas y Colas 50
def palchecker(aString):
chardeque = Deque()
for ch in aString:
chardeque.addRear(ch)
stillEqual = True
while len(chardeque) > 1 and stillEqual:
first =chardeque.removeFront()
last = chardeque.removeRear()
if first != last:
stillEqual = False
return stillEqual
¿Es mejor hacer la función método de la clase Deque? Implementar el mismo programa sustituyendo el deque con una pila y una cola.
![Page 205: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/205.jpg)
Petia Ivanova Radeva
Lo que hemos visto…
La lógica de las estructuras básicas: pila, cola, cola de prioridad y deque.
La implementación de los tipos de datos abstractos pila, cola, cola de prioridad y
deque.
Implementar ejemplos de uso de las pilas, colas, colas de prioridad y deques.
Ser capaz de reconocer las propiedades de los problemas, donde son apropiadas
las pilas, colas, colas de prioridad y deques.
Pilas y Colas 51
Tema 3
![Page 206: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/206.jpg)
Colecciones, arrays y estructuras
enlazadas Tema 4
1
![Page 207: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/207.jpg)
Petia Ivanova Radeva 2
Objetivos
Reconocer diferentes categorías de colecciones y sus operaciones
◦ Entender la diferencia entre los tipos de datos abstractos y los datos concretos usados para
implementarlos
Realizar operaciones básicas sobre arrays, como inserciones y borrado de sus
elementos
◦ Poder cambiar de tamaño de un array cuando sea demasiado pequeño o grande
Realizar operaciones básicas como recorrido, inserciones, borrado sobre
estructuras enlazadas
Saber valorar el espacio y tiempo de gestión de arrays y estructuras enlazadas
desde punto de vista de los modelos de memoria que implican estas estructuras
de datos
![Page 208: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/208.jpg)
Petia Ivanova Radeva 3
Colecciones
Colección: Grupo de elementos que queremos tratar como unidades conceptuales ◦ Ejemplos: Listas, strings, pilas, colas, ABB, heaps, grafos, diccionarios,
conjuntos, etc.
◦
Pueden ser homogeneos o heterogeneos ◦ Las listas son heterogeneas en Python
Cuatro categorías principales: ◦ Lineales, jerárquicas, grafos, y no ordenadas.
![Page 209: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/209.jpg)
Petia Ivanova Radeva 4
Colecciones lineales
Ordenadas por su orden
Ejemplos ordinarios:
◦ Listas de compra
◦ Pila de platos
◦ Cola de usuarios en el banco
![Page 210: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/210.jpg)
Petia Ivanova Radeva 5
Colecciones jerárquicas
Estructura árbol
◦ El padre de D3 es D1; sus hijos son D4, D5, y D6
Ejemplos: el sistema de directorios de
ficheros, la tabla de contenido de un libro
![Page 211: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/211.jpg)
Petia Ivanova Radeva 6
Grafo: Colección en cual cada elemento puede tener muchos
padres y muchos hijos
Ejemplos: Mapas de las rutas de las aerolíneas entre
ciudades; los diagramas de cables eléctricos de los edificios
Colecciones de grafos
![Page 212: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/212.jpg)
Petia Ivanova Radeva 7
Colecciones sin orden (conjuntos)
Los elementos no tienen orden concreto
◦ No se puede definir el predecesor y el sucesor
Ejemplo: Bolsa de caniques
![Page 213: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/213.jpg)
8
Operaciones sobre Colecciones
![Page 214: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/214.jpg)
9
Operaciones sobre Colecciones
![Page 215: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/215.jpg)
Petia Ivanova Radeva 10
Abstracción y Tipos de datos abstractos
Para el usuario, una colección es una abstracción
En Ciencias de Computación, las colecciones son tipos de datos
abstractos (ADTs)
◦ Los usuarios de los ADT los interesa aprender la interface de las ADTs
◦ Los desarolladores son los que han de implementar su comportamiento de la
forma más eficiente posible
¿Cómo se pueden implementar ADTs como clases o conjuntos de clases
relacionadas en módulos?
![Page 216: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/216.jpg)
Petia Ivanova Radeva 11
Estructuras de Datos para implementar las
Colecciones: Arrays
La estructura de datos y el tipo de datos concreto se refieren a la representación interna de los datos de un ADT
Las dos estructuras de datos más usadas para implementar colecciones en la mayoría de lenguajes son: los arrays y las estructuras enlazadas
Un array es un objeto de tipo colección donde todos los elementos están físicamente almacenados en un espacio continuo
Una lista enlazada es un objeto de tipo colección donde todos los elementos no necesariamente están físicamente almacenados en un espacio continuo. La relación entre los elementos se consigue a través de sus enlaces
![Page 217: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/217.jpg)
Petia Ivanova Radeva 12
Estructuras de Datos para Implementar las
Colecciones: Arrays
Los arrays y las estructuras enlazadas ◦ Diferentes maneras para almacenar y acceder a los datos en la memoria del
ordenador
◦ Diferente forma de gestionar el espacio y el tiempo de ejecución de los
algoritmos que manipulan las colecciones
vs.
12
![Page 218: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/218.jpg)
Petia Ivanova Radeva 13
Array: Se basa a la lista en Python
◦ Es una estructura de datos más restringuida que las listas en Python
Definición de la clase Array
La Estructura de Datos Array
![Page 219: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/219.jpg)
Petia Ivanova Radeva
Implementación del Array
class Array:
"""Represents an array."""
def __init__(self, capacity, fillValue = None):
"""Capacity is the static size of the array.
fillValue is placed at each position.""“
self._items = list()
for count in xrange(capacity):
self._items.append(fillValue)
def __len__(self):
"""-> The capacity of the array."""
return len(self._items)
def __iter__(self):
"""Supports traversal with a for loop."""
return iter(self._items)
def __getitem__(self, index):
"""Subscript operator for access at index."""
return self._items[index]
def __setitem__(self, index, newItem):
"""Subscript operator for replacement at index."""
self._items[index] = newItem
def __str__(self):
"""-> The string representation of the array."""
return str(self._items)
14
An Array is a restricted list whose users can use only [], len, iter, and str. To instantiate, use: <variable> = array(<capacity>, <optional fill value>) The fill value is None by default.
![Page 220: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/220.jpg)
Petia Ivanova Radeva 15
Acceso Aleatorio y Memoria Continua
La indexación del array se realiza a través de una operación
La dirección de un elemento: la dirección de la base + offset
La operación de indexación tiene dos pasos:
Localiza la dirección base
Calcula suma de la base + index*k, donde k es el número de bytes de cada
elemento del array, y
Retorna la referencia o el contenido posicionado en la memoria
![Page 221: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/221.jpg)
Petia Ivanova Radeva 16
Memoria Estática y Memoria Dinámica
En los lenguajes viejos los arrays eran estáticos
◦ int v[10];
Los lenguajes modernos suportan arrays dinámicos
◦ int *v;
◦ v= new int[N];
![Page 222: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/222.jpg)
Petia Ivanova Radeva 17
Memoria Estática y Memoria Dinámica
Para reajustar la longitud de un array en tiempo de ejecución:
◦ Crea un array con un tamaño razonable al principio
◦ Cuando esté lleno, crea uno nuevo, más grande y copia los datos
◦ Cuando parece que el array no utiliza gran parte de la memoria, reduce
el tamaño de mismo modo
Estos ajustes en Python son automáticos cuando se utilizan las listas
de Python
1
3
4
5
1
3
4
5
17
![Page 223: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/223.jpg)
Petia Ivanova Radeva 18
Tamaño físico y tamaño lógico
El tamaño físico es el número de celdas del array
El tamaño lógico es el número de elementos que actualmente tiene
Arrays con diferente tamaño físico
Garbage collection – libera el espacio temporal que no se utiliza
Para evitar el garbage collection , se han de tener en cuenta los dos tamaños.
![Page 224: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/224.jpg)
Petia Ivanova Radeva 19
Tamaño físico y tamaño lógico
En general, el tamaño físico y el tamaño lógico nos dicen puntos
importantes sobre el estado del array:
◦ Si el tamaño lógico es 0, el array es vacío
Sino, en cada momento el índice del último elemento en el array es su tamaño lógico
menos 1.
◦ Si el tamaño lógico equivale al tamaño físico, no hay espacio para nuevos datos.
Tamaño físico Tamaño lógico
![Page 225: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/225.jpg)
Petia Ivanova Radeva 20
Operaciones sobre Arrays
Consideramos los siguientes datos:
Las operaciones seran usadas para definir métodos para las
colecciones que contienen arrays.
![Page 226: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/226.jpg)
Petia Ivanova Radeva 21
Incrementar el tamaño de un Array
Consiste en:
◦ Crear un nuevo array más grande
◦ Copiar los datos del array viejo al nuevo
◦ Reasignar a la variable del viejo array en el nuevo objeto
Para conseguir una ejecución más razonable, duplicar el tamaño del array cada
vez que se incrementa el tamaño:
1
3
4
5
1
3
4
5
![Page 227: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/227.jpg)
Petia Ivanova Radeva 22
Decrementar el tamaño de un Array
Esta operación ocurre en las listas de Python cuando usando pop() lleva a no aprovechar suficiente la memoria reservada (cuando
el número de elementos no usados supera un umbral)
Pasos:
◦ Crea un array nuevo más pequeño
◦ Copia los datos del viejo array al nuevo
◦ Reasigna a la vaiable del viejo array, la dirección del nuevo
1
3
4
5
1
3
4
5
![Page 228: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/228.jpg)
Petia Ivanova Radeva 23
Insertar un elemento en un array que crece
El programador ha de comprobar sobre el espacio suficiente
e incrementar el tamaño físico si es necesario
Se mueven los elementos desde la posición concreta hasta el
final lógico del array con una posición
◦ Se inserta el nuevo elemento
◦ Se incrementar el tamaño lógico con uno.
1 5 2 3 1
7
1 5 2 3 1
7
1 5 2 3 1 7
![Page 229: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/229.jpg)
24
Insertar un Elemento en un Array que
Aumenta
![Page 230: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/230.jpg)
Petia Ivanova Radeva 25
Borrar un Elemento de un Array
Pasos:
◦ Mover los elementos desde la posición concreta hasta el final del
tamaño lógico con uno
◦ Decrementar el tamaño lógico con uno
◦ Comprobar el espacio no utilizado y decrementar el tamaño físico del
array si es necesario
El coste del borrado, en promedio, es lineal (O(n)).
1 5 2 3 1 7
![Page 231: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/231.jpg)
26
Borrado de un Elemento en un Array
![Page 232: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/232.jpg)
Petia Ivanova Radeva 27
Complejidad: Tiempo, Espacio, y Arrays
El uso promedio de la memoria es O(n)
El coste de la memoria para usar un array corresponde con su factor de sobrecarga (el ratio de las
casillas ocupadas vs. el tamaño físico del array)
1 5 2 3 1 7
![Page 233: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/233.jpg)
Petia Ivanova Radeva 28
Arrays Bi-Dimensionales (Grids)
A veces, un array bi-dimensional puede ser más útil que un uni-dimensional
Llamamos esta estructura tabla (grid, matriz);
◦ para acceder un elemento:
![Page 234: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/234.jpg)
Petia Ivanova Radeva 29
Procesando un Grid
A parte de los dobles corchetes para devolver sus elementos, se pueden
añadir los siguientes dos métodos:
◦ Ejemplos: getHeight y getWidth
Las operaciones sobre arrays unidimensionales se extienden fácilmente
para arrays bidimensionales
![Page 235: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/235.jpg)
Petia Ivanova Radeva 30
Crear e inicializar una tabla (Grid)
Suponiendo que existe la clase Grid :
Una vez creada, se pueden cambiar sus valores:
altura
anchura
valor inicial
![Page 236: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/236.jpg)
31
Definiendo la clase Grid
![Page 237: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/237.jpg)
Petia Ivanova Radeva 32
Definiendo la clase Grid
El método __getitem__ es suficiente para suportar el uso del doble
corchete por el usuario de la clase:
![Page 238: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/238.jpg)
Petia Ivanova Radeva 33
Tablas no uniformes y arrays multidimensionales
En una tabla (grid) no uniforme, hay un número fijo de filas pero el número de
columnas en cada fila puede variar
Se puede implementar como un array de listas o un array de arrays
Se pueden definir dimensiones a la definición del grid; el único límite es la
memoria del ordenador
◦ Un array tri-dimensional se puede visualizar como una caja de cajas más pequeñas con
sus columnas y filas
Profundidad, altura, y anchura; tres índices; tres bucles
def __init__(self, rows, columns, fillValue = None): self._data = Array(rows) for row in xrange(rows): self._data[row] = Array(columns, fillValue)
![Page 239: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/239.jpg)
Petia Ivanova Radeva 34
Estructuras enlazadas
Después de los arrays, las estructuras enlazadas son probablemente las
estructuras de datos más usadas en los diferentes lenguajes
De mismo modo como el array, la estructura enlazada es un tipo concreto
de datos que se usa para implementar varios tipos de colecciones,
incluyendo las listas
Existen varias características que se han de tener en cuenta cuando se usan las
estructuras enlazadas para implementar otros tipos
![Page 240: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/240.jpg)
Petia Ivanova Radeva 35
Estructuras enlazadas simples y doble enlazadas
No existe el acceso aleatorio, se ha de recorrer toda la lista.
No hace falta mover elementos ni en la inserción ni en el borrado (por qué?).
Se puede aumentar/disminuir la lista sin coste de memoria.
Enlace vacío
![Page 241: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/241.jpg)
Petia Ivanova Radeva 36
Memoria no continua y Nodos
Una estructura enlazada separa la secuencia lógica de los elementos en la
estructura de cualquier ordenación en la memoria física
◦ Esquema de representacion de memoria no continua
La unidad básica de representación es el nodo:
Nodo enlazado simple
Nodo enlazado simple
![Page 242: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/242.jpg)
Petia Ivanova Radeva 37
Memoria no continua y Nodos
Según el lenguaje, se pueden definir los nodos para enlazar partes
separadas de la memoria de forma diferente:
◦ Usando dos arrays paralelos
![Page 243: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/243.jpg)
Petia Ivanova Radeva 38
Memoria no continua y Nodos
Formas de definir los nodos para usar la memoria no continua:
◦ Usando apuntadores (null o nil representan enlaces vacíos como valor de
un apuntador)
Memoria alocatada a partir del objeto
◦ Usando referencias de objetos (e.g., Python)
En Python, None puede ser usado para asignar un enlace vacío
Un garbage collection automático facilita para que el usuario no ha de ir
liberando la memoria
De aquí adelante vamos a usar los términos enlace, apuntador y
referencia de forma equivalente.
![Page 244: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/244.jpg)
Petia Ivanova Radeva 39
Definición de la Clase Nodo Enlazado Simple
La clase Nodo ha de ser simple
◦ La flexibilidad y la facilidad de uso son críticos
Un nodo simple enlazado ha de contener los datos y la referencia al siguiente
nodo:
class Node: def __init__(self, data, next=None): '''Instantiates a Node with default next of None''' self.__data=data self.__next=next def __str__(self): return str(self.__data)
![Page 245: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/245.jpg)
Petia Ivanova Radeva 40
Usando la Clase Nodo Enlazado Simple
Las variables del Node se inicializan como None o algun otro objeto Node
node1=None
# Just an empty link
node2=Node('a', node1)
# A node containing data and an empty link
node3=Node('b', node2)
# A node containing data and a link to node2
![Page 246: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/246.jpg)
Petia Ivanova Radeva 41
Usando la Clase Nodo Enlazado Simple
node1.__next = node3 -> AttributeError
◦ Solución:
node1 = Node("C", node3)
Las estructuras enlazadas se procesan con bucles
![Page 247: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/247.jpg)
Petia Ivanova Radeva 42
Usando la Clase Nodo Enlazado Simple
¿Qué hace este código?
class Node: def __init__(self, data, next=None): '''Instantiates a Node with default next of None''' self.__data, self.__next=data,next def __str__(self): return str(self.__data) def getNext(self): return self.__next def setNext(self,newNext): self.__next=newNext def getData(self): return self.__data def setData(self,newData): self.__data=newData
for count in xrange(1,6): head=Node(count,head) while head!= None: print head head=head.getNext()
¿Qué problema tiene este código y cómo evitarlo?
![Page 248: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/248.jpg)
Petia Ivanova Radeva 43
La lista enlazada class LinkedList: def __init__(self): self.__head=None def initialize(self,until): '''Add X nodes to the linked list'’’ self.__head=None for count in xrange(0,until): self.__head=Node(until-count,self.__head) def getHead(self): ‘’’Returns the first element’’’ return self.__head
![Page 249: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/249.jpg)
Petia Ivanova Radeva 44
Operaciones sobre las Estructuras Enlazadas
Simples
Casi todas las operaciones en arrays son basadas en índices
◦ Los índices son una parte integral de una estructura de tipo array
¿Podemos emular operacions basadas en el índice
manipulando los enlaces dentro de la estructura?
◦ ¿Son eficientes? ¿Cuáles?
¿Cómo realizar estas operaciones comunes como?:
◦ Recorridos
◦ Inserciones
◦ Borrados
![Page 250: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/250.jpg)
Petia Ivanova Radeva 45
Recorrido
Recorrido: Visitar cada nodo sin borrarlo
◦ Usar una variable de referencia temporal
Ejemplo:
None sirve de centinela para el proceso
◦ Los recorridos son lineales en tiempo,
◦ No requieren memoria extra
def traverse(self): probe=self.__head while probe!= None:
print probe probe=probe.getNext()
![Page 251: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/251.jpg)
46
Recorrido
![Page 252: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/252.jpg)
Petia Ivanova Radeva 47
Búsqueda Recuerda al recorrido, pero necesita dos posibles sentinelas:
◦ Un enlace vacío
◦ En elemento que recorre los datos
Ejemplo:
En promedio, es lineal para estructuras enlazadas simples.
def find(self,targetItem): ‘’’Traverse and look for a targetItem, returns True or False’’’ probe, res = self.__head, True while probe != None and targetItem!=probe.getData(): probe = probe.getNext() if probe != None: print 'TargetItem has been found' else: res=False print 'TargetItem is not in the linked list' return res
![Page 253: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/253.jpg)
Petia Ivanova Radeva 48
Búsqueda Accediendo al elemento i-ésimo de una estructura enlazada es una
operación de búsqueda secuencial
◦ Se empieza con el primer nodo y se cuentan el número de enlaces hasta llegar al nodo i-
ésimo.
Las estructuras enlazadas no suportan el acceso aleatorio
◦ ¿Se puede utilizar la búsqueda binaria?
def __getitem__(self,index): ‘’’Looks for the ith element’’’ probe=self.__head while index>0 and probe.getNext(): probe=probe.getNext() index-=1 if index>0: return None else: return probe.getData()
![Page 254: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/254.jpg)
Petia Ivanova Radeva 49
Reemplazar un elemento con otro
Necesita recorrido, una vez encontrado, lo reemplaza.
def replace(self, targetItem, newItem): probe=self.__head while probe!=None and targetItem!=probe.getData(): probe=probe.getNext() if probe!=None: probe.setData(newItem) return True else: return False
![Page 255: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/255.jpg)
Petia Ivanova Radeva 50
Reemplazar un elemento con otro
Reemplaza el i-ésimo elemento asumiendo 0 <= i < n
En promedio, coste lineal O(n) de las dos operaciones.
def replacei(self, index, newItem): if index<0: print'Index negativo' return False probe=self.__head while probe!=None and index>=0: probe=probe.getNext() index-=1 if index<0: probe.setData(newItem) return True else: return False
![Page 256: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/256.jpg)
Petia Ivanova Radeva 51
Insertar al principio
Usa tiempo y memoria constante
def insertFirst(self,data): ‘’’Inserta data como primer elemento’’’ self.__head=Node(data,self.__head)
![Page 257: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/257.jpg)
Petia Ivanova Radeva 52
Insertar al final
Insertar un elemento al final de un array
(append en una lista de Python)
requere tiempo y memoria constantes
◦ Siempre y cuando el array no ha de ser
cambiado de tamaño
Para insertar al final cuántos casos
hemos de considerar?
![Page 258: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/258.jpg)
53
Inserting at the End (continued)
def insertLast(self,data): probe=self.__head if probe==None: probe=Node(data) else: while probe.getNext(): probe=probe.getNext()
probe.setNext(Node(data))
![Page 259: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/259.jpg)
54
Borrar al Principio
def removeFirst(self): if self.__head==None: return None res=self.__head.getData() self.__head=self.__head.getNext()
![Page 260: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/260.jpg)
Petia Ivanova Radeva 55
Borrar del final
Borrar un elemento del
final del array (pop en
una lista de Python)
requere tiempo y
memoria constante
◦ Siempre y cuando el
array no ha de cambiar
de tamaño
¿Cuántos casos hemos de
contemplar para borrar al
final de una estructura?
![Page 261: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/261.jpg)
Petia Ivanova Radeva 56
Borrar del final
Borrar un elemento del final del array (pop en una lista de Python) requere
tiempo y memoria constante
◦ Siempre y cuando el array no ha de cambiar de tamaño
¿Cuántos casos hemos de contemplar para borrar al final de una estructura?
def removeLast(self): ‘’’’Borra el nodo del final de la estructura’’’ if self.__head==None: return None if self.__head.getNext()==None: res, self.__head=self.__head.geData(), None else: probe=self.__head while probe.getNext().getNext()!=None: probe=probe.getNext() res=probe.getNext().getData() probe.setNext(None) return res
![Page 262: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/262.jpg)
Petia Ivanova Radeva 57
Insertar a cualquier posición
Inserción al principio (mirar transparencias anteriores)
En las otras posiciones i, primero encuentra el nodo a la posición i - 1 (si i
< n) o el nodo a la posición n - 1 (if i >= n)
Tiempo lineal O(n); uso constante de la memoria
def inserti(self, index,data): ‘’’Insertar a posicion i’’’ if self.__head==None or index<0: self.__head=Node(data) else: probe=self.__head while probe.getNext() and index>1: probe=probe.getNext() index-=1 #una vez llegado a la posición index, insertamos probe.setNext(Node(data,probe.getNext()))
![Page 263: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/263.jpg)
58
Insertar a Cualquier Posición
![Page 264: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/264.jpg)
Petia Ivanova Radeva 59
Borrar de cualquer posición
Tres casos por considerar:
def removei(self, index): if self.__head==None: removedItem=None elif index<=0 or self.__head.getNext()==None: removedItem=self.__head.getData() self.__head=None else: probe=self.__head while probe.getNext().getNext()!=None and index>1: probe=probe.getNext() index-=1 removedItem=probe.getNext().getData() probe.setNext(probe.getNext().getNext()) return removedItem
![Page 265: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/265.jpg)
Petia Ivanova Radeva 60
Complejidad : Uso del tiempo y el espacio en
las estructuras enlazadas simples
La principal ventaja es no tanto el tiempo, sino el uso óptimo
de la memoria!!!
![Page 266: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/266.jpg)
Petia Ivanova Radeva 61
Extensiones de las estructuras enlazadas
Una estructura circular enlazada con un Nodo de Cabecera
Estructuras Dobles Enlazadas
![Page 267: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/267.jpg)
Petia Ivanova Radeva 62
Variaciones sobre las estructuras enlazadas
lineales: Una estructura enlazada circular
Contiene un enlace desde el último nodo hasta el primer nodo de la
estructura
El nodo de cabeza sirve como un marcador para el inicio y el final de la
estructura enlazada
![Page 268: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/268.jpg)
Petia Ivanova Radeva 63
Una estructura enlazada circular class CircularLinkedList: def __init__(self): self.__head, self.__tail=None, None def __str__(self): if self.__head==None: return '' probe=self.__head res=str(probe.getData())+',' if probe.getNext()!=self.__head: probe=probe.getNext() while probe !=self.__head: res=res+str(probe.getData())+',' probe=probe.getNext() return res def insertFirst(self,data): if self.__head==None: self.__head=Node(data,self.__head) self.__tail=self.__head self.__head.setNext(self.__head) else: self.__head=Node(data,self.__head) self.__tail.setNext(self.__head)
![Page 269: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/269.jpg)
64
Estructuras Enlazadas Dobles
from node import * class TwoWayNode(Node): def __init__(self,data,previous=None, next=None): Node.__init__(self,data,next) self.__previous=previous
![Page 270: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/270.jpg)
65
Estructuras Enlazadas Dobles
![Page 271: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/271.jpg)
66
Estructuras Enlazadas Dobles
def traverse(self): ‘’’Traversing from front to back’’’ probe=self.__head while probe!= None: print probe.getData(), probe=probe.getNext() def traverseback(self): ‘’’Traversing from back to front’’’ probe=self.__tail while probe!= None: print probe.getData(), probe=probe.getPrevious()
![Page 272: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/272.jpg)
67
Estructuras Enlazadas Dobles
from twowaynode import * class DoubleLinkedList: def __init__(self): self.__head=None self.__tail=None def initialize(self,until): '''Add X twowaynodes to the linked structure''’ self.__head=TwoWayNode(0) self.__tail=self.__head for count in xrange(1,until): self.__tail.setNext(TwoWayNode(count,self.__tail)) self.__tail=self.__tail.getNext()
![Page 273: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/273.jpg)
Petia Ivanova Radeva
Relación con la práctica
¿Dadas las clases de la práctica: Card, Deck, Discard_Pile,
Player y Players, cuál de éstas se puede implementar como
una lista enlazada?
◦ ¿Qué tipo de lista exactamente utilizaríais?
Tema 3 Pilas y Colas 68
![Page 274: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/274.jpg)
Petia Ivanova Radeva
Relación con la práctica
¿Cómo sería la pila implementada como lista enlazada?
◦ Dibujarla
◦ Diseñar el TDA
◦ Implementarla
Tema 3 Pilas y Colas 69
![Page 275: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/275.jpg)
Petia Ivanova Radeva
Relación con la práctica
¿Cómo sería la cola y la cola de prioridad implementadas
como listas enlazadas? ◦ Dibujarlas
◦ Diseñar los TDA
◦ Implementarlas
Tema 3 Pilas y Colas 70
![Page 276: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/276.jpg)
Petia Ivanova Radeva 71
Resumen
Las colecciones son objetos que contienen 0 o más objetos ◦ Categorías principales: lineal, jerárquica, grafo, y sin orden
◦ Las colecciones son iterable
◦ Las colecciones son tipos de datos abstractos
Una estructura de datos es un objeto usado para representar los datos contenidos en una colección
Un array es una estructura de datos que suporta acceso aleatorio, en tiempo constante O(1), a cualquier elemento suyo a través de su posición
La inserción y el borrado en un array tiene coste O(n)
Puede ser bi-dimensional (grid) . ◦ Cuál es el coste del borrado en un grid?
![Page 277: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/277.jpg)
Petia Ivanova Radeva 72
Resumen
Una estructura enlazada es una estructura de datos que consiste en 0 o más nodos
◦ Un nodo enlazado simple contiene un elemento para los datos y un enlace para el siguiente nodo
◦ Las inserciones y los borrados en estructuras enlazadas no requiren trasladar elementos de datos -> Coste O(1)
◦ El recorruido y la búsqueda de elementos son secuenciales y por lo tanto tienen coste O(n)
Las listas circulares y las listas enlazadas dobles permiten moverse en las dos direcciones con mayor eficiencia
◦ Normalmente, la dualidad del coste en términos de tiempo y memoria de los algoritmos…
![Page 278: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/278.jpg)
Estructuras enlazadas: pilas, colas,
listas circulares y doblemente
enlazadas Tema 5
1
Brad Miller, David Ranum, Problem Solving with Algorithms and Data Structures Release 3.0, 2013. Pat Morin, “Open Data Structures (in pseudocode)”, Edition 0.1Gβ, http://opendatastructures.org.
![Page 279: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/279.jpg)
Petia Ivanova Radeva
Implementación de la clase pila class Stack:
“””Define un TDA Pila “”” def __init__(self):
def __str__(self):
def isEmpty(self):
def push(self, item):
def pop(self):
def peek(self):
def __len__(self):
Tema 3 Pilas y Colas 2
![Page 280: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/280.jpg)
Petia Ivanova Radeva 3
Pila: Constructor
self.__head class LinkedStack:
‘’’This is a Linked Stack’’’
def __init__(self):
self.__head=None
![Page 281: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/281.jpg)
Petia Ivanova Radeva 4
Pila: push() self.__head
def push(self, item):
if self.__head==None:
self.__head=Node(item)
D
![Page 282: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/282.jpg)
Petia Ivanova Radeva 5
Pila: push() self.__head
def push(self, item):
if self.__head==None:
self.__head=Node(item)
else:
self.__head=Node(item,self.__head)
D
D
D
D
D
![Page 283: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/283.jpg)
Petia Ivanova Radeva 6
Pila: pop() self.__head
def pop(self, item):
if self.__head==None:
return None
![Page 284: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/284.jpg)
Petia Ivanova Radeva 7
Pila: pop() self.__head
def pop(self):
if self.__head==None:
res=None
else:
res=self.__head.getData()
self.__head=self.__head.getNext()
return res
D
D
D
D
D
![Page 285: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/285.jpg)
Petia Ivanova Radeva
Implementación de la Cola
Tema 3 Pilas y Colas 8
class Queue:
“””Define un TDA Cola”””
def __init__(self):
def __str__(self):
def enqueue(self,el):
def dequeue(self):
def isEmpty(self):
def __len__():
![Page 286: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/286.jpg)
Petia Ivanova Radeva 9
Cola: Constructor
self.__head
class LinkedStack:
‘’’This is a Linked Stack’’’
def __init__(self):
self.__head=None
D D D
¿Cuántas variables centinelas necesitamos?
self.__tail
![Page 287: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/287.jpg)
Petia Ivanova Radeva 10
Cola: enqueue()
self.__head
def enqueue(self, item):
if self.__head==None:
self.__head=Node(item)
self.__tail=self.__head
D
![Page 288: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/288.jpg)
Petia Ivanova Radeva 11
Cola: enqueue ()
def enqueue(self, item):
if self.__head==None:
self.__head=Node(item)
self.__tail=self.__head
else:
self.__tail.setNext(Node(item))
self.__tail=self.__tail.getNext()
self.__head
D D D
self.__tail
D
![Page 289: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/289.jpg)
Petia Ivanova Radeva 12
Extensiones de las estructuras enlazadas
Una estructura circular enlazada con un Nodo de Cabecera
Estructuras Dobles Enlazadas
![Page 290: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/290.jpg)
Petia Ivanova Radeva 13
Variaciones sobre las estructuras enlazadas
lineales: Una estructura enlazada circular
Contiene un enlace desde el último nodo hasta el primer nodo de la
estructura
El nodo de cabeza sirve como un marcador (centinela) para el inicio y el
final de la estructura enlazada
![Page 291: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/291.jpg)
Petia Ivanova Radeva 14
Lista enlazada circular: Constructor
self.__head
![Page 292: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/292.jpg)
Petia Ivanova Radeva 15
Lista enlazada circular: InsertFront
Casos:
self.__head
self.__head D
self.__head D D
![Page 293: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/293.jpg)
Petia Ivanova Radeva 16
Lista enlazada circular: InsertFront
self.__head
Caso lista vacía:
self.__head D
![Page 294: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/294.jpg)
Petia Ivanova Radeva 17
Lista enlazada circular: InsertFront
self.__head self.__head D
if self.__head==None:
self.__head=Node(data,self.__head)
self.__head.setNext(self.__head)
![Page 295: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/295.jpg)
Petia Ivanova Radeva 18
Lista enlazada circular: InsertFront
self.__head D
D
Caso lista con un nodo:
![Page 296: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/296.jpg)
Petia Ivanova Radeva 19
Lista enlazada circular: InsertFront
Caso lista con un nodo:
self.__head D
D
elif self.__head.getNext()==self.__head:
self.__head=Node(data,self.__head)
self.__head.getNext().setNext(self.__head)
![Page 297: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/297.jpg)
Petia Ivanova Radeva 20
Lista enlazada circular: InsertFront
self.__head D D
D
Caso de lista con varios nodos:
![Page 298: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/298.jpg)
Petia Ivanova Radeva 21
Lista enlazada circular: InsertFront
Caso de lista con varios nodos:
self.__head D D
D self.__head=Node(data,self.__head)
probe=self.__head.getNext()
while probe.getNext()!=self.__head:
probe=probe.getNext()
probe.setNext(self.__head)
probe
![Page 299: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/299.jpg)
Petia Ivanova Radeva
Lista enlazada circular: InsertFront
def insertFirst(self,data):
if self.__head==None:
self.__head=Node(data,self.__head)
self.__head.setNext(self.__head)
elif self.__head.getNext()==self.__head:
self.__head=Node(data,self.__head)
self.__head.getNext().setNext(self.__head)
else:
self.__head=Node(data,self.__head)
probe=self.__head.getNext()
while probe.getNext()!=self.__head:
probe=probe.getNext()
probe.setNext(self.__head)
22
Podemos ahorrar este parágrafo?
![Page 300: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/300.jpg)
Petia Ivanova Radeva
Lista enlazada circular: InsertFront
def insertFirst(self,data):
if self.__head==None:
self.__head=Node(data,self.__head)
elif self.__head.getNext()==self.__head:
self.__head=Node(data,self.__head)
self.__head.getNext().setNext(self.__head)
else:
self.__head=Node(data,self.__head)
probe=self.__head.getNext()
while probe.getNext()!=self.__head:
probe=probe.getNext()
probe.setNext(self.__head)
23
![Page 301: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/301.jpg)
Petia Ivanova Radeva 24
InsertFront (alternativa)
self.__head D D
D
def insertFirst(self,data):
if self.__head==None:
self.__head=Node(data,self.__head)
self.__tail=self.__head
self.__head.setNext(self.__head)
else:
self.__head=Node(data,self.__head)
self.__tail.setNext(self.__head)
probe tail
![Page 302: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/302.jpg)
Petia Ivanova Radeva
Lista circular enlazada (alternativa)
class CircularLinkedList:
def __init__(self):
self.__head=None
self.__tail=None
def insertFirst(self,data):
if self.__head==None:
self.__head=Node(data,self.__head)
self.__tail=self.__head
self.__head.setNext(self.__head)
else:
self.__head=Node(data,self.__head)
self.__tail.setNext(self.__head)
25
Ventajas?
![Page 303: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/303.jpg)
Petia Ivanova Radeva
Lista doblemente enlazada
Una lista enlazada que se puede recorrer en las
dos direcciones
26
![Page 304: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/304.jpg)
27
Estructuras Enlazadas Dobles
from node import *
class TwoWayNode(Node):
def __init__(self,data,previous=None, next=None):
Node.__init__(self,data,next)
self.__previous=previous
class Node:
def __init__(self,data,previous=None, next=None):
self.__previous=previous
self.__next=next
¿Cómo definir el nodo?
![Page 305: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/305.jpg)
Petia Ivanova Radeva 28
Lista doblemente enlazada: Constructor
self.__head
class DoubleLinkedList:
‘’’Una lista doblemente enlazada’’’
def __init__(self):
self.__head=None
![Page 306: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/306.jpg)
29
Estructuras Enlazadas Dobles
def forward(self):
‘’’Traversing from front to back’’’
probe=self.__head
while probe!= None:
print probe.getData(),
probe=probe.getNext()
![Page 307: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/307.jpg)
30
Estructuras Enlazadas Dobles
def backword(self):
‘’’Traversing from back to front’’’
probe=self.__tail
while probe!= None:
print probe.getData(),
probe=probe.getPrevious()
![Page 308: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/308.jpg)
Petia Ivanova Radeva 31
Lista doblemente enlazada: insert()
self.__head
class DoubleLinkedList:
‘’’Una lista doblemente enlazada’’’
def __init__(self):
self.__head=None
self.__tail=None
![Page 309: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/309.jpg)
Petia Ivanova Radeva 32
Lista doblemente enlazada: insertfront()
self.__head
D D D
D
self.__tail
def insertFront(self,data):
self.__head=TwoWayNode(data,None, self.__head)
if self.__head.getNext():
self.__head.getNext().setPrevious(self.__head)
![Page 310: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/310.jpg)
Petia Ivanova Radeva 33
Lista doblemente enlazada: insert()
self.__head
D D D
D
self.__tail
¿Qué casos de excepción hemos de considerar?
![Page 311: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/311.jpg)
Petia Ivanova Radeva
Relación con la práctica
¿Dadas las clases de la práctica: Card, Deck, Discard_Pile, Player y Players,
cuál de éstas tiene sentido implementarla como lista enlazada?
◦ ¿Qué tipo de lista exactamente utilizar?
Tema 3 Pilas y Colas 34
![Page 312: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/312.jpg)
Petia Ivanova Radeva
Relación con la práctica
¿Cómo sería la pila implementada como lista enlazada?
◦ Dibujarla
◦ Diseñar el TDA
◦ Implementarla
Tema 3 Pilas y Colas 35
![Page 313: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/313.jpg)
Petia Ivanova Radeva
Relación con la práctica ¿Cómo sería la cola y la cola de prioridad implementadas
como listas enlazadas? ◦ Dibujarlas
◦ Diseñar los TDA
◦ Implementarlas
Tema 3 Pilas y Colas 36
![Page 314: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/314.jpg)
Petia Ivanova Radeva
Skiplistas
¿Cómo conseguir el acceso, inserción y borrado en una lista
en tiempo O(log n)?
Se basa en el concepto de la randomización.
Suponen listas ordenadas.
Bi liografía: Pat Morin, Open Data “tru tures in pseudo ode , Edition . Gβ
37
![Page 315: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/315.jpg)
Petia Ivanova Radeva
Skiplistas
Definición: una skiplista es una secuencia de listas enlazadas L0, L1, …Lr,
donde L0 es la lista original ordenada.
Construcción: Construimos recursivamente las listas Lr de las listas Lr-1
escogiendo aleatoriamiante un subconjunto de elementos de Lr-1.
38
![Page 316: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/316.jpg)
Petia Ivanova Radeva
Skiplistas
En una skiplista, para cada elemento x se define su altura en función de
en cuantas sublistas pertenece. La altura máxima de los elementos define
la altura de la skiplista.
Como primer elemento de cada lista está un nodo llamado
centinela/cabecera.
¿Se puede demostrar que la altura de cada elemento corresponde a
cuántas veces ha sido escogido aleatoriamente?
39
![Page 317: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/317.jpg)
Petia Ivanova Radeva
Skiplistas: buscar un elemento (find)
40
Se puede demostrar que la búsqueda se hace en O(log n)
![Page 318: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/318.jpg)
Petia Ivanova Radeva
Skiplistas: añadir un elemento (insert)
41
Se puede demostrar que la inserción se hace en O(log n)
![Page 319: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/319.jpg)
Petia Ivanova Radeva
Skiplistas: borrar un elemento (remove)
42
Se puede demostrar que el borrado se hace en O(log n)
![Page 320: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/320.jpg)
Petia Ivanova Radeva
Indexación eficiente en las skiplistas
43
Si codificamos cada arco con el número de elementos en la lista L0, podemos ir a la dirección i en O(log n). ¿Cómo?
![Page 321: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/321.jpg)
Petia Ivanova Radeva
Extender la inserción y el borrado actualizando
los arcos (homework)
44
![Page 322: Teoria Parcial 1 ED](https://reader034.vdocumento.com/reader034/viewer/2022051019/55cf8fb0550346703b9ec7e9/html5/thumbnails/322.jpg)
Petia Ivanova Radeva 45
Resumen
Una estructura enlazada es una estructura de datos que consiste en 0 o más nodos
◦ Un nodo enlazado simple contiene un elemento para los datos y un enlace para el siguiente nodo
◦ Las inserciones y los borrados en estructuras enlazadas no requiren trasladar elementos de datos -> Coste O(1)
◦ El recorruido y la búsqueda de elementos son secuenciales y por lo tanto tienen coste O(n)
Las listas circulares y las listas enlazadas dobles permiten moverse en las dos direcciones con mayor eficiencia
◦ Normalmente, la dualidad del coste en términos de tiempo y memoria de los algoritmos…
Las pilas y las colas son fácilmente implementadas como listas enlazadas
Las skiplistas aseguran O(log n) para las operaciones básicas.