Algoritmos e Estrutura de Dados.

README.md

Algoritmos e Estrutura de Dados

Algoritmos

Definição

Análise

Tipos Básicos

• Inteiros

• Reais (float)

• Caracteres (char)

• String (sequência de caracteres)

• Array (vetor)

• Ponteiros

Tipos Abstratos

Criando novos tipos a partir dos tipos básicos

Listas Encadeada

Sequência de objetos armazenados na memoria do computadot, onde cada elemento da sequência, armazenado em uma célula, ou nó (nodo), onde há um campo da célula que armazena o dado e outro que é uma referência para a proxima célula, nó, da lista.

Exemplo:

struct nodo {
    int dado;
    struct nodo *prox;
};

typedef struct nodo nodo;

     nodo
┌─────────┬───────┐
│         │       │
│         │       │
│   *     │  o────┼─────────────►
│         │       │
│ dado    │ prox  │
│         │       │
└─────────┴───────┘

Funções

Algumas funções básicas

• inicializar/criar lista (vazia)

• inserir nó

• remover nó

• buscar dado na lista

• limpar lista

Filas

Pilhas

Árvores

Grafos

Referências

• Algoritmos e Estruturas de dados(USP/IME)

• Playlist Youtube/Programação Dinâmica

Blog

WSRicardo

abstractLinkedList.py

import node
"""
Observar que Filas, Pilhas são um tipo
especifico de lista onde é imposto condições
sobre em que posição o elemento é inserido 
e retirado.
"""

class AbstractLinkedList:
    """
    Classe implementa estrutura lista encadeada (ligada).
    Uma lista L de n elementos (nós) com L[1] o primeiro nó
    e L[k] o k-ésimo nó, onde seu antecessor é L[k-1] com
    0 < k <= n. 
    Head -> L[1]
    prox -> L[k], 0 < k <= n
    """

    def __init__(self):
        self.head = None
        self._size = 0

    def __repr__(self):
        return f'Head -> {self.head}'
    
    def __len__(self):
        return self._size
    
    @property
    def size(self):
        return self._size
    
    def inserir(self, valor):
        """
        Insere no fim da lista
        """
        return self
    
    def remove(self):
        """
        Remove o último elemento da lista.
        """
        return self
    
class LinkedList(AbstractLinkedList):
    """
    Métodos simples de inserção, remoção e busca de nó.
    """
    def __init__(self, head=None):
        super().__init__()
        self.head = head
    
    def insere(self, valor):
        """
        Insere nó no inicio trocando ponteiro head para 
        o novo nó criado que guardado o conteúdo da varável 'valor'.
        """
        aux = self.head 
        self.head = node.Node(valor)
        self.head.prox = aux
     
    def remove(self): 
        """
        Head -> [] -> [] -> ... -> [] -> None
        Função 'remove' remove o n-ésimo elemento da lista.
        """      
        ref = self.head
        current = self.head.prox
        # Head -> [] -> [] -> ... -> [] -> None
        #
        while ref.prox != None:
            current = ref
            ref = ref.prox
        #del(current.prox)
        current.prox = None

class Fila:
    def __init__(self):
        self.prim = None
        self.ult = None

    def __repr__(self):
        return f'> {self.prim}'

    def insere(self, valor):
        ref = self.ult
        if self.prim == None:
            self.prim = node.Node(valor)
            self.ult = self.prim
        else:
            novo = node.Node(valor)
            self.ult.prox = novo
            self.ult = self.ult.prox

    def remove(self):
        ref = self.prim.prox
        self.prim = ref        

    def busca(self, valor):
        """
        Retorna -2 para Fila vazia
        Retorna -1 para elemento não encontrado
        Retorna 0<= k <= n - 1 para posição da lista.
        """
        ref = self.prim
        k = 0
        if self.prim == None:
            return -2
        else:
            while ref != None:
                if ref.valor == valor:
                    return k 
                else:
                    k += 1
                    ref = ref.prox
        return -1

       
class Pilha:

    def __init__(self):
        self.topo = None

    def __repr__(self) -> str:
        return f'Topo -> {self.topo}'
    
    def insere(self, valor):
        ref = self.topo
        self.topo = node.Node(valor)
        self.topo.prox = ref
        
    def remove(self):
        #del(self.topo)
        self.topo = self.topo.prox # topo <- L[k-1]

    def busca(self, valor):
        ref = self.topo
        k = 0
        while ref:
            if ref.valor == valor:
                return k
            else:
                ref = ref.prox
                k += 1
        
        return -1

