Estructuras de datos de Python

En el último tutorial, echamos un vistazo a algunos algoritmos de programación comunes. Un complemento de estos algoritmos es un conjunto de estructuras de datos comunes. Los algoritmos de programación necesitan trabajar con datos y esos datos a menudo están contenidos en formatos o estructuras de datos específicos. Ahora es un buen momento para aprender más sobre estas estructuras de datos comunes que se utilizan al crear varios algoritmos. El propósito de las estructuras de datos es organizar la información de manera que sea fácil de operar mediante algoritmos. Es posible que tenga una lista de seguimiento de acciones y es posible que desee poder clasificarlas por rendimiento de dividendos o Relación P / E. Otro ejemplo sería una estructura de árbol que representa una colección de carpetas y archivos donde desea encontrar un archivo específico dentro de todas esas carpetas. Cada escenario tiene datos asociados con una estructura de datos diferente. Las estructuras de datos más comunes en las que debe estar bien versado son matrices, listas enlazadas, pilas, colas, árboles y tablas hash. Las diferentes aplicaciones necesitarán diferentes tipos de estructuras de datos para contener la información con la que los algoritmos necesitan trabajar. En este tutorial, exploraremos estos temas más a fondo.

Matrices

Una matriz es un grupo de elementos donde la posición de cada elemento se identifica mediante un índice o un valor clave. Una matriz unidimensional es el tipo más básico de matriz, y el diagrama siguiente muestra cómo se vería.

Matriz unidimensional

Las posiciones de los elementos se pueden calcular utilizando una expresión matemática que permite acceder directamente a los elementos de la matriz en un enfoque de acceso aleatorio. Lo que esto significa es que dado que la posición de cada elemento se puede calcular directamente, no hay necesidad de navegar o atravesar la estructura de datos para acceder a un elemento. El primer elemento de índice de una matriz siempre está en la posición 0. Aquí hay un ejemplo de una matriz unidimensional simple en Python.

1
2
3
4
5
import array
 
one_dimensional = array.array('i', [3, 6, 9, 12, 15])
for i in range(0, len(one_dimensional)):
    print(one_dimensional[i])

Accediendo a todos los demás elementos de la matriz

1
2
3
4
5
import array
 
one_dimensional = array.array('i', [3, 6, 9, 12, 15])
for i in range(0, len(one_dimensional), 2):
    print(one_dimensional[i])

3
9
15

Accediendo a un elemento directamente

1
2
3
4
5
import array
 
one_dimensional = array.array('i', [3, 6, 9, 12, 15])
 
print(one_dimensional[4])

Las matrices pueden tener varias dimensiones. Para crear una matriz bidimensional, la primera dimensión puede contener matrices. Para acceder a un elemento en una matriz bidimensional, debe proporcionar dos índices. A continuación se muestra un diagrama de una matriz bidimensional con un índice de 2,1 resaltado.

Matriz multidimensional

En Python, es probable que use más comúnmente la estructura de datos de lista, que es un tipo de datos similar a una matriz. Tanto la lista como la matriz en Python se comportan de manera similar, ya que puede iterar sobre ellos y almacenar elementos en un índice específico. La diferencia entre los dos está en las funciones que puede realizar en ellos. Es más trabajo usar matrices verdaderas en Python porque tiene que importar el módulo de matriz y declarar una matriz. Las listas son simplemente una parte de la sintaxis de Python, por lo que se usan con mucha más frecuencia y cubren la mayoría de los casos de uso que necesitará. Los arreglos verdaderos serán mejores para funciones matemáticas así como para trabajar con grandes cantidades de datos. La mayoría de las veces, simplemente puede ir con Listas. Aquí hay algunos ejemplos de algunas listas en Python.

1
2
3
4
5
6
7
empty_list = []
 
list_of_ints = [3, 6, 9]
 
mixed_list = [2, 'Boo', 3.14]
 
two_dimensional_list = [[3, 6, 9], [2, 'Boo', 3.14]]

Listas vinculadas

La estructura de datos de la lista vinculada es una colección lineal de elementos de datos que a menudo se denominan nodos. Son similares a las matrices, sin embargo, cada uno de los nodos tiene un campo que apunta al siguiente elemento de la lista, a diferencia de una matriz. Hay listas de enlaces simples y listas de enlaces dobles. Aquí hay un par de diagramas que muestran esto.

Lista vinculada única

El primer elemento de una lista vinculada se llama encabezado. Cada elemento contiene un campo que apunta al siguiente elemento de la lista. El último elemento de una lista vinculada apunta a nulo, lo que significa que es el final de la lista.
lista enlazada única

Lista vinculada doble

En una lista de doble enlace, cada elemento de datos tiene una referencia tanto al elemento anterior como al siguiente.

Lista enlazada en Python (enlace único)

