sábado, 4 de maio de 2013

Exemplo de lista duplamente encadeada

                O programa exemplo de lista duplamente encadeada repete alguma das funções mostrada no exemplo de lista singularmente encadeada, com as alterações relativas ao suporte do apontamento anterior (prior) que passa a integrar o nó.

                Na declaração do nó incluímos as alterações do ponteiro para o item anterior e o novo apontador para o fim da lista ptrEnd.

typedef struct tagNode
      {
            char strName[80];
            struct tagNode *next;
            struct tagNode *prior;
      } sNode;

sNode *ptrStart;
sNode *ptrEnd;

                INSERIR

                Com a alteração do tipo de dado, adapta-se função DLListStore para receber alem do novo nó e o inicio da lista, o apontamento de fim da lista. A primeira ação é verificar se a lista está vazia e iniciar corretamente os apontadores de fim e inicio, junto dos ponteiros anterior e seguinte.

      if ( *pStart == NULL ) {
            *pStart = *pEnd = pNew;
            pNew->next = NULL;
            pNew->prior = NULL;
      }

                Desta vez o processo de percorrer a lista despreza o uso de outro nó contendo a informação anterior.

      sNode *pInfo = *pStart;

      while( pInfo ) {
            if ( strcmp( pNew->strName, pInfo->strName ) > 0 ) {
                  pInfo = pInfo->next;
            }
      }

                O novo nó pNew é inserido antes do nó pInfo que está percorrendo a lista, primeiro atualiza-se a informação dos apontamentos do novo nó.

      pNew->next  = pInfo;
      pNew->prior = pInfo->prior;

Nó pInfo que aponta para a atual posição da lista fica após o novo nó pNew, portanto muda-se o endereço de anterior para o novo nó, na sequencia, caso a informação copiada para o ponteiro anterior (prior) seja nula, significa que o novo nó foi inserido no inicio da lista, portanto atualiza o ponteiro de inicio pStart.

      pInfo->prior = pNew;

      if ( pNew->prior ) {
            pNew->prior->next = pNew;
      }
      else {
            *pStart = pNew;
      }

Quando o nó pInfo de posição percorrer toda lista, o nó pNew deve ser inserido no fim da lista.

      pNew->prior = *pEnd;
      pNew->next = NULL;
      (*pEnd)->next = pNew;
      *pEnd = pNew;

EXCLUIR

                A rotina DLListDelete também foi adaptada para receber o apontador para fim da lista ptrEnd, o processo de exclusão quando encontra o elemento a ser excluído trata de quatro situações:

1)      Apagar o único nó da lista
      if (*pStart == *pEnd)
            *pStart = *pEnd = NULL;

2)      Remover o início da lista
      if ( pInfo->prior == NULL ) {
            *pStart = pInfo->next;
            pInfo->next->prior = pInfo->prior;
      }

3)      Excluir o nó do final da lista.
      if ( pInfo->next == NULL ) {
            *pEnd = pInfo->prior;
            pInfo->prior->next = pInfo->next;       
      }

4)      Eliminar um nó intermediário.
      pInfo->prior->next = pInfo->next;       
      pInfo->next->prior = pInfo->prior;

                Caso precise de ajuda quando executar o programa, as ações do menu e seu funcionamento estão descritas na postagem que apresenta a versão de exemplo para lista singularmente encadeada, o programa completo segue abaixo.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct tagNode
      {
            char strName[80];
            struct tagNode *next;
            struct tagNode *prior;
      } sNode;

sNode *ptrStart;
sNode *ptrEnd;

void DLListStore( sNode *, sNode **, sNode ** );
sNode *DLListDelete( char *, sNode **, sNode **);
void Display( sNode * ); 

int Menu( void );
void Insert( void );
void Input( char *, char *, int );
void Delete( void );

int main( int argc , char *argv[] )
{
      ptrStart = ptrEnd = NULL;

      for ( ; ; ) {
            switch ( Menu() ) {
                  case 1:     Insert();               break;
                  case 2:     Delete();               break;
                  case 3:     Display(ptrStart);      break;
                  case 0:     exit(1);
            }
      }
      return(0);
}