if __name__=='__main__':
    """#
    Testes de Pilha
    p = Pilha()
    #print(p)
    #p.insere(12)
    print(p)
    p.insere(32)
    print(p)
    p.insere(328)
    print(p)
    p.remove()
    print(p)
    print(p.busca(328))
    """
    
    """
    Testes listas encadeadas"""
    l  = LinkedList()
    l.insere(12)
    l.insere(98)
    l.insere(9)
    print(l)
    l.remove()
    print(l)
    l.remove()
    print(l)

    """f = Fila()
    print(f)
    f.insere(12)
    print(f)
    f.insere(43)
    print(f)
    f.insere(98)
    f.insere(98987)
    print(f)
    f.remove()
    print(f)
    print(f.busca(98))"""

algoritmo.md

Listas Encadeadas

# Linked list
class Node:
    
    def __init__(self, data=None,
    	 next=None):
        self.data = data
        self.next = next

    def __repr__(self):
        return '%s :-> %s'%(self.data, self.next)

class LinkedList:
    def __init__(self, head=None):
        self.head = head
        self.tail = None
        self._size = 0
        
    def __repr__(self):
        return 'Head ->[%s] Tail ->[%s]'%(self.head, self.tail)
    
    def __len__(self):
        return self._size
        
    @property
    def size(self):
        return self._size
           
    def insert(self, data):
        
        pointer = self.head
        nova = pointer 
        aux = None
        #print('head pointer', pointer)
        
        if self.head==None:
            self.head = Node(data)
            self.tail = self.head
            
        else:
            while pointer.next != None:
                pointer = pointer.next

            pointer.next = Node(data)
            self.tail = pointer.next
            
        self._size = self._size + 1
      
        nova = pointer 
        #print('size list', self._size)
        #print(pointer)
        
    def insert_in_index(self, index, elem):
        
        pointer = self.head
        count = 0
        
        if index > self._size:
            raise BaseException('Index out range list')
            
        else:
            while count < index - 1:
                pointer = pointer.next
                count = count + 1
        
        no = Node(elem)
        no.next = pointer.next
        pointer.next = no
        self._size = self._size + 1 
     
    def remove(self):
         
        #del(self.tail)
        corrente= self.head
        ant = corrente 
        while corrente.next:
            ant = corrente
            corrente = corrente.next
            
        ant.next = None 
        self.tail = ant
        self._size -= 1
  
    def walkfw(self, l):
        #import copy
        """
        Caminha pela lista recursivamente.
        """

        #lis = copy.copy(self)
        lis = l.head
        corrente = lis
        
        if corrente:
            #print('. ', lis)
            lis.head = corrente.next
            self.walkfw(lis)

        return corrente

    def busca(self, dado):
        
        corrente = self.head
        pos = -1
        
        while corrente.next:
            pos += 1

            if corrente.data == dado:
                return pos
            
            corrente = corrente.next
            
        pos = -1
        return pos


    def removerc(self):
        lis = self
        corrente = lis
        ant = corrente
        if corrente.next:
            pass
    
if __name__=='__main__':
    l = LinkedList()
    l.insert( 2)
    l.insert(7)
    l.insert(13)
    
    print(f'> {l}\n\n')
    l.insert_in_index(2, 21)
    l.insert_in_index(1, 35)
    
    print(f'> {l}\n') 
    print('size l', l.size)
    print('len function ', len(l))
    
    
    # Endereço de a
    #a = 2
    #print(id(a))
    
    l.remove()
    print(f'> {l}')
    print(f' Size: {l.size}')

    print('. ', l.walkfw(l))

    print('busca ', l.busca(0) )

    print('busca ', l.busca(35) )

    print('busca ', l.busca(7))

Output:

> Head ->[2 :-> 7 :-> 13 :-> None] Tail ->[13 :-> None]


> Head ->[2 :-> 35 :-> 7 :-> 21 :-> 13 :-> None] Tail ->[13 :-> None]

size l 5
len function  5
> Head ->[2 :-> 35 :-> 7 :-> 21 :-> None] Tail ->[21 :-> None]
 Size: 4
.  2 :-> 35 :-> 7 :-> 21 :-> None
busca  -1
busca  1
busca  2

node.py

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

    def __repr__(self):
        return f'{self.data} :-> {self.next}'