Blog de Helton Duarte

Mais um pouco de conhecimento adquirido!

Bem pessoal, venho hoje postar a segunda aula do nosso curso “Programando melhor”, como sempre baseado no livro Programming Challenges, de Steven Skiena e Miguel Revilla, falando hoje um pouco sobre Estruturas de Dados, as quais infelizmente eu não vi no curso do CEFET-RN (atual IF-RN), contudo acredito serem essenciais para um bom programador. No final estarei indicando os links de exercícios para vocês praticarem o assunto estudado, blz? Vamos começar!

Aula 2 – Estruturas de Dados

Conteúdo: abordagem das estruturas de dados elementares, assim como mais dicas de como abordar um problema e os métodos para testar/debuggar.

Estruturas de dados são primordiais em qualquer programa robusto, sendo primordial a escolha da estrutura certa para representar o problema, evitando códigos feios e diversos bugs pela frente. ^^

Iremos mostrar as principais estruturas de dados (pilhas, filas e dicionários), com algumas operações básicas para manipulá-las. Para aqueles programadores de C++ e Java já existem bibliotecas prontas para esse controle, contudo é interessante o entendimento de como elas trabalham por dentro. Para C++: stl.h; para Java: java.util.

Pilhas: as pilhas e as filas são estruturas nas quais seus itens são controlados de acordo com a ordem de inserção e não pelo conteúdo armazenado. Ao inserir ou remover um item, fazemos em seu topo. As operações básicas são as seguintes:

Push(x, s) – Insere o item x no topo da pilha s.

Pop(s) – Retorna (e remove) o item do topo da pilha s.

Initialize(s) – Cria uma pilha vazia.

Full(s), Empty(s) – Testa se a pilha pode aceitar mais Push ou Pop, respectivamente.

Obs.: Não há operação para procurar um item na pilha, justamente pelo fato que o conteúdo não importa, somente é vista a ordem de inserção.

Filas: assim como nas pilhas, não importa o conteúdo, apenas a ordem. Nas filas os itens são inseridos em seu final e removidos do início. Um exemplo interessante do uso de filas é quando se trabalha com baralhos de cartas (tente fazer um exemplo para entender melhor XD ). A seguir, as operações:

Enqueue(x,q) – Insere o item x no fim da fila q.

Dequeue(q) – Retorna (e remove) o item da frente da fila q.

Initialize(q), Full(q), Empty(q) – Análogos às operações de pilhas.

Filas precisam de um pouco mais de cuidado, já que acontecem coisas nos dois lados da estrutura. O modo mais simples de implementação é utilizando arrays (vetores), inserindo no final e movendo todos os elementos restantes para preencher o espaço vazio do Dequeue. Contudo, temos que pensar um pouco antes de criar filas com vetores, pois é bastante desperdício esse movimento a cada Dequeue e o fato de filas circulares, ou seja, o primeiro e o último elemento são iguais. Por essas e outras, filas são estruturas mais simples de se trabalhar com listas encadeadas (um pouco sobre ponteiros para os adeptos de Pascal aqui) do que com vetores.

Dicionários: estruturas as quais pode-se trabalhar com o conteúdo dos elementos, tendo como operações primárias:

Insert(x,d) – Insere o item x no dicionário d.

Delete(x,d) – Deleta o item x (ou o item apontado por x) do dicionário d.

Search(k,d) – Retorna o item com a chave k se o mesmo existir no dicionário d.

Nós precisamos, então, saber qual é a melhor maneira de se trabalhar com esse tipo de estrutura e assim segue abaixo cada caso:

Dicionários estáticos => Essas estruturas são criadas uma vez e nunca mais mudadas, precisando então apenas do Search, não mais do Insert ou Delete. O melhor jeito para se trabalhar com eles é na utilização de vetores, sendo então sua preocupação apenas de como mantê-los ordenados, para otimizar suas buscas, contudo isso iremos ver em outras aulas.

Dicionários semi-dinâmicos => São aqueles em que se pode inserir ou pesquisar (Search), porém não pode deletar. Se soubermos o máximo de elementos, é possível a utilização de vetores, contudo sem essa informação será preciso novamente trabalhar com listas encadeadas.

Dicionários dinâmicos => Aqueles em que é permitida qualquer operação. Como muitos já devem ter percebido, a melhor maneira de se implementar esse tipo de estrutura é com a utilização de listas encadeadas, somente, para não tornar nosso código extremamente horroroso.

