Embed Size (px)
Citation preview
Estrutura de Dados:Aula 3 - Linguagem C
Uso de Memória
● Alocação de memória Estática – Ocorre em tempo de compilação
– no momento em que se define uma variável ou estrutura é necessário que se definam seu tipo e tamanho.
– Exemplos:● Vetores e Matrizes
● Alocação de memória Dinâmica– ocorre em tempo de execução
– variáveis e estruturas são declaradas sem a necessidade de se definir seu tamanho
– nenhuma memória será reservada ao colocar o programa em execução
PILHA
● última informação a entrar é a primeira a sair– LIFO - last in irst out
● conjunto ordenado de itens
● Os itens são adicionados e removidos pelo topo.
PILHA
● Funções
– push - coloca uma informação na pilha (empilha).
– pop - retira uma informação da pilha (desempilha).
– size - retorna o tamanho da pilha.
– stackpop - retorna o elemento superior da pilha sem removê-lo .
– empty - verifica se a pilha está vazia.
PILHA
● Pseudo-código
PILHA
● Pseudo-código
PILHA
● Pseudo-código
PILHA
● Pseudo-código
PILHA
● Pseudo-código
PILHA
● Inserção
PILHA
● Remoção
PILHA
● Resumindo
Fila
● Um item é adicionado no final da fila e é retirado no início da fila.– Primeiro que entra é o primeiro que sai
● First in, First out (FIFO)
Fila
● Função– insert ou enqueue - insere itens numa fila (ao
inal).
– remove ou dequeue - retira itens de uma fila (primeiro item).
– empty - verifica se a fila está vazia.
– size - retorna o tamanho da fila.
– front - retorna o próximo item da fila sem retirar o mesmo da fila.
Fila
● Pseudo-código
–
Fila
● Pseudo-código
–
Fila
● Pseudo-código
–
Fila
● Pseudo-código
–
Fila
● Pseudo-código
–
Fila●
Fi la
Ci r
cul a
r
–
Lista
● Similar a um pilha ou fila● Possui tamanho fixo na memória● Tipos
– Simplesmente ligada
– Lista circular
– Ordenada
– Não ordenada
●
●
Lista
● Lista simplesmente encadeada
Lista
● Lista duplamente encadeada
Lista
● Operações
– insert - insere num determinado ponto uma informação na lista.
– add - adiciona ao inal da lista uma informação.
– delete - deleta um nó da lista.
– info - retorna uma informação da lista atual.
– next - desloca o ponteiro atual da lista caminhando para o inal.
– last - desloca o ponteiro atual da lista caminhando para o início da lista.
Lista●
Pseu
do-c
ód
igo
Lista●
Pseu
do-c
ód
igo
Árvore Binária
●
Árvore Binária
●
Árvore Binária
●
Árvore Binária
● Relações
● Grau de saída do nó
● Caminho
● Nível do nó
● Altura do nó
Árvore Binária Completa
● Profundidade: K● O número total de nós é:
● Operações em Árvores Binárias
● Inserção● Pesquisa● Exclusão● Maior elemento● Menor elemento● Percorrendo uma árvore
● Operações em Árvores Binárias
● Inserção– Busca elemento
● Se não existir e for menor é colocado na subárvore da esquerda do nó raiz
● Se não existir e for maior é colocado na subárvore da direita do nó raiz
● Operações em Árvores Binárias
● Inserção–
● Operações em Árvores Binárias
● Pesquisa– Se o valor for igual a raiz
● Encontrou o valor
– Se valor de busca menor que o da raiz● Buscar na subárvore da esquerda.
– Se valor de busca maior que o da raiz● Buscar na subárvore da direita.
● Operações em Árvores Binárias
● Pesquisa–
● Operações em Árvores Binárias
● Exclusão– Exclusão da folha
● Operações em Árvores Binárias
● Exclusão– Exclusão de nó com um filho
● Operações em Árvores Binárias● Exclusão
– Exclusão de nó com dois filhos● Substituir o valor do nó a ser retirado pelo valor
sucessor (o nó mais à esquerda da subárvore direita).
● Operações em Árvores Binárias
● Exclusão
– Exclusão de nó com dois filhos● Substituir o valor do nó a ser retirado pelo valor
antecessor (o nó mais à direita da subárvore esquerda).
● Operações em Árvores Binárias
● Exclusão
–
● Operações em Árvores Binárias
● Exclusão
–
● Operações em Árvores Binárias
● Maior elemento– Elemento mais a direita
● Operações em Árvores Binárias
● Menor elemento– Elemento mais a esquerda da árvore
● Operações em Árvores Binárias
● Percorrendo uma árvore– Visitar todos os nós
– pré-ordem ou profundidade●
● Operações em Árvores Binárias
● Percorrendo uma árvore– Visitar todos os nós
– pré-ordem ou profundidade●
● Operações em Árvores Binárias
● Percorrendo uma árvore– Visitar todos os nós
– pós-ordem ●
● Operações em Árvores Binárias
● Percorrendo uma árvore– Visitar todos os nós
– pós-ordem ●
● Operações em Árvores Binárias
● Percorrendo uma árvore– Visitar todos os nós
– ordem simétrica●
● Operações em Árvores Binárias
● Percorrendo uma árvore– Visitar todos os nós
– ordem simétrica●
● Operações em Árvores Binárias
● Percorrendo uma árvore– Visitar todos os nós
– ordem simétrica●
Árvore Binária
●
Árvore Binária
●
Árvore Binária
●
Ordenação
● BubbleSort
● Ordenação por Seleção
● Ordenação por Inserção
● QuickSort
● MergeSort
● HeapSort
● ShellSort
● Ordenação Digital
● Ordenação Parcial
