Lista Encadeada Genérica 1ª parte

Tipo de Dado Abstrato para Lista Encadeada e Primitiva.

Os exemplos até agora vistos para lista encadeada, foram criados com o propósito de mostrar o conceito dos nós, para manter a simplicidade as rotinas eram dependentes do tipo de dado e da forma como o mesmo deveria ser armazenado, no caso optamos por salvar nomes numa lista sequencial, como feito anteriormente com a estrutura de dados pilha, esta postagem mostra as rotinas implementadas para uma lista encadeada genérica que como o nome indica, pode ser usada para qualquer tipo de informação que precise ser armazenado e tratado dentro de uma lista.

O arquivo de cabeçalho llgen.h mostra as declarações das primitivas para a nossa lista duplamente encadeada que consiste numa corrente de elementos chamados de nó, cada nó possui um tipo de dado e dois ponteiros usados para apontar para o elemento anterior e próximo. Tipo de dado usado é o ponteiro void que consiste no ponteiro genérico de C, que permite ser moldado através do operador cast para qualquer tipo de dado sem erros.

typedef struct tagSNODE {     struct tagSNODE *prior;     struct tagSNODE *next;     void            *pdata; } SNODE;

Neste mesmo arquivo, define-se SLINK como um tipo ponteiro para o nó, SLIST como uma estrutura de dados de uma lista ligada contendo o nó do inicio, o nó do fim, o total de nós na lista e apontamentos para funções especificas da implementação dos dados.

typedef SNODE *      SLINK; typedef struct tagSLIST {     SLINK           slkHead;     SLINK           slkTail;     unsigned int    uiCount;     void *  ( * fCreateData )       ( void * );     BOOL    ( * fDeleteData )       ( void * );     int     ( * fDuplicatedNode )   ( SLINK, SLINK );     int     ( * fNodeDataCmp )      ( void *, void * ); } SLIST;

Por mais abrangente e genérica que se possa criar uma função, a lista encadeada realmente genérica consegue manipular apenas as conexões do nó, esse tipo de operação não precisa saber como os dados se parecem, restando quatro tipos de operações que manipulam os dados diretamente e dependem do tipo definido. Criar, apagar, comparar e tratar duplicado são funções que fazem parte do arquivo llapp.c de rotinas especificas da aplicação e passam a integrar a estrutura de dados lista através dos ponteiros da estrutura mostrada.

FUNÇÕES ESPECIFICAS PARA LISTA ENCADEADA
Nome	Descrição
fCreateData	Recebe um ponteiro do objeto definido para a aplicação, espera-se o retorno de um ponteiro para o que venha a ser o dado armazenado na lista.
fDeleteData	Recebe um ponteiro do objeto definido para a aplicação que deve estar armazenado na lista ligada. fDeleteData deve destruir o objeto
fDuplicateNode	São passados dois ponteiros. O primeiro ponteiro é o nó que deve ser adicionado e o segundo é o nó que já se encontra na lista, mas que é igual(duplicada) a informação do primeiro ponteiro, retornando: 0 -> nenhuma ação na lista 1 -> destruir duplicada 2 -> adicionar duplicada
fNodeDataCmp	São passados dois ponteiros do objeto definido para o dado e deve compara-lo, retornando um numero que é < 0, zero, ou > 0, dependendo da relação entre o primeiro e segundo objeto.

Para permitir maior legibilidade foram feitas as seguintes redefinições:

#define LLHead          (L->slkHead) #define LLTail          (L->slkTail) #define NodeCount       (L->uiCount) #define CreateData      (*(L->fCreateData)) #define DeleteData      (*(L->fDeleteData)) #define DuplicatedNode  (*(L->fDuplicatedNode)) #define NodeDataCmp     (*(L->fNodeDataCmp))

As rotinas abaixo fazem parte das primitivas genéricas para lista encadeadas, tais funções manipulam somente as ligações do nó, sendo completamente independentes da aplicação e não devem ser alteradas.

Função	AddNodeAtHead
Propósito	Adiciona um nó no inicio (cabeça) da lista NÃO ordenada
Parâmetros	SLIST *L -> ponteiro para estrutura de dados que trata a lista NÃO ordenada void *nd -> nó a ser inserido na lista NÃO ordenada
Retorno	TRUE - adicionou no inicio da lista o nó FALSE - não conseguiu criar um nó para inserir na lista
Descrição	Armazena um novo nó sempre no inicio da lista, primeiro aloca espaço para o dado, a seguir aloca um nó com ponteiro para o dado, então adiciona o nó na lista.

