Lista Encadeada Genérica 2ª parte

Montando a aplicação com ajuda das primitivas.

Utilizando as primitivas apresentadas anteriormente, para inicializar uma aplicação com uma lista ligada, cria-se a estrutura SLIST como mostrado abaixo, que se será referenciada no código através do ponteiro L.

SLIST *L;     L = CreateLList(    CreateData,                         DeleteData,                         DuplicatedNode,                         NodeDataCmp);

Cada função primitiva abaixo com exceção de CreateLList recebe como primeiro parâmetro o endereço (ponteiro L) da estrutura contendo os itens individuais de informação da lista ligada.

Primitivas Genéricas:	BOOL AddNodeAscend( SLIST *, void * );
	BOOL AddNodeAtHead( SLIST *, void * );
	SLINK CreateNode( SLIST *, void * );
	BOOL DeleteNode( SLIST *, SLINK );
	SLINK FindNode( SLIST *, void * );
	SLINK FindNodeAscend( SLIST *, void * );
	SLIST *CreateLList(     void * (* fCreateData)     (void *),     BOOL   (* fDeleteData)     (void *),     int    (* fDuplicatedNode) (SLINK, SLINK),     int    (* fNodeDataCmp)    (void *, void *));
	BOOL DestroyLList( SLIST * );

O arquivo de cabeçalho llapp.h tem o dado do aplicativo e que será armazenado na lista como um nó, segue a definição do tipo da estrutura SNODEDATA e do tipo de ponteiro pND mostrado abaixo.

typedef struct tagSNODEDATA {     char *pName; }SNODEDATA; typedef SNODEDATA *pND;

Pode-se notar que algumas rotinas precisam ser capazes de examinar, mas não modificam os dados de um nó. Por exemplo, a função AddNodeAscend(), que adiciona um nó em ordem ascendente, precisa ser capaz de comparar os dados do nó que será adicionado com o que está sendo a posição atual da pesquisa. Para isto, chama a comparação de lista especifica apontado por fNodeDataCmp na estrutura SLIST. A sintaxe para chamar a rotina através do ponteiro foi simplificada pelo uso de macro de (*(L->fNodeDataCmp)) para NodeDataCmp.

For ( ; slkCurr != NULL; slkPrev = slkCurr, slkCurr = slkCurr->next) {    iCompare = NodeDataCmp(slkPn->pdata, slkCurr->pdata);    if (iCompare <= 0)         break; }

fNodeDataCmp é o nome de um ponteiro para função em SLIST. L é um ponteiro para a estrutura SLIST que estamos acessando, portanto, L->fNodeDataCmp é o atual ponteiro de função. Para chamar a função se utiliza o símbolo * de referencia. Portanto, ao usar a macro NodeDataCmp(a, b), tem o efeito de chamar a função e passar os argumentos a e b. Todas as rotinas especificas da aplicação seguem esse modelo.

int NodeDataCmp(void *first, void *second) {     return (strcmp( ((pND) first)->pName, ((pND) second)->pName)); }

Atente que ao se adicionar um nó sem se preocupar em utilizar ordem ascendente, usa-se AddNodeAtHead().

Todas estas funções, com exceção da comparação, retornam 0 se algum erro acontece e 1 em caso de sucesso. AddNodeAscend(), que adiciona nó em ordem ascendente, encontra um nó com o valor igual, primeiro chama a função especifica da aplicação DuplicateNode() que deve decidir o que fazer.

iAction = DuplicatedNode(slkPn, slkCurr); if (iAction == 2) { }   else {   // if (iAction == 0 || iAction == 1)     LLHead = snDummy.next;     LLHead->prior = NULL;     if (iAction == 1) {         DeleteData(slkPn->pdata);         free(slkPn);     } }

Retorna então um dos três possíveis valores: 0 indicando erro, 1 para excluir o nó duplicado e 2 que manda adicionar o nó duplicado na lista.

int DuplicatedNode(SLINK slkNewNode, SLINK slkListNode) {     return (2); }

Devido a uma característica embutida ao dado, apagar um nó requer uma função especifica. Imagine que o dado do nó tenha um ponteiro para string, se apagarmos o nó usando free(), o ponteiro para string desaparece, mas a string continua alocada na memória ocupando espaço, como resultado para eliminar apropriadamente o nó, deve-se primeiro apagar os dados usando a rotina especifica fDeleteData() e então se pode liberar o nó.

BOOL  DeleteData(void *data) {     free( ((pND) data)->pName);     free( ( data );     return TRUE; }

O mesmo ocorre quando se cria o nó, não se pode simplesmente copia um ponteiro de dados, suponha novamente que o ponteiro direcione para um buffer que será reutilizado assim que nó estiver na lista.

slkNewNode->pdata = CreateData(data);

A função genérica não tem como saber se a permanência dos dados foi feita, como resultado ao se criar um nó, inclui outra rotina especifica fCreateNode. Esta rotina copia a string para a nova área e usa este endereço, como o endereço da string.

void *CreateData(void *data) {     SNODEDATA *pNewData;     pNewData = (SNODEDATA *) malloc(sizeof(SNODEDATA));     pNewData->pName = _strdup((char *) data);     if (pNewData->pName == NULL) {         free(pNewData);         return (NULL);     }     else         return (pNewData); }

Desta forma as rotinas genéricas conseguem manter a integridade evitando a persistência de dados não mais utilizados.

O código exemplo a ser utilizado irá criar duas listas encadeadas L1 e L2 a partir da leitura de nomes em um arquivo texto, a lista L1 será ordenada e L2 adicionará os nomes em sua ordem de leitura.

AddNodeAscend(L1, name));     AddNodeAtHead(L2, name));

