Lista encadeada de inteiros

Prévia do material em texto

Estruturas de dados em C++
Lista encadeada de inteiros
Por Robson Eduardo
Uma lista encadeada é uma estrutura de dados que armazena o seu conteúdo de forma sequencial. 
Isto é, dada uma posição é possível que alí haja algum elemento. A característica principal da lista
encadeada é a posição em que os dados é guardada na memória não são contíguas. Em C++, a 
lista encadeada pode ter sua integridade basada em módulos que são encontrados na memória 
através de apontadores.
A interface
A lista deve ser capaz de adicionar, remover e permitir a visualização de seus elementos pelo 
usuário. Assim criamos a interface pública da classe. Além disto, como se trata de uma estrutura 
baseada em apontadores, é necessário desenvolver o construtor de cópias e o destrutor. Estas 
funções são importantes quando um objeto é passado por cópia para um método e quando o escopo
de um objeto termina, respectivamente. Se estas funções não forem implementadas, problemas de 
integridade podem surgir, ou o uso de memória se torna descontrolado. 
Implementação
O elemento básico de uma lista encadeada é o nodo. Ele possui um elemento da lista e um 
apontador que define qual o próximo nodo e assim, de forma recursiva a lista é formada por 
completo. O último nodo possui um apontador nulo, indicando que alí ela termina o conteúdo.
class Lista{
public:
 Lista();
 Lista(Lista&);
 ~Lista();
 void insere (int);
 void insere (int, int);
 int retira (int);
 int verifica (int);
 void imprime();
private:
 Nodo * raiz;
};
Programa de teste
Para testar o funcionamento da classe, criamos um programa que utiliza as funções da estrutura 
de forma sistemática para verificarmos se seu funcionamento está correto. Este teste está 
incompleto, tendo em vista que deveríamos testar a passagem da lista por valor e verificar se a 
destrução está sendo eficaz no final das funções. (Eu tinha a escolha de publicar este texto com 
este problema ou não publicar)
class Lista;
class Nodo{
private:
 int valor;
 Nodo* proximo;
public:
 Nodo();
 friend class Lista;
};
Nodo::Nodo(){
 proximo=NULL;
}
#include "Lista.h"
#include <iostream>
using namespace std;
int main(){
 Lista l;
 l.insere(5);
 l.insere(3);
 l.insere(9);
 l.insere(7);
 l.insere(5);
 l.imprime();
 l.retira(1);
 l.insere(2,2);
 l.retira(4);
 l.insere(4,4);
 l.retira(5);
 l.imprime();
 return 0;
}
Implementação dos métodos da classe
Construtor
A lista inicia sempre vazia. Isto é indicado através do apontador para o primeiro nodo da lista ser 
nulo.
Função de inserção
Cada vez que um elemento for inserido na lista, é necessário percorrer todos os nodos até a 
posição desejada, ora a única referência direta que é guardada é a do primeiro elemento. Faremos 
duas funções distintas para inserção: a com posição definida e a com posição indefinida, sendo, 
neste caso, a inserção feita na última posição. É possível reunir estas duas funções em apenas uma 
utilizando um valor default para posição, no entanto, seria difícil distinguir uma chamada sem este
parâmetro de outra em que o parâmetro é informado e coincide com o default, o que deveria gerar 
um lançamento de exceção. Dessa forma, foi escolhido por duas implementações distintas.
Lista::Lista(){
 raiz = NULL;
}
void Lista::insere (int x){
 cout << "insere " << x << endl;
 if(!this->raiz){
 raiz = new Nodo();
 raiz->valor=x;
 return;
 }
 Nodo* nd = this->raiz;
 while(true)
 if(nd->proximo){
 nd = nd->proximo;
 }
 else{
 break;
 }
 nd->proximo=new Nodo();
 nd->proximo->valor=x;
}
Função de remoção
Se é necessário colocar novos elementos na lista, é, também, remover o que está nela. Para isso, 
usamos uma função que recebe uma posição e, se válida, remove o elemento daquela posição. Para
isto, precisamos manter a consistência da lista fazendo que o termo anterior aponte para o 
seguinte, podendo então deletar com segurança o Nodo a ser removido.
void Lista::insere (int x, int pos){
 if(pos<=0)
 throw new exception ();
 if (pos==1){
 Nodo* aux = raiz;
 raiz = new Nodo();
 raiz->valor=x;
 raiz->proximo=aux;
 return;
 }
 Nodo* nd = raiz;
 int indice = 2;
 while(indice<pos){
 if(!nd->proximo)
 throw new exception();
 indice++;
 nd=nd->proximo;
 }
 Nodo* aux=nd->proximo;
 nd->proximo=new Nodo();
 nd->proximo->valor=x;
 nd->proximo->proximo=aux;
}
Função de exibição
Quando precisamos percorrer a lista verificando seus elementos, podemos usar a seguinte função.
int Lista::retira (int pos){
 if(pos<=0)
 throw new exception ();
 if (pos==1){
 system("pause");
 int x = raiz->valor;
 Nodo* aux = raiz->proximo;
 delete raiz;
 raiz=aux;
 system("pause");
 return x;
 }
 int indice=2;
 Nodo* nd = raiz;
 while (indice<pos){
 if(!nd->proximo)
 throw new exception();
 nd = nd->proximo;
 indice++;
 }
 if(nd->proximo){
 Nodo* aux = nd->proximo->proximo;
 delete nd->proximo;
 nd->proximo=aux;
 }
}
void Lista::imprime(){
 Nodo* nd = this->raiz;
 while(nd){
 cout << nd->valor << ", ";
 nd=nd->proximo;
 }
}
	A interface
	Implementação
	Programa de teste
	Implementação dos métodos da classe
	Construtor
	Função de inserção
	Função de remoção
	Função de exibição