Breve Introdução Histórica

A linguagem C++ foi desenvolvida durante os anos 80 na Bell Labs, pelo cientista de computação dinamarquês Bjarne Stroustrup. Esta linguagem é muitas vezes retratada como uma evolução da linguagem C. De facto, esta linguagem foi a principal base de desenvolvimento de C++, tanto mais que a primeira versão da nova linguagem tinha o nome de C With Classes, evoluindo mais tarde para C++. Em português deve-se pronunciar “cê mais mais” sendo que em inglês esta linguagem é pronunciada como “cee plus plus”.

As vantagens introduzidas pelo C++ face ao C são indiscutíveis. No entanto, e muitas vezes devido ao facto de ser uma linguagem com facilidades de alto nível, ocorrem erros lógicos (os temidos bugs) difíceis de resolver e frequentemente com consequências trágicas para o computador que está a correr a aplicação. São por isso famosas as duas citações de Stroustrup acerca das “facilidades” da sua nova linguagem:

• “C faz com que dar um tiro no pé seja fácil; C++ torna isso mais difícil, mas quando nós o fazemos rebenta com a perna toda.”
• “Sempre desejei que o meu computador fosse tão fácil de usar como o meu telefone. O meu desejo realizou-se. Já não sei usar o meu telefone.”

Nem sempre é simples para iniciantes da linguagem ou programadores inexperientes evitar que estes erros aconteçam. É por esta razão que muitas vezes é recomendado um período de adaptação à sintaxe de C e desenvolvimento de aplicações nesta linguagem, antes de se dar o salto para o C++.

Algoritmos Clássicos – Ordenação

Existe um alargado conjunto de algoritmos informáticos que desempenham um papel quase vital no desenvolvimento de aplicações coerentes e sólidas. Estes algoritmos, conhecidos como algoritmos clássicos, são frequentemente usados como “sub-rotinas” em aplicações mais complexas.

Um grupo de algoritmos clássicos que apresenta um vasto domínio de aplicação é o dos algoritmos de ordenação. Este grupo de algoritmos apresenta variadas técnicas que possibilitam a ordenação dos elementos de um array segundo uma determinada lógica (pode-se proceder a uma ordenação de forma ascendente ou descendente).

Neste artigo serão apenas abordados dois dos muitos algoritmos de ordenação de arrays: o QuickSort (por muitos considerado o melhor algoritmo de ordenação) e o BubbleSort.

BubbleSort

O algoritmo BubbleSort é talvez o algoritmo mais simples de se perceber dentro do género. A sintaxe que este algoritmo apresenta não necessita de explicações exaustivas, visto recorrer a aspectos básicos de programação (ciclos for/while, comparação de diferentes elementos do array, incrementação de uma variável, etc.). O próprio funcionamento do BubbleSort é muito simples: por cada iteração do ciclo, o maior elemento do array (para um determinado intervalo de elementos desse mesmo array) é colocado no índice final, previamente estabelecido. Isto é conseguido à custa de sucessivas comparações de um elemento do array com o seu elemento seguinte.

O seguinte excerto de código ilustra a implementação do BubbleSort:

//função para trocar dois elementos do array (utilização de referências para afectação directa)
void swap (int& n1, int& n2)
{
  //guardar o valor de n2
  int aux = n2;
  //afectar n2 com o valor de n1
  n2 = n1;
  //afectar n1 com o valor de aux (valor inicial de n2)
  n1 = aux;
}
 
//a função recebe como argumentos o array a ordenar e o numero máximo de elementos a ordenar 
void bsort (int v[], int n)
{
  for (int i = n; i > 0; --i)  //ciclo responsável pelas decrementações do índice máximo 
  {
    for (int j = 0; j < i; ++j) //ciclo responsável por incrementar os índices a ordenar
    {
      if (v[j] > v[j+1]) //se um elemento é maior que o seu elemento seguinte
      {
         swap (v[j], v[j+1]); //chamar a função para trocar dois elementos do array
      }
    }
  }
}