Outra característica de L1 será não incluir nomes iguais e contar o numero de vezes em que um item repetido apareceu,  L2 irá inserir duplicadas, para tanto L1 deve incluir uma nova informação em seu nó, no caso o contador de duplicadas, o resultado da declaração segue abaixo.

typedef struct tagSNODEDATA1 {     char *pName;         //  ponteiros para palavras     unsigned int uCont;  // e a contagem de ocorrencias }SNODEDATA1; typedef struct tagSNODEDATA2 {     char *pName;         //  ponteiros para palavras }SNODEDATA2;

Ao optar por dois nós diferentes, precisa-se criar rotinas especificas para cada nó, assim a função DuplicateNode para L1 resulta no incremento do contador de palavras repetidas e retorna 1 para que o nó repetido não seja incluído na lista.

int   DuplicatedNode1(SLINK slkNewNode, SLINK slkListNode) {     pND1 pnd;     // altera o ponteiro de dados para da aplicacaoh     pnd = slkListNode->pdata;     // adiciona-se uma ocorrencia para a palavra existente     pnd->uCont += 1;     return 1; }

O arquivo lldriver.c detalha todas as operações que serão feitas com as duas listas, cria-se as estruturas de dados e inicia o processo de inserção de nomes através da leitura do arquivo.

fin = fopen(argv[1], "rt");     L1 = CreateLList(   CreateData1,                         DeleteData1,                         DuplicatedNode1,                         NodeDataCmp1);     L2 = CreateLList(   CreateData2,                         DeleteData2,                         DuplicatedNode2,                         NodeDataCmp2);     // comecah a processar o arquivo     while (fgets(name, 128, fin) != NULL) {         // adiciona a palavra em ambas as lista         AddNodeAscend(L1, name);         AddNodeAtHead(L2, name);     }     fclose(fin);

Encerrando a criação das listas, passam a realizar diversas operações em ambas as listas imprimindo o resultado na tela, no trecho abaixo a lista é percorrida tanto pelo inicio como pelo fim.

printf("L2 contem %u itens:\n", L2->uiCount); w1 = L2->slkHead; w2 = L2->slkTail; for (; w1 != NULL && w2 != NULL; w1 = w1->next,  w2 = w2->prior) {     printf(" %30s %30s\n", ((pND2) (w1->pdata))->pName,                            ((pND2) (w2->pdata))->pName); }

Uma da ultimas operações será a exclusão de nós, ao percorrer a lista vai excluindo um nó a cada dois que encontra.

count = 0; w1 = L1->slkHead; while (w1 != NULL) {     w3 = FindNode(L1, w1->pdata);     if (w3 != 0) {         printf("Encontrou noh %s", ((pND1) (w3->pdata))->pName);         ++count;         w1 = w3->next;         if (count & 1) {             DeleteNode(L1, w3);             printf(" e apagou o mesmo.");         }     }     else         w1 = NULL; }

 O código se encontra neste link, junto do arquivo lista.txt para ser usado em testes, digite na linha de comando no nome do executável gerado seguido pelo arquivo texto que contem os nomes. O resultado assemelha-se ao apresentado abaixo.

C:\Projects\LLGen\Debug>LLGen LISTA.TXT L1 contem 5 item(ns):  Bianca ocorre 1 vez(es).  Laura ocorre 1 vez(es).  Mariana ocorre 1 vez(es).  Roberto ocorre 1 vez(es).  Vanusa ocorre 1 vez(es). L2 contem 5 item(ns):  Mariana  Laura  Bianca  Roberto  Vanusa L2 contem 5 item(ns):                         Mariana                         Vanusa                           Laura                        Roberto                          Bianca                         Bianca                         Roberto                          Laura                          Vanusa                        Mariana Encontrou noh Mariana e apagou o mesmo. Encontrou noh Laura Encontrou noh Bianca e apagou o mesmo. Encontrou noh Roberto Encontrou noh Vanusa e apagou o mesmo. L2 contem 2 item(ns):                           Laura                        Roberto                         Roberto                          Laura Encontrou noh Bianca e apagou o mesmo. Encontrou noh Laura Encontrou noh Mariana e apagou o mesmo. Encontrou noh Roberto Encontrou noh Vanusa e apagou o mesmo. L1 contem 2 item(ns):                           Laura                        Roberto                         Roberto                          Laura

O arquivo de teste incluso tem uma quantidade maior de nomes do que o exemplificado acima, sua visualização no console ficará prejudicada pelo excesso de informação. Como sugestão para analise, o ideal é colocar a saída em um arquivo texto para visualização posterior.

Para não aumentar o tamanho e complexidade do programa gerenciando outro arquivo, acrescente ao final da linha de comando “ > log.txt”, que irá redirecionar a saída da tela para o arquivo indicado.

C:\Projects\LLGen\Debug>LLGen LISTA.TXT > log.txt

                               

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.