Exemplo de lista encadeada

Como exemplo para o conceito apresentado na postagem anterior (Lista Encadeada), segue um programa simples e completo que armazena nomes em ordem crescente, abaixo segue a declaração de como será o nó da lista a ser utilizada, junto do ponteiro que indica o inicio da lista:

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

Apesar de ser ideal utilizar funções como getnode e freenode, utilizando em separado rotinas de ordenação, é mais simples construir a lista de forma já ordenada, inserindo cada novo elemento na sequencia apropriada.

INSERIR

A função LListStore recebe o novo nó e o ponteiro com o inicio da lista, a primeira verificação, é para inicializar a lista caso está esteja vazia com o novo nó.

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

A próxima parte consiste em percorrer a lista comparando o nome do novo elemento, com o que está armazenado, temos um nó pInfo para a posição atual e outro nó pPrior para a posição anterior.  Enquanto pInfo apontar para um elemento valido, avança para o próximo nó.

sNode *pInfo = *pStart;       sNode *pPrior = NULL;       while( pInfo )       {             if ( strcmp( pNew->strName, pInfo->strName ) > 0 )             {                   pPrior = pInfo;                   pInfo = pInfo->next;             }       }

Para o caso aonde o novo elemento será o novo inicio da lista, significa que pPrior ainda é nulo, atualizamos o endereço seguinte do novo elemento e direciona-se o ponteiro pStart para o novo nó. 

if ( pPrior == NULL) {             pNew->next  = pInfo;             *pStart = pNew;       }

Se ponteiro pPrior não for nulo, significa inserção entre dois elementos, atualiza o endereço do ponteiro pPrior para o novo nó e novo nó aponta para o elemento atual da lista.

if ( pPrior ) {             pPrior->next = pNew;             pNew->next  = pInfo;       }

Ao terminar de percorrer toda lista sem ter encontrado uma posição, significa incluir no fim da lista, portanto o ponteiro anterior pPrior aponta para o novo nó e que passa indicar fim de lista com nulo no campo de endereço seguinte.

pPrior->next = pNew;       pNew->next = NULL;

EXCLUIR

Para o processo de exclusão a rotina LListDelete recebe o como entrada cuja ocorrência na lista deverá ser excluída, junto do inicio da lista, repetindo a forma de percorrer a lista como visto acima, as posições são controladas por pInfo para atual e pPrior para anterior. 

Sendo o nó pPrior nulo, significa excluir o primeiro elemento, basta atualizar o ponteiro pStart que indica o inicio da fila para o seguinte.

if ( pPrior == NULL )             *pStart = pInfo->next;

Para as demais situações do processo de exclusão, basta copiar o valor do endereço do próximo nó do elemento a ser excluído para o nó anterior.

if ( pPrior )             pPrior->next = pInfo->next;

Copiar o valor de next simplifica o processo, pois o mesmo já está inicializado com o valor do próximo nó ou indicação de nulo.

Observe que a busca do nó deveria ser feito em separado da rotina para excluir o nó, entretanto por se tratar de uma lista singularmente encadeada, o processo de exclusão necessita do endereço do nó a ser excluído, junto do nó anterior, o que aumentaria também a complexidade do processo de busca do que deveria ser um simples exemplo, a modularidade desejada será atendida quando for apresentado o conceito de lista duplamente encadeada que irá incorporar o endereço anterior à estrutura do nó.

Os processos para alocar e liberar a memória usada na lista foi realizado fora de LListStore e LListDelete para manter as mesmas compactas e enfatizar somente o processo de controle de apontamento, as rotinas responsáveis por isto são Insert e Delete, fazem parte do menu com as opções de operação em lista, o programa completo segue abaixo.

A execução resulta na seguinte tela, aonde se pode escolher a ação digitando o numero entre parênteses.

Inserir  ( 1 ) Apagar   ( 2 ) Listar   ( 3 ) Sair     ( 0 ) Escolha umas das alternativas anteriores :

Após selecionar  ‘1’ para iniciar a entrada de nome para a lista e realizar a inclusão dos nomes, o usuário deve confirmar o campo nome estando vazio,  para encerrar o processo de inserir.

Escolha umas das alternativas anteriores : 1 Digite o nome : roberto Digite o nome : vanusa Digite o nome : mariana Digite o nome : laura Digite o nome : bianca Digite o nome : Inserir  ( 1 ) Apagar   ( 2 ) Listar   ( 3 ) Sair     ( 0 ) Escolha umas das alternativas anteriores :

Digite ‘2’ para selecionar a opção de apagar um nome na lista, após a entrada do nome, o item será excluído caso seja encontrado, do contrario, informa que não foi possível encontrar o item.

Escolha umas das alternativas anteriores : 2 Digite o nome que deseja excluir da lista : mariana Item removido Inserir  ( 1 ) Apagar   ( 2 ) Listar   ( 3 ) Sair     ( 0 ) Escolha umas das alternativas anteriores : 2 Digite o nome que deseja excluir da lista : mari Nao encontrado

A terceira opção de listar os nomes, apresenta os nomes em ordem crescente junto das informações de endereço na memória, como o endereço do nó, mais o ponteiro para o próximo nó.

Name : bianca          Address :      004F1458          Next :         004F13D8 Name : laura          Address :      004F13D8          Next :         004F1258 Name : roberto          Address :      004F1258          Next :         004F12D8 Name : vanusa          Address :      004F12D8          Next :         00000000