Aquí hay una implementación de una lista vinculada en Python. Utiliza dos clases. Uno para representar los nodos de la lista y otro para representar la propia lista enlazada. La Nodeclase implementa el tipo de nodo que se almacenará en la lista vinculada. Tiene un solo nextcampo, lo que indica que se trata de una lista enlazada individualmente. La LinkedListclase tiene campos para el headasí como un countcampo que realiza un seguimiento de cuántos nodos hay en la lista.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Node(object):
    def __init__(self, val):
        self.val = val
        self.next = None
 
    def get_data(self):
        return self.val
 
    def set_data(self, val):
        self.val = val
 
    def get_next(self):
        return self.next
 
    def set_next(self, next):
        self.next = next
 
 
class LinkedList(object):
    def __init__(self, head=None):
        self.head = head
        self.count = 0
 
    def get_count(self):
        return self.count
 
    def insert(self, data):
        new_node = Node(data)
        new_node.set_next(self.head)
        self.head = new_node
        self.count += 1
 
    def find(self, val):
        item = self.head
        while (item != None):
            if item.get_data() == val:
                return item
            else:
                item = item.get_next()
        return None
 
    def delete(self, index):
        if index > self.count:
            return
        if self.head == None:
            return
        else:
            tempIndex = 0
            node = self.head
            while tempIndex < index - 1:
                node = node.get_next()
                tempIndex += 1
            node.set_next(node.get_next().get_next())
            self.count -= 1
 
    def print_list(self):
        tempnode = self.head
        while (tempnode != None):
            print('Node: ', tempnode.get_data())
            tempnode = tempnode.get_next()

Inicializar una lista vinculada y almacenar algunos valores

1
2
3
4
5
6
7
linkedlist = LinkedList()
linkedlist.insert(3)
linkedlist.insert(6)
linkedlist.insert(9)
linkedlist.insert(12)
linkedlist.insert(15)
linkedlist.print_list()

Nodo: 15
Nodo: 12
Nodo: 9
Nodo: 6
Nodo: 3

Imprimir el recuento de la lista vinculada

1
print('Number of items in List: ', linkedlist.get_count())

Número de elementos en la lista: 5

Encuentra dos objetos de nodo en la lista vinculada

1
2
print('Finding item: ', linkedlist.find(6))
print('Finding item: ', linkedlist.find(9))

Buscando elemento: <__ main __. Objeto de nodo en 0x03512FD0>
Buscando elemento: <__ main __. Objeto de nodo en 0x03538028>

Eliminar un nodo en una lista vinculada

1
2
3
4
linkedlist.delete(3)
print('Number of items in List: ', linkedlist.get_count())
print('Finding item: ', linkedlist.find(12))
linkedlist.print_list()

Número de elementos en la lista: 4
Buscando elemento: <__ main __. Objeto de nodo en 0x031A8058>
Nodo: 15
Nodo: 12
Nodo: 9
Nodo: 3

Estructura de datos de pila

La estructura de datos de la pila es una colección de elementos que tiene dos operaciones básicas, push y pop. Las pilas son estructuras de datos LIFO, o las últimas en entrar, primero en salir. El último elemento que se coloca en una pila es el primero que aparece. Un ejemplo de pila es cuando usa el botón Atrás en su navegador. Mientras navega por Internet, el navegador agrega cada enlace a una pila para mantener el orden en que fueron visitados. Cuando hace clic en el botón Atrás, la URL agregada más recientemente se extrae de la pila y luego se vuelve a visitar.

Estructura de datos de pila en Python

Puede obtener las características de trabajar con una estructura de datos de pila en Python haciendo uso de una lista.

Inicializar una pila

1
stack = []

Empujar (agregar) elementos a la pila

1
2
3
4
stack.append('Tom')
stack.append('Dick')
stack.append('Harry')
stack.append('Bosch')

Imprime la pila

1
print(stack)

['Tom', 'Dick', 'Harry', 'Bosch']

Saca un artículo de la pila

1
2
3
popped = stack.pop()
print(popped)
print(stack)

Bosch
['Tom', 'Dick', 'Harry']

Apilar como clase

También puede hacer algo como lo siguiente, que usa una clase definida por el usuario para ofrecer funcionalidad de pila. Esto sigue siendo solo un envoltorio para usar el tipo de lista, pero ahora tiene un método push () real que puede usar.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Stack:
    def __init__(self):
        self.stack = []
 
    def __bool__(self):
        return bool(self.stack)
 
    def __str__(self):
        return str(self.stack)
 
    def push(self, data):
        self.stack.append(data)
 
    def pop(self):
        if self.stack:
            return self.stack.pop()
        else:
            raise IndexError('Stack is empty')
 
    def size(self):
        return len(self.stack)
 
 
stack = Stack()
for i in range(5):
    stack.push(i)
 
