Buscar

Aula_1

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.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*

Teste o Premium para desbloquear

Aproveite todos os benefícios por 3 dias sem pagar! 😉
Já tem cadastro?

Outros materiais