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