TEP_Slides-02

Universidade Federal do Espírito Santo – CCA UFES
Universidade Federal do Espírito Santo
Centro de Ciências Agrárias – CCA UFES
Departamento de Computação
Estruturas de Dados
Tópicos Especiais em Programação
Site: http://jeiks.net
E-mail: [email protected]
Universidade Federal do Espírito Santo – CCA UFES
Sumário
●
Estruturas de dados elementares;
●
Bibliotecas padrões do C++;
●
Testando e debugando;
●
Problemas.
2
Universidade Federal do Espírito Santo – CCA UFES
Estruturas de dados elementares
●
●
●
●
●
As estruturas de dados formam a parte principal de um
programa sofisticado.
A seleção da estrutura de dados correta pode fazer
enorme diferença na complexidade e no resultado da
implementação.
Escolher a melhor estrutura de dados fará com que sua
implementação seja mais fácil e com menos erros.
Escolher uma estrutura de dados ruim pode fazer com que
você gaste uma enorme quantidade de tempo e debug.
Principais estruturas de dados: pilhas, filas, dicionários,
filas de prioridades e conjuntos.
3
Universidade Federal do Espírito Santo – CCA UFES
Pilhas
●
●
Pilhas e filas são estruturas onde os itens são retirados seguindo a
ordem que foram inseridos, independentemente de seu conteúdo.
Nas pilhas, temos:
–
●
●
O último a entrar é o primeiro a sair.
As operações da pilha são:
–
push(x,s) → insere o item x no topo da pilha s;
–
pop(s) → retorna (e retira) o item no topo da pilha s;
–
initialize(s) → cria uma pilha vazia;
–
full(s), empty(s) → informa se a pilha está cheia ou vazia. Devem ser utilizados
para evitar erros ao inserir ou retirar itens.
São importantes para trabalhar com estruturas aninhadas, como:
–
Fórmulas com parênteses;
–
Chamadas recursivas de programas; e
–
Percorrer profundidade em Grafos.
4
Universidade Federal do Espírito Santo – CCA UFES
Filas
●
Nas Filas, temos:
–
●
●
●
O primeiro a entrar é o primeiro a sair.
As operações em filas são:
–
enqueue(x,q) → insere o item x na fila q;
–
dequeue(q) → retorna (e retira) o item da frente da fila q;
–
initialize(q) → cria uma fila vazia;
–
full(q), empty(q) → informa se a fila está cheia ou vazia. Devem ser
utilizados para evitar erros ao inserir ou retirar itens.
Filas são mais complicadas de implementar devido à
modificação de itens em seu início e em seu fim.
Uma ideia de utilização é não remover os itens, ou seja, utilizar
o vetor de forma cíclica, definindo sempre onde a fila começa e
onde termina no vetor.
5
Universidade Federal do Espírito Santo – CCA UFES
Dicionários
●
●
●
Os Dicionários permitem obter a informação baseando-se em
seu conteúdo, diferindo assim de pilhas e filas, que retiram o
conteúdo baseado em sua posição.
As operações em dicionários são:
–
insert(x,d) → insere o item x no dicionário d;
–
delete(x,d) → remove o item x do dicionário d;
–
search(k,d) → retorna um item com a chave k se esta existir no
dicionário d.
Tipos comuns de dicionários:
–
Estáticos: quando o conteúdo é gerado uma vez e nunca mais muda.
Ele aceita busca, mas não aceita inserção ou remoção;
–
Semi-dinâmicos: aceita inserção e busca, mas não aceita remoção;
–
Dinâmicos: aceitam todas as operações, ideal utilizar tabelas hash.
6
Universidade Federal do Espírito Santo – CCA UFES
Filas de prioridade
●
●
●
As Filas de Prioridade são estruturas de itens que suportam três
operações:
–
insert(x,p) → insere o item x na fila de prioridade p;
–
maximum(p) → retorna o item com a maior chave na lista de prioridade p;
–
extractMax(p) → retorna e retira o item com o maior chave em p.
Filas de prioridades são utilizadas para manter horários e
calendários.
Elas gerenciam quais são os próximos que serão atendidos ou que
terão preferência em:
–
Aeroportos;
–
Estacionamentos;
–
Ou qualquer outro local onde seja necessário programar eventos de
acordo com o tempo.
7
Universidade Federal do Espírito Santo – CCA UFES
Conjuntos
●
●
Os Conjuntos são coleções de elementos não ordenados
de um conjunto universal U.
Diferença entre os Conjuntos e os dicionários:
–
●
Existe a necessidade de obter a informação sobre quais os
elementos de U que não estão em um subconjunto
determinado.
As operações dos conjuntos são:
–
member(x,S) → responde se x é um elemento do conjunto S;
–
union(A,B) → constrói um conjunto com A U B;
–
intersection(A,B) → constrói um conjunto A ∩ B;
–
insert(x, S), delete(x,S) → insere ou remove o item x do
conjunto S.
8
Universidade Federal do Espírito Santo – CCA UFES
Bibliotecas padrões do C++
●
Caminho no GNU/Linux: /usr/include/c++
●
O manual pode ser um bom caminho: man
●
Site bom para estudo:
<http://www.cplusplus.com/reference>
9
Universidade Federal do Espírito Santo – CCA UFES
STL C++ – Pilha (Stack)
●
// Exemplo
// Exemplo
#include <iostream>
#include <iostream>
#include <stack>
#include <stack>
using namespace std;
using namespace std;
int main ()
int main ()
{{
stack<int> pilha;
stack<int> pilha;
for (int i=0; i<5; ++i)
for (int i=0; i<5; ++i)
pilha.push(i);
pilha.push(i);
cout << "Removendo os itens...";
cout << "Removendo os itens...";
while (!pilha.empty())
while (!pilha.empty())
{
{
cout << ' ' << pilha.top();
cout << ' ' << pilha.top();
pilha.pop();
pilha.pop();
}
}
cout << endl;
cout << endl;
return 0;
return 0;
}}
empty:
–
●
size:
–
●
constrói e insere o item;
pop:
–
●
insere um item;
emplace (c++11):
–
●
acessa o próximo item;
push:
–
●
retorna o tamanho;
top:
–
●
testa se está vazia;
remove o item;
swap (c++11):
–
troca os itens de uma fila
para a outra.
10
Universidade Federal do Espírito Santo – CCA UFES
STL C++ – Fila (Queue)
#include <iostream>
#include <iostream>
#include <queue>
#include <queue>
using namespace std;
using namespace std;
int main () {
int main () {
queue<int> fila;
queue<int> fila;
int num;
int num;
cout << "Digite numeros (0):\n";
cout << "Digite numeros (0):\n";
do {
do {
cin >> num;
cin >> num;
fila.push (num);
fila.push (num);
} while (num);
} while (num);
cout << "A fila contem: ";
cout << "A fila contem: ";
while (!fila.empty())
while (!fila.empty())
{
{
cout << ' ' << fila.front();
cout << ' ' << fila.front();
fila.pop();
fila.pop();
}
}
cout << endl;
cout << endl;
}}
●
empty:
–
●
size:
–
●
constrói e insere o item;
pop:
–
●
insere um item;
emplace (c++11):
–
●
acessa o último item;
push:
–
●
acessa o próximo item;
back:
–
●
retorna o tamanho;
front:
–
●
testa se está vazia;
remove o item;
swap (c++11):
–
troca os itens de uma fila
para a outra.
11
Universidade Federal do Espírito Santo – CCA UFES
STL C++ – Fila (deck)
O C++ também possui a estrutura deque que é
um double-ended queue, ou seja, uma fila que
pode-se trabalhar tanto em seu início quanto em
seu fim.
Olhe mais detalhes em:
<http://www.cplusplus.com/reference/deque>
12
Universidade Federal do Espírito Santo – CCA UFES
STL C++ – Dicionário
●
Exemplo no arquivo: dicionario.cpp
{muito grande para caber aqui... rs}
●
Referências dos métodos no link:
<http://www.cplusplus.com/reference/map>
13
Universidade Federal do Espírito Santo – CCA UFES
STL C++ – Filas de prioridade
#include <iostream> #include <iostream> #include <queue> #include <queue> using namespace std;
using namespace std;
int main ()
int main ()
{{
priority_queue<int> mypq;
priority_queue<int> mypq;
cout << "Adicionando 30,100,25,40" << endl;
cout << "Adicionando 30,100,25,40" << endl;
mypq.push(30); mypq.push(100);
mypq.push(30); mypq.push(100);
mypq.push(25);mypq.push(40);
mypq.push(25);mypq.push(40);
out << "Removendo os elementos...";
out << "Removendo os elementos...";
while (!mypq.empty()) {
while (!mypq.empty()) {
cout << ' ' << mypq.top();
cout << ' ' << mypq.top();
mypq.pop();
mypq.pop();
}
}
cout << endl;
cout << endl;
}}
14
Universidade Federal do Espírito Santo – CCA UFES
STL C++ – Conjuntos
●
Exemplo no arquivo: conjuntos.cpp
{muito grande para caber aqui... rs}
●
Referências dos métodos no link:
<http://www.cplusplus.com/reference/set>
15
Universidade Federal do Espírito Santo – CCA UFES
STL C++
●
Verifique mais estruturas que podem ser
utilizadas no site:
<http://www.cplusplus.com/reference/stl/>
16
Universidade Federal do Espírito Santo – CCA UFES
Testando e Debugando
●
Lembre-se sempre de testar:
–
A entrada fornecida;
–
Uma entrada errada (somente
se o enunciado informar que
serão fornecidas esses tipos
de entradas);
–
Teste os limites, tanto mínimos
quanto máximos;
–
Teste instâncias que você
conhece a saída correta;
–
Teste exemplos grandes, onde
você não sabe a resposta
correta;
–
Teste com valores randômicos.
●
Debug:
–
Quando disponível, pode-se
utilizar o gdb ou o ddd:
●
Compile com: g++ -g arquivo.cpp
–
Exiba suas estruturas de
dados;
–
Inspecione seu código;
–
Faça impressões na tela com
definições, assim elas fazem
mais sentido;
–
Crie seus arrays um pouco
maiores que o necessário;
–
Tenha certeza que seus bugs
são bugs.
17
Universidade Federal do Espírito Santo – CCA UFES
Problemas para resolver
●
●
●
Fáceis:
–
Jolly Jumpers;
–
Contest Scoreboard;
Intermediários:
–
Poker Hands;
–
Hartals;
Difícil:
–
Yahtzee.
18