int Menu( void )
{
      char cTmp[10];
      int iChoice;

      printf("\n\nInserir  ( 1 )\n");
      printf(    "Apagar   ( 2 )\n");
      printf(    "Listar   ( 3 )\n");
      printf(    "Sair     ( 0 )\n\n");
      printf("Escolha umas das alternativas anteriores : " );
      fgets( cTmp , 9 , stdin );
      cTmp[strlen(cTmp)-1] = '\0' ;
      if ( *cTmp == '\0' || !(isdigit(*cTmp)) ) return 100;
      iChoice = atoi(cTmp) ;

      return iChoice;
}

void Insert( void )
{
      sNode *info;

      for ( ; ; )
      {
            info = (sNode *) malloc(sizeof(sNode));
            if ( info == NULL ) {
                  printf("\nSem Memoria\n\n");
                  return;
            }
            Input("Digite o nome : " , info->strName, 80 );
            if ( info->strName[0] == '\0' ) break;
           
            DLListStore( info, &ptrStart, &ptrEnd );
      }
}

void Input( char *pText , char *pContent , int size )
{
    printf( pText ) ;
    fgets( pContent , size-1 , stdin ) ;
    pContent[strlen(pContent)-1] = '\0' ;   
}

void DLListStore( sNode *pNew , sNode **pStart , sNode **pEnd )
{
      sNode *pInfo = *pStart;

      if ( *pStart == NULL ) {
            *pStart = *pEnd = pNew;
            pNew->next = NULL;
            pNew->prior = NULL;
            return;
      }

      while( pInfo ) {
            if ( strcmp( pNew->strName, pInfo->strName ) > 0 ) {
                  pInfo = pInfo->next;
            }
            else {
                  pNew->next  = pInfo;
                  pNew->prior = pInfo->prior;
                  pInfo->prior = pNew;

                  if ( pNew->prior ) {
                        pNew->prior->next = pNew;
                  }
                  else {
                        *pStart = pNew;
                  }
                  return;
            }
      }

      pNew->prior = *pEnd;
      pNew->next = NULL;
      (*pEnd)->next = pNew;
      *pEnd = pNew;
      return ;
}

void Delete( void )
{
      char strName[80] ;
      sNode *pInfo;

      printf("\n\nDigite o nome que deseja excluir da lista : ");
      fgets ( strName , 79 , stdin ) ;
      strName[strlen(strName)-1] = '\0' ;

      pInfo = DLListDelete( strName, &ptrStart, &ptrEnd );

      if ( pInfo ) {
            printf("\nItem removido\n\n");
            free(pInfo);
      }
      else
            printf("\nNao encontrado\n\n");
}

sNode *DLListDelete( char *strName , sNode **pStart  , sNode **pEnd )
{
      sNode *pInfo = *pStart;

      while( pInfo ) {
            if ( strcmp( strName, pInfo->strName ) == 0 ) { 
                  if (*pStart == *pEnd) {
                        *pStart = *pEnd = NULL;
                  }
                  else  if ( pInfo->prior == NULL ) {
                        *pStart = pInfo->next;
                        pInfo->next->prior = pInfo->prior;
                  }
                  else if ( pInfo->next == NULL ) {
                        *pEnd = pInfo->prior;
                        pInfo->prior->next = pInfo->next;       
                  }
                  else {
                        pInfo->prior->next = pInfo->next;       
                        pInfo->next->prior = pInfo->prior;
                  }
                  return (pInfo);
            }
            pInfo = pInfo->next;
      }

      return NULL;
}

void Display( sNode *pStart )
{
      printf ("\n Lista atual \n\n\n");
      while ( pStart != NULL ) {
            printf("Name : %s\n" , pStart->strName );
            printf("\t Prior: \t%p\n" , pStart->prior );
            printf("\t Add. : \t%p\n" , pStart );
            printf("\t Next : \t%p\n" , pStart->next );
            pStart = pStart->next ;
      }
}

quinta-feira, 2 de maio de 2013

Lista Duplamente Encadeada

Como o nome sugere, são compostas de nós ligados por dois ponteiros. Cada nó de uma lista duplamente encadeada consiste de três partes: alem dos dados e do ponteiro próximo (next), o nó passa a incorporar um ponteiro para o elemento anterior (prior).

