Lista de inteiros em c++

Prévia do material em texto

Estruturas de dados em C++
Lista de inteiros
Por Robson Eduardo
Uma lista é 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.
No presente trabalho mostramos a implementação de uma lista de inteiros para exemplificar a 
implementação desta importante estrutura de dados.
A interface da lista
Uma lista deve, assim como qualquer estrutura de dados, ser capaz de adicionar, remover e 
permitir a visualização de seus elementos pelo usuário. Assim criamos a interface pública da 
classe. O construtor cria uma lista vazia, as funções insere são capazes de adicionar um valor à 
lista em uma determinada posição, se omitida a posição, o elemento é adicionado ao final. A 
função retira faz a remoção do que se encontra em uma determinada posição e, por fim, a função 
imprime mostra todos os valores constantes na estrutura.
Escolha da implementação
Em C++, uma lista pode ser implementada de diversas maneiras. Provavelmente, a mais simples é 
lançando mão de um array de tamanho fixo para armazenar os seus elementos. Por achar esta 
forma mais fácil de ser implementada, ela foi escolhida.
class Lista{
public:
 Lista();
 void insere (int);
 void insere (int, int);
 int retira (int);
 int verifica (int);
 void imprime();
...
 
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á dentro dos conformes.
Implementação dos métodos da classe
Construtor
A lista inicia sempre vazia. Não fizemos um construtor de cópias e nem destrutor, já que não 
utilizamos alocação dinâmica de memória ou apontadores. Como a lista deve ser povoada durante 
o uso, não nos interessa o seu conteúdo durante a construção. Ficamos com o seguinte código:
... 
private:
 int elementos[100];
 int ndElem;
};
//testeLista.cpp
#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.insere(2,2);
 l.retira(4);
 l.insere(4,4);
 l.imprime();
}
Função de inserção
Cada vez que um elemento for inserido na última posição da nossa lista, devemos verificar se a 
posição é válida, ora pode ser pedido que se adicione um elemento à uma posição que não está 
coberta pela lista no momento da inserção. Faremos duas funções distintas para inserção: a com 
posição definida e a com posição indefinida. É 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. Dessa forma, foi 
escolhido por duas implementações distintas.
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.
 Lista::Lista(){
 ndElem=0;
 }
 void Lista::insere (int x){
 if(ndElem>=100){
 throw new exception();
 }
 else{
 elementos[ndElem]=x;
 ndElem++;
 }
 }
 void Lista::insere (int x, int pos){
 if(ndElem>=100 || pos<=0)
 throw new exception ();
 int i;
 for(i = ndElem; i>=pos; --i)
 elementos[i]=elementos[i-1];
 elementos[i]=x;
 ndElem++;
 }
Função de exibição
Quando precisamos percorrer a lista verificando seus elementos, podemos usar a seguinte função.
 int Lista::verifica (int pos){
 if(ndElem<pos || pos<=0)
 throw new exception ();
 return elementos[pos-1];
 }
 void Lista::imprime(){
 for(int i=0; i<ndElem; ++i)
 cout << elementos[i] << ", ";
 cout << endl;
 }
	A interface da lista
	Escolha da implementação
	Programa de teste
	Função de inserção
	Função de remoção
	Função de exibição