O primeiro ciclo for é o responsável por decrementar o índice máximo para as ordenações. Assim, se se quiser ordenar um array tomando em conta todos os seus elementos, terá de se iniciar a variável que irá percorrer todos os índices com o valor do tamanho do array. Depois de serem efectuadas todas as operações uma primeira vez, tem-se a certeza que o maior elemento do array se encontra no índice final. Na segunda vez que se irão realizar as operações de ordenação, não interessa que se tenha em conta todo o array (se assim fosse estariam a ser feitas comparações desnecessária, ocupando recursos da máquina injustificadamente). Logo, decrementa-se em 1 o índice máximo.

As operações terminarão quando o índice máximo for zero, ou seja, quando coincidir com o primeiro índice (índice zero). Isto acontece pois um array de um elemento está de certeza ordenado.

QuickSort

O algoritmo QuickSort (desenvolvido em 1960 pelo cientista Charles Antony Richard Hoare) é de longe o algoritmo de ordenação mais usado e considerado pelo maior parte dos programadores como o melhor algoritmo dentro do género.

Este algoritmo implementa uma solução para a ordenação de um array baseado no famoso lema da informática “dividir para conquistar”. O que basicamente o QuickSort faz é ir dividindo o array, através da selecção de um pivot (elemento de referência), e ordenando depois cada parte.

Apresenta-se a seguir um exemplo de implementação do QuickSort:

void qsort (int v[], int inicio_v, int fim_v)
{
  //afectar os indices que irão percorrer o array com as posições iniciais e finais do array
  int a = inicio_v, b = fim_v;
 
  if (a >= b)
    return;
 
  //pivot (elemento do meio do array)
  int pivot = v[(a+b)/2];
 
  do {
    //ir pesquisando por números que estejam à esquerda do pivot e que sejam maiores que este
    while ( v[a] < pivot)
      ++a;    //incrementar "a" para se ir avançando no array
 
    //ir pesquisando por números que estejam à direita do pivot e que sejam menores que este
    while ( v[b] > pivot)
      --b;   //decrementar "b" para se ir regredindo no array 
 
    if (a <= b)  //trocar apenas se “a” menor ou igual a “b” 
    {
      if (v[a] != v[b])   //efectuar trocas apenas se os valores forem diferentes
        swap (v[a], v[b]);
      //incrementar "a" e decrementar "b" para se retomar as pesquisas
      ++a; --b;      
    }
  } while (a <= b);
 
  //quer-se ordenar um sub-array que vai desde o principio do array principal ate antes do pivot.
  //quando se terminam as pesquisas, "b" representa a posição antes do pivot.
  qsort (v, inicio_v, b);   
 
  //quer-se ordenar um sub-array que vai desde a posição seguinte ao pivot até ao fim do array
  //principal quando se terminam as pesquisas, "a" representa a posição seguinte ao pivot.
  qsort (v, a, fim_v);
}
 
void swap (int& a, int& b)
{
  //troca do conteudo das variáveis
  int aux = a; a = b; b = aux;
}

No fundo, este algoritmo pode-se resumir a sucessivas colocações de valores maiores que o pivot à sua direita e de valores menores à sua esquerda. No exemplo apresentado, o elemento escolhido como pivot é o elemento central de cada parte do array. Esta escolha tem tanto valor como qualquer outra. No entanto, se o array estiver parcialmente ordenado, ela é preferível.

Imagine-se o seguinte array (denomine-se o array por v): [1,3,1,2,5,4,3]. Vamos recorrer ao QuickSort para o ordenar:

• Seleccionar o pivot. Para este caso o pivot será o elemento contido no índice 3 (elemento central), que contém o valor 2;
• Colocar à esquerda do pivot só elementos menores que este e à direita só elementos maiores. Começando no princípio do array (pesquisar por elementos maiores ou iguais que o pivot), o elemento de índice 1 (valor 3) é maior que o pivot. Portanto, o elemento do índice 1 terá de ser trocado.

Nota: no exemplo apresentado, elementos iguais ao pivot tanto se podem encontrar à esquerda como à direita deste. No entanto, se durante a pesquisa de valores maiores ou menores que o pivot for encontrado algum elemento igual ao pivot, este será tomado para troca.

