01. Introdução

Prévia do material em texto

INTRODUÇÃO
Estrutura de Dados
Pré-requisitos
 Algoritmos
 Iterativo
 Recursivo
 Tipos estruturados de dados
 Estáticos
 Dinâmicos
 Funções
 Manipulação de Arquivos
Aplicações
 Redes de computadores
 Sistemas Operacionais
 Arquitetura de computadores
 Compiladores
 Inteligência Artificial
 Entre outros
 E também melhorar suas técnicas de 
programação
Estruturas Estáticas
 Quais foram vistas?
 Arrays: Vetores e Matrizes
 Por que estáticas?
 Após definido, não é possível mudar a sua quantidade 
de elementos
 Quais as implicações?
 Superdimensionar o espaço de um vetor (desperdiçar 
memória) ou subdimensionar (e não ter espaço 
suficiente para resolver o seu problema)
Estruturas Dinâmicas
 Ponteiros (existem outras)
 Resolve o problema anterior?
 Alocação dinâmica
 Possui efeitos colaterais?
 Complexidade de código
Algoritmo
 É um processo sistemático para a resolução 
de um problema
 Computa uma saída (resultado do problema) 
a partir de uma entrada (dados fornecidos)
Algoritmo
Entrada Saída
(Dados)
Algoritmos Iterativos
 Seja uma seqüência de elementos 
armazenada no vetor S[i]. Construir um 
algoritmo para inverter os elementos da 
seqüência.
Algoritmo: Inversão de uma seqüência
para i = 1 até n/2 faça
temp = S[i]
S[i] = S[n-i+1]
S[n-i+1] = temp
3 5 94
1 2 3 4
9 4 35
1 2 3 4
Algoritmos Recursivos
 Um procedimento é recursivo quando ele 
chama a si mesmo
 A todo procedimento recursivo corresponde 
um iterativo (não recursivo)
Fatorial (recursivo)
função fat(i)
se i <= 1 então
1
senão
i * fat(i-1)
Fatorial (não recursivo)
F[0] = 1
para j = 1 até n faça
F[j] = j * F[j-1]
Dados de Entrada
 No processo de computação do resultado o 
algoritmo manipula os dados de entrada
 Lendo os dados para a memória
 Fazendo cálculos com os dados
 Movendo os dados na memória
 Dados são informações representadas de 
forma binária. Eles são formados por:
 Uma cadeia de bits. Ex.: 00100110
 Um tipo. Ex.: Inteiro (38), Caractere (&), Real
Organização dos Dados
 Os dados podem ser organizados na memória 
de diferentes formas. A mais comum é a 
organização seqüencial
00100110
00001100
00110110
01011000
00011010
01011010
00001111
01000101
Endereços de memória
Dados
na 
memória
38
12
54
88
26
90
15
69
Dados
0xCB20
0xCB21
0xCB22
0xCB23
0xCB24
0xCB25
0xCB26
0xCB27
Organização dos Dados
 Normalmente utiliza-se uma visualização 
horizontal para indicar uma organização 
seqüencial
00100110
00001100
00110110
01011000
00011010
01011010
00001111
01000101
Endereços de memória
Dados
na 
memória
38 12 54 88 26 90 15 69
Dados organizados
logicamente como uma 
seqüencia
0xCB20
0xCB21
0xCB22
0xCB23
0xCB24
0xCB25
0xCB26
0xCB27
Organização dos Dados
 Na linguagem de programação C/C++, uma 
organização seqüencial pode ser obtida com 
o uso de vetores
00100110
00001100
00110110
01011000
00011010
01011010
00001111
01000101
Endereços 
de memória
Dados
na 
memória
38 12 54 88 26 90 15 69
Dados organizados
logicamente como uma 
seqüencia
int vet[8] = {28,12,54,88,26,90,15};
0xCB20
0xCB21
0xCB22
0xCB23
0xCB24
0xCB25
0xCB26
0xCB27
Organização dos Dados
 Mas os dados também podem ser dispostos 
na memória em uma organização encadeada
00100110
00110110
01011000
01000101
01011010
Endereços 
de memória
Dados
na 
memória
38 54 88 90 69
Dados organizados
logicamente como uma 
seqüencia
0xCB20
0xCB21
0xCB22
0xCB23
0xCB24
0xCB25
0xCB26
0xCB27
Organização dos Dados
 Não importa como os dados estão dispostos 
na memória, existem várias formas de 
organizá-los logicamente
38 54 88 90 69
Dados organizados
logicamente como uma 
lista
Dados organizados 
logicamente como uma 
hierarquia
38
54
88
90
69
Organização dos Dados
 A organização lógica destes dados influi na 
forma como eles podem ser manipulados
 Ex.: A remoção de um dado numa organização de 
lista não ocorre da mesma forma que numa 
organização hierárquica
38 54 88 90 69
Dados organizados
logicamente como uma 
lista
Dados organizados 
logicamente como uma 
hierarquia
38
54
88
90
69
Estrutura de Dados
 Uma estrutura de dados compreende uma 
organização lógica dos dados e as operações 
de manipulação associadas
Inserção
Remoção
Ordenação
Inserção
Remoção
Percurso Inserção
Remoção
Listas e Filas
PilhasÁrvores
38 54 88 90 69
38 54 88 90 69
38
54
88
90
69
Estrutura de Dados
 Qual a melhor forma de se estruturar os 
dados no computador?
 Não existe uma resposta única
 Depende das operações de manipulação que se 
deseja executar sobre os dados:
 Inserção, remoção, busca, percurso
 Depende da freqüência das operações
 Depende do tipo de dado
 Depende da quantidade e tamanho dos dados
Estrutura de Dados
 Para usar uma estruturas de dados é 
necessário implementá-la (organização + 
operações) em uma linguagem de 
programação como C/C++
 A escolha da estrutura adequada depende 
diretamente da eficiência dos algoritmos de 
manipulação
 O conhecimento de princípios básicos de 
análise de algoritmos é imprescindível
Estrutura de Dados
 Conceito: formas de armazenamento e 
organização de dados na memória de 
computador para que possam ser usados de 
forma mais eficiente
 Algumas estruturas são de uso geral, 
utilizadas para gerar outras estruturas mais 
complexas
 Podem ser empregadas em diferentes tipos 
de aplicações, orientadas a tarefas específicas
Estrutura de Dados
 São tipos de dados compostos, classificados 
de acordo com os tipos de dados primitivos 
que elas contém
 Homogêneas
 Heterogêneas
Estrutura de Dados
 As estruturas de dados tratam do 
relacionamento lógico entre tipos de dados
 Próxima Aula: TAD’s