aula 01 - apresentação

Prévia do material em texto

Estrutura 
de dados 
em C
A U L A 0 1 –
A P R E S E N T A Ç Ã O
P R O F ª O T I L I A
2
Ementa
• Estruturas de dados heterogêneas. 
• Modularização. 
• Listas, Pilhas e filas. 
• Ordenação. 
• Árvores.
3
Objetivos
• Aplicar o uso de agregados heterogêneos e alocação dinâmica, baseando-se em conceitos de 
gerenciamento de memória, para propiciar melhor organização do código e permitindo maior 
manutenabilidade.
• Aplicar a passagem por referência de parâmetros, através de apontadores de endereços das 
informações, com o objetivo de manipular dados de forma mais precisa e diversificada.
• Construir códigos modularizados, utilizando fundamentos de tipos abstratos de dados, para 
desenvolver programas que encapsulem informações, simplifiquem métodos já criados e 
melhorem a legibilidade e manutenção.
• Diferenciar os tipos de problemas, em função dos requisitos e da solução a ser apresentada, 
para definir qual a melhor estrutura de dados a ser utilizada. 
• Executar algoritmos de busca e ordenação, desenvolvidos a partir de modelos e exemplos 
propostos, a fim de criar códigos capazes de pesquisar e ordenar dados através de métricas 
estabelecidas..
4
Temas de Aprendizagem
1. Estruturas de dados heterogêneas
1. Ponteiros com a utilização da linguagem de programação c
2. Estrutura de dados heterogênea
3. Structs com a utilização da linguagem de programação c
4. Estruturas de dados aninhadas, os vetores de estruturas e a instrução 
typedef usando a linguagem de programação c
5
Temas de Aprendizagem
2. Modularização
1. Conceitos gerais de procedimentos e funções
2. Tipos de funções predefinidas na linguagem c
3. Passagem de parâmetros por valor e por referência
4. Escopo das variáveis locais e globais
6
Temas de Aprendizagem
3. Listas, pilhas e filas (crédito digital)
1. principais conceitos envolvidos na manipulação de dados na memória
2. Contrastação da forma de manipulação por encadeamento da manipulação 
com estruturas sequenciais
3. Algoritmos das principais operações, 
baseados na linguagem C, e as características 
peculiares de pilhas
4. Algoritmos das principais operações, 
baseados na linguagem C, e as características 
peculiares de filas
7
Temas de aprendizagem
4. Ordenação
1. Conceitos fundamentais de ordenação para aplicação de métricas de 
classificação e escolha adequada do método na resolução de problemas
2. Algoritmos de ordenação da bolha, 
inserção e seleção para desenvolvimento 
de solução rápida e eficiente para 
implementação em linguagem C
8
Temas de aprendizagem
5. Árvores
1. Principais conceitos, as propriedades básicas e os termos relativos à árvore
2. Árvores binárias, suas particularidades 
e aplicações
3. Principais árvores de pesquisa, suas 
particularidades e aplicações
9
Procedimentos de avaliação
10
• AV1 - Contemplará os temas abordados na disciplina até a sua realização e será assim composta:
• Prova individual com valor total de 7 (sete) pontos;
• Atividades acadêmicas avaliativas com valor total de 3 (três) pontos, assim distribuídos:
• Realização de quiz avaliativo sobre os temas 1 e 2, vinculados ao conteúdo digital, com valor total de 3 (três) pontos, 
acompanhados pelo professor da disciplina.
A soma de todos os instrumentos que possam vir a compor o grau final da AV1 não poderá ultrapassar o grau máximo de 10 
(dez) pontos.
• AV2 - Contemplará todos os temas abordados pela disciplina e será composta por uma prova teórica no 
formato PNI - Prova Nacional Integrada, no seguinte formato: PNI de 0 a 5,0. As demais atividades 
acadêmicas avaliativas devem somar 5 (cinco) pontos. Para esta disciplina consiste no desenvolvimento de 
alguns programas simples envolvendo a contatação da forma de manipulação por encadeamento da 
manipulação com estruturas sequenciais e está definida na aula 10.
• AVD - Avaliação digital do(s) tema(s) / tópico(s) vinculado(s) ao crédito digital no valor total de 10 (dez) 
pontos ou AVDs - Avaliação digital do(s) tema(s) / tópico(s) vinculado(s) ao crédito digital no valor total 
de 10 (dez) pontos.
• AV3 - Contemplará todos os temas abordados pela disciplina. Será composta por uma prova no formato 
PNI - Prova Nacional Integrada, com total de 10 pontos, substituirá a AV1 ou AV2 e não poderá ser 
utilizada como prova substituta para a AVD.
11
Bibliografia Básica
12
• ASCENCIO, A.F.G., ARAUJO, G.S. Estrutura de Dados: Algoritmos, 
Análise da Complexidade e implementações em Java e C/C++. 1ª Ed. 
São Paulo: Pearson Prentice Hall, 2010. 
Disponível em: https://plataforma.bvirtual.com.br/Acervo/Publicacao/1995
• BALIEIRO, Ricardo. Estrutura de dados. 1ª Ed. Rio de Janeiro: SESES, 
2015. Disponível em: 
http://repositorio.novatech.net.br/site/index.html#/objeto/detalhes/2D35A184-BF64-4419-9DA9-D1ED12A97017
• VETORAZZO, Adriano S, et al. Estrutura de Dados. Porto Alegre: 
Sagah, 2018. Disponível em: 
https://integrada.minhabiblioteca.com.br/#/books/9788595023932/cfi/0!/4/2@100:0.00
13
https://plataforma.bvirtual.com.br/Acervo/Publicacao/1995
http://repositorio.novatech.net.br/site/index.html#/objeto/detalhes/2D35A184-BF64-4419-9DA9-D1ED12A97017
https://integrada.minhabiblioteca.com.br/#/books/9788595023932/cfi/0!/4/2@100:0.00
14
Datas Importantes
• AV1 – 19/04
• AV2 – 07/06
• AV3 – 27/06
• AVD – 26/05 à 11/06
• AVDs – 16/06 à 24/06
Estrutura de Dados em C
AU L A 0 1 – P ONT E I R OS C OM A U T I L I Z A Ç ÃO 
D A L I N G UA G EM D E P R O G R AMA ÇÃO C
P R O F ª O T I L I A
15
Objetivos
• Introduzir os conceitos de estruturas de dados, utilizando as 
linguagens C e C++ para ensinar a melhor aplicação de algoritmos, 
além de apresentar a motivação e construção de agregados 
heterogêneos.
16
Situação-Problema
Imagine que seria preciso criar algoritmos específicos para 
1) Manipular um conjunto de fichas de um fichário; 
2) Organizar as pessoas que querem ser atendidas num guichê; 
3) Organizar um conjunto de pratos que estão sendo lavados, um a um; e 
4) Visualizar o conjunto de pessoas que trabalham em uma empresa, tendo em conta sua função. 
Qual seria a melhor solução para realizar operações em cada uma destas situações?
Estrutura de Dados
• Programa = Algoritmo + Dados
• Resolução de Problema: abstração
• Cadastro de Clientes
• Quais dados são importantes?
• A idade do cliente é importante?
• A cor do cabelo do cliente é importante?
• Qual o algoritmo usar?
• Como encontrar um cliente?
• Como inserir um novo cliente?
17
Estrutura de Dados
• O que é um “dado digital”?
• O que o diferencia de “lixo digital”?
• Sua organização
• Sabemos como encontrá-los
• E isso permite...
• Busca
• Remoção
• Inserção...
• Organização → Desempenho
18
No Dia-a-dia
19
Estrutura de dados no dia-a-dia
• Representar a organização de uma empresa
• 1 presidente, 1 vice-presidente, 1 diretor de vendas e 1 de criação, este último 
com 2 subdiretores?
20
Árvore 
(hierarquia!)
Presidente
Vice-
Presidente
Diretor de 
Vendas
Diretor de 
criação
Subdiretor 1 Subdiretor2
Estrutura de dados no dia-a-dia
• Como representar a bibliografia do curso?
• ASCENCIO, A.F.G., ARAUJO, G.S. Estrutura de Dados: Algoritmos, Análise 
da Complexidade e implementações em Java e C/C++. 1ª Ed. São Paulo: 
Pearson Prentice Hall, 2010. 
• BALIEIRO, Ricardo. Estrutura de dados. 1ª Ed. Rio de Janeiro: SESES, 2015. 
• VETORAZZO, Adriano S, et al. Estrutura de Dados. Porto Alegre: Sagah, 
2018.
21
LISTA
Estrutura de dados no dia-a-dia
• Como o motoboy organiza as pizzas?
22
Pilha
Estrutura de dados no Dia-a-dia
• Como as pessoas esperam no banco?
23
Fila
Estrutura de dados no Dia-a-dia
• Como representar os trajetos possíveis em uma companhia aérea?
24
Grafo
Tipos de 
estrutura de 
dados
25
Tipos de Estrutura de Dados
• Lineares x Não-lineares
• Lineares
26
• 1º elemento bem definido
• Último elemento bem definido
• Elementos intermediários: um antecessor e um sucessor
Tiposde Estrutura de Dados
• Não-lineares
27
• Árvore: relação hierárquica
• Grafo: relação qualquer
Presidente
Vice-
Presidente
Diretor de 
Vendas
Diretor de 
criação
Subdiretor 1 Subdiretor2
É fundamental 
identificar a melhor
estrutura para cada 
problema!!!
Formas de 
armazenamento de 
manipulação de 
estrutura de dados
28
Armazenamento de Estruturas
• Duas maneiras de armazenar
• Sequencial (ou contígua)
• Espaço pré-alocado
• Tamanho pré-definido
• Encadeada (ou ligada)
• Tamanho inicialmente desconhecido
• Alocação à medida da necessidade
29
Armazenamento de Estruturas
• Iniciaremos com as sequenciais...
• Qual o tipo de variável de C/C++ que serve para guardar, 
sequencialmente, muitos dados iguais?
• Vetores
• Vamos começar com uma lista de números
• Que operações vocês conseguem imaginar?
• O que gostaríamos de poder fazer com uma lista?
30
Manipulação de Estruturas
• Imagine uma lista de notas
• Inicialmente vazia
• Inserir notas
• Remover notas
• Buscar notas...
• Como realizar essas tarefas?
• Existiria muita diferença se tivéssemos uma lista de alunos? Ou uma lista 
de rendimentos?
31
Manipulação de Estruturas
• Inserir, Remover e Buscar serão semelhantes para qualquer lista
• Sempre que precisarmos inserir, o código é o mesmo
• Que tal criarmos um algoritmo chamado inserir, por exemplo?
• Sempre que precisarmos inserir um valor, bastará solicitar que o computador 
execute o algoritmo inserir
32
Manipulação de Estruturas
• Esses “algoritmos” com nome recebem o nome de funções
• Antes de estudarmos as estruturas em si...
• Vamos aprender a implementar funções!
33
Funções
34
Funções 
• Funções pré-definidas
• abs(x)
• O que fazer se a função abs(x) não existisse?
35
C++
C
Funções
• abs “na raça”:
• Se tivéssemos de usar isso toda hora...?
• O que fazer?
• Copiar e colar?
36
Que tal criar 
nosso próprio 
abs?
Criando nossas 
próprias 
funções
37
Criando funções
• Passo 1: criar um programa que calcule o perímetro de um círculo de 
raio 2
• P = 2∙Π∙R
• Π = 3,141592
• Passo 2: transformar o cálculo em uma função chamada calcula
• As variáveis criadas dentro da função só existem dentro desta função
• Elas são chamadas variáveis locais
• Não é possível acessar uma variável local a não ser de dentro da própria 
função
• Os valores das variáveis locais são destruídos quando a função finaliza
38
Criando Funções
• Passo 3: modificar a função calcula para que ela para que ela 
retorne o resultado, ao invés de imprimi-lo
• return deve sempre retornar um valor do tipo correto
• return pode ser usado sem nenhum valor em funções cujo retorno é do tipo 
“void”
• Passo 4: modificar a função calcula para que ela receba o raio do 
círculo como parâmetro
• Os parâmetros funcionam como variáveis locais
• O valor fornecido como parâmetro (o raio) é copiado para essa “variável local”
39
Criando Funções
• Passo 5: modificar a função calcula para que ela retorne, além do 
perímetro da circunferência, também a área do círculo e o volume 
da esfera
• A = Π∙R2
• V = (4/3) ∙Π∙R3
• Parâmetros cujo nome é precedido por & são passados “por referência”, isto é, 
podem ser modificados na função
• Passo 6: mova a função para o fim do arquivo
• A declaração inicial é chamada “protótipo de função”
40
Variáveis Globais
42
Variáveis Globais
• Variáveis das funções: locais
• Passar dados: parâmetros
• Receber respostas: return, parâm. por ref.
• Não há um jeito diferente?
• Sim: Variáveis globais
• Declarar variável junto com os protótipos das funções
• Cuidado!
• Problemas!
• • Exemplo
43
Aprofundar no 
conhecimento
44
Leitura Específica
• ASCENCIO, A.F.G., ARAUJO, G.S. Estrutura de Dados: Algoritmos, 
Análise da Complexidade e implementações em Java e C/C++. 1ª Ed.. 
São Paulo: Pearson Prentice Hall, 2010. Disponível em: 
https://plataforma.bvirtual.com.br/Acervo/Publicacao/1995
Páginas 1 a 10
• Estruturas de Dados e Algoritmos - Structs. Disponível em: 
https://www.cos.ufrj.br/~rfarias/cos121/aula_04.html
45
https://plataforma.bvirtual.com.br/Acervo/Publicacao/1995
Aprenda +
• Video "O que são Estruturas de dados?". 
Disponível em: 
https://www.youtube.com/watch?v=Frkc_otGrGU
•
Video "Por que e como estudar ALGORITMOS e 
ESTRUTURA DE DADOS?". 
Disponível em: 
https://www.youtube.com/watch?v=SqBgnMgFQTU
46
https://www.youtube.com/watch?v=Frkc_otGrGU
https://www.youtube.com/watch?v=SqBgnMgFQTU