• A pesquisa por elementos maiores que o pivot (e que estivessem inicialmente à esquerda deste) termina, tomando-se o valor v[1] para troca;
• Para a pesquisa de valores menores que pivot e que estejam à sua direita (inicialmente), começa-se no índice final do array, com sucessivos decrementos. Como se pode observar, começando em v[6], o elemento v[3], que é o valor 2, é igual ao pivot (realce-se que o pivot é um valor). Ora, o ciclo while em que é feita a pesquisa por valores menores que o pivot, terminará para um valor igual ao pivot. Assim, será tomado para troca o valor contido em v[3].
• Procede-se à troca. O valor que se usou para ir percorrendo o array ascendentemente (no exemplo é a variável a) é menor que o que se usou para percorrer o array de forma descendente (no exemplo é a variável b). Portanto, a condição a <= b é verdadeira, entrando-se assim no processo de troca de elementos;
• Os elementos não são iguais (v[1] != v[3] é verdadeiro), logo todas as condições previstas para a troca estão satisfeitas;
• Invoca-se a função de troca (swap()), que se encarregará de trocar os elementos;
• Depois de trocados os elementos, fica-se com o vector v da seguinte forma: v = [1,2,1,3,5,4,3];
• Os índices a e b são, respectivamente, incrementado e decrementado. Retoma-se, portanto, a pesquisa por valores maiores que o pivot em v[2] e a pesquisa por valores menores em v[2];
• Durante a pesquisa por valores maiores, conclui-se que o elemento v[3] (contém o valor 3) é maior que pivot. Logo, será tomado para troca;
• Já para as pesquisas por elementos menores que pivot, o elemento v[2] é igual que pivot, logo será tomado para troca;
• No entanto, a troca não será efectuada, já que o índice usado para percorrer o array ascendentemente é maior que o usado para percorrer o array descendentemente. Desta forma, não se processa a troca de elementos (a é maior que b, logo a condição a <= b é falsa);
• O ciclo do…while é também terminado, já que a condição de teste deste ciclo é a <= b;
• Procede-se então às duas chamadas recursivas à função qsort(), sendo que na primeira chamada será apenas tomado em conta o sub-array [1,2,1] e na segunda o sub-array [3,5,4,3] (no entanto, para questões de indexação, o array em causa continua a ser o próprio v, sendo que para o segundo sub-array, v[3] representa o primeiro valor 3);
• Para a primeira parte do array, o pivot será o valor 2 (v[1]), sendo que se troca v[1] (valor 2) e v[2] (valor 1);
• Para a segunda parte do array, o pivot será o valor 5 (v[4]), sendo que a única troca que se efectua é entre v[4] (valor 5) e v[6] (valor 3);
• Depois destas duas trocas, o array está totalmente ordenado;

O algoritmo QuickSort termina quando numa chamada recursiva a qsort(), o parâmetro inicio_v for maior ou igual a fim_v. Foi imposta esta condição terminal pois um array de um elemento está de certeza ordenado (se o índice que representa o início do array for o mesmo que representa o fim do array, então está-se na presença de um array de 1 elemento).

Algoritmos Clássicos – Pesquisa em Arrays

Tanto no mundo da programação, como no dia-a-dia, somos confrontados com diversas situações que requerem a pesquisa de algo num determinado conjunto de elementos, que em princípio terão características semelhantes ou iguais àquilo que se quer encontrar. Um exemplo muito simples, mas ilustrativo deste facto, é a situação em que se tem de encontrar um livro de uma disciplina dentro de uma mochila, na qual existem também outros materiais escolares (estojos, cadernos, etc.).

Em informática, o conceito e toda a logística em torno do pesquisar tem assumido um papel preponderante nos últimos anos. Exemplo disso é toda a agitação em torno dos diferentes motores de busca na Internet (Google, Yahoo!, etc.).

A própria programação não foge a esta regra. As pesquisas representam também uma operação com importância chave numa aplicação.

