Estruturas de Dados

Em todo programa de maratona o que fazemos é manipular dados. Por isso é conveniente que esses dados sejam armazenados de forma que sua utilização se torne mais fácil e eficiente. É daí que surge o estudo Estruturas de Dados. Para um bom desempenho nas competições de programação é fundamental dominar as estruturas de dados básicas, que utilizaremos constantemente.

Como regra geral, evite sempre alocação dinâmica explícita de memória e manipulação de apontadores. Normalmente basta definir todas as estruturas já com o tamanho máximo que elas precisam.

Outra regra é que é uma grande perda de tempo ficar definindo explicitamente algumas estruturas de dados, declarando sua estrutura e seus métodos. Às vezes isso ajuda, mas são casos especiais.

Linguagens

Java é uma linguagem que possui o conhecido Collections Framework que define diversas estruturas de dados avançadas no pacote java.util que podem ser realmente úteis. No entanto estas estruturas trabalham apenas com o tipo Object e não manipulam tipos de dados básicos (int, char, etc.) o que exige diversas transformações utilizando casts e as wraper classes, complicando o código e tornando-o mais extenso e menos legível, além de deixar o programa mais ineficiente. No entanto é uma boa opção de se não der para fazer o trabalho com um simples vetor.

A linguagem C não oferece bibliotecas padrões para a manipulação de estruturas muito avançadas. O máximo que se tem são matrizes e um tipo muito limitado e ineficiente de string, que nada mais é que um vetor de caracteres terminado em '\0'.

Das três linguagens principais a que oferece mais vantagens é C++. A Standard Template Library (STL) é uma extensa biblioteca que oferece diversas estruturas prontas e algoritmos para manipulá-las que atendem a praticamente toda necessidade que se possa ter em uma competição de programação. A possibilidade de se manipular qualquer tipo utilizando templates e a sobrecarga de operadores são grandes vantagens.

Estruturas

Apresentaremos aqui as principais estuturas de dados e como utilizá-las em uma competição.

Vetores

Em geral sabemos antecipadamente qual será o número máximo de elementos no vetor. Então, em C ou C++, basta fazer:

TIPO vetor[MAX_TAM];

Onde MAX_TAM é uma constante que indica o número máximo de elementos que o vetor vai guardar. Se não soubermos o tamanho do vetor em tempo de compilação e o compilador utilizado for o gcc, podemos fazer:

TIPO vetor[n];

Onde n é uma variável que indica quantos elementos deve caber no vetor. O gcc gera código para a alocação dinâmica automaticamente.

Um caso difícil de acontecer, mas que pode aparecer, é quando temos que guardar dados em vetores antes de saber qual será seu tamanho final. Isso pode acontecer, por exemplo, em um problema de grafos em que temos que usar listas de adjacência e o grafo é descrito por suas arestas. Nesse caso podemos utilizar o tipo vector de C++. Declaramos ele assim:

#include<vector>
using namespace std;
vector<TIPO> vetor;

Para adicionar um elemento elem ao seu fim:

vetor.push_back(elem);

Para saber seu tamanho:

vetor.size()

Podemos ordenar vetores em C utilizando a função qsort da stdlib.h. Para isso é necessária uma função de comparação que recebe dois elementos e retorna um valor negativo, 0 ou positivo se o primeiro elemento é menor, igual ou maior que o segundo, respectivamente. Para a ordenação de um vetor de inteiros, usamos:

#include<stdlib.h>
...
int comp(void *a, void *b) {
  return *((int*)a)-*((int*)b);
}
int main() {
  int vetor[MAX_TAM];
  ...
  qsort(vetor, n, sizeof(*vetor), comp);
  ...
}

Onde n é o número de elementos no vetor.

Mas para quê fazer isso se temos C++? É muito mais simples:

#include<algorithm>
using namespace std;
int main() {
  int vetor[MAX_TAM];
  ...
  sort(&vetor[0],&vetor[n]);
  ...
}

Para vector podemos utilizar também sort(vetor.begin(),vetor.end()).

Strings

C++ e Java dão um bom suporte para o trabalho com strings. C é uma péssima opção para trabalhar com esse tipo de dados.

Cabeçalho:

C: #include<strings.h>
C++ #include<string>
Java: (nenhum)

