Fila de Prioridade

CÓDIGO-FONTE: https://github.com/r-bauer/prioQueue/archive/master.zip

Como explicado na postagem anterior(Fila Circular), um problema singular ocorre quando se cria um tipo de dado abstrato como a fila usando vetores, aonde inserir e remover elementos continuamente desloca os dados por  toda a memória, como solução utiliza-se um buffer circular, em um segundo caso quando criamos uma fila com lista encadeada, a mesma sofre de uma deficiência ligeiramente diferente em seu formato, continuar criando e apagando nós da lista, acabara por fragmentar a memória com as sucessivas operações de alocar e liberar.

No caso da fila com lista encadeada temos duas soluções para o problema:

1.       Usar funções próprias para alocar e devolver a memória, esta função iria alocar uma sequencia de nós que seriam usados e devolvidos.

2.       Criar uma lista encadeada de nós livres, conforme os itens foram inseridos, os nós são movidos da lista livre para a fileira, ao remover, os nós retornam para a lista livre.

Será utilizada a abordagem numero 2, as rotinas de lista encadeada a serem utilizadas, foram introduzidas anteriormente na postagem lista encadeada genérica parte 1 e parte 2. Para os arquivos de aplicação qapp.c e qapp.h, teremos a adaptação da lista ligada para uma fila, semelhante à forma com que se trabalhou com os arquivos llapp.c e llapp.h.

Uma lista ordenada será usada para representar a fila de prioridade, utilizando uma lista ordenada ascendente, implica numa alteração do processo de inserção, aonde abandonamos o FIFO (First In, First Out) para colocar o elemento na posição indicada para sua prioridade, a rotina insere fica responsável em manter a ordem enquanto a rotina remove mantém sua simplicidade ao remover o primeiro da fila, em termos de desempenho o processo de inserção requer uma media de aproximadamente n/2 nós para inserção e apenas um nó para eliminação.