Uma maneira de encontrar algo no dia-a-dia poderá ser uma pesquisa sequencial aos elementos de um determinado conjunto. Ou seja, verificam-se, um a um, os elementos do conjunto até se encontrar o elemento pretendido. Este processo, apesar de se poder implementar em programação, não é de todo o melhor para se encontrar um elemento dentro de um conjunto de dados (por exemplo um array).

Neste contexto surge a pesquisa dicotómica, um algoritmo que facilita a procura de um certo elemento dentro de um array.

Pesquisa Dicotómica em Arrays

A pesquisa dicotómica em arrays (também muitas vezes referida como pesquisa binária) requer, antes de mais, que o array esteja ordenado. Ou seja, este algoritmo requer que antes da sua execução seja posto em execução um algoritmo de ordenação, tal como o QuickSort ou o BubbleSort.

Este algoritmo é provavelmente um dos mais simples e rápidos de entender dentro do mundo da programação. Este algoritmo propõe que se vá verificando sucessivamente o elemento central do array (que vai sendo divido em sub-arrays), fazendo uma comparação entre este e o elemento que se quer encontrar. Se o elemento central for menor que o valor que se deseja encontrar, então deverão analisar-se os elementos que estão à direita do elemento central. Caso o elemento central seja maior, deverá proceder-se à pesquisa na parte esquerda do array.

Se o elemento nunca for encontrado, então a função retorna -1, indicando que no array em questão não existe o elemento que se procurava.

Exemplo de implementação de pesquisa dicotómica em arrays:

int search (int v[], int find, int inicio_v, int fim_v)
{
  //se o delimitador à esquerda for maior que o da direita
  if (inicio_v > fim_v)
  //o elemento não existe no array em causa
    return -1;
 
  //elemento central (índice central do array)
  int pivot = (inicio_v+fim_v)/2;
 
  if (v[pivot] == find)        //se o elemento central for igual ao pretendido
    return pivot;             //indicar o índice em que se encontrou
 
  //se o valor central for maior que o valor a pesquisar
  if (v[pivot] > find)
    return search (v, find, inicio_v, pivot-1);  //pesquisar na parte esquerda do array
  //se o valor central for menor
  else
    return search (v, find, pivot+1, fim_v);    //pesquisar na parte direita do array
}

A função que implementa o algoritmo de pesquisa dicotómica em arrays (no exemplo é a função search), recebe como parâmetros o array a analisar (variável v), o valor a encontrar (variável find), o índice inicial da parte do array a ser analisada (variável inicio_v) e o índice final da parte do array a analisar (variável fim_v).

Esta função termina quando a condição inicio_v > fim_v for verdadeira. Pense-se no seguinte: após várias chamadas à função search() ocorre nova chamada à função, desta vez com uma parte do array principal que só apresenta um elemento. Neste caso, o pivot que será escolhido será esse mesmo elemento. Se o pivot não for igual ao valor que se procura, então de certeza que o valor que se procurava não existe no array. No entanto, o algoritmo continua a ser executado. Só que para ambas as possibilidades que se apresentam (o pivot ser maior que o valor que se procura ou ser menor), o parâmetro inicio_v será maior que fim_v.

Se o pivot for maior que o valor que se procura, então o parâmetro formal inicio_v terá o mesmo valor com que iniciou essa chamada à função, sendo que o parâmetro formal fim_v terá o valor de pivot – 1 (como se trata de uma parte do array que tem apenas um elemento, tanto inicio_v como fim_v têm o mesmo valor que pivot, logo fim_v será passado na nova chamada à função com um valor menor que inicio_v).

O outro caso que pode ocorrer (pivot ter um valor menor que o valor que se procura), o parâmetro formal inicio_v será afectado com o valor de pivot + 1 e o parâmetro formal fim_v terá o mesmo valor com que iniciou essa chamada à função (tal como no caso do pivot ser maior que o valor em procura, também neste caso fim_v e inicio_v têm o mesmo valor que é o valor de pivot).

Portanto, faz todo o sentido que quando fim_v for passado com um valor menor que inicio_v o algoritmo cesse, indicando-se que o valor que se procura não estava contido no array (return -1 indica a inexistência do valor dentro do array).

