self-referential structures

Autor: VoidPointer (Diego Rocha)

self-referential structures são estruturas que contém um ponteiro para uma estrutura do mesmo tipo, exemplo:


  struct words {
        char word[100];
        struct words *next;
    };

Repare que o *next é um ponteiro para uma estrutura do mesmo tipo que words, e isso é totalmente válido em C, essa técnica é muito útil para armazenar sequências de dados, como listas, queues, stacks e arvores de dados por exemplo, vamos supor que você queira criar uma lista de palavras, primeiro precisamos de uma estrutura que aponte para uma estrutura do mesmo tipo (no nosso caso a struct words), para assim criar a sequência de dados, e precisaremos também de algumas funções para manipular essa estrutura, vamos criar uma função para adicionar palavras no final dessa estrutura, a função seria basicamente assim:

    struct words *add_word( struct words *w, char *word )
    {
        /* verificamos se a estrutura esta livre para receber uma palavra */
        if (w == NULL) {
            w = (struct words*)malloc(sizeof(struct words)); //alocamos memoria para a estrutura
            if (w == NULL)
                return NULL; //problema ao alocar memoria

            (void)strlcpy(w->word, word, sizeof(w->word)); //copiamos word para w->word
            w->next = NULL;
        }else
            w->next = add_word(w->next, word); //chamada recursiva
        return w; //retornamos w
    }

Repare que usamos uma função recursiva para “caminhar” pela estrutura ate o ponto livre para receber uma palavra, agora vamos fazer uma função para imprimir todas as palavras da lista, poderíamos usar recursao também, mais vou usar outro metódo para fazer isso, vou usar o for para “caminhar” pela estrutura,




    void printf_words( struct words *w )
    {
        struct words *pw; //criamos um ponteiro do tipo words para apontar para w
        for( pw = w; pw != NULL; pw = pw->next ) //"caminhamos" pela estrutura w
            (void)fprintf( stdout, "%s\n", pw->word ); //imprimos a palavra
        fflush( stdout );
        return;
    }

bom agora criamos o main e testamos,




  int main( int argc, char *argv[] )
    {
        struct words *glb_w = NULL;//estrutura principal
        /* adicionamos palavras a lista */
        glb_w = add_word( glb_w, "teste1" );
        glb_w = add_word( glb_w, "teste2" );
        glb_w = add_word( glb_w, "teste3" );
        glb_w = add_word( glb_w, "teste4" );
        glb_w = add_word( glb_w, "teste5" );
        /* imprimimos as palavras */
        printf_words( glb_w );
        return 0;
    }

e compilamos com gcc -Wall words.c -o words agora executamos com ./words

[diego@blackbird ~]$ ./words
teste1
teste2
teste3
teste4
teste5

codigo completo:




#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    struct words {
        char word[100];
        struct words *next;
    };

    struct words *add_word( struct words *w, char *word )
    {
        if( w == NULL ) /* verificamos se a estrutura esta livre para receber uma palavra */
        {
            w = (struct words*)malloc(sizeof(struct words)); //alocamos memoria para a estrutura
            if( w == NULL )
                return NULL; //problema ao alocar memoria
            (void)strlcpy(w->word, word, sizeof(w->word)); //copiamos word para w->word
            w->next = NULL; //w->next aponta para nada
        }else
            w->next = add_word( w->next, word ); //chamada recursiva
        return w; //retornamos w
    }

    void printf_words( struct words *w )
    {
        struct words *pw; //criamos um ponteiro do tipo words para apontar para w
        for( pw = w; pw != NULL; pw = pw->next ) //"caminhamos" pela estrutura w
            (void)fprintf( stdout, "%s\n", pw->word ); //imprimos a palavra
        fflush( stdout );
        return;
    }

    int main( int argc, char *argv[] )
    {
        struct words *glb_w = NULL;//estrutura principal
        /* adicionamos palavras a estrutura */
        glb_w = add_word( glb_w, "teste1" );
        glb_w = add_word( glb_w, "teste2" );
        glb_w = add_word( glb_w, "teste3" );
        glb_w = add_word( glb_w, "teste4" );
        glb_w = add_word( glb_w, "teste5" );
        /* imprimimos as palavras */
        printf_words( glb_w );
        return 0;
    }

Pelo nosso amigo voidpointer artigo original –> http://blue.kracknet.net/~voidpointer/articles/self_referential_struct.html
encontre voidpointer no servidor do IRC irc.freenode.net no canal openbsd-br…