BOOL AddNodeAtHead( SLIST *L, void *nd ) {     SLINK slkPn;                // ponteiro do noh a ser inserido na lista     slkPn = CreateNode(L, nd);  // cria o noh e passa o endereco     if (slkPn == NULL)          // naoh conseguiu alocar o noh         return FALSE;           // retorna indicando fracasso     // adiciona o noh     if (LLHead == NULL)         // primeiro noh a ser inserido na lista ?     {         LLHead = LLTail = slkPn;// sim     }     else                        // naoh     {         LLHead->prior = slkPn;  // noh antes do inicio(cabeca)         slkPn->next = LLHead;   // inicio como seguinte do novo noh         LLHead = slkPn;         // aponta o inicio para o novo noh     }     ++NodeCount;                // soma o novo noh no total     return TRUE; }

Função	AddNodeAscend
Propósito	Adiciona um nó ascendente
Parâmetros	SLIST *L -> ponteiro para estrutura de dados que trata a lista void *nd -> nó a ser inserido na lista
Retorno	TRUE - adicionou na lista o nó, caso seja duplicata, remove, adiciona ou ignora, depende da configuração da lista FALSE - não conseguiu criar um nó para inserir na lista
Descrição	Adiciona um nó numa lista ordenada

BOOL AddNodeAscend( SLIST *L, void *nd ) {     SLINK slkPn;      // ponteiro de para o noh a ser inserido na lista     SLINK slkPrev;    // ponteiro do link anterior da lista durante a busca     SLINK slkCurr;    // ponteiro do link atual da lista durante a busca     SNODE snDummy;    // noh temporario     int iCompare;     // resultado da comparacaoh entre dois nohs     int iAction;      // acaoh a ser tomada em caso de nohs duplicados     slkPn = CreateNode(L, nd);   // cria o noh e passa o endereco     if (slkPn == NULL)           // naoh conseguiu alocar o noh         return FALSE;            // retorna indicando fracasso     // ignora o tratamento especial que se faz para o inicio da lista     // adiciona o noh temporario ao inicio da lista     // e passa a tratar o noh inicial(cabeca) como um noh igual aos demais     // simplificando a logica de tratamento     snDummy.next = LLHead;     snDummy.prior = NULL;     if (snDummy.next != NULL)           // se a lista naoh estiver vazia         snDummy.next->prior = &snDummy; // igual, LLHEAD->prior = &snDummy;     // se prepara para percorrer a lista     slkPrev = &snDummy;     // noh anterior aponta p/ o noh temporario     slkCurr = snDummy.next; // noh atual aponta p/ o noh inicial da lista     // busca     // enquanto o link do noh for valido     // copia o noh atual para o anterior     // copia o noh seguinte para o atual     for ( ; slkCurr != NULL; slkPrev = slkCurr, slkCurr = slkCurr->next)     {         // usa funcaoh que compara dados do atual com o noh a ser inserido         iCompare = NodeDataCmp(slkPn->pdata, slkCurr->pdata);         if (iCompare <= 0) {             break;          // o novo noh eh igual ou precede o atual         }     }     // se naoh percorreu a lista ateh o final     // e o encontrou uma copia(duplicada) dos dados na lista     if ((slkCurr != NULL) && (iCompare == 0))     {         // chama a funcaoh que retorna a acaoh desejada         // no caso de noh duplicado         iAction = DuplicatedNode(slkPn, slkCurr);         //        fDuplicateNode retorna:         //              2 -> adicionar duplicada         if (iAction == 2) {             // nada faz, deve ser inserido             // o tratamento continua fora             // da condicional 'if ((slkCurr != NULL) && (iCompare == 0))'         }           //        fDuplicateNode retorna:         //              0 -> nenhuma acaoh na lista         //              1 -> destruir duplicada         else    // if (iAction == 0 || iAction == 1)         {             // primeiro, arruma a lista ligada tiramos o noh             // temporario do inicio e restauramos o inicio original             LLHead = snDummy.next;             LLHead->prior = NULL;             // se apropriado, apaga o noh duplicado             if (iAction == 1) // ||(iAction == 0)             {                 // apaga os dados que dependem da implementacaoh do objeto                 DeleteData(slkPn->pdata);                   free(slkPn);                // desalocamos o noh             }             // se a iAction == 0, um erro aconteceu,             // o tratamento vai ser feito fora desta funcaoh             return TRUE;             // encontrou uma duplicata,tomou a acaoh de ignorar ou excluir         }                }     // vai adicionar o noh entre o anterior e o atual     slkPrev->next = slkPn;    // o noh anterior aponta para o novo     slkPn->prior = slkPrev;   // o novo aponta 'prior' para o noh anterior     slkPn->next = slkCurr;    // o novo aponta 'next' para o noh atual     // se o noh corrente aponta para uma posicao valida na lista     if (slkCurr != NULL)     {         slkCurr->prior = slkPn; // noh atual aponta 'prior' para o novo noh     }     // do contrario, significa que percorreu a lista ateh o final     else     {         LLTail = slkPn;             //  este noh eh a novo fim(cauda)     }     ++NodeCount;                    // soma o novo noh no total     // retiramos o noh temporario     LLHead = snDummy.next;     LLHead->prior = NULL;     return TRUE; }

Função	CreateLList
Propósito	Cria e inicia uma estrutura de gerenciamento de lista ligada
Parâmetros	ponteiro para as funções especifica da lista void *(*fCreateData)(void *) cria dado int   (*fDeleteData)(void *) apaga dado int   (*fDuplicatedNode)(SLINK, SLINK) tratar duplicado. int   (*fNodeDataCmp)(void *, void *)  compara nós
Retorno	ponteiro SLIST     pL   - ponteiro para uma estrutura do tipo lista inicializada     NULL - não conseguiu criar a lista ligada
Descrição	Cria uma estrutura de lista ligada e retorna um ponteiro da mesma. Em erro, retorna NULL. Esta função aceita ponteiros para as quatro funções especificas de uma lista e inicializa a estrutura com elas.

SLIST *CreateLList( void *  ( * fCreateData ) ( void * ),                     BOOL    ( * fDeleteData ) ( void * ),                     int     ( * fDuplicatedNode ) ( SLINK, SLINK ),                     int     ( * fNodeDataCmp ) ( void *, void *)) {     SLIST *pL;     // aloca uma estrutura que gerencia uma lista ligada     pL = (SLIST *) malloc(sizeof(SLIST));     if (pL == NULL)         //  caso fracasse em alocar memoria         return NULL;        // retorna a indicacaoh     // tendo alocado, inicializa as variaveis     pL->slkHead = NULL;     pL->slkTail = NULL;     pL->uiCount = 0;         // e armazena as funcoesh especificas para tratamento da lista     pL->fCreateData = fCreateData;     pL->fDeleteData = fDeleteData;     pL->fDuplicatedNode = fDuplicatedNode;     pL->fNodeDataCmp = fNodeDataCmp;     return (pL);            // devolve o enderecoh da lista }

Função	CreateNode
Propósito	Criar um nó para a lista ligada
Parâmetros	SLIST *L   -> estrutura lista c/ ponteiro para a função CreateData void *data -> ponteiro genérico c/ o dado do nó
Retorno	slkNewNode - ponteiro para uma estrutura do tipo nó NULL - não conseguiu criar um nó
Descrição	Cria um nó e então chama a função especifica da aplicação CreateData() para criar o dado da estrutura do nó. Em caso de falha retorna NULO

SLINK CreateNode( SLIST *L, void *data ) {     SLINK slkNewNode;     // aloca os ponteiros para seguinte, anterior e dado para o noh     slkNewNode = (SLINK) malloc(sizeof(SNODE));     if (slkNewNode == NULL)     // caso fracasse em alocar memoria         return (NULL);          // retorna indicacaoh de NULO     // tendo sucesso na alocacaoh, inicializa as variaveis     slkNewNode->prior = NULL;     slkNewNode->next = NULL;     // agora chama a aplicacaoh especifica para alocacah de dados     slkNewNode->pdata = CreateData(data);     // caso naoh consiga alocar memoria para o dado do noh     if (slkNewNode->pdata == NULL)     {         free(slkNewNode);       // libera a memoria previamente alocada         return (NULL);          // retorna NULO para indicar falha     }     // alocou toda a memoria nescessaria     else {         return (slkNewNode);    // retorna o ponteiro para a funcaoh     } }

Função	DeleteNode
Propósito	Apaga um nó da lista ligada
Parâmetros	SLIST *L          -> estrutura lista c/ ponteiro para a função DeleteData SLINK slkToDelete -> o nó a ser excluído
Retorno	TRUE  - exclui o nó e atualizou a lista FALSE - não era um nó valido p/ exclusão
Descrição	Apaga um nó apontado por slkToDelete. Verifica se o nó se encontra no inicio, meio ou fim p/ tratamento especifico. Função chama a aplicação especifica da lista para apagar o dado

BOOL DeleteNode( SLIST *L, SLINK slkToDelete ) {     SLINK slkPn;     if (slkToDelete == NULL)    // certifica-se de ser um noh valido         return FALSE;           // antes de tentar apagar qualquer coisa     if (slkToDelete->prior == NULL)// se encontra no inicio da lista (cabeca)     {         LLHead = slkToDelete->next;// atualiza o inicio         LLHead->prior = NULL;      // o anterior do inicio deve ser NULO     }     else if (slkToDelete->next == NULL) // se encontra no fim da lista (cauda)     {         LLTail = slkToDelete->prior;// atualiza o fim         LLTail->next = NULL;        // o seguinte do fim deve ser NULO     }     else                            // se encontra no meio da lista     {         slkPn = slkToDelete->prior; // vai para o noh anterior ao da exclusaoh         slkPn->next = slkToDelete->next;// atualiza para o proximo         slkPn = slkToDelete->next;  // vai para o noh seguinte ao da exclusaoh         slkPn->prior = slkToDelete->prior;// e atualiza para o anterior     }     DeleteData(slkToDelete->pdata);     // apaga o dado do noh     free(slkToDelete);                  // libera a memoria do noh     --NodeCount;                        // subtrai o noh do total     return TRUE; }

Função	FindNode
Propósito	Pesquisa a lista inteira obs.:por ser NÃO ordenada
Parâmetros	SLIST *L -> estrutura com as variáveis de controle e função de comparação void *nd -> nó a ser encontrado
Retorno	slkPCurr - aponta para o nó desejado na lista NULL     - não encontrou o nó
Descrição	Encontra um nó, iniciando a busca no inicio da lista, avançando em cada nó e comparando os itens do dado com a chave de pesquisa. Precisa percorrer toda a lista, por se tratar de uma NÃO ordenada

SLINK FindNode( SLIST *L, void *nd ) {     SLINK   slkPCurr;       // o noh que estamos examinando     if (LLHead == NULL) {   // lista vazia ?         return (NULL);      // retornando indicando NULO como falha     }     // posiciona slkPCurr no inicio da lista     // enquanto for valido, avancah p/ o seguinte     for (slkPCurr = LLHead; slkPCurr != NULL; slkPCurr = slkPCurr->next)     {         // compara, se igual         if (NodeDataCmp(nd, slkPCurr->pdata) == 0)         {             return (slkPCurr);// retorna o ponteiro p/ a posicaoh da lista         }     }     // naoh consigou encontrar o noh     return (NULL); }

Função	FindNodeAscend
Propósito	Pesquisa a lista ordenada.
Parâmetros	SLIST *L -> estrutura com as variáveis de controle e função de comparação void *nd -> nó a ser encontrado
Retorno	slkPCurr - aponta para o nó desejado na lista NULL     - não encontrou o nó
Descrição	Encontra um nó, iniciando a busca no inicio da lista, avançando em cada nó e comparando os itens do dado com a chave de pesquisa ENQUANTO não for maior que o desejado, por estar previamente ordenada, não pode se encontrar no restante da fila

SLINK FindNodeAscend( SLIST *L, void *nd ) {     SLINK   slkPCurr;       // o noh que estamos examinando     int     iCmpResult;     // resultado da comparacao     if (LLHead == NULL) {   // lista vazia ?         return (NULL);      // retornando indicando NULO como falha     }     // posiciona slkPCurr no inicio da lista     // enquanto for valido, avancah p/ o seguinte     for (slkPCurr = LLHead; slkPCurr != NULL; slkPCurr = slkPCurr->next)     {         // salva o resultado, para poder fazer duas analises posteriores         iCmpResult = NodeDataCmp(nd, slkPCurr->pdata);         // compara, se o noh pesquisado eh maior que a posicaoh atual da lista         if (iCmpResult < 0)         {             // indica falha, pois naoh pode estar no restante da fila             return (NULL);         }         // compara, se igual         if (iCmpResult == 0)         {             return (slkPCurr);// retorna o ponteiro p/ a posicaoh da lista         }     }     // naoh consigou encontrar o noh em toda lista     return (NULL); }

Função	DestroyLList
Propósito	Apaga a estrutura de gerenciamento de lista ligada e seus nós
Parâmetros	ponteiro SLIST pL   - ponteiro da estrutura do tipo lista a ser liberada
Retorno	TRUE  - liberou toda a memória alocada previamente FALSE - não conseguiu apagar a lista ligada
Descrição	Após verificar que se trata de uma lista valida, percorre a mesma, apagando os nós individualmente, por fim, libera a memória usada pela própria estrutura de gerenciamento.

BOOL DestroyLList(SLIST *pL) {     SLINK slk1, slk2;    // cursores p/ percorrer as lista     if (pL == NULL)      //  caso naoh exista uma estrutura valida         return FALSE;    // retorna a indicacaoh de falha     // percorre a lista apagando todos os nohs     for (slk1 = pL->slkHead; slk1 != NULL;) {         slk2 = slk1;            // faz um backup da posicaoh         slk1 = slk1->next;      // avanca para o proximo         DeleteNode(pL, slk2);   // usa o backup para apagar o noh     }         free(pL);       // libera a estrutura que gerencia a lista ligada     return TRUE;    // informa que a lista foi destruida }

Devido a grande extensão do assunto, o texto foi dividido em duas partes, a próxima postagem trará um exemplo de aplicação realizando várias operações com as primitivas apresentadas.