Namespaces

Variants
Actions

Please note that as of October 24, 2014, the Nokia Developer Wiki will no longer be accepting user contributions, including new entries, edits and comments, as we begin transitioning to our new home, in the Windows Phone Development Wiki. We plan to move over the majority of the existing entries over the next few weeks. Thanks for all your past and future contributions.

Listas Duplamente Encadeadas

From Wiki
Jump to: navigation, search
Article Metadata

Artigo
Criado por cabezonxdg em Cabezonxdg
Última alteração feita por hamishwillee em 09 Dec 2011

Contents

Conceito

Listas duplamente encadaedas são um tipo de estrutura de dados onde um elemento dentro da lista contêm uma referência ao elemento sucessor e anterior.

No Symbian estas listas são circulares, ou seja o último elemento contêm um link (ponteiro) para o primeiro elemento.

A lista possui um inicio (conhecido como cabeça ou em inglês head), meio (todos os elementos intermediários entre a cabeça o e fim da lista) e um fim. Cada elemento possui uma referência para o elemento sucessor e o anterior.

Implementação

Como o SymbianOS não suporta o conjunto de bibliotecas STL (Standard Template Library) ele provê sua própria coleção de classes templates.

Criação e manipulação de listas duplamente encadeadas envolve a utilização destas classes:

  • TDblQueLink
  • TDblQue<class T>
  • TDblQueIter<class T>


TDblQueLink - Classe utilizada para operações relacionadas aos links, contêm ponteiros para o elemento posterior e anterior ao elemento atual.

TDblQue<class T> - Esta classe é responsável pela inserção de elementos no começo e no fim da lista (mas não no meio), também provê funcionalidades para verificar se um elemento é o inicio ou fim da lista.

TDblQueIter<class T> - Este é o iterador da lista, ele é responsável por percorrer os elementos da lista através dos operadores ++ ou --. Um iterador é uma istância da classe TDblQueIter e ele mantem uma referência ao elemento atual da lista.

Construindo a lista

Para exemplificar o uso de listas duplamente encadeadas no Symbian iremos tomar como base o clássico jogo Snakes distribuído pela Nokia. A lógica do jogo é bastante simples, a cada fruta comida pela cobra seu corpo é acrescentado de +1 parte. Podemos construir o corpo da cobra através de uma lista e então fazer adições de mais partes inserindo este novo elemento no final da lista.

/* Esta classe representa uma parte singular da cobra e será parte de uma lista */
class TParteCobra
{
private:
TPoint iPosCobra; // Salva a posição desta parte em relação ao contexto do jogo.
public:
TParteCobra() { }
inline void SetarPosicao( const TPoint& aNovaPos )
{
iPosCobra = aNovaPos;
}
TDblQueLink iLink;
static const TInt iOffset; // Offset do link a partir do inicio da lista.
};
 
const TInt TParteCobra::iOffset = _FOFF(TParteCobra,iLink);
/* Esta classe será responsável por fazer a criação da cobra e realizar suas operações */
class CCobra : public CBase
{
public:
// Construção em duas fases
static CCobra * NewL();
static CCobra * NewLC();
virtual ~CCobra ();
private:
CCobra();
void ConstructL(); // Parte do construtor de 2 fases
void CriarCobra(); // Método para construir a lista duplamente encadeada
TDblQue<TParteCobra> iListaCobra;
TDblQueIter<TParteCobra> iIterador;
};
 
/* PS: A criação dos outros métodos é apenas procedimento padrão e não será descrita aqui. */
 
CCobra::CCobra() : iListaCobra( TParteCobra::iOffSet ), iIterador( iListaCobra )
{
 
}
void CCobra::ConstructL()
{
CriarCobra();
}
 
void CCobra::CriarCobra()
{
TPoint refPosicao;
// Como exemplo , iremos apenas fazer a criação da cobra ( com 3 partes)
for( TInt i = 0; i < 3; i++)
{
// Primeiro elemento da lista, ou seja, a cabeça da cobra
if( i == 0)
{
TParteCobra* novoSegmento = new (ELeave) TParteCobra;
refPosicao.SetXY( i , 0 );
novoSegmento->SetarPosicao( refPosicao );
// Adiciona no inicio da lista
iListaCobra.AddFirst( *novoSegmento );
// Faz o iterador apontar para o primeiro elemento da lista
iIterador.SetToFirst();
}
// Última posição na lista, referente a cauda
else if( i == 2)
{
TParteCobra* novoSegmento = new (ELeave) TParteCobra;
refPosicao.SetXY( i , 0 );
novoSegmento->SetarPosicao( refPosicao );
// Adiciona no fim da lista
iListaCobra.AddLast( *novoSegmento );
}
else
{
TParteCobra* novoSegmento = new (ELeave) TParteCobra;
// segmentoAtual aponta para o elemento atual da lista
TParteCobra* segmentoAtual = iIterador;
refPosicao.SetXY( i , 0 );
novoSegmento->SetarPosicao( refPosicao );
// Insere a referência ao elemento que esta sendo criado no link do elemento atual da lista
novoSegmento->iLink.Enque( &segmentoAtual->iLink );
// Faz o iterador apontar para este elemento
iIterador.Set( *novoSegmento );
}
}
 
// Destrutor da classe, percorre a lista do começo ao fim desalocando os recursos
CCobra::~CCobra()
{
TParteCobra* temp = NULL;
iIter.SetToFirst();
while((temp = iIter++) != NULL)
{
delete temp;
}
}

Referências

This page was last modified on 9 December 2011, at 04:14.
219 page views in the last 30 days.

Was this page helpful?

Your feedback about this content is important. Let us know what you think.

 

Thank you!

We appreciate your feedback.

×