Baixe o app para aproveitar ainda mais
Prévia do material em texto
Aula 2 – Revisão Algoritmo e Estrutura de Dados III SIF 130 Vanessa Souza Universidade Federal de Itajubá – Instituto de Matemática e Computação Tipo Abstrato de Dados (TAD) Um tipo abstrato de dados é formado por um conjunto de valores e por uma série de operações que podem ser aplicadas sobre esses valores. Um TAD estabelece o conceito de tipo de dado divorciado da sua representação (modelo matemático). Na representação de um TAD, emprega-se uma estrutura de dados. Tipo Abstrato de Dados (TAD) Exemplo : considere uma aplicação que utilize uma lista de inteiros. Conjunto de valores : LISTA de inteiros Operações: Crie a lista vazia Obtenha o primeiro elemento da lista; se a lista estiver vazia, então retorne nulo Insira um elemento na lista Exclua um elemento na lista Estruturas de Dados Meio para armazenar e organizar dados na memória com o objetivo de facilitar o acesso e as modificações. As estruturas diferem umas das outras pela disposição ou manipulação de seus dados. Podem ser estáticas ou dinâmicas Estruturas de Dados– Vetor Estático A forma mais simples de uma estrutura de dados é denominada Vetor, onde os elementos são armazenados na memória de forma indexada e contínua. Vetor estático Estruturas de Dados– Vetor Estático A forma mais simples de uma estrutura de dados é denominada Vetor, onde os elementos são armazenados na memória de forma indexada e contínua. Vetor estático Posições contínuas de memória!! Seu tamanho e localização na memória não se alteram durante a execução Estruturas de Dados– Vetor Estático A referência a uma posição de um vetor indica o cálculo de uma posição de memória a partir do início do vetor vet[3] = vet + 3*sizeof(int) vet Estruturas de Dados– Vetor Estático A referência a uma posição de um vetor indica o cálculo de uma posição de memória a partir do início do vetor vet[3] = vet + 3*sizeof(int) vet Estruturas de Dados– Matriz E uma matriz?? Estruturas de Dados– Matriz Estática E uma matriz?? mat[l][c]= mat + (l*tamCol + coluna)*sizeof(int) mat[1][0]= mat + (1*2 + 0)*sizeof(int) mat Estruturas de Dados Vetor X TAD Matriz X TAD Estruturas de Dados Vetor X TAD Criar vetor vazio Instanciar elementos no vetor Acessar elementos no vetor Estruturas de Dados Estruturas de dados estáticas são mais simples e fáceis de usar. Mas para a maioria das aplicações não se sabe a priori o número de elementos necessários na resolução do problema. Solução : ESTRUTURAS DE DADOS DINÂMICAS a quantidade de elementos pode ser alterada sempre que necessário. Estruturas de Dados Dinâmicas Estruturas de dados encadeadas são mais convenientes para estes tipos de problemas, pois: Evitam-se as movimentações de dados nas operações de inclusão e exclusão de dados. O esforço computacional destas operações é, praticamente, constante. Estruturas de Dados Dinâmicas A alocação dinâmica de memória é a base das estruturas dinâmicas de dados. Uma estrutura dinâmica de dados é, tipicamente um conjunto de nós (nodes) ligados por um conjunto de arcos direcionados (directed edge) entre esses nós. Os nós contêm a informação e os arcos são ligações funcionais entre os nós que permitem percorrer a estrutura de dados. Estruturas de Dados Dinâmicas Assim, o elemento da estrutura de dados deve conter as informações que serão armazenadas por ela e o(s) ponteiro(s) representando os arcos. Exemplo : Lista de Vinhos Estruturas de Dados Dinâmicas Assim, o elemento da estrutura de dados deve conter as informações que serão armazenadas por ela e o(s) ponteiro(s) representando os arcos. Exemplo : Lista de Vinhos Codigo Safra prox Tipo Estruturas de Dados Dinâmicas As operações sobre um conjunto dinâmico podem ser agrupadas em duas categorias: Consulta Retorna informações sobre o conjunto procuraElemento(S, x) MenorElemento(S) MaiorElemento(S) Vazio(S) Operações de Modificação Alteram o conjunto insereElemento(S,x) removeElemento(S,x) alteraElemento(S,x,A, k) Estruturas de Dados Dinâmicas As operações sobre um conjunto dinâmico podem ser agrupadas em duas categorias: Consulta Retorna informações sobre o conjunto procuraCodigoVinho(Lista, codigo) procuraSafraVinho(Lista, safra) VinhoSafraMaisAntiga(Lista) VinhoSafraMaisNova(Lista) Vazio(Lista) Operações de Modificação Alteram o conjunto insereVinho(Lista, vinho) removeVinho(Lista, codigo) alteraVinho(Lista, codigo, atributoAlterado, novoValor) Estruturas de Dados Dinâmicas Estruturas de dados Elementares Lista Fila Pilha Árvore binária Avançadas Árvores balanceadas Hash Grafos Estruturas de Dados Dinâmicas O que diferencia uma estrutura da outra? Estruturas de dados Elementares Lista Fila Pilha Árvore binária Avançadas Árvores balanceadas Hash Grafos Estruturas de Dados Dinâmicas O QUE VOCÊ PRECISA GUARDAR? COMO VOCÊ PRECISA GUARDAR? O QUE VOCÊ PRECISA FAZER COM ESSES DADOS? Estruturas de Dados Dinâmicas O QUE VOCÊ PRECISA GUARDAR? Dado COMO VOCÊ PRECISA GUARDAR? Estrutura de Dados O QUE VOCÊ PRECISA FAZER COM ESSES DADOS? Operações Estruturas de dados Elementares Lista Fila Pilha Árvore binária Avançadas Árvores balanceadas Hash Grafos Estruturas de Dados Dinâmicas LISTA Listas Estrutura de dados em que os objetos estão organizados em uma ordem linear. Diferente de um vetor, a ordem linear é determinada por um ponteiro em cada objeto. Operações: Inserir Onde? Remover Onde? Consultar Elemento, maior, menor, vazia Listas Qual o endereço de memória do elemento 4? Listas prox endereço de memória prox Listas Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa lista ligada ordenada de forma crescente. Listas Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa lista ligada ordenada de forma crescente. 3 Listas Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa lista ligada ordenada de forma crescente. 3 4 Listas Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa lista ligada ordenada de forma crescente. 3 4 5 Listas Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa lista ligada ordenada de forma crescente. 3 4 5 6 Listas Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa lista ligada ordenada de forma crescente. 3 4 5 6 Início da Lista Fim da Lista Listas Exemplo: Inserir o elemento 1 à lista criada 3 4 5 6 Início da Lista Fim da Lista Listas Exemplo: Inserir o elemento 1 à lista criada 3 4 5 6 Início da Lista Fim da Lista Instanciar o objeto 1 1 Listas Exemplo: Inserir o elemento 1 à lista criada 3 4 5 6 Início da Lista Fim da Lista Encontrar o local correto (primeiro número maior que 1) Listas Exemplo: Inserir o elemento 1 à lista criada 3 4 5 6 Início da Lista Fim da Lista 1 Movimentar os ponteiros e, nesse caso, o início da lista passa a ser o elemento 1. Listas Exemplo: Inserir o elemento8 à lista criada 3 4 5 6 Início da Lista Fim da Lista 1 Listas Exemplo: Inserir o elemento 8 à lista criada 3 4 5 6 Início da Lista Fim da Lista 1 8 Movimentar os ponteiros e, nesse caso, o fim da lista passa a ser o elemento 8. Listas Exemplo: Inserir o elemento 7 à lista criada 3 4 5 6 Início da Lista Fim da Lista 1 8 Listas Exemplo: Inserir o elemento 7 à lista criada 3 4 5 6 Início da Lista Fim da Lista 1 8 Instanciar o objeto 7 e encontrar o local correto para inserir 7 Listas Exemplo: Inserir o elemento 7 à lista criada 3 4 5 6 Início da Lista Fim da Lista 1 8 7 Movimentar os ponteiros Listas Sentinelas Objeto fictício que nos permite especificar condições limites. 3 4 5 6 Início da Lista Fim da Lista 1 8 7 Cabeça Listas Sentinelas Objeto fictício que nos permite especificar condições limites. 3 4 5 6 Início da Lista Fim da Lista 1 8 7 Cabeça Com o "list head", os “casos especiais” não serão mais necessários!! Listas Remover o elemento 4 da lista 3 4 5 6 Início da Lista Fim da Lista 1 8 7 Cabeça Listas Remover o elemento 4 da lista 3 4 5 6 Início da Lista Fim da Lista 1 8 7 Cabeça Encontrar o elemento na lista Listas Remover o elemento 4 da lista 3 4 5 6 Início da Lista Fim da Lista 1 8 7 Cabeça Movimentar os ponteiros Listas Remover o elemento 4 da lista 3 5 6 Início da Lista Fim da Lista 1 8 7 Cabeça Liberar a memória Vetor x Lista Vetor existe uma ordenação física dos elementos (posições consecutivas de memória). As movimentações de dados são necessárias para manter o vetor ordenado "sem buracos". Lista encadeada existe uma ordenação lógica dos elementos da lista (os elementos da lista ocupam posições quaisquer de memória, não necessariamente consecutivas). É preciso indicar (por meio de um outro ponteiro) qual é o “primeiro” elemento da lista. Lista – Tipos especiais Lista duplamente encadeada 3 5 6 1 8 7 Cabeça contém não apenas ponteiros para o “próximo” elemento, como também ponteiros para o elemento “anterior”. List Tail Lista – Tipos Especiais Lista circular 3 5 6 1 8 7 Cabeça Numa lista circular, o ponteiro prox do “último” elemento aponta para o “primeiro” elemento da lista e o ponteiro ant do “primeiro” elemento aponta para o “último” elemento da lista. Estruturas de dados Elementares Lista Fila Pilha Árvore binária Avançadas Árvores balanceadas Hash Grafos Estruturas de Dados Dinâmicas Filas Como as pilhas, as filas também têm um papel muito importante na Ciência da Computação. Aplicações envolvendo filas são muito comuns em situações nas quais é preciso “esperar sua vez” para ter acesso a algum serviço. Exemplo: filas de processos para serem executados pelo sistema operacional. Normalmente, estes processos correspondem a tarefas que competem entre si por um determinado recurso, como tarefas esperando para serem impressas ou tarefas esperando por uma fatia de tempo do processador. Em alguns casos, existe uma ordem de prioridade para atendimento aos elementos de uma fila (fila de prioridades). Filas Estrutura de dados que implementa a norma primeiro a entrar, primeiro a sair ou FIFO (First In First Out). Principais operações: Verifica se a fila está vazia ou não Inclui um novo elemento no fim da fila Exclui o elemento do início da fila Outras operações: Excluir todos os elementos da fila Retornar o primeiro elemento da fila, sem excluí-lo Retornar o último elemento da fila, sem excluí-lo Listas Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa fila. Listas Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa fila. 3 4 5 6 Início da fila Fim da fila Listas Exemplo: Remover elemento da fila. 3 4 5 6 Início da fila Fim da fila Listas Exemplo: Remover elemento da fila. 3 4 5 6 Início da fila Fim da fila Sempre sai o primeiro da fila Listas Exemplo: Remover elemento da fila. 4 5 6 Início da fila Fim da fila Limpa memória Estruturas de dados Elementares Lista Fila Pilha Árvore binária Avançadas Árvores balanceadas Hash Grafos Estruturas de Dados Dinâmicas Pilha A pilha é uma das estruturas de dados mais importantes na Ciência da Computação. Imagine, por exemplo, que um programa contém três funções: A, B e C. Considere que a função A chama B e B chama a função C. Evidentemente, a função B não pode terminar seu processamento enquanto a função C não retornar. Analogamente, A não pode terminar enquanto B não retornar de seu processamento. Portanto, as funções A, B e C têm a propriedade “a última função que começou sua execução será a primeira função a terminar seu processamento”. Como cada função necessita de seus próprios dados, esses dados devem ser alocados em uma estrutura que apresenta esta mesma propriedade, ou seja, uma pilha. Pilha Outra aplicação importante das pilhas é a avaliação de expressões aritméticas escritas na forma posfixa (notação polonesa). Avaliar fechamento de parênteses Funções recursivas em compiladores; Mecanismo de desfazer/refazer dos editores de texto; Navegação entre páginas Web; Pilha Estrutura de dados que implementa uma norma de último a entrar, primeiro a sair, ou LIFO (Last In First Out). Pilha Estrutura de dados que implementa uma norma de último a entrar, primeiro a sair, ou LIFO (Last In First Out). Operações Básicas: Empilhar Desempilhar Verifica se a pilha está vazia Outras operações: Excluir todos os elementos da pilha Retornar o topo da pilha sem excluí-lo. Pilha A operação INSERT sobre uma pilha é chamada PUSH. A operação DELETE é chamada POP. O topo é sempre o começo da lista. Só insere e remove do começo da lista!!! Pilha Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa pilha. Pilha Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa pilha. 3 Topo Push(P, 3) Pilha Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa pilha. 3 Topo Push(P, 4) 4 Pilha Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa pilha. 3 Topo Push(P, 5) 4 5 Pilha Exemplo: Representar o conjunto dinâmico {3, 4, 5, 6} numa pilha. 3 Topo Push(P, 6) 4 5 6 Pilha Exemplo: Remover elemento da pilha 3 Topo Pop(P) O argumento do Pop é só a pilha. PQ?? 4 5 6 Pilha Exemplo: Remover elemento da pilha 3 Topo Pop(P) Mudar o top 4 5 6 Pilha Exemplo: Remover elemento da pilha 3 Topo Pop(P) Liberar memória 4 5 RECURSIVIDADE Recursividade Um método que chama a si mesmo, direta ou indiretamente, é dito recursivo. Exemplo : Fibonacci A sucessão de Fibonacci ou sequência de Fibonacci é uma sequência de números naturais, na qual os primeiros dois termos são 0 e 1, e cada termo subsequente corresponde à soma dos dois precedentes. Recursividade Recursividade fatorial(5) fatorial(4)*5 Recursividade fatorial(5) fatorial(3)*4 fatorial(4)*5 Recursividade fatorial(5) fatorial(2)*3 fatorial(3)*4 fatorial(4)*5 Recursividade fatorial(5) fatorial(1)*2 fatorial(2)*3 fatorial(3)*4 fatorial(4)*5 Recursividade fatorial(5) fatorial(1) fatorial(1)*2 fatorial(2)*3 fatorial(3)*4 fatorial(4)*5 Recursividade fatorial(5) 1 fatorial(1)*2 fatorial(2)*3 fatorial(3)*4 fatorial(4)*5 Recursividade fatorial(5) 1 1*2 = 2 fatorial(2)*3 fatorial(3)*4 fatorial(4)*5 Recursividade fatorial(5) 1 1*2 = 2 2*3 = 6 fatorial(3)*4 fatorial(4)*5 Recursividade fatorial(5) 1 1*2 = 2 2*3 = 6 6*4 = 24 fatorial(4)*5 Recursividade fatorial(5) 1 1*2 = 2 2*3 = 6 6*4 = 24 24*5=120 Recursividade Vantagens Simplifica a solução de alguns problemas Algoritmos recursivos são mais compactos para alguns tipos de algoritmo, mais legíveis e mais fáceis de ser compreendidos e implementados. Desvantagens Por usarem intensamente a pilha de execução, os algoritmos recursivos tendem a ser mais lentos e a consumir mais memória que os iterativos, porém pode valer a pena sacrificar a eficiência em benefício da clareza. Erros de implementação podem levar a estoure de pilha. Recursividade Quadro comparativo da execução de algoritmos para o cálculo do Fibonacci. Evitar uso de recursividade quando existe uma solução óbvia por iteração. n 10 20 30 50 100 Recursivo 8 ms 1 s 2 min 21 dias 109 anos Iterativo 0.17 ms 0.33 ms 0.5 ms 0.75 ms 1.5 ms Estruturas de Dados Básicas Ok, eu sei como funciona uma lista, fila e pilha. Mas como implementa isso? Estruturas de Dados Dinâmicas O QUE VOCÊ PRECISA GUARDAR? Dado COMO VOCÊ PRECISA GUARDAR? Estrutura de Dados O QUE VOCÊ PRECISA FAZER COM ESSES DADOS? Operações Estruturas de Dados Dinâmicas O QUE VOCÊ PRECISA GUARDAR? Dado Vinho COMO VOCÊ PRECISA GUARDAR? Estrutura de Dados Lista Ordenada O QUE VOCÊ PRECISA FAZER COM ESSES DADOS? Operações Inserir, Remover, Consultar pelo código, pela safra e pelo tipo Listas Operação : Iniciar lista Inicializar lista vazia : Cabeça da Lista Listas Operação : Iniciar lista Cabeça da Lista Listas Operação : Iniciar lista Cabeça da Lista Listas Operação : Iniciar lista Forma + correta Cabeça da Lista Listas Inserir ordenado código 1 Listas Inserir ordenado código 8 Listas Inserir ordenado código 7 Listas Inserir ordenado código 7 Instanciar vinho de código 7 prox do objeto 7 aponta para o prox do objeto 6; prox do objeto 6 aponta para o novo objeto; Listas Listas Exercício Implementar uma lista simplesmente encadeada de produtos. Cada um dos registros (produto) deve conter: Código (inteiro sem sinal) Nome (string de 50 caracteres) Preço (float) Estoque (inteiro sem sinal) Os produtos devem ser lidos de um arquivo chamado entrada.txt Considerar que o código do produto é único Exercício A lista deve estar sempre ordenada de forma crescente pelo código do produto e suporta as seguintes operações: Inicializa lista Insere na lista Remove da lista Mostra elementos da lista Consulta produto na lista pelo nome Soma quantidade total em estoque (soma do estoque de todos os produtos) Calcula a média dos preços dos produtos Encontrar os produtos de maior e menor preços
Compartilhar