Aula 01 - estrutura de dados

Prévia do material em texto

ANÁLISE E DESENVOLVIMENTO DE SISTEMAS
zavaleta.jorge@gmail.com
Estrutura de Dados
Jorge Zavaleta
zavaleta.jorge@gmail.com
jorge.gavidia@estacio.br
Niterói, 2019-II
Aula 01: Apresentação da disciplina. 
Revisão de Agregados Homogêneos e 
Heterogêneos.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Sobre o Professor – Jorge Zavaleta
• Áreas de Interesse e Pesquisa:
• Inteligência Artificial
• Machine Learning
• Deep Learning
• Ciência de Dados Aplicados a: 
Educação, Saúde e Agricultura
• Linguagem Java, R e Python.
• Doutor em Engenharia de 
Sistemas e Computação - UFRJ
• Mestre em Ciência da 
Computação – UFRGS
• Licenciado em Matemática
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Disciplina CCT0637: Estrutura de Dados
• Ementa:
1. Agregados Homogêneos e Heterogêneos, 
2. Modularização, 
3. Alocação Dinâmica de Memória,
4. Tipos Abstratos de Dados, 
5. Listas, Pilhas, Filas, 
6. Árvores, 
7. Ordenação.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Objetivos Gerais
• Desenvolver técnicas para representação de estruturas de dados e as operações sobre as
mesmas, de maneira que seja possível solucionar problemas, escolhendo as estruturas de
dados mais adequadas para representação e manipulação dos dados em problemas
específicos.
Objetivos Específicos
1. Identificar e construir os agregados heterogêneos.
2. Aplicar os fundamentos da modularização de código.
3. Aplicar modularização de código em situações contextualizadas.
4. Aplicar os fundamentos da alocação dinâmica de dados em memória.
5. Construir as principais estruturas de dados lineares .
6. Identificar os Fundamentos da estrutura de dados Árvore;
7. Descrever os fundamentos da ordenação de elementos em estrutura de dados.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Bibliografia Básica
Ascencio, Ana Fernanda Gomes. Araújo, 
Graziela S. Estrutura de Dados: Algoritmos, 
Análise da Complexidade e implementações 
em Java e C/C++. 1. São Paulo: Pearson. 
Prentice Hall, 2010.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Bibliografia Básica
EDELWEISS, N, GALANTE, R. M. Estrutura 
de Dados, Volume 18 - Série Livros 
Didáticos Informática UFRGS. 1.ed. Rio 
Grande do Sul: Bookman, 2009.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Bibliografia Básica
KOFFMAN, Elliot B., WOLFGANG, Paul A.T. 
Objetos, Abstração, Estrutura de dados 
e Projeto usando C++. 1. Rio de Janeiro:: 
LTC, 2008.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Avaliação
• O processo de avaliação será composto 
de três etapas: 
• Avaliação 1 (AV1) 
• Avaliação 2 (AV2) 
• Avaliação 3 (AV3) 
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
1. Agregados Homogêneos e Heterogêneos
• Introdução: 
✓Um programa de computador envolve a definição de um algoritmo
para a resolução de um problema.
✓Programa = Algoritmo + Estrutura de Dados
✓Um algoritmo é representado através de expressões simbólicas de 
modo a descrever e a encontrar a solução de problemas do mundo 
real.
✓Um algoritmo representa uma sequência finita e não ambígua de 
instruções elementares bem definidas, conducente à solução de um 
determinado problema, cada uma das quais pode ser executada 
mecanicamente numa quantidade finita de tempo.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Algoritmos
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Algoritmos
• Um algoritmo é uma ferramenta para resolver um problema 
computacional bem especificado (bem definido).
• Os algoritmos são amplamente utilizados na área da computação, seja na 
elaboração de soluções voltadas à construção de interfaces, software e 
hardware, seja no planejamento de redes.
• Os algoritmos também constituem uma parte importante da 
documentação de sistemas, pois descrevem as tarefas a serem realizadas 
pelos programas.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Importância dos algoritmos na Computação 
• O uso/desenvolvimento de algoritmos “eficientes” é desejável em vários 
contextos:
✓projetos de genoma de seres vivos
✓rede mundial de computadores
✓sistemas de informação geográfica
✓comercio eletrônico
✓planejamento da produção de industrias
✓logística de distribuição
© Cid, Cândida, Orlando 
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Algoritmos e Tecnologia
• O avanço da tecnologia permite a construção 
de máquinas cada vez mais rápidas. Isto 
possibilita que um algoritmo para determinado 
problema possa ser executado mais 
rapidamente.
• Paralelamente a isto, encontra-se 
projetos/desenvolvimento de algoritmos 
“intrinsecamente mais eficientes” para um 
determinado problema. Isto leva em conta 
apenas as características inerentes ao 
problema, desconsiderando detalhes de 
software/hardware.
© Cid, Cândida, Orlando 
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Complexidade de Algoritmos
• A análise de algoritmo fornece uma medida objetiva de desempenho
proporcional ao tempo de execução do algoritmo.
• Queremos projetar/desenvolver algoritmos eficientes (rápidos).
• Mas o que seria uma boa medida de eficiência de um algoritmo?
• Não estamos interessados em quem programou, em que linguagem foi 
escrito e nem qual a máquina foi usada! 
• Queremos um critério uniforme para comparar os diversos algoritmos.
• O fato de um algoritmo resolver um dado problema não significa que seja 
aceitável na prática.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Projetos de Algoritmos
• O Projeto de algoritmos é um método para identificar e analisar um problema 
da vida real e desenvolver uma solução de modo eficiente.
• Etapas:
1. Definição do problema
2. Desenvolvimento de um modelo
3. Especificação do algoritmo
4. Projetando um algoritmo
5. Verificação da exatidão do algoritmo
6. Análise do algoritmo
7. Implementação do algoritmo
8. Teste de programa
9. Preparação da documentação.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Estrutura de Dados (ED)
• A estrutura de dados é um meio para armazenar e organizar dados com o 
objetivo de facilitar o acesso e as modificações.
• As ED representam de modo simbólico entidades e objetos do mundo real 
e definem a parte estática de um algoritmo. 
• A manipulação das ED através de declarações e instruções precisas de 
controle definem a parte dinâmica de um algoritmo. 
• A ED diminui sensivelmente a complexidade da representação dos dados, 
como também tende a criação de programas com maior desempenho.
• As EDs têm um papel importante no desenvolvimento de software 
permitindo criar programas com uma representação dos dados mais 
relevante de um problema real, de forma mais clara e limpa.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Estrutura de Dados (ED)
• Uma ED retrata as relações lógicas existente entre os dados. Forma de 
organização dada às informações de forma a permitir o acesso a elas por 
um algoritmo durante as operações de manipulação que ocorrem na 
resolução de um problema.
• Ao escolher uma estrutura de dados devemos considerar alguns 
elementos importantes:
✓De que forma essa ED será utilizada?
✓Que métodos de manipulação essas ED nos oferecem?
✓Que tipo de alocação de memória da ED utiliza?
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Estrutura de Dados (ED)
• Estruturas de dados e algoritmos estão intimamente ligados: 
✓não se pode estudar estruturas de dados sem considerar os algoritmos 
associados a elas, 
✓assim como a escolha dos algoritmos em geral dependeda 
representação e da estrutura dos dados.
• Para resolver um problema é necessário escolher uma abstração da 
realidade, em geral mediante a definição de um conjunto de dados que 
representa a situação real.
• A seguir, deve ser escolhida a forma de representar esses dados.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
ED – Escolha de representação dos dados
• A escolha da representação dos dados é determinada, entre outras, pelas 
operações a serem realizadas sobre os dados.
• Considere a operação de adição:
• A representação por dígitos decimais requer regras relativamente 
complicadas, as quais devem ser memorizadas.
• Entretanto, quando consideramos a adição de grandes números é mais 
fácil a representação por dígitos decimais (devido ao princípio baseado 
no peso relativo da posição de cada dígito).
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
ED – Tipos de Dados
• Tipo de dado = conjunto de valores (domínio) que uma variável pode 
assumir e um conjunto de operações que podem ser aplicadas sobre ele.
✓Tipos de dados básicos (tipos primitivos):
oInteiro, caractere, decimal, booleano, etc.
oNão é possível decompor um tipo primitivo em partes menores 
(eles são indivisíveis)
✓Tipos de dados estruturados:
oVetores, matrizes, registros.
oUma variável que pode agregar mais de um valor.
oAgregados de valores de tipos primitivos.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
ED – Tipos de Dados
• Os tipos de dados básicos ou primitivos ou simples são grupos de valores 
indivisíveis (como os tipos básicos integer, boolean, char e real da 
linguagem Pascal). 
✓Exemplo: uma variável do tipo boolean pode assumir o valor 
verdadeiro ou falso, e nenhum outro valor.
• Os tipos estruturados em geral definem uma coleção de valores simples 
(homogênea), ou um agregado de valores de tipos diferentes 
(heterogênea).
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
ED – Tipos de Dados
• As EDs podem ser divididas em duas formas:
✓homogênea (vetores e matrizes).
✓heterogênea (registros). 
• As estruturas homogêneas visam armazenar dados de um único tipo, 
como por exemplo, strings, booleanos, inteiros ou reais. 
• As EDs homogêneas são empregadas em situações onde as informações 
podem ser organizadas em um único tipo de dados, normalmente 
utilizando vetores e matrizes.
• As EDs são heterogêneas e são usadas na composição de diversos tipos de 
dados (registros).
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Tipo Abstrato de Dado (TAD)
• TAD = Modelo matemático, acompanhado das operações definidas sobre 
o modelo.
• Os tipos abstratos de dados são formados por um conjunto de tipos de 
dados e um conjunto de procedimentos (funções) que podem ser 
aplicadas sobre este conjunto de tipos de dados.
• Tipos Abstratos de Dados:
✓Especificam conceitualmente os dados (sua organização física e lógica).
✓Definem operações para manipulação da estrutura.
✓Geralmente não são fornecidos diretamente pela linguagem de 
programação.
✓Exemplos: Fila, Lista, Pilha, Árvore, etc.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Tipo Abstrato de Dado (TAD)
• Os TAD’s são utilizados extensivamente como base para o projeto de 
algoritmos.
• A implementação do algoritmo em uma linguagem de programação 
específica exige a representação do TAD em termos dos tipos de dados e 
dos operadores suportados.
• A representação do modelo matemático por trás do tipo abstrato de 
dados é realiza da mediante uma estrutura de dados.
• Podemos considerar TAD’s como generalizações de tipos primitivos e 
procedimentos como generalizações de operações primitivas.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Variável composta homogênea
• Estrutura de dados composta pelo mesmo tipo.
• Vetores e Matrizes.
• Tipos Char, int, double, boolean.
• Vetor: um arranjo unidimensional de dados do tipo básico, com um 
mesmo identificador (nome), mas diferenciado pela sua posição (índice) 
dentro do vetor.
0 1 2 3 ... N-2 N-1
...
índices
valores
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Variável composta homogênea - Vetor
• Exemplo:
0 1 2 3 4 5 6
20 1 4 23 10 2 5
índices
valores
índices
valores
0 1 2 3 4 5 6
Carlos Jane Vitor Luís Julio Jô Maria
índices
valores
0 1 2 3 4 5 6
1.2 0.5 1.33 10.0 2.5 30.5 12.0
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Vetor - declaração
• Uma vez que as variáveis que compõem o vetor têm o mesmo nome, o 
que distingue cada um delas é um índice, que referencia sua localização 
dentro da estrutura.
• Os Vetores são matrizes de 1 dimensão.
• <TIPO> <VARIÁVEL><[TAMANHO]><;> 
• tipo variável [tamanho];
• Exemplo: int notas[10];
• O TAMANHO precisa ser necessariamente um número inteiro e constante. 
Ele não pode ser resultado de uma expressão.
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Vetor - declaração
• O nome da variável também é chamado de uma expressão de referência 
de memória, ou simplesmente de referência de memória.
• Com os vetores, temos uma nova expressão de referência de memória: o 
operador de índice [ ]. Ele utiliza uma referência de memória 
(normalmente uma variável do tipo vetor) e um número inteiro (o índice).
• Ele retorna uma referência para o elemento correspondente ao índice. 
• O tipo do valor retornado é o mesmo tipo da declaração do vetor
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Vetor – atribuição e acesso
• Para atribuir um valor x numa determinada posição do vetor, escreve-se:
✓nome_do_vetor [posição] = valor; 
• Exemplo: notas[0]= 4; ou notas = {4, 7, 5};
• O índice zero indica a primeira posição no vetor. A expressão notas[0]
referencia a posição de memória correspondente ao elemento de índice 
zero no vetor. 
• Para somar os primeiros três elementos e armazenar o valor calculado no 
quarto elemento, escrevemos: 
• notas[3]= notas[0] + notas[1] + notas[2];
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Vetor – exemplo
• É muito comum utilizar a estrutura 
de repetição “for” para percorrer 
todos os elementos de um vetor.
• EX1- “Construa um programa que 
declare um vetor de inteiros com 12 
elementos e o inicialize com 
números fornecidos pelo usuário, 
através da entrada padrão”.
#include <iostream>
using namespace std;
int main(){ 
setlocale(LC_ALL, ""); //portugues
int vetor[12], indice;
cout << "Introduzir os elementos" << endl;
for(indice=0; indice<12; indice++){ 
cout << "vetor[" << indice << "]= ";
cin >> vetor[indice];
}
return 0;}
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Matrizes
• Uma matriz é um arranjo de várias dimensões de dados do tipo básico, 
com um mesmo identificador (nome), mas diferenciado pelas suas 
posições (índices) dentro da matriz.
0 1 2 3 ... N-2 N-1
0 [0][3]
1 [1][3]
2 [2][3]
3 [3][3] [][]
...
N-2
N-1
linhas
colunas
tipo A[linhas][colunas];
//
int A[2][4];
float B[10][10];
float salario[5][2];
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Matriz
• EX2- “Construa um programa que 
declare uma matriz de números 
reais que permita fazer a leitura de 
3 notas para 5 estudantes. Inicialize 
a matriz com as notas fornecidas 
pelo usuário, através da entrada 
padrão”.
#include <iostream>
using namespace std;
int main(){
setlocale(LC_ALL, ""); //usar portugues
float notas[5][3]; 
int i, j;
cout << "Introduzir as notas" << endl;
for(i=0; i<5; i++){ 
for(j=0;j<3;j++){
cout << "notas[" << i <<","<< j << "]= ";
cin >> notas[i][j];
}
}
return 0;}
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Registros(Struct)
• Um registro é um agrupamento de dados, os quais no necessariamente 
são do mesmo tipo. Permite organizar um grupo de variáveis como uma 
única variável. Em C++ se definem com a palavra “struct”.
• As variáveis que compreendem o registro são chamadas de elementos 
ou campos.
• Declaração:
struct nome_do_tipo_do_registro{
tipo1 campo1;
tipo2 campo2;
…
tipon campon;
}; 
struct aluno{
int ID;
string nome[30];
char inicial[1];
int idade;
float nota; }; 
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Registros (Struct)
• Referenciando campos do registro:
• Os campos individuais são referenciados por meio do operador (.)
• variavel_reg.campo;
• Exemplos:
• id = aluno.ID;
• nome = aluno.nome;
• idade = aluno.idade;
• Atribuição:
• aluno.nome = “zeca”;
ADS – ESTRUTURA DE DADOS
zavaleta.jorge@gmail.com AULA 01Prof. Dr. Jorge Zavaleta
Registros (Struct)
#include <iostream>
#include <string>
using namespace std;
int main(){
setlocale(LC_ALL, ""); 
struct aluno{
int ID;
string nome;
char inicial;
int idade;
float nota;
};
aluno al;
al.ID = 123;
al.nome = "Cezar";
al.inicial ='C';
al.idade = 20;
al.nota = 7.5;
cout << "-----------------------------"<< endl;
cout << " ID = " << al.ID << endl;
cout << " Nome = " << al.nome << endl;
cout << " A idade é " << al.idade << endl;
cout << " Nota = " << al.nota << endl;
return 0;
}