Finalmente chegamos ao fim dessa abordagem sobre estruturas de dados propriamente dita, esperando ter conseguido relembrar e otimizar o uso delas, além de fazê-lo mais preparado para os problemas que virão. A seguir colocarei mais dicas de resolução de problemas.

Sua solução começa agora

• Leia o programa atentamente – Leia cada linha do problema cuidadosamente e releia quando o juiz online lhe reportar algum. Veja até mesmo a história que você acha não ter importância, no início do problema, porém preste bastante atenção às descrições de entrada/saída, além de seus exemplos.
• Não assuma nada – Esteja atento a instruções de entrada não especificadas, números sem limites, linhas longas de entrada, números negativos, etc. NÃO ESQUEÇA: qualquer situação que não é explicitada como proibida deve ser assumida como possível!
• Não tão rápido – Não se preocupe tanto com eficiência, a menos que você esteja passando por problemas com o juiz (como um conhecido “Time limit exceeded”). Ao conhecer bem as especificações, ou seja, sabendo qual o valor máximo para as entradas, é possível prever quão rápido necessitará ser seu algoritmo. IMPORTANTE: eu não estou incentivando códigos feios e cheios de gambiarras, todavia não é preciso um cuidado excessivo com isso logo no começo do trabalho, deu pra entender?

Testando e “debuggando”

Aprender a evitar erros bestas que podem penalizá-lo em situações de competição é crucial para o sucesso em qualquer lugar, por isso seguem abaixo algumas táticas:

• Mesmo que pareça simples, é importantíssimo o teste feito com as entradas dadas pelo problema, pois lhe dirá qual a maneira de colocar sua saída na tela;
• Se o problema exige determinadas ações ao se colocar entradas inválidas, certifique-se primeiramente que elas estão sendo feitas;
• Crie sempre situações de teste simples, as quais você pode testar no papel e compare as soluções, pois pode ajudar na procura de erros mais comuns;
• Coloque sempre entradas gigantescas (no limite do permitido), para ver como o programa se comporta, ou seja, se ele não fica “doido” com números grandes, comportando-se de maneira inesperada.
• Conheça seu “Debugger” – Qualquer ambiente de desenvolvimento vem agora com um “debugger” (a opção de executar o programa linha por linha) e é preciso que você o conheça claramente. Quanto mais cedo você começar a usá-lo, mais tempo e frustação que você vai evitar ^^;
• No caso de não possuir esse “debugger”, crie pontos no programa para imprimir certos valores importantes, entretanto faça-os com linhas relevantes para ler a saída rapidamente e achar os possíveis erros;
• Faça seus vetores um pouco maiores do que o necessário – precisa comentar? É apenas para garantir que a memória não vai “acabar” durante a execução…

É isso aí! Agora vamos para os exercícios e, como já avisado, apenas colocarei os links para eles no site do UVa Online Judge:

• Jolly Jumpers – Nível 1
  
• Poker Hands – Nível 2
  
• Hartals – Nível 2
  
• Crypt Kicker – Nível 2
  
• Stack ‘em Up – Nível 1
  
• Erdös Numbers – Nível 2
  
• Contest Scoreboard – Nível 1
  
• Yahtzee – Nível 3
  

Posts interessantes:

• Programando melhor: Exercícios 1 (Parte II)
• Programando melhor: Exercícios 1 (Parte I)
• Programando melhor: Aula 1 – Começando
• Cursos grátis na Internet – MIT

Como falei no meu Twitter: Bora lá pessoal, nossa guerra ainda está no começo! Animação! Qualquer dúvida sobre o assunto pode perguntar. Novamente, quando tiver dicas sobre os exercícios postarei e vocês façam o mesmo. Comentem!

Helton de Melo Duarte

“Ainda que a figueira não floresça, nem haja frutos nas vides; ainda que falhe o produto da oliveira, e os campos não produzam mantimento; ainda que o rebanho seja extirpado da malhada e nos currais não haja gado; todavia eu me alegrarei no Senhor, exultarei no Deus da minha salvação.” Habacuque 3.17,18

This entry was posted on sexta-feira, fevereiro 20th, 2009 at 21:08 and is filed under Programando Melhor. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.