Estruturas de Dados

public class LinearProbingHashST< Key, Value>
{
   private int N;
   private int M = 16;
   private Key[] keys;
   private Value[] vals;

   public LinearProbingHashST( ) {
      keys = (Key[]) new Object[M];
      vals = (Value[]) new Object[M];
   }

   private int hash( Key key) { 
      return (key.hashCode( ) & 0x7fffffff) % M; 
   }

   private void resize( int cap) {
      LinearProbingHashST< Key, Value> t;
      t = new LinearProbingHashST< Key, Value>( cap);
      for (int i = 0; i < M; i++)
         if (keys[i] != null)
            t.put( keys[i], vals[i]);
      keys = t.keys;
      vals = t.vals;
      M = t.M;
   }

   public void put( Key key, Value val) {
      if (N >= M/2) resize(2*M);
      int i;
      for (i = hash( key); keys[i] != null; i = (i+1) % M)
         if (keys[i].equals( key)) { 
            vals[i] = val; 
            return; 
         }
      keys[i] = key;
      vals[i] = val;
      N++;
   }

   public Value get( Key key) {
      int i;
      for (i = hash( key); keys[i] != null; i = (i+1) % M)
         if (keys[i].equals( key))
            return vals[i];
      return null;
   }
}

O tema dessas notas é o mesma de boa parte da Ciência/Engenharia da Computação:  a construção de programas rápidos, programas que resolvem problemas de maneira eficiente (ou seja, sem desperdício de tempo).

O segredo de muitos programas rápidos está na maneira como seus dados são organizados durante o processamento, ou seja, na estrutura de dados (data structure) empregada pelo programa. Muitas vezes, a melhor maneira de organizar os dados não é óbvia nem simples. Mas uma boa estrutura de dados tem um efeito dramático sobre a velocidade do programa. (É o caso, por exemplo, da estrutura conhecida como árvore rubro negra.)

O estudo de boas estruturas de dados é o assunto central destas notas.  Isso envolve, em particular, o estudo de algoritmos para a criação e manipulação dessas estruturas.  Assim,  o título deste sítio poderia ser Algoritmos e Estruturas de Dados.

Conteúdo deste sítio:

• Aulas, descaradamente copiadas do livro de Sedgewick e Wayne.
• Dicionário de abreviaturas e termos técnicos.
• Livros e sítios na rede WWW.

Pré-requisito: Supõe-se que o leitor já teve um curso de introdução à programação e um curso de projeto de algoritmos.

 

Quais foram as disciplinas mais importantes que você cursou no BCC (Bacharelado em Ciência da Computação na USP)?  Resultado de levantamento feito entre ex-alunos (2009-2013):