Algoritmos Clássicos – Gestão de Dados

Nos dias que correm, a gestão de dados através de aplicações informáticas é um domínio extremamente importante e em que se tem apostado fortemente em termos de desenvolvimento e pesquisa. Não é por isso de admirar que exista uma variedade tão grande de facilidades e algoritmos dentro deste ramo.

Desde sempre foi uma necessidade do ser humano ter a informação ordenada da melhor maneira possível, sendo que as técnicas usadas para a ordenação dessa informação foram evoluindo e transformando-se ao longo do tempo. E neste aspecto a informática não foi excepção. Desde que foi lançado o primeiro computador pessoal até à data actual, muita coisa se modificou na forma de gestão de dados. Os algoritmos responsáveis pela boa gestão de dados forem evoluindo, foram criadas plataformas específicas para gestão de dados (as tão famosas aplicações de gestão de base de dados, tais como Oracle, MySQL, SQL Server, Access, etc.). Como este é um ramo em constante transformação prevê-se que as inovações não cessem para já. Mais, é dito que as condições para mais evoluções e descobertas de soluções muitíssimo eficientes a este nível estão agora reunidas. Os algoritmos implementados em linguagens tradicionais (nomeadamente o OOP, Object-Oriented Programming) estão a começar a ser implementados em sistemas específicos de gestão de dados.

É um ramo da informática sobre o qual recaem imensas expectativas.

Listas Ligadas (apresentação de uma lista simplesmente ligada em anel)

Um dos algoritmos mais famosos para a gestão de dados é o que implementa uma estrutura de dados denominada Listas Ligadas. Esta estrutura de dados supera o armazenamento e gestão de dados em arrays na medida em que na altura de se inserir um novo elemento na lista não é necessário alterar a posição dos restantes elementos. Isto acontece pois todos os elementos da lista estão ligados ao seu seguinte (numa variação deste algoritmo é mesmo possível ligar cada elemento ao seu anterior), tal como num comboio, em que as diversas carruagens estão ligadas sequencialmente, construindo a estrutura total.

Também dentro deste algoritmo existem inúmeras variações, nomeadamente a Lista Simplesmente Ligada, a Lista Simplesmente Ligada em Anel e a Lista Duplamente Ligada. Neste artigo será apresentada a Lista Simplesmente Ligada em Anel pela sua simplicidade e eficiência nos objectivos a que se propõe o algoritmo.

Exemplo de implementação de uma simplesmente ligada:

class List
{
struct Node //estrutura que representa o nó/célula
{
  int data; //atributo em que será contida a informação do nó
  Node* nextNode; //apontador para o nó seguinte da lista

  //construtor que será invocado para criar cada nó da lista
  Node (int val, Node* next)
  {
    data = val;
    nextNode = next;
  }

  //construtor default que será invocado para construir o nó sentinela
  Node()
  {
    nextNode = this;
  }
};

  //criação do nó que servirá de sentinela (invoca o construtor default da estrutura)
  Node guard;

  //método auxiliar find() para verificar se um dado valor existe ou não na lista
  bool find (int val, Node*& prev, Node*& next);
 
public:
  //método para inserir um novo elemento numa lista
  bool insert (int val);

  //método para remover um determinado valor da lista
  bool remove (int val);

  //destrutor; elimina todos os nós da memória
  ~List();
};

Neste exemplo, o algoritmo é implementado através do paradigma OOP. Desta forma, consegue-se uma melhor abstracção e sobretudo prima-se em organização e eficiência.

Como foi referido, as listas ligadas representam uma estrutura de dados constituída por células/nós, que contêm a informação a armazenar e a gerir, estando estes ligados numa forma sequencial. Em termos de programação, os nós da lista são implementados através uma estrutura (struct), contendo esta um ou mais atributos para conter informação e um outro atributo que a liga às restantes estruturas da lista. No exemplo, os nós são referenciados pela variável Node.

