Revisão AV2

Prévia do material em texto

ESTRUTURAS DE DADOS EM C – REVISÃO AV2
FUNÇÕES
Parâmetros
• Conjunto de comandos que realiza uma tarefa específica (módulo).
• Necessário chamar a função. 
• Argumentos vs parâmetros 
• int soma (int a, int b);
• void alterar(int a, float x, float y);
• void calculadora(int a, int b, char aux);
• void troca(int *r, int *s);
int main ( ) {
int nota = 3;
int num = 4;
float suco = 6.5;
float biscoito = 9.5;
soma (nota, num);
alterar (nota, suco, biscoito);
troca (&nota, &num);
}
ESTRUTURAS DE DADOS:
HOMOGÊNEAS X HETEROGÊNEAS
Homogêneas:
• São conjuntos de dados formados 
pelo mesmo tipo de dados. 
• Agrupamento de várias 
informações ou valores 
dentro de uma mesma 
variável
• Vetores
• Matrizes
• Listas 
• Pilhas
• Filas
• Árvore
Heterogêneas:
• São conjuntos de dados formados 
por tipos de dados diferentes.
• Onde teremos informações de vários 
tipos: Nome, telefone, endereço etc.
(como os registros).
• Estruturas
Organização dos dados
• Pilhas
• A regra é LIFO - Last In, First Out, ou seja, o último a entrar é o primeiro a sair da estrutura.
• Ex: Imaginar uma pilha de pratos. 
• (o último prato a entrar na estrutura, esta sempre no topo.)
• Filas
• A regra é FIFO - First in, first out), ou seja, o primeiro elemento a entrar na estrutura é o primeiro a sair.
• Ex: imagine uma fila de um banco. 
• (inserir um nó na última posição da estrutura, retirar um nó no primeiro elemento da estrutura)
Características de cada uma das estruturas
Organização dos dados
• Listas
• A regra é manipular o acesso aos elementos do mesmo tipo, seja eles unidimensionais (vetores) ou 
multidimensionais (matrizes) por meio de índices.
• Ex: Imagine Lista de compras do supermercado. (duas casas)
• (Os dados são armazena e o acesso é sequencial aos elementos.)
• Árvores
• A forma como os dados são organizados em uma árvore é representada de forma hierárquica, 
depende do tipo específico de árvore que está sendo utilizada.
• Ex: Imagine uma organização hospitalar que tem ou não restrições.
• Percurso em ordem (in-order traversal), Percurso em pré-ordem (pre-order traversal). 
• Percurso em pós-ordem (post-order traversal), percurso em largura (level-order traversal). 
Características de cada uma das estruturas
Árvores
Percurso em pré-ordem (pre-order traversal) 
No percurso em pré-ordem, primeiro visitamos o nó raiz, em seguida, visitamos 
o nó esquerdo e, por fim, visitamos o nó direito. 
Essa ordem é seguida recursivamente para todos os nós da árvore.
Árvores
Percurso em pós-ordem (post-order traversal)
No percurso em pós-ordem, primeiro visitamos o nó esquerdo, em seguida, visitamos 
o nó direito e, por fim, visitamos o nó raiz. 
Essa ordem é seguida recursivamente para todos os nós da árvore.
Árvores
A hierarquia é estabelecida através da relação entre os nós
• Nó Raiz: É o nó no topo da árvore e não possui um nó pai. É a partir do nó raiz que 
toda a árvore é acessada e percorrida.
• Nós Pais: Cada nó, exceto o nó raiz, tem um nó pai. O nó pai é o nó imediatamente 
acima do nó atual na hierarquia. Ele é responsável por gerar o nó atual.
• Nós Filhos: São os nós que têm um nó pai. Cada nó pode ter zero ou mais nós filhos, 
dependendo do tipo específico de árvore. 
• Nós Irmãos: Os nós que têm o mesmo nó pai são chamados de nós irmãos.
• Nós Folhas: São os nós que não possuem nós filhos. São os elementos mais baixos da 
hierarquia da árvore e estão no nível mais baixo da árvore.
Árvores
O grau de saída (ou simplesmente grau) de um nó
É definido como o número de filhos deste nó que estamos nos referindo.
• Nesse exemplo, os nós A e C possuem grau 2.
• Os nós B, D e E tem grau zero.
• O nó A é o nó raiz da 
árvore. A é pai de C e B. 
• O nó C é nó raiz da 
subárvore direita de A e
é irmão de B. 
• O D e E é neto de A.
• Os nós B, D e E são nós 
folhas.
• A e C são nós interiores. 
Nós que não são folha 
são chamados de nós 
interiores.
• Uma árvore de grau 2 é 
chamada binária.
• Uma árvore de grau 3 é 
chamada ternária.
• Uma árvore genérica de 
grau m, m-ária. 
• Listas - A regra é, os dados são armazena e o acesso é sequencial aos elementos. (Ordem)
Lista, Pilha e Fila
Definições Simples
Tomate
Cenoura
Maça
Alface
Banana
Macarrão
Batata
Abacate
Alho
TomateCenoura
Maça
Alface Banana MacarrãoBatataAbacate
Alho
Lista de 
compras
...
• Pilhas - A regra é, o último a entrar é o primeiro a sair da estrutura.
Lista, Pilha e Fila
Definições Simples
• Filas - A regra é, o primeiro elemento a entrar na estrutura é o primeiro a sair.
Lista, Pilha e Fila
Definições Simples
Lista, Pilha e Fila
Exemplo prático
Z = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Empilhar Pilha A = {3, 2, 1}
Entrada de dados
Desempilhar Pilha B = {15, 16, 17}
Saída de dados
Z = {4, 5, 6, 7, 8, 9, 15, 16, 17}
Z = {8, 3, 5, 1, 4, 9, 10, 2, 6}
Inserir Lista Ordenada A = {3, 5, 8}
Entrada de dados
Antes
Depois
Antes
Depois
Ordem de Saída do conjunto Z é da Esquerda e a Entrada é a Direita.
Remover Lista Ordenada B = {20, 21, 22}
Saída de dados
Z = {1, 4, 9, 10, 2, 6, 20, 22}
Z = {1, 7, 5, 4, 9, 8, 0, 2, 6}
Antes
Depois
Z = {4, 9, 8, 0, 2, 6, 34, 35, 36}
Enfileirar Fila A = {1, 7, 5}
Entrada de dados
Desenfileirar Fila B = {34, 35, 36}
Saída de dados
Ordenação
Algoritmos de Ordenação
Bubble Sort: Compara elementos próximo e também trocando-os se estiverem na ordem 
errada. Esse processo é repetido até que a lista esteja completamente ordenada.
Ordenação
Algoritmos de Ordenação
Insertion Sort: percorre uma lista de elementos e insere cada elemento em sua posição 
correta dentro de uma sublista já ordenada. Esse processo é repetido até que a lista 
esteja completamente ordenada.
Ordenação
Algoritmos de Ordenação
Selection Sort: divide a lista em duas partes: uma sublista ordenada e uma sublista não 
ordenada. Ele percorre repetidamente a sublista não ordenada, encontra o elemento 
mínimo e o coloca na posição correta na sublista ordenada. Esse processo é repetido até 
que a sublista não ordenada esteja vazia e a lista esteja completamente ordenada.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17