Um dos assuntos que estudamos em ciência da computação ou processamento de dados que eu mais gosto é: Algoritmos e Estrutura de Dados.
Se bem que gostar não é garantia de dominar, né? É sempre um assunto meio complicado. Admiro muito os professores dessa matéria, que resolvem problemas desse tipo quase sem pensar.
Uma das coisas que se estuda nessa matéria é a Lista Ligada. Trata-se de uma estrutura simples, porém poderosa, onde um atributo desta estrutura é um dado (de qualquer tipo que o programador queira) e um ponteiro para um próximo objeto de mesmo tipo. Se o ponteiro for null (em linguagens c-like, nil em pascal, nothing em basic) significa que não há próximo objeto.
Abaixo a figura de um nó da lista.
Esses nós podem ser ligados uns aos outros em cadeias, conforme a figura abaixo.
Além disso as listas podem ter dois ponteiros, um apontando para o elemento posterior e outro apontando para o anterior, formando uma lista duplamente ligada. A lista pode também ser circular, com o último elemento apontando para o primeiro. Nesses casos é comum termos um valor especial no "primeiro" nó para indicar que ele é a "cabeça" e assim não se navegar infinitamente pela lista. A cabeça também pode ser implementada com um ponteiro fora da lista circular apontando para um elemento qualquer da lista, sendo este o primeiro.
Em linguagens sem suporte a OO isso é feito criando - se uma struct (ou record) onde um dos elementos é o tipo de dado requerido e o outro é um ponteiro para a própria estrutura. Nas linguagens OO todo objeto já é um ponteiro, a manipulação de referências torna-se transparente. Um nó nada mais é do que um objeto contendo uma propriedade de um determinado tipo e a outra propriedade do próprio tipo nó.
Embora seja uma estrutura muito útil, se você trabalha com sistemas de informação você raramente usará listas ligadas no seu dia-a-dia, porque os frameworks e bibliotecas que usamos no nosso trabalho já tem tudo isso pronto, por isso podemos focar em regras de negócio e usabilidade, que é o que realmente é importante especificamente em nossa área.
No entanto, periodicamente, aparecem problemas e exercícios envolvendo listas ligadas em avaliações de processos seletivos.
Um processo seletivo pelo qual eu passei recentemente tinha a seguinte avaliação:
Exercício A - implementação de lista ligada
Os objetivos desse exercício são:
- Parte 1 - implementar um sistema de lista-ligada
- Parte 2 - realizar uma tarefa simples usando essa implementação
Parte 1 - implementação da lista ligada
Implemente um sistema de lista ligada integralmente de sua autoria. Não use as classes de
Listas das suas bibliotecas
Você decide se a solução vai envolver (uma ou mais) classes ou apenas funções; a
implementação deve ser adequada (não excessiva) para a utilização que se fa rá dela (vide
abaixo).
Parte 2 - utilização da lista ligada
Utilizando o sistema de lista ligada implementado na etapa anterior, escreva um programa que:
- crie duas listas ligadas: (por ex) Lista1 e Lista2
- leia o arquivo texto entrada.txt e armazene suas linhas em Lista1
- copie os elementos de Lista1 para Lista2 invertendo a sua ordem
- grave os elementos de Lista2 no arquivo texto saida.txt
Nada muito difícil, como pode ser visto, mas é o tipo de coisa que pode te pegar de surpresa porque você só viu na faculdade e, francamente, poucos de nós treinamos este tipo de algoritmo para estarmos sempre preparados.
Minha resolução foi a seguinte: primeiro criei o nó.
///
/// Classe Nó, um elemento da lista. Optei por torná-la genérica, assim ela pode carregar qualquer elemento em um nó.
///
///
public class No
{
public T valor { get; set; }
public No proximo { get; set; }
}
Note que criei a estrutura genérica assim um nó pode armazenar qualquer tipo de dado e tem uma propriedade, da classe No, que é o próximo nó genérico do mesmo tipo.
Depois criei a função para ler o arquivo de entrada, conforme o código abaixo. Estas funções para manipulação da lista são métodos estáticos na própria classe Program de um console application que fiz.
///
/// Carrega o arquivo definido no caminho e cria uma lista ligada na variavel n
///
///
///
private static void CarregaArquivo(No n, string caminho)
{
using (StreamReader sr = new StreamReader(caminho))
{
No p = n;
string s = sr.ReadLine();
p.valor = s;
while (!sr.EndOfStream)
{
p.proximo = new No();
s = sr.ReadLine();
p = p.proximo;
p.valor = s;
}
}
}
Fiz um código estilo quick and dirty, obviamente esse código poderia ser otimizado. Ele poderia trazer a lista no seu retorno, atuando como factory method, assim eu não precisaria passar uma variável para ele inicializar por mim. Mas ele funciona. Ele pega a primeira linha do aquivo, joga no primeiro elemento e encadeia novos elementos conforme vai lendo as próximas linhas. Acredito não ser necessário explicar cada linha de código aqui, o .net framework fala por si :).
Uma das coisas que o avaliador quer saber nesse tipo de exercício é se o candidato sabe recursividade. E para entender a recursividade você primeiro precisa saber a recursividade. Funções que se chamam a si mesmas, conceitos definidos em termos de si mesmos. Isso é recursividade. Você a vê a rodo na natureza e na matemática.
Por isso as funções Imprime e Inverte eu criei recursiva. Na verdade é a melhor maneira de se trabalhar com estruturas de dados.
Criei também uma Inverte iterativa (usando o laço while) porque me deparei com um desafio desses em uma outra avaliação para processo seletivo:
Inverta uma lista ligada sem usar recursividade. Parece que o pessoal conhece "de cor" só a maneira recursiva. No dia achei difícil, estava nervoso, começo de carreira, e fui pego de surpresa. Hoje parece trivial.
///
/// imprime o conteudo da lista ligada (partindo do nó n) na tela. Faz isso recursivamente.
///
///
private static void Imprime(No n)
{
if (n == null)
return;
Console.WriteLine(n.valor);
n = n.proximo;
Imprime(n);
}
///
/// Inverte usando while
///
///
///
private static No InverteIterativa(No n)
{
No tmp;
No corrente = n;
No invertido = null;
while (corrente != null)
{
tmp = corrente.proximo;
corrente.proximo = invertido;
invertido = corrente;
corrente = tmp;
}
return invertido;
}
///
/// inverte recursivamente
///
///
///
private static void InverteRecursiva(No n, ref No invertida)
{
No tmp;
No corrente = n;
if (n == null)
return;
tmp = corrente.proximo;
corrente.proximo = invertida;
invertida = corrente;
corrente = tmp;
InverteRecursiva(corrente, ref invertida);
}
///
/// salva a lista resultante no caminho especificado
///
///
///
private static void Salva(No n, string caminho)
{
using (StreamWriter sw = new StreamWriter(caminho))
{
No corrente = n;
while (corrente != null)
{
sw.WriteLine(corrente.valor);
corrente = corrente.proximo;
}
}
}
E a função main é esta:
static void Main(string[] args)
{
No L1 = null;
No L2 = null;
L1 = new No();
CarregaArquivo(L1, @"c:\entrada.txt");
Console.WriteLine("Dados originais");
Imprime(L1);
L2 = InverteIterativa(L1);
//InverteRecursiva(L1, ref L2);
Console.WriteLine("Dados invertidos");
Imprime(L2);
Salva(L2, @"c:\saida.txt");
Console.ReadLine();
}
Então é isso. Você pode
baixar aqui o código completo desse exercício de lista ligada. Espero que te ajude nos seus estudos e nas suas entrevistas. Me deixe saber se tem algo errado com o código (sempre tem).
Uma versão alternativa da função de carregar arquivo seria assim:
private static No CarregaAlternativo(string caminho)
{
No result = new No();
No next = result;
using (StreamReader sr = new StreamReader(caminho))
{
string s = "";
while ((s = sr.ReadLine())!=null)
{
next.valor = s;
if (!sr.EndOfStream)
{
next.proximo = new No();
next = next.proximo;
}
}
}
return result;
}
Have fun :)
Comentários
Postar um comentário