typedef struct tagSNODEDATA {       char *pText;                 // ponteiro para um texto       unsigned int uiPriority;     // o nivel de prioridade }SNODEDATA;

A vantagem de uma lista sobre vetor para programar a fila de prioridade reside no fato de que não é necessário nenhum deslocamento de dados, um item pode ser inserido numa lista sem deslocar os demais, enquanto que a mesma operação num vetor fica impossível se não houver espaços vazios.

A estratégia para o programa se inicia com a criação de duas estruturas de lista encadeada slQueue e slFreeList no arquivo qdriver.c.

SLIST *slQueue, *slFreeList;     // configura a estrutura de lista ligada para filas     slQueue = CreateLList(  CreateData1,                             DeleteData1,                             DuplicatedNode,                             NodeDataCmp1 );     slFreeList = CreateLList(   CreateData2,                                 DeleteData2,                                 DuplicatedNode,                                 NodeDataCmp2 );

Antes de detalhar as rotinas especificas de cada lista, é importante ressaltar que toda a memória usada será criada pela lista livre e compartilhada pelas duas listas, o que resulta na criação de todos os nós pela lista livre no seguinte trecho.

for (iCount = 0; iCount < QMAX; ++iCount)     {         AddNodeAtHead(slFreeList, cRecord);     }

A consequência desta lógica acaba com as rotinas CreateData1 e DeleteData1 jamais sendo executadas no código, com suas declarações sendo vazias no arquivo qapp.c.

void *CreateData1(void *data) {     return (NULL); } BOOL  DeleteData1(void *data) {     return TRUE; }

O mesmo acontece para tratamento de elementos duplicados , apesar de incluir a rotina DuplicateNode, a mesma não é chamada por nenhuma das duas listas, mantendo sua declaração apenas com fim de compatibilidade, ambas as listas compartilham a mesma rotina.

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

A única operação especifica para a lista slQueue será a comparação dos nós através do valor de prioridade para posicionar na fila.

int   NodeDataCmp1(void *first, void *second) {     return (((pND)first)->uiPriority - ((pND)second)->uiPriority); }

Como a lista slFreeList fica responsável por gerar e apagar o nós, CreateData2 e DeleteData2 serão as únicas rotinas com a tarefa de alocar e liberar.

void *CreateData2(void *data) {     SNODEDATA *pNewData;     // aloca sua estrutura de dados     pNewData = (SNODEDATA *) malloc(sizeof(SNODEDATA));     // move os valores para a estrutura de dados     pNewData->uiPriority = 0;     pNewData->pText = (char *) malloc(TEXT_SIZE + 1);     *pNewData->pText = '\0';     return (pNewData);     // retorna o endereco da estrutura } BOOL  DeleteData2(void *data) {     // SNODEDATA consiste em: um ponteiro e um inteiro.     // Sendo nescessario liberar a string manualmente     free( ((pND) data)->pText);     // e somente agora libera SNODEDATA     free(  data );     return TRUE; }

Com a adaptação das rotinas especificas de lista encadeada para uso com a fila de prioridade, monta-se o controlador de fila, com as rotinas para inserir e remover elementos da fila.

Função	InsertQueue
Propósito	Armazenar um dado baseado em sua prioridade
Parâmetros	SLIST *slQueue - lista ligada usada para fila de prioridade SLIST *slFree - lista com as vagas livres a serem inseridas void *pNewEntry - a nova entrada a ser guardada na fila
Retorno	TRUE - dado armazenado FALSE - não foi possível armazenar o dado
Descrição	Enfileira os dados passados no inicio da lista livre, e depois adiciona o nó na lista baseada na prioridade.

BOOL InsertQueue(SLIST *slQueue, SLIST *slFree, void *pNewEntry) {     SLINK slkCurr, slkNewNode;     // existe algum noh livre na lista     if (slFree->uiCount == 0)         return (FALSE);     // usa como novo noh, o inicio da lista livre     slkNewNode = slFree->slkHead;     DataCopy(slkNewNode->pdata, pNewEntry);     // adiciona os dados numa lista vazia     if (slQueue->uiCount == 0)     {         // encontrou uma vaga, corrige a lista livre         // atualiza a o inicio da lista para o seguinte         slFree->slkHead = slFree->slkHead->next;         // ponteiros do noh = NULO por ser o primeira insercaoh         slkNewNode->prior = NULL;         slkNewNode->next = NULL;         // indica que o novo noh faz parte da lista de prioridade         slQueue->slkTail = slkNewNode;         slQueue->slkHead = slkNewNode;         slQueue->uiCount = 1;// inicia o contador da lista         --slFree->uiCount;   // retira uma vaga da lista livre         return (TRUE);     }     // jah existem dados na lista     else     {         //´percorre a lista para encontrar a posicaoh de insercaoh         for (slkCurr = slQueue->slkHead; ; slkCurr = slkCurr->next)         {             if ((slkCurr == NULL) || // se for fim da fila            // ou dentro dele            (slQueue->fNodeDataCmp(pNewEntry, slkCurr->pdata) < 0))             {                 // encontrou uma vaga, corrige a lista livre                 // atualiza a o inicio da lista para o seguinte                 slFree->slkHead = slFree->slkHead->next;                 // eh o fim da lista ?                 if (slkCurr == NULL) {                     // novo noh aponta para o fim da fila                     slkNewNode->prior = slQueue->slkTail;                       // naoh tem para quem apontar                     slkNewNode->next = NULL;                     // o seguinte do fim aponta para o novo noh                     slQueue->slkTail->next = slkNewNode;                        // indica o novo fim da lista                     slQueue->slkTail = slkNewNode;                 }                 else {                     // estah adicionando no inicio da lista ?                     if (slkCurr->prior == NULL)                         // atualiza o inicio da lista                         slQueue->slkHead = slkNewNode;                          // atualiza os ponteiro do novo noh                     slkNewNode->prior = slkCurr->prior;                           // colocando ele entre o atual e anterior                     slkNewNode->next = slkCurr;                                 // naoh estah adicionando no inicio                     if (slkCurr->prior != NULL)                         // anterior p/ referenciar o novo noh                         slkCurr->prior->next = slkNewNode;                       // ajusta o atual p/ referenciar o novo noh                     slkCurr->prior = slkNewNode;                 }                 // atualiza a contagem das lista                 // adiciona um noh na lista de prioridade                 ++slQueue->uiCount;                 // subtrai um noh da lista de livres                 --slFree->uiCount;                 return (TRUE);             }         }     } }

Função	RemoveQueue
Propósito	Retira o dado de uma fila
Parâmetros	SLIST *slQueue - lista ligada usada para fila de prioridade SLIST *slFree - lista com as vagas livres a serem inseridas  void *pOurData - o dado retirado da fila
Retorno	TRUE - recuperou a informação da fila FALSE - Fila vazia ou erro ao copiar dado para buffer
Descrição	Para remover, usa um ponteiro para o nó no inicio da fila. Move esse nó inicial retirado da fila e o insere na lista de nó livres. Obs.: Se não os dados não forem usados antes que se execute uma nova operação p/ enfileirar (insertQueue), os dados serão perdidos, portanto copie se for necessário.

BOOL RemoveQueue(SLIST *slQueue, SLIST *slFree, void *pOurData) {     SLINK slkRemove;     // existe algum dado p/ desinfilerar ?     if (slQueue->uiCount == 0)         return (FALSE);     // faz a copia dos dados desenfilerados     DataCopy(pOurData, slQueue->slkHead->pdata);     // salva a posicaoh do dado a ser retirado da fila     slkRemove = slQueue->slkHead;     // remove o noh da fila de prioridade     // atualizando o inicio p/ o seguinte da lista     slQueue->slkHead = slQueue->slkHead->next;          // se diferente de nulo, tem elemento armazenados na fila     if (slQueue->slkHead != NULL)         // eliminando a referencia de um previo         slQueue->slkHead->prior = NULL;              // se o inicio for nulo, fila foi esvaziada, atualiza o fim     else         // naoh existe dados armazenados         slQueue->slkTail = NULL;                    --slQueue->uiCount; // ajusta a contagem de itens na fila         // e adiciona no inicio da lista de livres     slkRemove->prior = NULL;          // aponta o anterior p/ NULO     // e o seguinte para o inicio da lista de livres     slkRemove->next = slFree->slkHead;     // e atualiza o inicio da lista de nohs livres     slFree->slkHead = slkRemove;          ++slFree->uiCount;  // avisa que tem + 1 noh livre     return (TRUE); }

Para testarmos o resultado, a função QDriver servirá de exemplo de tratamento para fila de prioridade, irá abrir para leitura um arquivo de dados consistindo em linhas de texto no formato X9MESSAGE, aonde:

X	I – para inserir na fila R – remover L – listar a fila
9	Prioridade do item da fila
MESSAGE	Texto a ser inserido

Obs.: A ações D e P não tem prioridade ou texto.

O arquivo texto com dados deverá ter o seguinte padrão:

I8Lacuna Coil I4Anthrax R L R I1Various I9White Zombie I2John Williams I4Killswitch Engage L I4Ayreon

O código simplificado de teste para abrir o arquivo e executar as ações que encontrar em cada linha segue abaixo.

fin = fopen(argv[1], "rt"); pTemp = CreateData2(NULL); while (fgets(cRecord, sizeof(cRecord) - 1, fin) != NULL) {       if (*cRecord == 'I')       {             ((pND) pTemp)->uiPriority = *(cRecord + 1) - '0';             ((pND) pTemp)->pText = cRecord + 2;             InsertQueue(slQueue, slFreeList, pTemp);       }       else if (*cRecord == 'R')       {             RemoveQueue(slQueue, slFreeList, pTemp);       }       else if (*cRecord == 'L')       {             SLINK slkCurr;             printf("\n- Fila -\n");             for ( slkCurr = slQueue->slkHead;                   slkCurr != NULL;                   slkCurr = slkCurr->next)             {                   printf("%d %s\n",                         ((pND) slkCurr->pdata)->uiPriority,                         ((pND) slkCurr->pdata)->pText);             }             printf("\n");       } } fclose(fin);

Os arquivos deste projeto se encontram no github: https://github.com/r-bauer/prioQueue, o arquivo prio.txt deve ser criado para ser usado no teste como indicado acima, ao rodar o programa terá como resultado: 

C:\Algorit\Projects\pqueue\Debug>pqueue PRIO.TXT         Enfilerou (1 Bryan Adams)         Enfilerou (4 KC and the Sunshine Band)         Desenfilerou (1 Bryan Adams) ----------- Fila ateh o momento ----------- 4 KC and the Sunshine Band         Enfilerou (2 Meat Loaf)         Enfilerou (1 R.E.M)         Enfilerou (9 Sugar Ray)         Desenfilerou (1 R.E.M)         Desenfilerou (2 Meat Loaf) ----------- Fila ateh o momento ----------- 4 KC and the Sunshine Band 9 Sugar Ray         Enfilerou (7 The Mission)         Enfilerou (4 Temple of the Dog)         Enfilerou (3 Pantera)         Enfilerou (1 Ministry)         Enfilerou (1 Kelly Clarkson)         Desenfilerou (1 Ministry)         Desenfilerou (1 Kelly Clarkson) ----------- Fila ateh o momento ----------- 3 Pantera 4 KC and the Sunshine Band 4 Temple of the Dog 7 The Mission 9 Sugar Ray

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.