Bun venit!

Structuri de date și algoritmi în Python

Miriam Antona

Software Engineer

Importanța algoritmilor și a structurilor de date

  • Structurile de date și algoritmii ne permit să
    • rezolvăm probleme cotidiene
    • folosind cod eficient
  • Cursul poate fi predat în orice limbaj de programare
Structuri de date și algoritmi în Python

Algoritmi și structuri de date

  • Algoritm: set de instrucțiuni care rezolvă o problemă

    1. Proiectare

      Imagine schematică a proiectării unui algoritm.

    2. Cod

      Imagine schematică a codului unui algoritm.

  • Structuri de date: rețin și manipulează datele în timpul execuției unui algoritm
    • Structuri de date avansate: liste înlănțuite, stive, cozi...
Structuri de date și algoritmi în Python

Liste înlănțuite

Exemplu vizual al unei liste înlănțuite cu pașii de preparare a pâinii.

  • Secvență de date conectate prin linkuri
Structuri de date și algoritmi în Python

Liste înlănțuite - structură

Reprezentarea unui nod dintr-o listă înlănțuită.

Structuri de date și algoritmi în Python

Liste înlănțuite - structură

Reprezentarea unui nod dintr-o listă înlănțuită cu cuvântul "DATA" în prima parte.

Structuri de date și algoritmi în Python

Liste înlănțuite - structură

Reprezentarea unui nod dintr-o listă înlănțuită cu cuvintele "DATA" în prima parte și "NEXT" cu un pointer în a doua parte.

Structuri de date și algoritmi în Python

Liste înlănțuite - structură

Reprezentarea a două noduri dintr-o listă înlănțuită conectate printr-un link.

Structuri de date și algoritmi în Python

Liste înlănțuite - structură

Reprezentarea mai multor noduri dintr-o listă înlănțuită conectate prin linkuri.

Structuri de date și algoritmi în Python

Liste înlănțuite - structură

Reprezentarea unei liste înlănțuite în care ultimul nod indică spre null.

Structuri de date și algoritmi în Python

Liste înlănțuite - structură

Reprezentarea unei liste înlănțuite cu cuvântul "HEAD" în primul nod.

Structuri de date și algoritmi în Python

Liste înlănțuite - structură

Reprezentarea unei liste înlănțuite cu cuvântul "TAIL" în ultimul nod.

  • Datele nu trebuie stocate în blocuri contigue de memorie
  • Datele pot fi plasate la orice adresă de memorie disponibilă
Structuri de date și algoritmi în Python

Liste simplu înlănțuite

Reprezentarea unei liste simplu înlănțuite.

  • Un singur link: listă simplu înlănțuită
Structuri de date și algoritmi în Python

Liste dublu înlănțuite

Reprezentarea unei liste dublu înlănțuite.

  • Două linkuri în ambele direcții: listă dublu înlănțuită
Structuri de date și algoritmi în Python

Liste înlănțuite - utilizări reale

  • Implementarea altor structuri de date:
    • stive
    • cozi
    • grafuri
  • Accesarea informațiilor prin navigare înainte și înapoi
    • browser web
    • playlist muzical
Structuri de date și algoritmi în Python

Liste înlănțuite - clasa Node

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None
Structuri de date și algoritmi în Python

Liste înlănțuite - clasa LinkedList

class LinkedList:
  def __init__(self):
    self.head = None
    self.tail = None
Structuri de date și algoritmi în Python

Liste înlănțuite - metode

  • insert_at_beginning()
  • remove_at_beginning()
  • insert_at_end()
  • remove_at_end()
  • insert_at()
  • remove_at()
  • search()
  • ...
Structuri de date și algoritmi în Python

Liste înlănțuite - insert_at_beginning

Reprezentarea unei liste simplu înlănțuite.

Structuri de date și algoritmi în Python

Liste înlănțuite - insert_at_beginning

Reprezentarea unei liste simplu înlănțuite și a unui nod nou,

 def insert_at_beginning(self, data):
    new_node = Node(data)

    if self.head:
Structuri de date și algoritmi în Python

Liste înlănțuite - insert_at_beginning

Reprezentarea unei liste simplu înlănțuite cu noul nod conectat.

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
Structuri de date și algoritmi în Python

Liste înlănțuite - insert_at_beginning

Reprezentarea unei liste simplu înlănțuite cu noul nod conectat și cuvântul "HEAD" în acest nod.

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node
Structuri de date și algoritmi în Python

Liste înlănțuite - insert_at_beginning

Reprezentarea unui nod nou într-o listă înlănțuită goală.

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node
    else:

      self.tail = new_node      
      self.head = new_node
Structuri de date și algoritmi în Python

Liste înlănțuite - insert_at_end

  def insert_at_end(self, data):
    new_node = Node(data)
    if self.head:  

      self.tail.next = new_node

      self.tail = new_node

    else:

      self.head = new_node
      self.tail = new_node
Structuri de date și algoritmi în Python

Liste înlănțuite - search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

Reprezentarea unei liste simplu înlănțuite cu cuvântul "current_node" indicând spre primul nod.

Structuri de date și algoritmi în Python

Liste înlănțuite - search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

Reprezentarea unei liste simplu înlănțuite cu cuvântul "current_node" indicând spre al doilea nod.

Structuri de date și algoritmi în Python

Liste înlănțuite - search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

  return False

Reprezentarea unei liste simplu înlănțuite cu cuvântul "current_node" indicând spre al treilea nod.

Structuri de date și algoritmi în Python

Liste înlănțuite - exemplu

Reprezentarea unui nod nou într-o listă înlănțuită goală.

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")
Structuri de date și algoritmi în Python

Liste înlănțuite - exemplu

Reprezentarea unui nod nou adăugat la sfârșitul unei liste înlănțuite.

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll")
Structuri de date și algoritmi în Python

Liste înlănțuite - exemplu

Reprezentarea unui nod nou adăugat la începutul unei liste înlănțuite.

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll") 
sushi_preparation.insert_at_beginning("assemble")
Structuri de date și algoritmi în Python

Liste înlănțuite - exemplu

Reprezentarea unei liste înlănțuite.

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False
Structuri de date și algoritmi în Python

Să exersăm!

Structuri de date și algoritmi în Python

Preparing Video For Download...