Estruturas de Dados em JAVA

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);
...
}



bons xtudos,...