Array ➡ pesquisa
Lista ligada ➡ inserção/remoção sob demanda
Uma estrutura de dados é composta por dados/operações e algoritmos
Programa = estrutura de dados + algoritmos
Alocação Estática: Arrays; elementos constantes; aloca espaços de acordo com o número de elementos
Alocação Dinâmica: Ponteiros; não há um máximo de dados de elementos; usa espaço suficiente para um dado elemento
Tipo Abstrato de Dados (ADT)
Contém duas partes:
Dados armazenados
Funções que manipulam os dados
Encapsulamento de dados e operações
Os dados podem ser armazenados em variáveis, arrays ou ponteiros
As funções implementam procedimentos através de subprogramas chamados operações, métodos ou serviços
INSERIR | REMOVER | CONSULTAR
Fila
Estrutura linear
FIFO - primeiro a entrar, primeiro a sair
Inserção no final
Remoção no início
código
publicclassQueue { privateint capacity;privateint size;privateint[] data;publicQueue(int c) { capacity = c; size =0; data =newint[capacity]; }publicbooleanisEmpty() {return size ==0; }publicbooleanisFull() {return size == capacity; }// insere no fimpublicvoidenqueue(int d) { if (isFull()) {System.out.print("Full!"); } else { data[size] = d; size++; } }// remove do topopublicvoiddequeue() { if (isEmpty()) {System.out.print("\nEmpty!"); }for (int i=0; i < size-1; i++) { data[i] = data[i+1]; } size--; }publicvoidprint() {if(isEmpty()) { } else {System.out.println();for (int i=0; i < size; i++) {System.out.print(data[i] +" "); } } }}
Sequência de elementos chamados nós, onde cada nó está conectado ao próximo nó por meio de um ponteiro
dados - informação armazenada | próximo - ponteiro para o próximo nó
cabeça - primeiro nó | cauda - último nó (ponta para NULL)
código
publicclassLinkedList { Node head;// adiciona um nó no primeiro índice, substitui nó cabeçapublicvoidaddHead(int d) {Node newNode =newNode(d);newNode.next= head; // liga novo nó com antiga cabeça head = newNode; }// insere no fimpublicvoidappendNode(int d) { Node current = head; // ponteiro temporárioNode newNode =newNode(d);if (isEmpty())appendNode(d);else {// loop para procurar último nówhile (current.next!=null) { current =current.next; }current.next= newNode; } }publicNoderemoveHead() {Node aux =null;if (!isEmpty()) { head =head.next; }return aux; }publicNodesearch(int d) {Node aux =null;Node current = head; // ponteiro temporário// loop para percorrer listawhile (current !=null) {if (current.data== d) { aux = current;break; } current =current.next; }return aux; }// loop simplificadopublicNodesearch2(int d) {Node aux =null;Node current = head;// une todas as condições/// for ( inicialização; condição; incremento)for(; current!=null&¤t.data!=d; current=current.next) { }// quando valor é encontrado aux = current;return aux; }publicbooleanisEmpty() {return head ==null; }publicvoidprint() {No current = head;while (current !=null ) {System.out.print(current.data+" "); current =current.next; }System.out.println(); }}
Dividir para conquistar ➡ divide um problema maior em um problema recursivo menor
A chave é o particionamento
Escolhe um pivô e divide o array em torno do pivô escolhido
Então, usando dois ponteiros, um para a esquerda e outro p/ a direita, compara os números ao pivô
Os números menores que o pivô vão p/ o lado esquerdo e os maiores p/ o lado direito
Merge Sort
Também divide para conquistar
Divide o array pela metade, então continua dividindo até que fique em grupos menores
Compara os elementos de um grupo com outro para organizá-los em ordem, então mescla os elementos em um grupo maior
E continua até que o array esteja totalmente unido e em ordem
código
publicstaticvoidmergeSort(int[] array) {int sizeArray =array.length;if(sizeArray <2) { // se houver somente 1 elementoreturn; }int middle = sizeArray /2; int[] left =newint[middle]; // parte esquerdaint[] right =newint[sizeArray - middle]; // parte direita// capacidade do array = tam vetor - meio (para calcular array com tamanho impar)// Preenchendo os Arraysfor(int i=0; i < middle; i++) { // início até o meio left[i] = array[i]; }for(int i=middle; i < sizeArray; i++) { // meio até o final right[i - middle] = array[i]; // [i - meio] para iniciar na posição 0 do vetor// já que o contador/index "i" inicia em "meio" }// Chamada recursiva para divisão dos vetoresmergeSort(left);mergeSort(right);// Unindo as metadesmerge(array, left, right);}publicstaticvoidmerge(int[] array,int[] left,int[] right) {int leftSize =left.length;int rightSize =right.length;// index/contadoresint iL=0,// esquerda iR=0,// direita iA=0; // vetor de merge// loop até esgotar os elementoswhile (iL < leftSize && iR < rightSize) { if (left[iL] <= right[iR]) { array[iA] = left[iL]; iL++; } else { array[iA] = right[iR]; iR++; } iA++; }// Como o loop continua até acabarem os elementos de 1 dos arrays// precisa-se confirmar se há elementos restantes// Adicionando elementos da esquerda, se ainda houverwhile(iL < leftSize) { array[iA] = left[iL]; iL++; iA++; }// Adicionando elementos da direita, se ainda houverwhile(iR < rightSize) { array[iA] = right[iR]; iR++; iA++; }}
Árvores
Estrutura composta por um nó raiz e abaixo dela suas subárvores
Cada nó tem um "nó pai"
Nós que não têm filhos são chamados de folhas
Valores menores que o nó pai vão a sua esquerda e maiores a direita
Grau: Número de filhos de um nó
Grau máximo de uma árvore identifica tipo de árvore (binária, ternária etc)
Altura (h): Número máximo de links/arestas no caminho mais longo entre um nó e o último nó folha
Altura de uma árvore = altura da raiz
Árvore Binária: Abaixo de cada nó podem ter no máximo dois filhos
Árvore Estritamente Binária: Árvore binária em que todo nó que não é folha tem subárvores esquerda e direita
Árvore Binária Completa: Se uma árvore binária contém m nós no nível k, ela conterá 2m nós no nível k+1
publicclassTree {Node root;publicbooleanisEmpty() {return root ==null; }publicvoidadd(int value) {Node newNode =newNode(value);if (isEmpty()) { root = newNode; } else {Node temp = root, last = root;while (temp !=null) { last = temp;if (value ==temp.value)break;if (value >temp.value) temp =temp.right;else temp =temp.left; } if (value ==last.value)System.out.println(value +" - Value already exists!");elseif (value >last.value)last.right= newNode;elselast.left= newNode; } }publicbooleandelete(Node startNode,int key) {if (isEmpty()) {System.out.println("Tree is empty!");returnfalse; }Node current, parentNode; current =search(startNode, key); // nó atual parentNode =searchParent(startNode, key); // pai do nó atualif (current ==null) {System.out.println("No item to delete!");returnfalse; }Node replacement, parentReplacement;// Se não há nós a esquerda e/ou a direita do nó atual// Nó a ser excluido tem 0 ou 1 filhoif (current.left==null||current.right==null) {if (current.left!=null) replacement =current.left;else replacement =current.right;if (parentNode ==null) // raiz não tem paithis.root= replacement;else {// Atribui a atual o valor do substituto selecionadoif (parentNode.left== current)parentNode.left= replacement;elseparentNode.right= replacement; } current =null; // remove nó atual// Se há nós a esquerda e a direita do nó atual// Nó a ser excluido tem 2 filhos } else { // Encontra maior valor a esquerda para manter ordenação replacement =leftLargest(current); // Busca pai do nó atual parentReplacement =searchParent(this.root,replacement.value);// Atribui a atual o valor do substituto selecionadocurrent.value=replacement.value;/* Remove valor nó substituto, dado que * valor já foi reinserido na árvore * no lugar do nó atual */if (parentReplacement!=null)if (parentReplacement.left== replacement)parentReplacement.left=replacement.left;elseparentReplacement.right=replacement.left; replacement =null; }returntrue; }// Métodos para buscapublicNodesearch(Node temp,int value) {if (temp!=null)if (value >temp.value)returnsearch(temp.right, value);elseif (value <temp.value)returnsearch(temp.left, value);return temp; }publicNodesearchParent(Node root,int value) {Node temp = root; // starts from rootNode parent =null; // null because root doesn't have a parentwhile (temp!=null&&temp.value!= value) { parent = temp; // update parent of searched valueif (value >temp.value) temp =temp.right;else temp =temp.left; }return parent; }/// busca elemento mais próximo do nó a ser removido/// maior número a esquerda, porém, ainda menor que o nó atualpublicNodeleftLargest(Node node) { node =node.left;if (node!=null) {while (node.right!=null) { node =node.right; } }return node; }publicvoidprintPreOrder(Node root) {if (root ==null)return;System.out.print(root.value+" ");printPreOrder(root.left);printPreOrder(root.right); }// Impressão da ÁrvorepublicvoidprintInOrder(Node root) {if (root ==null)return;printInOrder(root.left);System.out.print(root.value+" ");printInOrder(root.right); }publicvoidprintPostOrder(Node root) {if (root ==null)return;printPostOrder(root.left);printPostOrder(root.right);System.out.print(root.value+" "); }}
Tabela Hash
Tabela de dispersão ou espalhamento
Endereçamento direto
Por meio de uma função de hash, transforma chaves em endereços de uma tabela
n chaves para serem armazenadas em uma tabela T de tamanho m, as posições da tabela estão no intervalo [0, m-1]
transforma cada chave x em um endereço-base h(x)
se h(x) estiver desocupado, armazena-se a chave x
Hash é uma estrutura de dados do tipo dicionário
não permite elementos repetidos
não permite recuperar elementos sequencialmente (ordenado)
Funções de HashMétodo da Divisão
simples e amplamente utilizado
chave x é dividida pela dimensão da tabela m e o resto da divisão é usado como endereço da chave
deve-se escolher bem o valor de m para bons resultados práticos; deixar espaços livres para casos de colisão, porém não a ponto de ser desperdício de memória
m deve ser um número primo não próximo a uma potência de 2
m não deve possuir divisores primos menores que 20
Colisão: Quando o cálculo da função de hash retorna endereços iguais para chaves distintas, sendo necessário um tratamento de colisão
Tratamento de Colisão - TécnicasEncadeamento: Informação é armazenada em estruturas encadeadas; tabela armazena ponteiros para uma lista ligada de elementos com mesmo endereço
Endereçamento Aberto: Informação é armazenada na própria tabela hash, sem utilização de ponteiros; redução no consumo de memória
Rehash Linear: função hash para gerar sequências de tentativas