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 ;
}
}
|
Nenhum comentário:
Postar um comentário