Out4Mind O seu portal multi-temático
Na primeira parte deste artigo, vimos a estrutura das classes template que irão suportar a nossa lista duplamente ligada. Agora, vamos ver exemplos de utilização.
No código fonte completo, que poderá descarregar no link disponível no final deste artigo, temos dois exemplos de listas. Um exemplo com uma lista de números inteiros e outro exemplo com uma estrutura “Agenda” com nomes, telefones e endereços de e-mail.
Volto a lembrá-lo que, como estamos a usar classes template, há certas operações que não podem ser directamente implementadas nas classes, pois desconhecemos os tipos de dados associados!
Lista duplamente ligada com números inteiros
Neste exemplo, criamos uma lista de números inteiros por ordem decrescente. Desta vez não vou testar números duplicados, pelo que estes poderão existir. Por isso, deverá ter em consideração que, se eliminarmos um nó com um determinado valor, e se ele existir em duplicado, apenas a primeira ocorrência será eliminada.
Repare como declaramos a lista, pois estamos a usar uma classe template:
ListaDupla<int> *listaInteiros = new ListaDupla<int>();
Vamos agora ver como fazemos a inserção de um número, dado numa variável “v”. Neste exemplo, iremos procurar o valor “maior” do que o que queremos introduzir a partir da cauda, pelo que o código vai-se comportar como se estivéssemos a inserir por ordem crescente!
if (listaInteiros->vazia()) {
listaInteiros->insereUltimo(v);
}
else {
Iterador<int> *i = listaInteiros->obtemIteradorCauda();
NoDuplo<int> *procura;
while ((procura=i->noAnterior())!=NULL) {
int p = procura->elemento;
if (p>v) {
break;
}
}
if (procura==NULL) {
listaInteiros->inserePrimeiro(v);
}
else {
listaInteiros->insereDepoisDe(procura, v);
}
delete i;
}
Como habitual, devemos de testar se a lista está vazia (linha 1) e, se estiver, usamos o método “insereUltimo” para inserir o nosso primeiro número. Podíamos usar o método “inserePrimeiro”, mas o objectivo é termos exemplos de ambos os casos. Se a lista não estiver vazia, passamos para o código do bloco “else” (linha 4) e vamos pedir à classe um apontador para um iterador iniciado à cauda (linha 5). Declaramos um apontador para um nó “procura” e executamos o ciclo “while” da linha 7, onde vamos pedir o próximo nó ao iterador até que este devolva NULL (que neste caso, como estamos a procurar a partir da cauda, indica que passámos para trás do início da lista).
Dentro do ciclo, se encontrarmos um número maior do que queremos introduzir (relembro que estamos a procurar a partir da cauda), interrompemos o ciclo com a instrução “break” na linha 10. Depois do ciclo, na linha 13, verificamos se não encontrámos nenhum valor maior do que queremos inserir (o apontador “procura” ficou a NULL) e, neste caso, vamos querer inserir o número à cabeça e usamos o método “inserePrimeiro” na linha 14. Se o valor for encontrado, passamos para o bloco “else” da linha 16 e usamos o método “insereDepoisDe”, passando o nó resultante da procura e o valor que queremos inserir.
Como o iterador foi obtido como um apontador para um novo iterador, teremos que o libertar da memória na linha 19.
Agora, vamos ver como remover um determinado valor, dado numa variável “v”. Desta vez, vamos procurar o valor a partir da cabeça:
Iterador<int> *i = listaInteiros->obtemIteradorCabeca();
NoDuplo<int> *procura;
while ((procura=i->noSeguinte())!=NULL) {
if (procura->elemento==v) {
break;
}
}
if (procura==NULL) {
cout << "O valor não foi encontrado ou a lista está vazia" << endl;
}
else {
if (listaInteiros->remove(procura)) {
cout << "Valor removido com sucesso" << endl;
}
else {
cout << "Erro ao remover o valor" << endl;
}
}
delete i;
Neste caso, não vou verificar se a lista está vazia, pois nesse caso o iterador irá logo devolver NULL. Volto a lembrá-lo que, a lista não pode receber um valor para o procurar e apagá-lo pois podemos ter uma lista com qualquer tipo de dados, incluindo estruturas ou outras classes. Assim, na linha 1, obtém-se um iterador iniciado à cabeça. Declaramos um nó “procura”, o qual vai ser usado no ciclo da linha 3. Se encontrarmos o nosso valor, interrompemos o ciclo na linha 5.
Na linha 8, verificamos se o apontador usado na procura é NULL. Se o for, quer dizer que o valor não foi encontrado ou a lista está vazia. Caso contrário, tentamos remover o valor, passando o apontador do seu nó (linha 12). Este deverá sempre ser removido pois estamos a usar um apontador de um nó que existe na lista! Se não o for, é porque temos algum erro no código!
Finalmente, vejamos o código para listar os valores da nossa lista:
cout << endl << "Inteiros por ordem decrescente" << endl;
Iterador<int> *i = listaInteiros->obtemIteradorCabeca();
NoDuplo<int> *listar;
while ((listar=i->noSeguinte())!=NULL) {
cout << listar->elemento << endl;
}
delete i;
Neste caso, estamos a listar os valores a partir da cabeça (linha 2). Aqui não está o teste para verificar se a lista está vazia, mas poderá encontrá-lo no código completo.
Lista duplamente ligada com uma estrutura (“struct“)
Neste exemplo, vamos ter uma estrutura (“struct“) chamada “Agenda” com nomes, telefones e endereços de e-mail.
A “struct” está declarada no ficheiro “agenda.h” e tem o seguinte aspecto:
struct Agenda {
string nome;
string telefone;
string email;
};
No nosso programa, em “agenda.cpp”, temos a lista declarada como:
ListaDupla<Agenda> *listaAgenda = new ListaDupla<Agenda>();
Assumindo que os dados foram introduzidos pelo utilizador e foi declarado uma nova variável “agenda” do tipo “Agenda” (ver código fonte), podemos inserir um contacto na lista, ordenado por nome, da seguinte forma:
if (listaAgenda->vazia()) {
listaAgenda->inserePrimeiro(agenda);
}
else {
Iterador<Agenda> *i = listaAgenda->obtemIteradorCabeca();
NoDuplo<Agenda> *procura;
while ((procura=i->noSeguinte())!=NULL) {
Agenda a = procura->elemento;
if (a.nome>nome) {
break;
}
}
if (procura==NULL) {
listaAgenda->insereUltimo(agenda);
}
else {
listaAgenda->insereAntesDe(procura, agenda);
}
delete i;
}
Novamente, como já é hábito, lá vamos testar se a lista está vazia (linha 1). Se assim for, desta vez uso já o método “inserePrimeiro” para inserir o primeiro contacto da nossa agenda. Caso contrário, vamos procurar onde inserir o novo contacto a partir da cabeça (linha 5), usando um apontador “procura” no ciclo “while” da linha 7.
Repare que, na linha 8, estamos a declarar uma variável do tipo “Agenda” com o elemento retornado pelo iterador. Como estamos a querer inserir os contactos ordenados por nome, se encontrarmos um nome “maior” do que o que estamos a querer inserir, interrompemos o ciclo na linha 10. De forma análoga ao exemplo da lista dos inteiros, se não encontrámos um nome “maior” do que o que queremos inserir, o nó “procura” será NULL (linha 13) e iremos inserir no fim da lista com “insereUltimo”. Se encontrámos o tal nome “maior”, usamos o método “insereAntesDe” passando o nó da procura e o novo contacto definido em “agenda”.
Para removermos um contacto, podemos fazê-lo pelo nome. Assim, tendo o nome que queremos eliminar numa variável “nome”, o código será:
Agenda agenda;
Iterador<Agenda> *i = listaAgenda->obtemIteradorCabeca();
NoDuplo<Agenda> *procura;
while ((procura=i->noSeguinte())!=NULL) {
agenda = procura->elemento;
if (agenda.nome==nome) {
break;
}
}
if (procura==NULL) {
cout << "O nome não foi encontrado na agenda" << endl;
}
else {
if (listaAgenda->remove(procura)) {
cout << "Contacto removido com sucesso" << endl;
}
else {
cout << "Erro ao remover contacto" << endl;
}
}
delete i;
break;
Mais uma vez, obtemos o iterador a partir da cabeça (linha 2) e executamos um ciclo “while” até ao final da lista (linha 4). Se encontrarmos o nosso nome, interrompemos o ciclo (linha 7) e, no fim deste, na linha 10, verificamos se o apontador “procura” é NULL, significando que o nome não foi encontrado na lista. Se encontrámos o nosso nome a remover, na linha 14 tentamos remover o nó que contem esse nome. Mais uma vez, deveremos de conseguir remover o nó. Caso contrário, teremos algum erro no nosso código.
Para listar os elementos da nossa lista, teremos o seguinte código:
cout << endl << "Lista de contactos" << endl;
Iterador<Agenda> *i = listaAgenda->obtemIteradorCabeca();
NoDuplo<Agenda> *lista;
while ((lista=i->noSeguinte())!=NULL) {
cout << "Nome: " << lista->elemento.nome << endl;
cout << "Telefone: " << lista->elemento.telefone << endl;
cout << "E-Mail: " << lista->elemento.email << endl << endl;
}
delete i;
Na linha 2, obtemos o iterador a apontar para a cabeça da lista e executamos o ciclo “while” da linha 4 para listar todos os nós até ao fim da lista.
Podemos ainda listar os elementos da nossa lista por ordem inversa:
cout << endl << "Lista de contactos por ordem inversa" << endl;
Iterador<Agenda> *i = listaAgenda->obtemIteradorCauda();
NoDuplo<Agenda> *lista;
while ((lista=i->noAnterior())!=NULL) {
cout << "Nome: " << lista->elemento.nome << endl;
cout << "Telefone: " << lista->elemento.telefone << endl;
cout << "E-Mail: " << lista->elemento.email << endl << endl;
}
delete i;
Desta vez, na linha 2, obtemos o iterador a apontar para a cauda da lista e executamos o ciclo “while” de trás para a frente (linha 4), para obtermos todos os nós até ao início da lista.
Com este artigo fecho o capítulo das listas, esperando que tenha sido útil para si. Se tiver algumas dúvidas ou quiser outros exemplos de listas, não hesite em usar a área de comentários para deixar as suas questões e/ou sugestões. Note que, existem implementações com mais métodos e que permitem até facilitar as operações realizadas nestes exemplos, incluindo métodos para pesquisa de nós e afins. Contudo, o objectivo foi dar uma ideia sobre a matéria e, após perceber o mecanismo destas listas, o ideal é mesmo usar as classes da STL do C++.
Poderá fazer o donwload do código fonte no link indicado no final do artigo. O código foi escrito em XCode e a codificação dos caracteres está em UTF-8. Os códigos de fim de linha estão em modo OS X / Unix.
Siga-nos nas redes sociais e esteja a par das nossas novidades no nosso blogue multi-temático Out4Mind!
Este artigo foi escrito de acordo com a antiga grafia.
Código fonte (UTF-8 ; OS X / UNIX):
