Baixe o app para aproveitar ainda mais
Prévia do material em texto
ESTRUTURA DE DADOS Profa. Jane Mestre em Engenharia de Sistemas e Computação COPPE /UFRJ Aula 1- parte 1 AULA 1 Unidade 1 Introdução Revisão de vetor/matriz 2 MOTIVAÇÃO PARA O ESTUDO DE ESTRUTURA DE DADOS Para a solução de um problema é importante determinarmos uma abstração da realidade, o que significa representar as informações (dados) que são relevantes para a solução deste problema. A abstração pode ser vista como uma simplificação dos dados. Exemplo : Considere um cadastro de alunos de uma escola. Existem dados relevantes (nome, matrícula, disciplinas, ano ...) e irrelevantes (cor dos olhos do aluno, cor da mochila, marca da borracha ...). 3 Como escolher os dados relevantes ? Analisando as características do problema a ser resolvido. Uma vez feito isto, como representar estas informações ? A escolha da forma de representar os dados não é trivial e vai depender das relações existentes entre tais dados, ou seja, da organização dos dados e também, da forma com que eles serão manipulados para a solução do problema. 4 Niklaus Wirth : programa = algoritmo + dados Para programar é fundamental sabermos como organizar (estruturar) os dados dos nossos programas e realizar operações (manipulações) sobre tais dados, através das instruções dos algoritmos. 5 PORTANTO : As estruturas de dados estudam as relações lógicas existentes entre os dados (ex: relação linear, relação hierárquica ..) e serão manipuladas através de operações sobre os dados (ex: consultar uma informação em um conjunto de fichas de alunos, remover um assinante de uma lista de assinantes, apagar um diretório em uma árvore de diretórios e subdiretórios...). A escolha da estrutura de dados a ser utilizada, refletirá diretamente na construção de uma solução mais eficiente ou menos eficiente para o problema. 6 NÃO FAÇA CONFUSÃO DE ... Estrutura de dados ≠ tipos de dados. Note que os tipos de dados dividem-se em : Tipos primitivos : estão embutidos na linguagem. Exemplos no C++ : os tipos int, float, double, char, bool. Tipos agregados : podem ser construídos. Exemplos : vetor (array), matriz, registro (no C/C++ usamos a palavra reservada struct para criar registro) 7 EXEMPLOS DE ESTRUTURAS DE DADOS Lista Pilha Fila Árvore Grafo 1) Como representar a estrutura organizacional de uma empresa com 1 presidente, 1 vice- presidente, 2 diretores (Vendas e Finanças) e 3 sub-diretores ? 2) Como representar o conjunto de livros informados nesta disciplina ? 3) Como organizar o esquema de tele-entrega de pizzas ? Imagine uns 4 tipos de pizzas. Como devem ser organizadas, estruturadas para que o esquema de entrega seja mais adequado ? Imagine como as pizzas podem ser organizadas na garupa da moto de um moto-boy. 9 Exemplos : Como você representaria graficamente e de forma livre, sem formalismos, cada item a seguir ? 4) Como funciona o sistema de atendimento nas linhas de ônibus ? 5) Como funciona a entrega de cigarros de uma marca X na Tijuca, sabendo-se que existe uma Van que cobre 10 pontos de vendas, conectados por ruas de mão única e de mão dupla ? Como representar estes pontos e as ligações entre eles ? 10 CONCLUINDO .... Estrutura de dados linear lista, pilha, fila relação linear entre os dados (existe um 1º. elemento, um último elemento e dado um elemento qualquer (exceto o 1º. e o último), ele possui um antecessor e um sucessor.) Exemplos : 2, 3 e 4 Estrutura de dados não lineares árvore e grafo. No caso de árvore, existe uma relação de hierarquia, de subordinação. Já no caso do grafo, existe possibilidade de relação entre quaisquer elementos. Exemplos 1) e 5) – slides 20 e 21 11 POR EXEMPLO ... PENSANDO NA ESTRUTURA DE DADOS LISTA ... Como representar na memória do computador os dados de uma lista ? Há 2 formas : sequencial (contígua) : os dados estão dispostos de forma seqüencial na memória, um após o outro, em endereços seqüenciais ou contíguos. Devemos pré- definir o tamanho máximo da lista. Usa-se vetor. encadeada : os dados estão dispostos de forma encadeada na memória, não seguindo uma ordem seqüencial, mas sim um armazenamento aleatório. Não é preciso pré-definir um tamanho máximo.
Compartilhar