estructuras de datos - unamgil/2020-1/_downloads/d67b0d92f77… · interfaz vs implementación •...

Estructuras de Datos

Una Estructura de datos es una manera particular de organizar y almacenar datos

• Arreglos

• Listas

• Conjuntos

• Diccionarios

Todas las estructuras de datos están diseñadas para organizar datos que cumplen cierto propósito, de tal manera que se pueda acceder a ellos y trabajar de manera eficiente

• Muchas compañías basan su éxito en el uso de estructuras de datos

• Interactuamos con las estructuras de datos de manera cotidiana

Abrir un archivo: sistema de archivos

Entrar en tu red social favorita

Realizar una búsqueda en Internet

Busar una ruta en waze

Tu lista de contactos

Interfaz VS implementación

• Una interfaz describe lo que hace una estructura de datos

• Una implementación describe como lo hace

Interfaz VS implementación

• La interfaz define el conjunto de operaciones de la estructura de datos (se conoce estructura de datos abstracta ADT)

• La implementación incluye la representación interna de la estructura de datos y la definición de las operaciones

Interfaz Lista

• size(): regresa n, la longitud de la lista

• append(x): agrega el elemento x al final de la lista

• delete(x): borramos el elemento x de la lista

class Node:

def __init__(self, data=None): self.data = data self.next = None

def __str__(self): return self.data

class Node:

def __init__(self, data=None): self.data = data self.next = None

def __str__(self): return self.data

class Node:

def __init__(self, data=None): self.data = data self.next = None

def __str__(self): return self.data

class Node:

def __init__(self, data=None): self.data = data self.next = None

def __str__(self): return self.data

class LinkedList(object): """Implementación de una lista ligada"""

def __init__(self): self.head = None

def add(self, data): node = Node(data) if self.head is None: self.head = node else: current = self.head while current.next is not None: current = current.next current.next = node

class LinkedList(object): """Implementación de una lista ligada"""

def __init__(self): self.head = None

def add(self, data): node = Node(data) if self.head is None: self.head = node else: current = self.head while current.next is not None: current = current.next current.next = node

class LinkedList(object): """Implementación de una lista ligada"""

def __init__(self): self.head = None

def append(self, data): node = Node(data) if self.head is None: self.head = node else: current = self.head while current.next is not None: current = current.next current.next = node

class LinkedList(object): """Implementación de una lista ligada"""

def __init__(self): self.head = None self.tail = None

def append(self, data): node = Node(data) if self.head is None: self.head = node self.tail = node else: self.tail.next = node self.tail = node

class LinkedList(object): """Implementación de una lista ligada"""

def size(self): count = 0 current = self.head while current.next is not None: count += 1 current = current.next return count

class LinkedList(object): """Implementación de una lista ligada"""

def __init__(self): self.head = None self.tail = None self.size = 0

def append(self, data): node = Node(data) if self.head is None: self.head = node self.tail = node else: self.tail.next = node self.tail = node self.size += 1

class LinkedList(object): """Implementación de una lista ligada"""

def __init__(self): … self.size = 0

def size(self): return self.size

class LinkedList(object): """Implementación de una lista ligada"""

def delete(self, data): pass

def search(self, data): pass