Algoritmos e Estruturas de dados 2

Professor Coelho

---

Informações Básicas :

• Bibliografia :
  • https://algs4.cs.princeton.edu
  • Sedgewick
• Linguagem principal : Java, C também ( «mas foda-se a linguagem», COELHO, THE)
• Monitores
• 3 provas e várias provinhas de 10 minutos (toda terça)
• A nota das provinhas entra como psub
• Instalar o ambiente de programação algs4

---

Aula 01

• Interface : É uma fronteira entre a implementação de uma biblioteca e o programa que usa a biblioteca. Ou seja, ele define estruturas de dados, nomes de função, constantes… é basicamente uma API. O cliente não precisa saber como as coisas são implementadas, por isso a interface faz essa certa separação
• Cliente : É o programa que chama alguma função de uma biblioteca
• Implementação : Explicita como as funções definidas na interface são feitas de fato.

Bag (saco) : Estrutura de dados que tem as seguintes operações :

• add() : coloco um item

• iterar : procurar todos os itens

  O saco pode ser usado para implementação de grafos.

Podemos definir a API de um saco de inteiros : (fazer em casa, é de boa, até porque o coelho não fez em aula e eu fiquei com preguiça rs mas é uma interface, tipo um .h)

Podemos definir a implementação da API :

import java.util.Iterator; // puxa as ferramentas do java pra fazer um iterador, primeiro passo

public class Bag<Item> implements Iterable<Item> { // garante que vou implementar algo iterável
    private Node first; // instanciando um objeto da classe node, não tem problema estanciar antes de definir a classe Node
    private int n;
    private Node current;
    private class Node { // subclasse
        /*public Node (Integer item, Node next) {
            this.item = item;
            this.next = next;
        }
        Eu poderia ter feito assim tambem, mas dai eu teria que sempre escrever um "new" antes de criar um novo nó, exemplo : 
        	private current = new Node();
        */
        private Item item;
        private Node next;
    }
    public Bag<Item>() { // metodo construtor
        first = null;
        n = 0;
    }

    public void add(Integer item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        n++;
    }

    public int size() {
        return n;
    }

    public boolean isEmpty() { // boolean retorn true ou false
        return n == 0;
    }

    public Iterator<Item> iterator() {
        return new BagIterator();
    }

    private Class BagIterator implements Iterator<Item> {
        private Node current = first;
        public boolean hasNext() {
            return current != null;
        }

        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

    }


    /*  
    			 	Métodos sem usar o iterator : 
    public void startIterator() {
        current = first;
    }

    public boolean hasNext() {
        return current != null; // aqui não é interessante colocar um current.next == null porque dá problema caso eu tente acessar o proximo de uma lista vazia
    }

    public Item next() {
        Item item = current.item;
        current = current.next;
        return item;
    }
    */
}

Como fazer uma classe iteravel :

• importo o java.util.iterator
• Garanto que minha classe implementa um iteravel (implements iterable)
• Implemente um método iterável

Podemos definir um cliente do saco de inteiros >

import edu.princeton.cs.algs4.StdOut;
public class cliente { 
    public static void main(string[] args) { 
        Bag<Integer> bag = new bag<Integer>(); 
        for (int i = 10; i < 20; i++) {
            bag.add(i);
        }

        StdOut.println(bag.size());
        Iterator<Integer>it = bag.iterator();



        for(Integer valor:bag) { // basicamente eu pego um valor dentro de bag.valor e vou iterando
            StdOut.println(valor);
        }
        /* 		Versão sem o iterador utilizado totalmente
        while(it.hasNext()) {
			Integer valor = it.next();
            StdOut.println(valor)
        }

        */


        /*
        	Versão sem usar iterator
        bag.startIterator(4);
        while(bag.hasNext()) {
            Integer valor = bag.next();
            stdOut.println(valor);
        }*/
    }
}

/* GLOSSARIO DO JAVA : 

	Estilo : Usamos camelCase em geral, nomes de função começam em letra minúscula e Nomes de objeto começam em maiúsculo (checar isso)
	linha1 e linha2, public : Denota que aquilo que está designado por "public" faz parte da API

	linha1, Cliente : aqui, o "cliente" denota em qual arquivo esse trecho tem que estar (no cliente.java).

	linha2, public static : O public static mostra que é função.

	linha2, string[]args : ssim que eu defino o main, como se fosse no C. ele toma como argumento um vetor de strings

	linha3, new bagInteger() : o bagInteger é a classe, o new instancia um novo objeto chamando o método construtor(que nem no js, python...)

	linha10, integer : é a mesma coisa que fazer um int*, ele se refere a o endereço, chamamos esse tipo de dado de variavel de referencia (como se fosse um ponteiro) : as variaveis de referencia são referenciadas pelo tipo de dado mas com a primeira letra maiúscula (Integer, Boolean, Float...).

*/

A api permite apenas um iterador, mas queremos vários.