Embed Size (px)
Citation preview
Estruturas de Dados
Slide 0116/03/2017
@Cleziel
/Cleziel
Prof. Cleziel Franzoni da Costa
1
42
EMENTA
Listas lineares e suas variações. Filas e pilhas. Árvores binárias
e suas variações. Utilização de uma linguagem de
programação.
3
Conteúdo Programático / Cronograma
Aula 01 16/03/2017 Introdução às Estruturas de Dados
Aula 02 17/03/2017 Listas
Aula 03 18/03/2017 Pilhas
Aula 04 23/03/2017 Filas
Aula 05 24/03/2017 Listas Encadeadas
Aula 06 25/03/2017 Listas Ordenadas
Aula 07 30/03/2017 Recursividade
Aula 08 31/03/2017 Aplicações de Estruturas da Dados
Aula 09 01/04/2017 Avaliação parcial de aprendizagem
Aula 10 06/04/2017 Algoritmos de Ordenação - part 1
Aula 11 07/04/2017 Algoritmos de Ordenação - part 2
Aula 12 08/04/2017 Algoritmos de Busca
Aula 13 27/04/2017 Árvores
Aula 14 28/04/2017 Árvores Binárias de Busca
Aula 15 29/04/2017 Avaliação parcial de aprendizagem
4
Avaliação de Aprendizagem
Prova Teórica (80%)
Seminário sobre Estruturas de Dados (20%)
5
Introdução
6
Abstração de Dados
A abstração de dados é necessária sempre que resolvemos problemas
usando um computador;
Dados são manipulados a partir de um determinado conhecimento,
visando produzir novas informações:
Dados + Conhecimento = Informação
Dado e informação são conceitos relativos. Dado é o que entra no
processo, enquanto informação é o que dele sai.
7
Abstração de Dados
Enquanto programadores, devemos voltar nossa atenção à duas questões
básicas:
Como representar a abstração da realidade no computador?
Como representar o conhecimento necessário para manipular essa abstração?
8
Tipo de Dados Abstratos (TDA)
Um TDA é um modelo matemático definido por um conjunto de valores e
por um conjunto de operadores que atuam sobre esses valores;
As TDAs servem tanto para especificar características relevantes das
entidades envolvidas nos problemas, quanto para definir de que forma
elas se relacionam entre si e como podem ser manipuladas.
9
Tipo de Dados Abstratos (TDA)
Sendo o TDA apenas um modelo matemático, sua definição não leva em
conta como os valores são armazenados na memória do computador ne
se preocupa com o tempo gasto para efetuar operações com esses
valores;
Para utilizar um TDA na solução de problemas por computados,
precisamos antes transforma-lo em um tipo de dado concreto. Esta
operação recebe o nome de implementação
10
Tipo de Dados Abstratos (TDA)11
implementaçãoTipo de dados
concreto
Tipo de dados
abstrato
Estruturas Primitivas (Tipos de Dados)
São os tipos de dados ou elementos primitivos que os quais são construídas
outras mais complexas;
São tipos básicos implementados na maioria das linguagens de
programação:
Inteiro ou integer (ou int);
Real (float, double);
Lógico (boolean, bool);
Caracter (char).
12
Objetivos das Estruturas de Dados
Objetivo teórico: especificar TDAs e determinar que classe de problemas
podem ser resolvidas com eles;
Do ponto de vista teórico, consideramos o TDA um recurso a ser usado na
solução de problemas;
13
Objetivos das Estruturas de Dados
Objetivo prático: implementar TDAs, criando representações concretas de
seus valores e projetar algoritmos para efetuar operações com elas.
Do ponto de vista prático, consideramos a implementação de um TDA como
um problema em si, que pode ser solucionado empregando outros TDAs mais
simples já implementados.
14
Tipos primitivos na linguagem C
char
int
float
long int
double
15
Função printf
Possibilita a saída de valores, segundo um determinado formato
previamente descrito;
Para cada valor que se deseja imprimir, deve existir um especificador de
formato correspondente na cadeia de caracteres, seguem alguns deles:
%c – char
%d (ou %i) – int
%f – double (ou float)
%s – cadeia de caracteres (strings).
16
Exemplo na linguagem C17
Utilizando o scanf18
Utilizando Strings em C19
Exercício
Crie um algoritmo, em C, para ler um valor em real e converte-lo, ao
mesmo tempo, para Euro (€) e para Dólar (US$):
Valor do dólar: R$ 3,118
Valor do Euro: R$ 3,358
20
Funções e Procedimento
Função
int produto(int x, int y) {
return (x * y);
}
Procedimento
void soma(int k, int z) {
printf(“%d”, x+y);
}
21
Exercício
Crie um algoritmo que utilize a função Resto, cujo objeto é imprimir na tela
o resto de uma divisão inteira;
22
Exercício
Implemente um algoritmo que seja capaz de utilizar uma dentre as quatro
funções abaixo, de acordo com a escolha do usuário, em uma operação
entre dois números.
Soma(int n1, int n2);
Subtracao(int n1, int n2);
Multiplicacao(int n1, int n2);
Divisao(int n1, int n2);
23
Ponteiros
Para cada tipo de dado existente, há um tipo de ponteiro que pode
armazenar endereços de memória onde existem valores do tipo
correspondente armazenados;
Ponteiros armazenam endereços de memória;
24
Utilizando Ponteiros25
Referências
PEREIRA, Silvio do Lago. Estruturas de dados fundamentais: conceitos e
aplicações . 12. ed.,. São Paulo: Érica, 2012. 264 p. ISBN 9788571943704;
SILVA, Osmar Quirino da. Estrutura de dados e algoritmos usando C:
fundamentos e aplicações . Rio de Janeiro, RJ: Ciência Moderna, 2007. 460
p. ISBN 9788573936117.
26
Estruturas de Dados
Slide 0116/03/2017
@Cleziel
/Cleziel
Prof. Cleziel Franzoni da Costa
27
