Faculdade de Informática e Tecnologia de Pernambuco
ESTRUTURA DE DADOS
Profa. Juliana Mafra
([email protected])
21 de Setembro de 2009
Ementa
 Introdução às Estruturas de Dados
 Estruturas Elementares
 Algoritmos de Ordenação e Recursão
 Árvores e Grafos
 Algoritmos para Estruturas Complexas
2
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Objetivo Geral
 Possibilitar aos alunos a utilização otimizada das
diversas estruturas de dados apresentadas,
levando em consideração o problema a ser
resolvido ou otimizado, e também o contexto no
qual ocorre esse problema.
3
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Objetivos Específicos
 Fornecer domínio da alocação dinâmica de memória;
 Apresentar
as principais estruturas de dados e suas
implementações, em termos de representação física e algoritmos
de manipulação, guiando-se pelo conceito de tipos abstratos de
dados;
 Apresentar os principais processos de pesquisa e classificação de
dados;
 Introduzir aspectos básicos da complexidade de algoritmos;
 Consolidar os conhecimentos sobre programação previamente
adquiridos, utilizando estruturas de dados em aplicações
particulares.
4
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Metodologia
 A
disciplina será trabalhada com aulas
expositivo-dialogadas, onde serão fornecidos os
componentes teóricos e será feita a prática de
exercícios.
5
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Bibliografia
 Livro Texto:
 Veloso, P.A . da S. – Estrutura de Dados –Editora Campus,
1983.
 Livros de Referência:
 Horowitz, E e Shani, S. - Fundamentos de Estruturas de
Dados - Editora Campus, Rio de Janeiro, 1983.
 Referências Complementares:
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,
Clifford Stein - Algoritmos: Teoria e Prática, Editora
Campus, Rio de Janeiro, 2002.
6
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Introdução às Estruturas de Dados
Tipo Abstrato de Dados (TDA)
7
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Tipos de Dados
 Define a forma como um dado deve ser armazenado ou
recuperado, bem como os possíveis valores que ele pode
assumir e as operações que podem ser efetuadas sobre os
mesmos.
 Exemplo em Pascal:
 integer - permite valores inteiros e operações de adição, multiplicação,
subtração e divisão;
 string - permite valores literais e operações de concatenação;
 Obs. Esses tipos estão intrinsecamente relacionados com o hardware.
8
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Tipo Abstrato de Dados (TAD)
 Um tipo
abstrato de dados (TAD) é a especificação
matemática de um conjunto de dados e das operações que
podem ser executadas sobre esses dados.
 O conceito de tipo de dado abstrato é dissociado do hardware.
 TAD define o que cada operação faz, mas não como faz.
 Assim,
um mesmo tipo abstrato de dados pode ser
concretizado (ou implementado) de diversas formas.
9
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Tipo Abstrato de Dados (TAD)
 TADs são materializados pelas estruturas de dados.
– Lista Encadeada (implementação com referências)
– Lista com alocação estática (implementação usando array)
 Estruturas de dados são formas genéricas de se estruturar
informação de modo a serem registradas e processadas pelo
computador.
 Contudo, estas só
adquirem significado quando associadas
a um conjunto de operações, que visam, de um modo
geral, manipulá-las (algoritmos).
10
ESTRUTURA DE DADOS
Profa. Juliana Mafra
TAD em C
 Uma boa técnica de programação é implementar os TADs em
arquivos separados do programa principal.
 Para isso, geralmente separa-se a declaração e a implementação
do TAD em dois arquivos:
 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
11
ESTRUTURA DE DADOS
Profa. Juliana Mafra
TAD:Exemplo
 Implemente um TAD ContaBancaria, com os campos número e
saldo onde os clientes podem fazer as seguintes operações:
 Iniciar uma conta com um número e saldo inicial
 Depositar um valor
 Sacar um valor
 Imprimir o saldo
 Faça um pequeno programa para testar o seu TAD.
12
ESTRUTURA DE DADOS
Profa. Juliana Mafra
ContaBancaria.h
// definição do tipo
typedef struct{
int numero;
double saldo;
}ContaBancaria;
// cabeçalho das funções
void Inicializa(ContaBancaria* conta, int numero, double saldo);
void Deposito(ContaBancaria* conta, double valor);
void Saque(ContaBancaria* conta, double valor);
void Imprime(ContaBancaria conta);
13
ESTRUTURA DE DADOS
Profa. Juliana Mafra
ContaBancaria.c
#include <stdio.h>
#include "ContaBancaria.h”
void Inicializa(ContaBancaria* conta, int numero, double saldo) {
(*conta).numero = numero;
(*conta).saldo = saldo;
}
void Deposito(ContaBancaria* conta, double valor){
(*conta).saldo += valor;
}
void Saque(ContaBancaria* conta, double valor){
(*conta).saldo -= valor;
}
void Imprime(ContaBancaria conta){
printf(" Numero: %d \n", conta. numero);
printf(" Saldo: %f \n", conta.saldo);
}
14
ESTRUTURA DE DADOS
Profa. Juliana Mafra
Main.c
#include <stdio.h>
#include <stdlib.h>
#include "ContaBancaria.h“
int main(int argc, char *argv[])
{
ContaBancaria conta1;
Inicializa(&conta1,918556,300.00);
printf("\n Antes da movimentacao: \n");
Imprime(conta1);
Deposito(&conta1, 50.00);
Saque(&conta1, 70.00);
printf("\n Depois da movimentacao: \n");
Imprime(conta1);
}
15
ESTRUTURA DE DADOS
Profa. Juliana Mafra