Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
Objetivo básico da disciplina: Estudar as principais técnicas de representação e manipulação de dados na memória principal Estrutura de Dados Na resolução de um problema por meio de um programa, a primeira providência é conceber um algoritmo adequado. A eficiência do algoritmo está relacionada com a disposição, na memória, dos dados que são tratados pelo programa. Exemplo: agenda telefônica Estruturas de Dados ordem alfabética ordem de altura São formas de representar e relacionar os dados, de modo a tornar mais eficientes os algoritmos que manipulam esses dados. Estruturas de Dados Representar os dados significa estudar várias formas de estruturar e armazenar os dados na memória principal. Manipular os dados significa estudar diversas operações que podemos aplicar sobre os dados. Exemplo: Dados (nome, endereço, telefone) Estruturas de Dados Representação e armazenamento dos dados Operações: procurar, adicionar, apagar, ... Exemplos: Estruturas de Dados Problema: manipular um conjunto de fichas em um fichário. Solução: organizar as fichas em ordem alfabética. Operações Possíveis: inserir, retirar ou procurar uma ficha, etc. Estrutura de Dados Correspondente: ? Estruturas de Dados Problema: organizar as pessoas que querem, ser atendidas em um guichê. Solução: colocar as pessoas em fila. Operações Possíveis: a medida que uma pessoa é atendida no guichê, outra entra no final da fila. Não é permitido “furar” a fila, ou seja, entrar entre outras que já estão presentes. Estrutura de Dados Correspondente: ? Exemplos: Estruturas de Dados Problema: organizar um conjunto de pratos que estão sendo lavados, um a um, em um restaurante. Solução: colocar os pratos empilhados. Operações Possíveis: colocar um prato limpo no alto da pilha, retirar um prato do alto da pilha, etc. Estrutura de Dados Correspondente: ? Exemplos: Estruturas de Dados Problema: conseguir um modo de visualizar, o conjunto de pessoas que trabalham em uma empresa, tendo em conta sua função. Solução: construir um organograma da empresa. Operações Possíveis: inserir ou retirar certas funções, localizar uma pessoa, etc. Estrutura de Dados Correspondente: ? Exemplos: Estruturas de Dados Problema: estabelecer um trajeto para percorrer todas as capitais de um país. Solução: utilizar um mapa que indique as rodovias existentes e estabelecer uma ordem possível para percorrer todas as cidades. Operações Possíveis: encontrar um modo de percorrer todas as cidades, determinar o caminho mais curto para ir de uma cidade a outra, etc. Estrutura de Dados Correspondente: ? Exemplos: Tipos de Dados Identificar os tipos de dados; O tipo é diferenciado pelo valor que pode assumir e pelo conjunto de operações que pode sofrer. Exemplo: variável do tipo boolean: true / false Considere que fruta é um tipo de dado, que valores esta variável poderá assumir? Tipos de Dados A declaração de uma variável especifica: quantidade de bytes que deve ser reservado; como o dado deve ser interpretado. Tipos de Dados Classificação: Primitivos ou Básicos: São tipo mais freqüentes com conjunto de operações e valores restritos. Exemplo: inteiro, real, lógico, caractere. Estruturados: são tipos criados a partir de combinações dos tipos básicos. Dados do tipo estruturado são definidos pelo programador, ao contrário do tipo primitivo que acompanha a linguagem de programação utilizada. Exemplo: vetores, matrizes, registros. Tipos Abstratos de Dados São estruturas de dados capazes de representar os tipos de dados que não foram previstos no núcleo das linguagens de programação e que, normalmente, são necessários para aplicações específicas. Essas estruturas são divididas em duas partes: Dados e Operações. Tipos Abstratos de Dados Exemplo: Tipo de dado fruta: maça, pêra, uva, ... Operações: ? O TAD encapsula a estrutura de dados Tipos Abstratos de Dados É uma forma de definir um novo tipo de dado juntamente com as operações que manipulam esse novo tipo de dado. As aplicações que utilizam esse TAD são denominadas clientes do tipo de dado. Representação do TAD: - definição da estrutura de dados; - especificação das operações aplicáveis sobre ele. Tipos Abstratos de Dados Os TADS são geralmente implementados através do conceito de BIBLIOTECAS. A implementação das operações propriamente ditas é feita em um arquivo separado. Para isso geralmente separa-se a declaração e a implementação do TAD em dois arquivos (C): NomeDoTAD.h : com a declaração NomeDoTAD.c : com a implementação O programa ou outros TADs que utilizam o seu TAD devem dar um #include no arquivo .h Tipos Abstratos de Dados Em linguagens orientadas por objeto (C++, Java) a implementação é feita através de classes Em linguagens estruturadas a implementação é feita pela definição de tipos juntamente com a implementação de funções: C (typedef e structs) Pascal (type, record) Tipos Abstratos de Dados Propriedades dos TADs Encapsulamento: definição isolada de outras unidades do programa - Invisibilidade e Proteção: representação do tipo deve ser acessada somente no ambiente encapsulado Estruturas Uma estrutura é uma coleção de uma ou mais variáveis, possivelmente de tipos diferentes, colocadas juntas sob um único nome para manipulação conveniente. Por exemplo, para representar um aluno são necessárias as informações nome, matrícula, conceito Ao invés de criar três variáveis, é possível criar uma única variável contendo três campos. Em C: struct Em Pascal: record struct Aluno { char nome[100]; int matricula; char conceito; }; main() { struct Aluno al, aux; al.nome = “Luiz” al.matricula = 200712; al.conceito = ‘A’; aux = al; printf(“%s”, aux.nome); } Estruturas (struct) em C typedef float Real; (tipo float) typedef unsigned char UChar; (tipo char sem sinal) typedef int* PInt; (tipo ponteiro para int) typedef float Vetor[4]; (vetor de 4 elementos) Exemplo de uso: Vetor v; Definição de “novos” tipos em C struct ponto { float x; float y; }; Typedef struct ponto Ponto; Assim, o Ponto passa a representar a estrutura ponto. Definição de “novos” tipos em C Também podemos definir um nome para o tipo ponteiro para a estrutura. Typedef struct ponto *Pponto; Exemplo de uso: Ponto p; Podemos declarar um ponteiro para um ponto: Pponto pp; Definição de “novos” tipos em C Podemos definir a estrutura e associar mnemônicos para elas em um mesmo comando: Typedef struct ponto { float x; float y; } Ponto; Definição de “novos” tipos em C Tipos Abstratos de Dados Vantagens da utilização do conceito de TADS: * possibilidade de sua utilização em diversas aplicações diferentes; * possibilidade de alterar o tipo sem alterar as aplicações que utilizam. REUTILIZAÇÃO Tipos Abstratos de Dados Vantagens da utilização do conceito de TADS: * Código do cliente do TAD não depende da implementação. * Segurança: - clientes não podem alterar a representação; - clientes não podem tornar os dados inconsistentes. Tipos Abstratos de Dados TADS genéricos Estrutura de Dados nos quais é possível acrescentar qualquer item de dados. Exemplos: TAD listas. Pode ser utilizado para representar uma lista de freqüências de alunos, lista telefônica, etc. TADs específicos Definidos para um dado domínio de aplicação como uma agenda de telefones. Tipos Abstratos de Dados Exemplo: TAD Ponto (ponto.h) Modelo Par ordenado (x,y) Dados representando o modelo Coordenada X Coordenada Y Tipos Abstratos de Dados Exemplo: TAD Ponto (ponto.h) Operações: • cria: operação que cria um ponto, alocando memória para as coordenadas x e y; • libera: operação que libera a memória alocada por um ponto; • acessa: operação que devolve as coordenadas de um ponto; • atribui: operação que atribui novos valores às coordenadas de um ponto; • distancia: operação que calcula a distância entre dois pontos. Tipos Abstratos de Dados Exemplo: TAD Ponto (ponto.h) Operações: • cria (x,y) • libera (ponto P) • acessa (ponto P) • atribui (ponto P, x,y) • distancia (ponto P1, ponto P2) Estruturas de Dados coleção de variáveis; representa o modelo matemático; método para implementar TAD; cada estrutura de dados é constituída dos tipos básicos e estruturados de uma linguagem de programação. Para implementarmos um TAD em uma linguagem de programação, empregamos uma ED Estruturas de Dados Listas Árvores Grafos listas seqüenciais e encadeadas, pilhas, filas e deques A principal diferença entre cada uma destas estruturas está na forma de relacionar os dados Estruturas de Dados LISTA - seqüência de elementos dispostos em ordem. FILA - seqüência de elementos dispostos em ordem com uma regra para a entrada e saída dos elementos (o 1º elemento que chega também é o 1º que sai da estrutura). PILHA - seqüência de elementos dispostos em ordem, mas com uma regra para a entrada e saída dos elementos (o último que chega é o 1º que sai da estrutura). Estruturas de Dados ÁRVORE - estrutura de dados que caracteriza uma relação de hierarquia entre os elementos (uma pessoa não pode pertencer a dois departamentos diferentes, cada diretoria tem os seus próprios departamentos, etc.). GRAFO - estrutura bastante genérica que organiza vários elementos, estabelecendo relações entre eles, dois a dois. Representação física dos dados CONTIGUIDADE FÍSICA Os dados são armazenados em posições contíguas na memória. A ordem é definida implicitamente pela posição ocupada pelos nodos da memória. Representação física dos dados CONTIGUIDADE FÍSICA – Vantagens Proteção de memória – a alocação é feita antes do início da execução do programa, garantindo a proteção da memória. Transferência de dados – como todos os dados estão alocados em bloco, a transferência dedados entre memória principal e secundária fica facilitada; Representação física dos dados CONTIGUIDADE FÍSICA – Vantagens Estruturas simples – é apropriada para armazenar estruturas simples, principalmente aquelas que utilizam a ordem física em uma representação; Representação – algumas estruturas de dados possuem uma representação lógica semelhante à contigüidade física, simplificando desta maneira a representação dos dados; Representação física dos dados CONTIGUIDADE FÍSICA – Vantagens Acesso – qualquer nodo pode ser diretamente acessado a qualquer momento, através de um índice associado à sua posição. Representação física dos dados CONTIGUIDADE FÍSICA – Desvantagens Compartilhamento de memória – este tipo de alocação não permite o compartilhamento de memória; Previsão de espaço físico – é necessário definir, antes da execução da aplicação, o número máximo de nodos a serem alocados. Representação física dos dados CONTIGUIDADE FÍSICA – Desvantagens Estruturas complexas – não é apropriado para estruturas complexas, devido à natureza seqüencial. Inserção e exclusão de componentes – estas duas operações geralmente implicam no deslocamento de um número considerável de informações, de modo a preservar as relações lógicas representadas. Representação física dos dados ENCADEAMENTO O espaço necessário para a representação dos dados pode ser alocado à medida que se torne necessário, através de alocação dinâmica. Os nodos são alocados em posições aleatórias na memória, e não lado a lado, como na representação por contigüidade física. Os nodos tem seu campo adicional onde é colocado o endereço físico do próximo nodo. Representação física dos dados ENCADEAMENTO – Vantagens Compartilhamento de memória – uma vez que os nodos de uma estrutura são indicados através de seus endereços, os mesmos nodos poderiam fazer parte de mais de uma estrutura; Maleabilidade – a alocação e a liberação de memória feita de forma dinâmica favorece a maleabilidade dos programas; Representação física dos dados ENCADEAMENTO – Vantagens Facilidade para inserção e remoção de componentes – a inserção e a remoção de nodos é facilmente realizada, sendo somente necessário ajustar os campos de elo dos nodos envolvidos na operação, sem a necessidade de deslocamento de informações. Representação física dos dados ENCADEAMENTO – Desvantagens Transferência de dados – é dificultada neste tipo de representação, uma vez que os dados estão espalhados na memória; Gerência de memória mais onerosa – toda a manipulação da estrutura é feita através de alocação e/ou liberação de memória, o que deve ser realizado pelo gerenciador de memória. Representação física dos dados ENCADEAMENTO – Desvantagens Procedimentos menos intuitivos – a utilização de alocação dinâmica implica na construção de procedimentos que envolvam alocações e liberação de memória, e no encadeamento dos nodos. Isto faz com que os procedimentos escritos para as operações sobre os dados sejam mais complexos. Representação física dos dados ENCADEAMENTO – Desvantagens Acesso – o processamento dos dados encadeados deve ser feito de forma serial, isto é, um nodo deve ser sempre acessado a partir de outro acessados anteriormente. Não é possível, como nos casos dos arranjos, acessar qualquer nodo a qualquer momento, a menos que todos os endereços sejam armazenados individualmente. Alocação de Memória Ao criar um programa em C usualmente temos que especificar, antes de começar a executar o programa, as variáveis que vamos usar, reservando assim um espaço na memória. As variáveis que são alocadas em posições fixas da memória são chamadas de variáveis estáticas, e as variáveis que não possuem uma posição fixa, e que são criadas e destruídas durante a execução do programa, são chamadas de variáveis dinâmicas. Alocação Estática: os dados tem um tamanho fixo e estão organizados seqüencialmente na memória do computador. O espaço de memória para as variáveis é reservado no início da execução Um exemplo típico de alocação estática são as variáveis globais, e os vetores (estáticos). Alocação de Memória Alocação Dinâmica: os dados não precisam ter um tamanho fixo, pois podemos definir para cada dado quanto de memória desejamos usar. O espaço de memória para as variáveis pode ser alocado dinamicamente durante a execução do programa. Os espaços de memória (blocos) não precisam estar necessariamente organizados de maneira seqüencial, podendo estar distribuídos de forma esparsa na memória do computador. Alocação de Memória A memória alocada dinamicamente é acessada através de Apontadores (pointers) que na verdade são variáveis que armazenam o endereço de uma área de memória. A memória alocada dinamicamente faz parte de uma área de memória chamada heap. Basicamente, o programa aloca e desaloca porções de memória do heap durante a execução. Alocação de Memória Conjunto de dados com alocação estática: A) Listas lineares seqüenciais B) Filas C) Pilhas D) Deques Conjuntos de dados com alocação dinâmica: A) Listas encadeadas simples B) Filas C) Pilhas D) Listas duplamente encadeadas E) Árvores Alocação de Memória Variáveis do tipo ponteiro A linguagem C permite o armazenamento e a manipulação de valores de endereços de memória. Quando escrevemos <int a;> automaticamente reserva-se um espaço na memória suficiente para armazenar valores inteiros (geralmente 4 bytes). int *p; p armazena endereços de memória em que existe um inteiro armazenado. Para atribuir e acessar endereços de memória, a linguagem oferece dois operadores unários: & (endereço de) – aplicado a variáveis, resulta no endereço da posição da memória reservada para a variável. * (conteúdo de) – aplicado a variáveis do tipo ponteiro, acessa o conteúdo do endereço de memória armazenado pela variável ponteiro. Variáveis do tipo ponteiro int a; int* p; a = 5; p = &a; *p = 6; 104 108 112 a p “lixo” Não foram inicializadas Variáveis do tipo ponteiro Exemplos: int main (void) { int a; int *p; p = &a; *p = 2; printf (“ %d ”, a); return; } Variáveis do tipo ponteiro Exemplos: int main (void) { int a, b, *p; a = 2; *p = 3; b = a + (*p); printf (“ %d ”, b); return 0; } Variáveis do tipo ponteiro Passando ponteiros para funções As funções não podem alterar diretamente valores de variáveis da função que fez a chamada. No entanto, se passarmos para uma função os valores dos endereços de memória em que suas variáveis estão armazenadas, essa função pode alterar, indiretamente, os valores das variáveis da função que a chamou. Passando ponteiros para funções # include <stdio.h> void somaprod (int a, int b, int *p, int *q) { *p = a + b; *q = a * b; } int main (void) { int s, p; somaprod (3, 5, &s, &p); printf (“Soma = %d Produto = %d\n”, s, p); return 0; } 104 108 112 s p Passando ponteiros para funções # include <stdio.h> void somaprod (int a, int b, int *p, int *q) { *p = a + b; *q = a * b; } int main (void) { int s, p; somaprod (3, 5, &s, &p); printf (“Soma = %d Produto = %d\n”, s, p); return 0; } 104 108 112 s p 116 120 124 a b p q 3 5 104 108 Passando ponteiros para funções # include <stdio.h> void somaprod (int a, int b, int *p, int *q) { *p = a + b; *q = a * b; } int main (void) { int s, p; somaprod (3, 5, &s, &p); printf (“Soma = %d Produto = %d\n”, s, p); return 0; } 104 108 112 s p 116 120 124 a b p q 3 5 104 108 15 8 Passando ponteiros para funções # include <stdio.h> void somaprod (int a, int b, int *p, int *q) { *p = a + b; *q = a * b; } int main (void) { int s, p; somaprod (3, 5, &s, &p); printf (“Soma = %d Produto = %d\n”, s, p); return 0; } 104 108 112 s p 116 120 124 15 8 Passando ponteiros para funções # include <stdio.h> void troca (int *px, int *py) { int temp; temp = *px; *px = *py; *py = temp; } int main (void) { int a = 5, b = 7; troca (&a, &b); printf (“ %d %d \n”, a, b); return 0; } 104 108 112 116 120 124 Vetores e alocação dinâmica A forma mais simples de estruturar um conjunto de dados é por meio de vetores. int v[10]; v é um vetor de inteiros dimensionado com 10 elementos. É reservado um espaço de memória contínuo para armazenar 10 elementos inteiros. Assim, se cada int ocupa 4 bytes, a declaração reserva um espaço de memória de 40 bytes. 104 144 v Alocação dinâmica A linguagem C oferece meios de requisitar espaços de memória em tempo de execução. Existem três maneiras de reservar o espaço de memória para o armazenamento de informações: - usar variáveis globais (e estáticas) - usar variáveis locais - reservar a memória requisitando ao sistema, em tempo de execução , um espaço de um determinado tamanho. Esse espaço, alocado dinamicamente, permanece reservado até que seja explicitamente liberado pelo programa. Se o programa não liberar o espaço alocado, ele será automaticamente liberado quando a execução do programa terminar. Alocação dinâmica Funções presentes na biblioteca padrão stlib: malloc – alocar memória Recebe como parâmetro o número de bytes que se deseja alocar e retorna o endereço inicial da área de memória alocada. int *v; /*ponteiro de inteiros para armazenar retorno do malloc. v= malloc (10*4); /*10 valores inteiros de 4 bytes cada. v= malloc (10*sizeof (int)) ; /*para ficar independente de compiladores e máquinas. Alocação dinâmica int *v; Abre-se espaço na pilha para o ponteiro (variável local) Alocação dinâmica v = malloc (10*sizeof (int)) ; Código do Programa Variáveis Globais e Estáticas Livre v 40 bytes 504 504 Reserva espaço de memória da área livre e atribui endereço à variável. Alocação dinâmica Se não houver espaço livre suficiente para realizar a alocação, a função retorna um endereço nulo (NULL – definido em stdlib.h). Podemos tratar isso: ... v = (int*) malloc (10*sizeof(int)); if (v == NULL) { printf (“Memória insuficiente. \n”); exit (1); /*aborta o programa e retorna 1 para o sisop } Alocação dinâmica Apontadores (ponteiros) são normalmente utilizados com tipos estruturados. Alocação dinâmica Pesquisar e estudar Registros e Ponteiros em C. Tarefa * Quando desejamos resolver um problema através de um programa utilizando o computador a primeira providência que devemos tomar é a de elaborar o algoritmo mais adequado para o programa. Para cada programa desenvolvido na disciplina de algoritmos vocês conceberam um algoritmo antes de implementar o mesmo. A eficiência do algoritmo vai depender da disposição dos dados, ou elementos que servem de base para a resolução do problema, na memória. Quando maior for a facilidade o computador achar na memória estes dados, maior será a eficiência do programa. Para entender a relação entre eficiência e algoritmo vamos ver o exemplo da agenda telefônica. Supondo que freqüentemente utilizamos a agenda telefônica para descobrir o número de telefone de nossos conhecidos, é conveniente dispor de uma relação dos números, organizada na agenda. Se a organização for feita por ordem alfabética, a agenda de fato ajuda. Se, porém, organizássemos nossa agenda pela ordem de altura das pessoas, com raras exceções, a agenda se tornaria difícil de manusear. Se soubermos organizar a nossa agenda de forma a tornar a busca de um número de telefone bastante facilitada, então, estaremos executando a tarefa de busca de forma eficiente. * Quando desejamos resolver um problema através de um programa utilizando o computador a primeira providência que devemos tomar é a de elaborar o algoritmo mais adequado para o programa. Para cada programa desenvolvido na disciplina de algoritmos vocês conceberam um algoritmo antes de implementar o mesmo. A eficiência do algoritmo vai depender da disposição dos dados, ou elementos que servem de base para a resolução do problema, na memória. Quando maior for a facilidade o computador achar na memória estes dados, maior será a eficiência do programa. Para entender a relação entre eficiência e algoritmo vamos ver o exemplo da agenda telefônica. Supondo que freqüentemente utilizamos a agenda telefônica para descobrir o número de telefone de nossos conhecidos, é conveniente dispor de uma relação dos números, organizada na agenda. Se a organização for feita por ordem alfabética, a agenda de fato ajuda. Se, porém, organizássemos nossa agenda pela ordem de altura das pessoas, com raras exceções, a agenda se tornaria difícil de manusear. Se soubermos organizar a nossa agenda de forma a tornar a busca de um número de telefone bastante facilitada, então, estaremos executando a tarefa de busca de forma eficiente. * Estruturas os dados é distribuir e relacionar os dados disponíveis, de modo a tornar mais eficiente a ação dos algoritmos que manipulam esses dados. Portanto, o objetivo básico da disciplina de dados é estudar as principais técnicas de representação e manipulação de dados na memória principal. Representar os dados significa estudar várias formas de estruturar e armazenar os dados na memória principal. Manipular os dados significa estudar diversas operações que podemos aplicar sobre os dados. * Por exemplo, supondo que nós queremos montar a nossa agenda. Nós temos os seguintes dados: nome, endereço e telefone. Representaremos e armazenaremos os dados na agenda por ordem alfabética de nome. Agora podemos realizar operações sobre a nossa agenda, operações como: procurar por um número através do nome da pessoa, adicionar mais uma pessoa, apagar um nome da agenda. Já pensou de organizássemos nossa agenda por endereço? Tornaríamos nossa tarefa de busca mais difícil e possivelmente demorada. Desta forma, perderíamos em eficiência. Imagine nossa agenda com mais de 100 pessoas! * Vejamos mais alguns problemas que podemos resolver através do computador com o auxílio das estruturas de dados. Voltaremos mais tarde a esses problemas para identificar a estrutura de dados que podemos utilizar para cada um. Problema 1.... * Problema 2... * * * * Antes de identificar as estruturas de dados que serão utilizadas para resolver cada um dos problemas apresentados anteriormente, vamos compreender o que é um dado e o que significa tipos de dados, termos utilizados em estruturas de dados. Quando vamos implementar um programa precisamos identificar os tipos de dados que o computador, a linguagem de programação ou mesmo um algoritmo são capazes de entender. Por exemplo: quando desejamos implementar um programa que calcule a média de um aluno, informamos ao programa a nota da primeira e da segunda avaliação do aluno, para que o computador posso realizar o cálculo da média e informar o resultado. Cada nota é um dado que possui o mesmo tipo de dado, ou seja, as duas notas são definidas no programa como variáveis inteiras. Portanto a nota 1 e a nota 2 possuem o mesmo tipo de dado, são inteiras. No entanto as variáveis podem assumir tipos de dados diferentes. Supondo que queremos calcular a média do aluno Marcos. Vamos informar ao programa a nota 1 e a nota 2 que são variáveis inteiras e o nome do aluno que é um variável caracter. Temos aqui tipos de dados diferentes inteiro e caracter sobre cada tipo de dados podemos realizar operações diferentes. Por exemplo: podemos realizar cálculos com as notas por serem variáveis numéricas que contem valores numéricos, no entanto não podemos fazer o mesmo com o nome do aluno, pelo fato de ser uma variável caracter. Portanto, para cada tipo de dados teremos operações diferentes para realizar. Exemplo de dado: variável do tipo boolean, variável lógica que pode assumir apenas dois valores, true e false. Vamos supor que fruta é um tipo de dados, quais seriam os valores que o tipo fruta poderia assumir? O que significa declarar uma variável no início do programa? A declaração da variável indica ao computador e ao programa a quantidade de bytes que deve ser reservado em memória para armazenar esta variável. E como o dado deverá ser interpretado pelo computador, se numérico, se é caracter, ... * Antes de identificar as estruturas de dados que serão utilizadas para resolver cada um dos problemas apresentados anteriormente, vamos compreender o que é um dado e o que significa tipos de dados, termos utilizados em estruturas de dados. Quando vamos implementar um programa precisamos identificar os tipos de dados que o computador, a linguagem de programação ou mesmo um algoritmo são capazes de entender. Por exemplo: quando desejamos implementar um programa que calcule a média de um aluno, informamos ao programa a nota da primeira e da segunda avaliação do aluno, para que o computador posso realizar o cálculo da média e informar o resultado. Cada nota é um dado que possui o mesmo tipo de dado, ou seja, as duas notas são definidas no programa como variáveis inteiras. Portanto a nota 1 e a nota 2 possuem o mesmo tipo de dado, são inteiras. No entanto as variáveis podem assumir tipos de dados diferentes. Supondo que queremos calcular a média do aluno Marcos. Vamos informar ao programa a nota 1 e a nota 2 que são variáveis inteiras e o nome do aluno que é um variável caracter. Temos aqui tipos de dados diferentes inteiro e caracter sobre cada tipo de dados podemos realizar operações diferentes. Por exemplo: podemos realizar cálculos com as notas por serem variáveis numéricas que contem valores numéricos, no entanto não podemos fazer o mesmo com o nome do aluno, pelo fato de ser uma variável caracter. Portanto, para cada tipo de dados teremos operações diferentes para realizar. Exemplo de dado: variável do tipo boolean, variável lógica que pode assumir apenas dois valores, true e false. Vamos supor que fruta é um tipo de dados, quais seriam os valores que o tipo fruta poderia assumir? O que significa declarar uma variável no início do programa? A declaração da variável indica ao computador e ao programa a quantidade de bytes que deve ser reservado em memória para armazenar esta variável. E como o dado deverá ser interpretado pelo computador, se numérico, se é caracter, ... * Os dados podem ser classificados em dois tipos que são: Primitivos ou básicos: a partir desse tipo básico podemos definir demais tipos de dados. São tipo mais freqüentes com conjunto de operações e valores restritos. Por exemplo: variáveis do tipo inteiro e real podem assumir valores numéricos; variáveis do tipo caracter podem assumir letras e caracteres especiais; variáveis do tipo lógica podem assumir dois valores true/false. Estruturados: são tipos criados a partir de combinações dos tipos básicos. Dados do tipo estruturado são definidos pelo programador, ao contrário do tipo primitivo que acompanha a linguagem de programação utilizada. Exemplo: array ou vetores, record ou registros. Exemplo: em um programa para calcular a média, definimos uma variável chamada média = real em um programa para calcular o perímetro de uma circunferência, definimos uma variável P = real em um programa de cadastro, definimos uma variável para armazenar informações de uma pessoa, pessoaA : nome=caracter; idade=inteiro; cpf=real. Esta última definição exemplifica o tipo estruturado record ou registro, onde temos vários tipos básicos que formam um tipo estruturado onde o nome da variável é pessoaA. * Vimos 2 tipos de dados que são: primitivos e estruturados. Vamos ver agora o que são tipos de dados abstratos utilizado em estruturas de dados. Tipos abstratos de dados nada mais são do que um modelo matemático com várias operações que podem ser aplicadas sobre os mesmos. Considerando que temos o tipo de dado fruta, os valores que esse tipo poderá assumir é o seguinte: maça, pêra, uva,... Podemos aplicar operações sobre este tipo, você saberia dizer quais operações? Portanto, temos aqui um TAD. Temos um tipo de dado sobre o qual podemos efetuar operações, isto é um TAD. Definimos o tipo de dado e as operações que podemos realizar sobre o mesmo para depois implementar este tipo de dado. Há a separação entre o conceito e a implementação. * Vimos 2 tipos de dados que são: primitivos e estruturados. Vamos ver agora o que são tipos de dados abstratos utilizado em estruturas de dados. Tipos abstratos de dados nada mais são do que um modelo matemático com várias operações que podem ser aplicadas sobre os mesmos. Considerando que temos o tipo de dado fruta, os valores que esse tipo poderá assumir é o seguinte: maça, pêra, uva,... Podemos aplicar operações sobre este tipo, você saberia dizer quais operações? Portanto, temos aqui um TAD. Temos um tipo de dado sobre o qual podemos efetuar operações, isto é um TAD. Definimos o tipo de dado e as operações que podemos realizar sobre o mesmo para depois implementar este tipo de dado. Há a separação entre o conceito e a implementação. * Vimos 2 tipos de dados que são: primitivos e estruturados. Vamos ver agora o que são tipos de dados abstratos utilizado em estruturas de dados. Tipos abstratos de dados nada mais são do que um modelo matemático com várias operações que podem ser aplicadas sobre os mesmos. Considerando que temos o tipo de dado fruta, os valores que esse tipo poderá assumir é o seguinte: maça, pêra, uva,... Podemos aplicar operações sobre este tipo, você saberia dizer quais operações? Portanto, temos aqui um TAD. Temos um tipo de dado sobre o qual podemos efetuar operações, isto é um TAD. Definimos o tipo de dado e as operações que podemos realizar sobre o mesmo para depois implementar este tipo de dado. Há a separação entre o conceito e a implementação. * Vimos 2 tipos de dados que são: primitivos e estruturados. Vamos ver agora o que são tipos de dados abstratos utilizado em estruturas de dados. Tipos abstratos de dados nada mais são do que um modelo matemático com várias operações que podem ser aplicadas sobre os mesmos. Considerando que temos o tipo de dado fruta, os valores que esse tipo poderá assumir é o seguinte: maça, pêra, uva,... Podemos aplicar operações sobre este tipo, você saberia dizer quais operações? Portanto, temos aqui um TAD. Temos um tipo de dado sobre o qual podemos efetuar operações, isto é um TAD. Definimos o tipo de dado e as operações que podemos realizar sobre o mesmo para depois implementar este tipo de dado. Há a separação entre o conceito e a implementação. * Vimos 2 tipos de dados que são: primitivos e estruturados. Vamos ver agora o que são tipos de dados abstratos utilizado em estruturas de dados. Tipos abstratos de dados nada mais são do que um modelo matemático com várias operações que podem ser aplicadas sobre os mesmos. Considerando que temos o tipo de dado fruta, os valores que esse tipo poderá assumir é o seguinte: maça, pêra, uva,... Podemos aplicar operações sobre este tipo, você saberia dizer quais operações? Portanto, temos aqui um TAD. Temos um tipo de dado sobre o qual podemos efetuar operações, isto é um TAD. Definimos o tipo de dado e as operações que podemos realizar sobre o mesmo para depois implementar este tipo de dado. Há a separação entre o conceito e a implementação. * Vimos 2 tipos de dados que são: primitivos e estruturados. Vamos ver agora o que são tipos de dados abstratos utilizado em estruturas de dados. Tipos abstratos de dados nada mais são do que um modelo matemático com várias operações que podem ser aplicadas sobre os mesmos. Considerando que temos o tipo de dado fruta, os valores que esse tipo poderá assumir é o seguinte: maça, pêra, uva,... Podemos aplicar operações sobre este tipo, você saberia dizer quais operações? Portanto, temos aqui um TAD. Temos um tipo de dado sobre o qual podemos efetuar operações, isto é um TAD. Definimos o tipo de dado e as operações que podemos realizar sobre o mesmo para depois implementar este tipo de dado. Há a separação entre o conceito e a implementação. * * * * * * * Vimos 2 tipos de dados que são: primitivos e estruturados. Vamos ver agora o que são tipos de dados abstratos utilizado em estruturas de dados. Tipos abstratos de dados nada mais são do que um modelo matemático com várias operações que podem ser aplicadas sobre os mesmos. Considerando que temos o tipo de dado fruta, os valores que esse tipo poderá assumir é o seguinte: maça, pêra, uva,... Podemos aplicar operações sobre este tipo, você saberia dizer quais operações? Portanto, temos aqui um TAD. Temos um tipo de dado sobre o qual podemos efetuar operações, isto é um TAD. Definimos o tipo de dado e as operações que podemos realizar sobre o mesmo para depois implementar este tipo de dado. Há a separação entre o conceito e a implementação. * Vimos 2 tipos de dados que são: primitivos e estruturados. Vamos ver agora o que são tipos de dados abstratos utilizado em estruturas de dados. Tipos abstratos de dados nada mais são do que um modelo matemático com várias operações que podem ser aplicadas sobre os mesmos. Considerando que temos o tipo de dado fruta, os valores que esse tipo poderá assumir é o seguinte: maça, pêra, uva,... Podemos aplicar operações sobre este tipo, você saberia dizer quais operações? Portanto, temos aqui um TAD. Temos um tipo de dado sobre o qual podemos efetuar operações, isto é um TAD. Definimos o tipo de dado e as operações que podemos realizar sobre o mesmo para depois implementar este tipo de dado. Há a separação entre o conceito e a implementação. * Vimos 2 tipos de dados que são: primitivos e estruturados. Vamos ver agora o que são tipos de dados abstratos utilizado em estruturas de dados. Tipos abstratos de dados nada mais são do que um modelo matemático com várias operações que podem ser aplicadas sobre os mesmos. Considerando que temos o tipo de dado fruta, os valores que esse tipo poderá assumir é o seguinte: maça, pêra, uva,... Podemos aplicar operações sobre este tipo, você saberia dizer quais operações? Portanto, temos aqui um TAD. Temos um tipo de dado sobre o qual podemos efetuar operações, isto é um TAD. Definimos o tipo de dado e as operações que podemos realizar sobre o mesmo para depois implementar este tipo de dado. Há a separação entre o conceito e a implementação. * Vimos 2 tipos de dados que são: primitivos e estruturados. Vamos ver agora o que são tipos de dados abstratos utilizado em estruturas de dados. Tipos abstratos de dados nada mais são do que um modelo matemático com várias operações que podem ser aplicadas sobre os mesmos. Considerando que temos o tipo de dado fruta, os valores que esse tipo poderá assumir é o seguinte: maça, pêra, uva,... Podemos aplicar operações sobre este tipo, você saberia dizer quais operações? Portanto, temos aqui um TAD. Temos um tipo de dado sobre o qual podemos efetuar operações, isto é um TAD. Definimos o tipo de dado e as operações que podemos realizar sobre o mesmo para depois implementar este tipo de dado. Há a separação entre o conceito e a implementação. * Vimos 2 tipos de dados que são: primitivos e estruturados. Vamos ver agora o que são tipos de dados abstratos utilizado em estruturas de dados. Tipos abstratos de dados nada mais são do que um modelo matemático com várias operações que podem ser aplicadas sobre os mesmos. Considerando que temos o tipo de dado fruta, os valores que esse tipo poderá assumir é o seguinte: maça, pêra, uva,... Podemos aplicar operações sobre este tipo, você saberia dizer quais operações? Portanto, temos aqui um TAD. Temos um tipo de dado sobre o qual podemos efetuar operações, isto é um TAD. Definimos o tipo de dado e as operações que podemos realizar sobre o mesmo para depois implementar este tipo de dado. Há a separação entre o conceito e a implementação. * Vimos 2 tipos de dados que são: primitivos e estruturados. Vamos ver agora o que são tipos de dados abstratos utilizado em estruturas de dados. Tipos abstratos de dados nada mais são do que um modelo matemático com várias operações que podem ser aplicadas sobre os mesmos. Considerando que temos o tipo de dado fruta, os valores que esse tipo poderá assumir é o seguinte: maça, pêra, uva,... Podemos aplicar operações sobre este tipo, você saberia dizer quais operações? Portanto, temos aqui um TAD. Temos um tipo de dado sobre o qual podemos efetuar operações, isto é um TAD. Definimos o tipo de dado e as operações que podemos realizar sobre o mesmo para depois implementar este tipo de dado. Há a separação entre o conceito e a implementação. * Agora podemos definir ED de uma maneira mais específica. ED é um método particular de se implementar um TAD. Ou seja, para implementarmos um TAD em uma linguagem de programação, empregamos uma ED. A escolha correta da ED adequada a cada caso depende diretamente do conhecimento de algoritmos para manipular a estrutura de maneira eficiente. * Temos aqui alguns exemplos de ED. Existem vários estruturas que podem ser implementadas dependendo do problema a ser solucionado. Durante a nossa disciplina estudaremos as principais ED, analisando a forma como elas organizam os dados, como armazenam fisicamente os dados na memória e algoritmos para a sua manipulação. O que diferencia uma estrutura de outra é o relacionamento lógico dos dados a serem representados. Veremos as seguintes estruturas: Listas (que inclui listas seqüenciais e encadeadas, pilhas, filas e deques); Matrizes, Árvores e Grafos. A principal diferença entre cada uma destas estruturas está na forma de relacionar os dados. As listas utilizam uma estrutura de ordem, seqüência. As árvores utilizam uma estrutura de subordinação. E os grafos utilizam relacionamentos mais completos, que permite o relacionamento entre quaisquer nodos. * Agora você é capaz de identificar o tipo de estrutura que podemos utilizar para o problema 1. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Compartilhar