Declaração:

C: char s[MAX_TAM];
C++: string s;
Java: String s; ou StringBuffer s;

Consulta:

C: s[i]
C++: s[i]
Java: s.charAt(i)

Alteração:

C: s[i] = c;
C++: s[i] = c;
Java: s.setCharAt(i,c); (somente para StringBuffer)

Cópia:

C: strcpy(dest, orig);
C++: dest = orig;
Java: dest = orig;

Concatenação:

C: strcpy(dest,s1); strcat(dest, s2);
C++: dest = s1 + s2;
Java: dest = s1 + s2;

Tamanho:

C, O(n): strlen(s);
C++, O(1): s.size();
Java, O(1): s.length();

As strings em C++ possuem o método c_str() que retorna um ponteiro para a string no formato de C (vetor de char terminado em '\0').

As strings em C++ e Java ainda possuem métodos para encontrar uma string em outra, extrair substrings, inserir strings no meio de outras, inverter a cadeia, além de outros.

Pilha

Um pilha em C ou C++ ou Java de no máximo MAX_TAM elementos do tipo TIPO pode ser definida simplesmente como:

TIPO pilha[MAX_TAM]; // Vetor onde serão guardados os elementos
int tp=0; // Inteiro que diz o tamanho da pilha

É importante ter em mente que o valor tp indica a posição onde o próximo elemento deve ser inserido, ou seja, uma posição à frente do elemento no topo da pilha.

Número de elementos:

tp

Testar se a pilha está vazia:

tp == 0

Inserir um elemento elem no topo da pilha:

pilha[tp++] = elem;

Retirar o elemento do topo da pilha e guardar em elem:

elem = pilha[--tp];

Com isso temos toda a funcionalidade de uma pilha de forma bem simples e eficiente e sem precisar definir explicitamente um novo tipo.

Fila

Um fila em C ou C++ ou Java em que se insira no máximo MAX_TAM elementos do tipo TIPO pode ser definida simplesmente como:

TIPO fila[MAX_TAM]; // Vetor onde serão guardados os elementos
int fi=0; // Inteiro que aponta para o início da fila
int ff=0; // Inteiro que aponta para o fim da fila

É importante ter em mente que a todo momento o valor fi indica a posição do elemento na frente da fila e o valor ff indica a posição onde será inserido o próximo elemento.

Número de elementos:

ff - fi

Testar se a pilha está vazia:

fi == ff

Inserir um elemento elem no fim da fila:

fila[ff++] = elem;

Retirar o elemento do início da pilha e guardar em elem:

elem = fila[fi++];

Com isso temos toda a funcionalidade de uma fila de forma bem simples e eficiente e sem precisar definir explicitamente um novo tipo. Note que o tamanho do vetor poderia ser apenas o número máximo de elementos simultaneamente na fila, realizando incrementos nos ponteiros com aritmética modular. No entanto normalmente a memória é mais do que suficiente para abrigar todos os elementos que serão inseridos, o que simplifica ao máximo nossa estrutura.

Mapas

Mapas são estruturas pouco utilizadas em competições, mas às vezes são necessárias. Quando eles aparecem normalmente são para mapear strings em inteiros.

A linguagem C não oferece um suporte especial para mapas. Em geral pode-se criar dois vetores. Um que guarda as chaves e outro que guarda os valores. Faz-se uma busca seqüencial no vetor das chaves para encontrar o índice e depois obtém-se o valor no outro vetor.

O mais prático é usar C++:

#include <map>
#include <string>
using namespace std;
...
  map<string,int> mapa;
  mapa["teste"] = 10;
  string key = "teste";
  int val = mapa[s]; // val recebe 10

É bom lembrar que esse mapa é implementado utilizando árvores, o que deixa a complexidade de consulta e alteração como O(log.n).

Java também possui mapas, mas a linguagem exige que se escreva mais código.

Outras Estruturas

Existem ainda outras estruturas mas que nunca são usadas na Maratona, como heaps, árvores de sufixo, etc. Participantes da Olimpíada devem dar uma olhada em algumas dessas estruturas, já que nessa competição procura-se o máximo de eficiência. Estruturas relacionadas com grafos ou geometria serão explicadas em outra seção.

Para Saber Mais