Baixe o app para aproveitar ainda mais
Prévia do material em texto
Tecnologia em Análise e Desenvolvimento de Sistemas Linguagem de Programação e Estrutura de dados Profª.Me.Merris Mozer TA1 Introdução Introdução da Aula 1 O que é Algoritmo? Entradas; Saídas; Processamento; Escopo; Eficiência. Introdução Por definição um algoritmo é um conjunto determinado de instruções (Ações) que, quando seguidas desempenham uma tarefa particular, e dependem da representação e da estrutura de dados. 1. Retirar um ovo da geladeira 2. Colocar a frigideira no fogo 3. Esperar até o óleo ficar quente 4. Colocar óleo 5. Quebrar o ovo separando a casca 6. Colocar o conteúdo do ovo na frigideira 7. Esperar um minuto 8. Retirar o ovo da frigideira 9. Apagar o fogo Introdução Exemplo: Como fritar um ovo ? 1. Retirar um ovo da geladeira 2. Colocar a frigideira no fogo 3. Colocar óleo 4. Esperar até o óleo ficar quente 5. Quebrar o ovo separando a casca 6. Colocar o conteúdo do ovo na frigideira 7. Esperar um minuto 8. Retirar o ovo da frigideira 9. Apagar o fogo Introdução Exemplo: Como fritar um ovo ? 1. Ir até o caixa eletrônico 2. Colocar o cartão no local solicitado 3. Digitar a senha solicitada 4. Solicitar a quantia a desejada a ser retirada 5. Se o saldo for maior ou igual a quantia desejada • 5.1. Sacar o dinheiro 6. Senão • 6.1. Mostrar uma mensagem de saldo insuficiente 7. Retirar o cartão 8. Sair do banco e ir embora Introdução Exemplo: Sacar dinheiro no caixa eletrônico Máquinas manejam dados; Linguagens descrevem a manipulação de dados; Mecanismos para obter dados refinados (viabilidade); Estruturas para representação dos dados (performance). Introdução Ciência da Computação é o estudo dos dados. Enfim, Estrutura de Dados é a maneira que será armazenado e organizado os dados num computador. Introdução Nenhum dos dois faz sentido sem o outro. Introdução Estrutura de dados e algoritmo devem ser considerados como unidades distintas e complementares, ou seja, são interligadas de modo inseparável. Assim, são necessários por exemplo para as disciplinas de Algoritmos, Técnicas de Programação, POO e Banco Dados. Profª.Me.Merris Mozer Tecnologia em Análise e Desenvolvimento de Sistemas TA2 Listas Estáticas Lineares Listas desordenadas: { 33, 18, 56, -1, 50} Listas ordenadas • {“Antônio”, “Carlos”, “Sérgio”, “Thago”} • Onde inserir o Paulo? Listas disciplinadas • PILHA • FILA Primeira Estrutura de Dados - LISTAS LISTAS conhecidas: Listas Estáticas (Arranjo) Listas Dinâmicas (Ponteiros) Introdução em Listas Estáticas Lineares Tipo de Alocação (Armazenamento) Relação de precedência; x1 é o primeiro elemento; ...........X = {x1 , x2 , ... , xn} xn é o último elemento; ..............X = {x1 , x2 , ... , xn} xk precede xk+1 quando 0 < k < n. X = {x1 , x2 , ... , xn} Listas Estáticas Lineares Conjunto de Nodos X = {x1 , x2 , ... , xn} pessoas em fila; vagões de um trem; letras de uma palavra; palavras de uma frase. Lista de compra de mercado; Listas Estáticas Lineares Exemplos práticos de listas lineares: O que é o Nodo? Parte da estrutura de dados responsável por armazenar a informação em questão. Listas Lineares O que é nodo? Listas Lineares acessar o késimo nodo; inserir um novo nodo; eliminar o késimo nodo; emendar duas listas; partir duas listas; copiar uma lista; determinar nº nodos; classificar a lista; pesquisar valor na lista. Operações Mais Comuns Regras definidas quanto as operações. Listas Lineares Casos Particulares de listas que nos interessam: Por que nos interessam? Por que são casos particulares? Lista Linear de Fila; Lista Linear de Pilha; amplamente utilizadas na informática. Profª.Me.Merris Mozer Tecnologia em Análise e Desenvolvimento de Sistemas TA3 Listas Estáticas Lineares com disciplina de FILA Regra das operações: Inserções: • sempre no final; Exclusões: • sempre no início; Pesquisa: • à partir do início. Listas Estáticas Lineares com disciplina de FILA Lista FIFO - First in First Out Caixa de Banco; Atendimento Ambulatorial; Lista de compra de mercado; Listas Estáticas Lineares com disciplina de FILA Exemplos Práticos de Fila: Montando uma fila O primeiro elemento a entrar na fila será o primeiro a sair (PEPS) Novos elementos são armazenados no final da fila DESmontando uma fila DESmontando uma fila DESmontando uma fila Compartilhamento de periféricos; Gerência de redes; Algoritmos de processamento de imagens; Lista de Impressão; Listas Estáticas Lineares com disciplina de FILA Exemplos Práticos de Fila para Informática: Profª.Me.Merris Mozer Tecnologia em Análise e Desenvolvimento de Sistemas TA4 Listas Estáticas Lineares com disciplina de PILHA Regra das operações: Inserções: • sempre no topo; Exclusões: • sempre no topo; Pesquisa: • à partir do topo. Listas Estáticas Lineares com disciplina de PILHA Lista LIFO - Last in First Out Exemplos Práticos de Pilha: Pilha de pratos; Pilha de caixas em estoque; Pilhas de um modo geral. Listas Estática Lineares com disciplina de PILHA Montando uma PILHA Os elementos da pilha O último elemento que entrou na pilha será o primeiro a sair (UEPS) Novos elementos são armazenados no topo da pilha Exemplos Práticos de Pilha para informática: Avaliação de expressões aritméticas; Construção de compiladores; Gerência de memória. Listas Estáticas Lineares com disciplina de PILHA Listas Estáticas Lineares Dois controladores COMEÇO e FIM. Somente um controlador TOPO. Qual estrutura de lista linear a imagem abaixo indica? Profª.Me.Merris Mozer Tecnologia em Análise e Desenvolvimento de Sistemas TA5 Listas Estáticas Lineares com disciplina de PILHA Alessandro Volta 1 2 - -1 4 5 + -1 9 * -9 Um bom exemplo é o navegador de internet; Outro exemplo é o funcionamento das calculadoras da HP(Hewlett-Packard), como empilharia a expressão (1-2)*(4+5) ? Exemplos de uso de PILHA: Calculadora pós-fixada Observe … Qual estrutura é utilizada, FILA ou PILHA, na imagem da cegonha acima ? Observe … Qual estrutura é utilizada, FILA ou PILHA, na imagem acima ? Implementação de Listas precisamos de: Utilização de vetores; Posições sequenciais de memória; Limite de armazenamento; Índice numérico para referenciar posição. Listas Estáticas Lineares Alocação Sequencial Fernando PaulaFelipeAmanda Implementação das operações de inserção, pesquisa, modificação e exclusão em uma lista linear de pilha por alocação sequencial. Listas Estáticas Lineares de Pilha - Alocação Sequencial Inserção: da variável Y para V.............. Exclusão: de V para variável Y ............ Pesquisa: localiza variável Y em V....... Modificação: localiza variável Y em V; troca valor de V pela variável X ........... Listas Estáticas Lineares de Pilha - Alocação Sequencial YV Y ? V XY ? V YV Profª.Me.Merris Mozer Tecnologia em Análise e Desenvolvimento de Sistemas TA6 Listas Estáticas Lineares com disciplina de PILHA YV Definir valor para TOPO Definir valor para N Definir valor o conteúdo de Y Listas lineares de pilha Alocação sequencial – Inserção se TOPO= n então OVERFLOW; senão TOPO := TOPO +1; V[TOPO] := Y; fim se; YV Listas lineares de pilha Alocação sequencial – Inserção TOPO= n=5 Y= Sofia Cleia Flávia Aline Silvia Topo = 1 Topo = 2 Topo = 3 Topo = 4 Topo = 5 YV Listas lineares de pilha Alocação sequencial – Exclusão TOPO começa em 5 n=5 Y= Topo = 1 Topo = 2 Topo = 3 Topo = 4 Topo = 5 se TOPO = 0 então UNDERFLOW; senão Y:= V[TOPO]; TOPO := TOPO - 1; fim se; SilviaAlineFláviaCleiaSofia
Compartilhar