No exemplo está implementada uma lista em que cada nó existe um atributo para conter informação (no caso um valor inteiro) e o atributo nextNode, que é do tipo apontador para Node (irá apontador para a estrutura que representa o nó seguinte). Node tem também dois construtores, um com dois parâmetros (responsável pela criação dos nós normais da lista) e um construtor default (que será invocada aquando da criação do nó sentinela).

O construtor com parâmetros recebe um valor do tipo inteiro (val), que será o valor que o novo nó conterá, e um apontador para Node (nextNode), que representa o nó seguinte ao nó que será criado.

A particularidade que esta lista introduz é da ligação em anel. A organização da lista é feita desta forma a fim de facilitar os algoritmos de inserção e remoção dentro da lista . Este nó denominado sentinela (referenciado no exemplo como guard) é sempre o primeiro nó da lista, sendo que quando a lista está vazia aponta para si mesmo (o nó seguinte ao nó sentinela é o próprio sentinela) e quando não está vazia, o último nó aponta para o sentinela (o nó seguinte ao último nó da lista é sempre o sentinela). Este nó especial é criado através da invocação do construtor default. Dentro deste construtor é usada a palavra-chave this para afectar o atributo nextNode do nó que invoca o construtor (neste caso, o sentinela). Ou seja, o nó que invocou o construtor passa a apontar para ele mesmo.

Se o código apresentado for posto em execução, a linha Node guard cria o sentinela, fazendo assim com que seja criado o primeiro nó da lista. Desta forma, quando a lista é criada tem este aspecto:

Quando forem inseridos valores na lista (os valores inseridos numa lista ficam sempre ordenados de uma forma ascendente), a lista apresenta o seguinte aspecto:

Repare-se na forma que a lista apresenta, com o último nó ligado ao sentinela.

No exemplo foram apresentados quatro métodos pertencentes à classe List: o método (auxiliar) find, o método insert, remove e o destrutor da classe.

O método find é usado pelos métodos de inserção e remoção da lista, insert e remove respectivamente, a fim de se saber se um dado valor existe ou não dentro da lista (não faria qualquer sentido tentar inserir um valor que já estivesse presente na lista ou remover um valor que nem sequer existia dentro da lista). O método find poderia ser então programado da seguinte forma:

bool List::find (int val, Node*& prev, Node*& next)
{
  guard.data = val; //truque para evitar a pesquisa infinita
 
  //afectar “next” como sendo o nó seguinte à sentinela e prev como sendo a própria sentinela
  for (next = guard.nextNode, prev = &guard;
  //cessar a pesquisa pelo elemento apenas quando a informação de "next" for maior ou igual a "val"
      next->data < val;
      //por cada iteração afectar "prev" com as características de "next" e "next" com as do nó seguinte
      prev = next, next = next->nextNode);
 
  //retornar TRUE se o valor existir ou FALSE se o valor não existir
  return next->data == val && next != &guard;
}

Este método realiza uma pesquisa por toda a lista para verificar a existência de um determinado valor. Recebe como parâmetros o valor a procurar e dois apontadores para Node passados por referência (prev e next, que serão afectados directamente, já que são argumentos passados por referência). O atributo val de guard é afectado com a valor a procurar. Esta afectação é feita devido à forma como a pesquisa é realizada: o atributo para conter informação do apontador next vai sendo afectado com os sucessivos valores dos nós que representa, sendo que a pesquisa termina quando next->data representar um valor maior que val. Assim, imaginando-se que o valor que se procura não existia na lista e que todos os valores contidos na lista eram menores que o que se procurava, se guard.data não fosse afectado com o valor a pesquisar, a pesquisa nunca teria fim, já que nunca se contrariava a condição next->data < val, o que implicaria um ciclo for infinito.

Este método retorna true ou false consoante o valor que se procurava exista ou não, respectivamente. O valor de retorno é dado pelo valor lógico da expressão next->data == val && next != &guard. “Dissecando” esta expressão, como se trata de um a expressão em que se usa o operador lógico &&, apenas se todos os operandos forem condições verdadeiras, o valor lógico da expressão total é verdadeiro. Caso contrário (basta que um operando seja falso) a expressão terá o valor lógico falso.