print('Initial stack: ' + str(stack))
print('pop(): ' + str(stack.pop()))
print('After pop(), the stack is now: ' + str(stack))
stack.push(7)
print('After push(7), the stack is now: ' + str(stack))
print('The size is: ' + str(stack.size()))

Pila inicial: [0, 1, 2, 3, 4]
pop (): 4
Después de pop (), la pila ahora es: [0, 1, 2, 3]
Después de presionar (7), la pila ahora es: [0, 1, 2, 3, 7]
El tamaño es: 5

Estructura de datos de la cola

La estructura de datos de la cola también admite la adición y eliminación de elementos, pero utiliza el método FIFO. FIFO es un enfoque de primero en entrar, primero en salir. Una cola vacía a la que se le agrega un elemento, sería el primer elemento de la lista. Hacer cola en más elementos simplemente aumenta la longitud de la lista. Las colas son muy comunes en la programación, ya que imitan gran parte de lo que sucede en la vida real. ¿Ha estado alguna vez en el departamento de vehículos de motor? Entonces sabes muy bien qué es una cola. Camina hasta el final de la línea (cola), espera una gran cantidad de tiempo (procesamiento de la cola) y finalmente obtiene servicio una vez que todos los demás frente a usted han sido atendidos. En software, el procesamiento de mensajes es un uso común de una cola.

Estructura de datos de cola en Python

Inicializar una cola vacía

1
2
3
from collections import deque
 
queue = deque()

Agregar algunos elementos a la cola

1
2
3
4
5
queue.append('Monday')
queue.append('Tuesday')
queue.append('Wednesday')
queue.append('Thursday')
queue.append('Friday')

Imprime la cola

1
print(queue)

deque (['Lunes', 'Martes', 'Miércoles', 'Jueves', 'Viernes'])

Sacar el artículo de la cola

1
2
3
popped = queue.popleft()
print(popped)
print(queue)

lunes
deque (['martes', 'miércoles', 'jueves', 'viernes'])

Estructura de datos de la tabla hash

Una tabla hash es básicamente una matriz asociativa. Muchos otros lenguajes de programación tienen matrices asociativas y Python tiene su implementación de esta estructura de datos a través de diccionarios. Esta estructura de datos asigna claves a valores, utilizando una función hash. Una función hash usa la clave para calcular un índice para las ranuras y asigna la clave a un valor. La capacidad de asignar de forma única una clave determinada a un valor específico es un gran beneficio de las tablas hash. Esto hace que trabajar con contadores y filtros sea rápido y sencillo. Las tablas hash también son bastante rápidas, lo que las hace buenas para grandes conjuntos de datos. Las tablas hash no ordenan sus elementos de ninguna manera específica, por lo que necesitaría agregar un mecanismo de clasificación si es necesario.

Estructura de datos de la tabla hash en Python

Inicializar una nueva tabla hash

1
2
hashone = dict({'firstkey': 1, 'secondkey': 2, 'thirdkey': 'three'})
print(hashone)

{'firstkey': 1, 'secondkey': 2, 'thirdkey': 'tres'}

Crea una segunda tabla hash con iteración

1
2
3
4
5
hashtwo = {}
hashtwo['firstkey'] = 1
hashtwo['secondkey'] = 2
hashtwo['thirdkey'] = 3
print(hashtwo)

{'firstkey': 1, 'secondkey': 2, 'thirdkey': 3}

Reemplazar un elemento en una tabla hash

1
2
hashtwo['secondkey'] = 'two'
print(hashtwo)

{'firstkey': 1, 'secondkey': 'dos', 'thirdkey': 3}

Iterar sobre la tabla hash para imprimir pares clave-valor

1
2
for key, value in hashtwo.items():
    print('key: ', key, ' value: ', value)

clave: primer valor de clave: 1
clave: segundo valor clave: dos
clave: tercer valor de clave: 3

Resumen de estructuras de datos de Python

Las matrices de Python verdaderas son un contenedor de las matrices de C y son buenas para trabajar con elementos del mismo tipo. No son tan fáciles de usar como las listas.
Las listas son un estilo más flexible de una matriz que puede contener una combinación de cualquier tipo de datos. Si necesita reducir y hacer crecer su lista sin problemas, son la mejor opción.
Es posible que se prefieran las listas vinculadas a las matrices, ya que son más fáciles y rápidas de reorganizar. Este artículo explica por qué querría utilizar una lista vinculada.
Las pilas crecen hacia la derecha y se encogen hacia la izquierda y son buenas para las operaciones de último en entrar, primero en salir.
Las colas utilizan el enfoque Primero en entrar, primero en salir y son buenas para mensajería, registro y otras aplicaciones.
Las tablas hash se implementan en Python mediante diccionarios y son una forma de matriz asociativa con pares clave-valor distintos.

Header Ads Widget