Algoritmos

Estruturas de Dados

O estudo sobre estruturas de dados é algo muito interessante para todos os que gostam de programar ou de procurar boas soluções para resolver problemas computacionais. Mas não é só no meio digital que esses estudos são aplicados. Filas de banco, organogramas, e produtos empilhados em uma prateleira de um supermercado são exemplos de estruturas que possuem regras para que você possa interagir para resolver um problema real.

Podemos fazer um comparativo bem simples entre um caixa de um banco e um processador de um computador. Vejam que, no banco não há caixas suficientes para atender prontamente a todos os que chegam para serem atendidos. Da mesma forma ocorre no computador. Internamente há muitas tarefas a serem realizadas e cada tarefa deve esperar em uma fila para que possa utilizar o processador. A diferença maior está na velocidade em elas são atendidas.

Observe o funcionamento geral de uma fila: chegue, espere no final da fila até você ser atendido. Esse mecanismo resolve o problema de poucos caixas para atender um número grande de clientes no banco. Agora veja uma pilha: coloque item por item, um sobre o outro. Quando for retirar, vá tirando item por item, mas sempre os de cima. Se puxar qualquer item que não seja o de cima, a pilha pode desabar. É com esse propósito que as estruturas de dados são usadas para resolver problemas do mundo real, no meio computacional.

“Na Ciência da computação, uma estrutura de dados é um modo particular de armazenamento e organização de dados em um computador de modo que possam ser usados eficientemente.” [1,2,3] Além disso é usado para estudar “os diversos mecanismos de organização de dados para atender aos diferentes requisitos de processamento”[4], ou seja, “são formas genéricas de se estruturar informação de modo a serem registradas e processadas pelo computador e só adquirem significado quando associadas a um conjunto de operações, que visam, de um modo geral, manipulá-las (algoritmos).” [5]

Bom, o que você deve ter entendido (eu acho) nesse paragrafo anterior é que as estruturas de dados são formas bem definidas de organizar a informação em um computador. Além disso, essas estruturas possuem formas de acesso para que você possa manipular a informação dentro da estrutura. Quando uma pessoa constrói uma estrutura, na verdade ele está definindo meios para que você possa utilizá-la, ou seja, a API da estrutura de dados.

Além desses conceitos, outros conceitos que são relativos à este são os tipos de dados e os tipos abstratos de dados, que podem, de uma maneira geral, se referir a mesma coisa, mas possuem definições e conceitos bem diferentes.

Referencias

  1. Paul E. Black (ed.), Data structure. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology, 2004. Versão online .
  2. Data structure. Encyclopædia Britannica (2009) Online
  3. http://pt.wikipedia.org/wiki/Estrutura_de_dados
  4. http://www.dca.fee.unicamp.br/cursos/EA876/apostila/HTML/node10.html
  5. http://www.univasf.edu.br/~marcelo.linder/arquivos_ed1/aulas/aula1.pdf

Lista Encadeada

Uma lista encadeada é um modelo conceitual para a representação de uma sequência de informações armazenadas de forma dinâmica na memória de um computador. Cada informação é armazenada em uma célula ou nó da lista: o primeiro elemento na primeira célula, o segundo na segunda e assim por diante. A estrutura de uma lista encadeada é geralmente representada por uma caixa divida em dois espaços, um para armazenar a informação e o outro para guardar o endereço da próxima caixa.

Existem vários tipos de listas encadeadas disponíveis na literatura, só para citar:

  • Lista encadeada
  • Lista duplamente encadeada
  • Lista circular
  • Pilha
  • Fila
  • Árvores Binárias

A principal diferença entre essas estruturas são as regras e restrições de acesso que elas possuem. Logo, o programador deve analisar as características de cada uma e ver qual se adapta melhor na resolução do problema. Eu poderia apontar aqui um conjunto vasto de vantagens e desvantagens de cada uma, mas isso seria uma discussão um pouco extensa. Vou deixar essa discussão para os próximos posts. Se desejar observar um exemplo de implementação de algumas dessas estruturas, consulte este repositório de código com implementações em C.

Programa que Identifica Palindromes

 
/* Data: 24/02/2011
 * Programador: Valberto Carneiro
 * Objetivo: Faça um programa que leia uma string do teclado e diga se ela é
   palíndrome. Uma string é palíndrome quando pode ser lida tanto
   de trás pra frente quanto de frente para trás e possui exatamente
   a mesma seqüência de caracteres. Ex.: ASA, SUBI NO ONIBUS.
   Desconsidere os espaços.
   Defina uma função chamada Palindrome que receba uma string como
   parâmetro e retorne um boolean no seu programa.
   Dica: Use a função do exercício 1.
 */

#include<stdio.h>
const int FALSE = 0;
const int TRUE = -1;

int is_palindrome(char *texto) {
  int palindrome = TRUE, tamanho = strlen(texto), y = 0, x = 0;

  //elimina brancos
  while(x < tamanho) {
    if(texto[x] == ' ') for(y=x; y < tamanho; y++) texto[y] = texto[y+1];
    x++;
  }

  tamanho = strlen(texto);

  //compara os caracteres
  for(x = 0; x < tamanho ; x++) {
    //printf("%c = %c\n", texto[x], texto[tamanho-1-x]);
    if (texto[x] != texto[tamanho-1-x]) {
      palindrome = FALSE;
      break;
    }
  }
  return palindrome;
}
int main(){
  char texto[100];
  printf("Escreva uma string para sabermos se ela é palindrome: ");
  gets(texto);
  printf("Resultado: %s", is_palindrome(texto) == FALSE ? "nao" : "sim");
  getch();
}

Ruby Ordenando Hash

Abra o console do Linux ou Windows e digite:

$ irb
> meuhash = {1=>"um", 3=>"tres", 2=>"dois"}
=> {1=>"um", 2=>"dois", 3=>"tres"}

Para ordenar um hash em ruby você só precisa chamar o método sort

> meuhash.sort
=> [[1, "um"], [2, "dois"], [3, "tres"]]

Porém o ruby não possui o método reverse para o hash, assim como existe em um array. Veja como fazer um reverse no seu hash.

> meuhash.sort {|a,b| -1*(a<=>b) }
=> [[3, "tres"], [2, "dois"], [1, "um"]]

Loop com incremento personalizado com Ruby

Criar um loop com incremento personalizado utilizando linguagens como C ou Java é bem fácil:

for(int i = 1; i < 10; i+=2) {
  System.out.println(i)
}

Porém como os loops em Ruby não seguem a mesma filosofia e oferecem recursos um pouco diferentes, para vc criar seu loop com incremento diferente do padrão (incrementando de 1 em 1) faça assim:

1.step(10,2) do |i| 
  puts i.to_s
end

onde:
1 é o número inicial do loop;
10 é o número final do loop;
2 é o incremento.

Assim vc exibirá uma sequência de números que começam em 1 e sendo incrementados de 2 em 2 até o 10. Ou seja, a saída será: 1, 3, 5, 7,9