O primeiro operando retorna true se o valor do atributo next->data for igual a val. Ora, se o valor que se procurava estiver inserido na lista, então quando a pesquisa terminar o apontador next representa o nó em que está contido o valor em procura e prev o seu nó anterior. Assim, se este operando retornar true, o valor encontra-se na lista.

No início do método, foi afectado guard.val com o valor que se procura (para assim evitar pesquisa infinita). Desta forma, se o valor que se passou como parâmetro não existir na lista, e se todos os valores da lista forem menores que o que se procura, next->data == val retorna true. Ou seja, é indicado que o valor em procura está contido na lista, quando na realidade isso não se passa. Daí que se teste se o endereço de memória apontado por next é o endereço do nó sentinela. Em C++, a condição que traduz este caso é next != &guard. Portanto, se esta condição retornar true, já se sabe que o apontador next não está a apontar para o nó sentinela, ou seja, não percorreu toda a lista, não encontrando o valor pretendido.

O método find retorna true (o valor existe de facto na lista) apenas quando next aponta para um nó que contém o valor pretendido e não está apontar para o sentinela.

Outro método apresentado no exemplo é o método de inserção. Exemplo de implementação do método de inserção de um novo valor:

bool List::insert (int val)
{
  //nós auxiliares para percorrerem a lista
  Node* next, *prev;
 
  if (find (val, prev, next))	//se o elemento já existir na lista
    return false; //indicar o insucesso da operação de inserção
 
  //criar um novo elemento
  prev->nextNode = new Node (val, next);
 
  //indicar o sucesso da operação
  return true;
}

Os nós auxiliares criados dentro deste método (next e prev) são os nós que serão passados por referência ao método auxiliar find. Sendo passados por referência, não existe necessidade de retornar estes nós no fim do método find.

A expressão dentro do if não é mais que uma chamada ao método auxiliar find, recebendo este como parâmetros o valor a pesquisar (val) e os nós auxiliares que irão percorrer toda a lista (next e prev). Se este método retornar true, então o valor já existe dentro da lista, logo não faz sentido tentar inseri-lo de novo. Daí que se faça return false caso isto se verifique.

Se a chamada find (val, prev, next) retornar false, então o valor ainda não existe na lista, logo pode ser inserido. Portanto, se verificar este retorno por parte de find, a execução da aplicação passa o controlo if (não atinge return false) e por isso é necessário invocar o construtor para os nós normais da lista. Ora, este construtor recebe dois parâmetros: o valor que será contido pelo nó e o nó seguinte a este. Como no final da pesquisa o apontador next aponta para o nó em que está contido o primeiro valor maior que o que se procura, então o nó seguinte ao nó que se pretende criar será exactamente o nó next. Portanto, os parâmetros a passar ao construtor estão já definidos. No entanto, será preciso ligar este nó ao seu nó antecessor. Daí se afectar o atributo nextNode de prev com o novo nó que será criado (prev->nextNode = new Node (val, next)).

Outro método importante para a implementação de listas é o método de remoção. Exemplo de implementação do método de remoção:

bool List::remove (int val)
{
  Node* next, *prev;
 
  if (!find (val, prev, next)) //se o valor não existir na lista
    return false; //indicar o insucesso da operação
 
  //desligar o nó que continha o valor pretendido da restante lista
  prev->nextNode = next->nextNode;
  //libertar o espaço de memória ocupado pelo nó a eliminar
  delete next;
  //indicar o sucesso da operação
  return true;
}

Também o método de remoção recorre ao método auxiliar find para reconhecer se o valor em questão já está ou não contido na lista. Neste caso, é indicado o insucesso da operação de remoção se o valor não estiver contido na lista (não faz qualquer sentido remover um valor que nem sequer está contido na lista). Daí que se faça return false caso a chamada find (val, prev, next) retorne false (através do operador ! nega-se o valor lógico da expressão a avaliar pelo if, daqui que se possa escrever simplesmente ! find (val, prev, next) ).