Ao avaliar o exemplo de lista ligada, pode-se perceber a dependência do mecanismo de inserir e excluir de uma busca que irá percorrer a toda a lista e a necessidade de durante toda a procura manter a informação do elemento anterior.

A melhoria para este tipo de situação se faz com o nó apontando também para o membro anterior da lista, apesar do aumento do tamanho do nó de informação, a vantagem aparece em termos de flexibilidade ao poder percorrer a lista em ambas as direções, ao somar a capacidade de percorrer a lista a partir de seus extremos, passa a incluir mais um apontador para o fim (end) da lista, junto do inicio (start).



Null


<
Prior


<
Prior

<
End


Info


Info


Info


Start
>

Next
>


Next
>


Null



O resultado das operações para este tipo de lista se torna mais intuitivo no momento de passar o conceito para o código do programa, tanto para inserir, como para remover, analisando uma inserção entre dois elementos:

a)      Encontrar a posição da lista para incluir o novo nó.


b)      Novo nó atualiza os endereços de seus apontadores, usando os dados do nó que utiliza a posição a ser ocupada na lista.


c)       Inclui o novo nó ao mudar o apontamento de próximo do nó anterior e o apontamento de anterior do próximo nó.
  
                Mesma situação se repete para excluir, ao inverter a sequencia de operação.

                Abaixo segue os Detalhes para as três situações que podem ocorrer quando se insere um item na lista duplamente encadeada:


1.                   Item pode se tornar o primeiro da lista;

Info
































Info


Info




Start
>
Next
>
Nulo





Nulo
<
Prior
<
End

·         Ponteiro anterior do primeiro da lista indica o novo item.
·         Novo item copia o endereço de próximo que está em Start.
·         Novo item coloca nulo para anterior.
·         Start aponta para o novo item.



Info











Start


next












Nulo


















Info


Info











Next


Nulo







Prior


Prior


End




2.       Inserir entre dois outros itens;








Info










































Info









Info



Start

Next




Nulo




Nulo





Prior


End

·         Novo item copia o endereço de próximo que está no item anterior.
·         Novo item copia o endereço de anterior que está no item próximo.
·         Item próximo atualiza o endereço anterior para o novo item.
·         Item anterior atualiza o endereço próximo para o novo item.








Info
















Next














Prior










Info









Info



Start


Next









Nulo




Nulo









Prior


End




3.       Ser o ultimo item da lista;



Info


Info




Info
Start


Next


Nulo






Nulo


Prior


End


·         Troca o Nulo pelo endereço do novo item no ultimo item da lista.
·         Novo item atualiza endereço de anterior para o ultimo da lista.
·          Novo item atualiza endereço de próximo para Nulo.
·         End aponta para o novo item.



Info


Info


Info



Start


Next


Next


Nulo




Nulo


Prior


Prior


End






Por fim, mais três situações podem ocorrer quando se remove um item na lista duplamente encadeada, repare que como reflexo da inserção, a sequência de operação se inverte:


1.       Excluir o primeiro da lista;



Info


Info


Info



Start


Next


Next


Nulo




Nulo


Prior


Prior


End

·         Copia o endereço de próximo no primeiro item para Start.
·         Coloca endereço anterior nulo para o novo primeiro item.






Info


Info



Start





Next


Nulo







Nulo


Prior


End





2.       Elimina numa posição intermediaria;



Info


Info


Info



Start

Next


Next


Nulo




Nulo


Prior


Prior


End

·         Copia no item anterior ao que vai ser excluído o endereço de próximo.
·         Copia no item próximo ao que vai ser excluído o endereço de anterior.



Info





Info



Start


Next




Nulo




Nulo





Prior


End




3.       Excluir o ultimo item;



Info


Info


Info



Start


Next


Next


Nulo




Nulo


Prior


Prior


End

·         Troca o endereço que aponta para o item a ser excluído por nulo.
·         Copia o endereço de anterior do item a ser excluído em End.



Info


Info



Start
>

Next


Nulo




Nulo


Prior


End




Um modelo simples e didático de código em linguagem C para uma lista duplamente encadeada está incluído na próxima postagem “Exemplo de lista duplamente encadeada” e serve como complemento prático mostrando a programação completa das rotinas para inserir, excluir e percorrer.