Se a chamada ao método auxiliar retornar true, então é necessário desligar o nó da restante lista. Para isso liga-se o nó anterior àquele que se vai remover ao nó seguinte daquele que se vai remover. Em C++ esta operação é implementada pela linha prev->nextNode = next->nextNode (mais uma vez se salienta que no final da pesquisa, se o valor existir dentro da lista, o apontador prev aponta para o nó anterior ao que se pretende remover e next representa o próprio nó a remover).

Para eliminar o nó da memória usa-se o operador delete, para assim se libertar o espaço de memória ocupado pelo nó, sem levantar qualquer problema para a máquina.

Finalmente, é também implementado um destrutor da classe List. Exemplo de implementação do destrutor da classe:

List::~List()
{
  //nó que irá percorrer a lista
  Node* actual;
 
  while (guard.nextNode != &guard)
  {
    //afectar "actual" com as características do nó seguinte à sentinela 
    actual = guard.nextNode;
    //desligar o nó da restante lista
    guard.nextNode = actual->nextNode;
    //eliminar o nó da lista 
    delete actual;
  }
}

A função deste destrutor não é mais que a de eliminar da memória todos os nós constituintes da lista. Para isso, vão-se eliminando os nós seguintes ao sentinela (guard.nextNode). Só deverá ser feita esta eliminação, obviamente, enquanto a lista não estiver vazia. Ora, a lista estar vazia significa que apenas permanece em memória o nó sentinela. Portanto, a lista estará apenas vazia quando o nó sentinela tiver como nó seguinte ele próprio. Este facto testa-se através da condição guard.nextNode != &guard (realça-se o facto de se usar o operador referência, para que assim se teste o endereço de memória do nó seguinte a guard, já que nextNode é do tipo apontador para Node). Enquanto a lista não estiver vazia, a operação realizada para eliminar o nó da memória é idêntica à realizada no método de remoção. Em primeiro lugar é necessário desligar o nó em questão da restante lista. O seu nó anterior (que será o sentinela) passa a ter como nó seguinte o nó que era seguinte àquele que se irá remover. Depois disto, basta simplesmente usar o operador delete, libertando-se assim o espaço de memória ocupado pelo nó.

Para além dos métodos apresentados, numa implementação de uma lista simplesmente ligada em anel podem ser implementados outros métodos. Um método também bastante comum de uma lista é o método que imprime no console os valores de todos os nós; é igualmente frequente a implementação de um método que simplesmente procura por um determinado valor dentro da lista (útil em caso do utilizador querer procurar por um valor específico, sem o intuito de proceder a inserções ou remoções).

Conclusão

Neste artigo foram apresentados alguns dos algoritmos mais conhecidos dentro do mundo da programação, recorrendo para isso à linguagem C++. No entanto, e apesar da breve introdução e de cada exemplo ser acompanhado por descrições e explicações detalhadas, pressupõe-se que o leitor tinha já adquiridos conceitos dentro desta linguagem. Aconselha-se então aos leitores menos familiarizados com esta linguagem que realizem uma pesquisa e aprendizagem mais aprofundadas dos conceitos e temas mais básicos.

Através da redacção do presente artigo pretende-se desenvolver o gosto pela algoritmia junto dos leitores. É bastante importante contrariar a mentalidade da nova geração de programadores de que este mundo se cinge à aprendizagem de linguagens de programação. Assiste-se, cada dia que passa, a um crescente desprezo pela algoritmia, a qual deveria ser tomada como o elemento mais importante dentro da programação.

Bibliografia

1. RODRIGUES, Pimenta; PEREIRA, Pedro; SOUSA, Manuela; Programação em C++ – Conceitos Básicos e Algoritmos; Lisboa; FCA; 7.ª edição; ISBN 972-722-038-X (1998);
2. http://www.portugal-a-programar.pt/forums/topic/1743-prepara%C3%A7%C3%A3o-para-concursos-algoritmia-n%C3%ADvel-m%C3%A9dio-resolu%C3%A7%C3%B5es/
3. http://www.portugal-a-programar.pt/forums/topic/3898-programa%C3%A7%C3%A3o-para-concursos-parte-2/
4. http://pt.wikipedia.org/wiki/C%2B%2B