Ponteiros de memória

Quando precisamos manipular uma lista de variáveis, utilizamos o array. No entanto, se declaramos um array de 100 posições e apenas 5 forem utilizadas, 95 posições na memória foram alocadas sem necessidade. Para resolver esse problema, a linguagem C permite a alocação dinâmica de memória que permite que a memória para as variáveis seja alocada conforme necessário.

Para alocação dinâmica de memória, é necessário criar variáveis de referência com um * conforme o exemplo abaixo:


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

int main() {
    int *num;
    
    num = malloc( sizeof( int ) );  
    *num = 10;
    
    printf( "Numero= %d", *num );
    return 0;
}

No exemplo acima, foi criada uma variável ponteiro no início do programa principal e, logo depois, a função malloc foi chamada para alocar memória dinamicamente para armazenar um valor inteiro. Repare que foi passada para a função malloc o resultado de outra função: a função sizeof que retorna a quantidade de bytes necessários para armazenar um valor de um determinado tipo de variável. Ex: sizeof( int ) retorna a quantidade de memória necessária para armazenar um número inteiro. A função malloc recebe a quantidade de bytes a serem alocados dinamicamente e depende da inclusão da biblioteca stdlib.h. Repare que para utilizar o conteúdo da variávei ponteiro é necessario um asterisco antes dela. Veja o exemplo abaixo:


#include <stdio.h>

int main() {
    int *num;
    
    *num = 10; // Isso gera um comportamento estranho
               // porque nao foi alocada memoria para 
               // esta variavel ponteiro.
               // eh necessario utilizar a funcao malloc 
               // ou calloc primeiro
    
    return 0;
}

Lista encadeada

Através de ponteiros de memória, é possível criar uma lista em que a memória vai sendo alocada conforme a lista cresce. Para tanto, cada elemento da lista tem que ter uma referência (Ponteiro de memória) para o próximo elemento da lista. Isso tras uma desvantágem da lista encadeada, em comparação com vetores. Cada elemento da lista encadeada precisa de memória para armazenar o endereço de memória do próximo elemento. Isso significa que, por exemplo, uma lista encadeada de 3 elementos gasta mais memória que um array de 3 elementos. Abaixo um exemplo de estrutura que permite encadear elementos em uma lista:


typedef struct st_numero {
    int num;
    struct st_numero *prox;
} numero;

Repare na estrutura acima que é criada uma variável prox que é uma referência a próxima posição de memória. Ou seja, para manipulação de uma lista encadeada, é necessário que cada elemento da lista, tenha uma referência que aponta para o próximo elemento. Para utilizar a variável num da estrutura é necessário fazer conforme abaixo:


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

typedef struct st_numero {
    int num;
    struct snum *prox;
} numero;

int main() {
    numero *p;
    p = malloc( sizeof( numero ) );
    
    (*p).num = 10;             
    
    printf( "Numero= %d", (*p).num );   
    
    return 0;
}

Perceba que p é do tipo ponteiro mas, *p e (*p) são do tipo estrutura (numero) e (*p).num é do tipo inteiro (int). Inclusive, (*p).num é o mesmo que p->num mas, para essa aula, vou utilizar apenas a primeira notação.

A tabela abaixo é uma representação de uma lista encadeada de números:

Endereço de memória	Número	Próximo
001	4	003
003	2	004
004	7	006
006	10	NULL

Perceba na tabela acima que quanto não há nenhum elemento a ser referenciado como próximo, a variável proximo recebe NULL.

Abaixo uma estrutura (struct) de pessoa para uma lista encadeada:


typedef struct st_pessoa {
    int id;
    char nome[100];
    char tel[100];
    int idade;
    float altura;
    struct st_pessoa *prox;
} pessoa;

Preste atenção na variável prox da estrutura acima. Ela é do tipo struct st_pessoa* e, para implementação de uma lista encadeada, é necessário que esta variável referencie o próximo elemento (tipo pessoa) da lista. Em um registro que é o ultimo da lista, a variável prox deve ser igual a NULL.

Abaixo um exemplo de função para inserir na lista simplesmente encadeada:


void insere( pessoa **lista, int id, char nome[], 
                             char tel[], int idade, float altura ) {
    pessoa *novo, *perc;
    novo = malloc( sizeof( pessoa ) );
    (*novo).id = id;
    strcpy( (*novo).nome, nome );
    strcpy( (*novo).tel, tel );
    (*novo).idade = idade;
    (*novo).altura = altura;
    (*novo).prox = NULL;
    
    if ( *lista == NULL ) {
        *lista = novo;
    } else {
        perc = *lista;
        while( (*perc).prox != NULL )
            perc = (*perc).prox;
        (*perc).prox = novo;
    }
}

Na função acima, a variável novo é o ponteiro do elemento a ser inserido na lista. A função malloc é chamada e é alocada memória para o ponteiro novo. Após isso, os dados da pessoa são carregados no registro apontado por novo (perceba que, inicialmente, todo registro inserido na lista tem a variável prox igual a NULL. Logo depois vem a varificação. Se o conteúdo apontado por **lista (que é acessado via *lista) for igual a NULL, significa que não tem nenhum registro inserido na lista e, então, a variável *lista deve apontar para a variável novo que, nesse caso passa a ser o único elemento da lista. caso a lista não esteja vasia, então a variável perc é posicionada no ultimo registro da lista para, então, fazer sua variável prox apontar para o novo registro (referenciado pela variável novo). Ou seja: (*perc).prox = novo.

Abaixo uma função para imprimir os elementos da lista encadeada:


void imprime_lista( pessoa *lista ) {
    pessoa *perc = lista;
    while( perc != NULL ) {
        printf( "\n" );
        printf( "\nPessoa ID(%d)", (*p).id );
        printf( "\n  Nome= %s", (*p).nome );
        printf( "\n  Telefone= %s", (*p).tel );
        printf( "\n  Idade= %d", (*p).idade );
        printf( "\n  Altura= %.2f", (*p).altura );
                
        perc = (*perc).prox;
    }
}

A função acima é mais simples que a função de insersão na lista encadeada. Na função imprime_lista acima, uma variável apontador perc é declarada e inicializada com a variável lista, passando assim a apontar para o mesmo endereço de memória que lista. Logo após, vem um laço cuja condição de parada é perc == NULL, ou seja, enquanto perc for diferente de NULL, o registro de pessoa apontado pelo ponteiro perc é impresso na tela e perc passa a apontar para o próximo registro da lista.

Abaixo, uma função para buscar um registro de pessoa por ID:


pessoa* busca( pessoa *lista, int id ) {
    pessoa *perc = lista;
    
    while( perc != NULL ) {
        if ( (*perc).id == id )
            return perc;    
        
        perc = (*perc).prox;        
    }
    
    return NULL;
}

No exemplo acima, a cada iteração do laço while é verificado se o registro atual apontado por perc tem ID igual ao ID buscado. Se sim, o apontador do registro é retornado pela função, se não, perc passa a apontar para o próximo registro da lista até que o ID seja encontrado ou o valor perc receba valor NULL.

Abaixo um exemplo de exclusão da lista por ID:


...

typedef int boolean;

...

boolean deleta( pessoa** lista, int id ) {
    pessoa *aux = *lista;
    pessoa *ant = *lista;
    boolean achou = FALSE;
    
    while( !achou && aux != NULL ) {
        if ( (*aux).id == id ) {
            achou = TRUE;
        } else {
            ant = aux;
            aux = (*aux).prox;
        }
    }
    
    if ( achou ) {
        if ( aux == *lista ) {      
            *lista = (*aux).prox;
        } else {        
            (*ant).prox = (*aux).prox;
        }
        free( aux );        
    }
    
    return achou;
}

No exemplo acima, uma busca é feita pelo ID passado como parâmetro. Caso exista algum registro com o ID buscado, a variável aux é apontada para esse registro e a variável ant é apontada para o registro anterior. Feito isso, se o registro foi encontrado, então a função remove-o da lista encadeada. Para tanto, é necessário verificar se o registro a ser removido é o primeiro da lista. Se sim, então a variável lista deve apontar para o próximo do registro a ser excluido e, caso contrário, a variável próximo do registro anterior (apontado por ant) recebe o próximo do registro encontrado (apontado por aux). Depois disso, o registro é removido com uso da função free.

Abaixo o exemplo agenda com ponteiros e alocação dinâmica de memória com as funções já mostradas:


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

#define TRUE 1
#define FALSE 0

typedef int boolean;

typedef struct spessoa {
    int id;
    char nome[100];
    char tel[100];
    int idade;
    float altura;
    struct spessoa *prox;
} pessoa;

void insere( pessoa **lista, int id, char nome[], 
                             char tel[], int idade, float altura ) {
    pessoa *novo, *perc;
    novo = malloc( sizeof( pessoa ) );
    (*novo).id = id;
    strcpy( (*novo).nome, nome );
    strcpy( (*novo).tel, tel );
    (*novo).idade = idade;
    (*novo).altura = altura;
    (*novo).prox = NULL;
    
    if ( *lista == NULL ) {
        *lista = novo;
    } else {
        perc = *lista;
        while( (*perc).prox != NULL )
            perc = (*perc).prox;
        (*perc).prox = novo;
    }
}

void imprime_pessoa( pessoa *p ) {    
    printf( "\nPessoa ID(%d)", (*p).id );
    printf( "\n  Nome= %s", (*p).nome );
    printf( "\n  Telefone= %s", (*p).tel );
    printf( "\n  Idade= %d", (*p).idade );
    printf( "\n  Altura= %.2f", (*p).altura );
}

void imprime_lista( pessoa *lista ) {
    pessoa *perc = lista;
    while( perc != NULL ) {
        printf( "\n" );
        imprime_pessoa( perc );
                
        perc = (*perc).prox;
    }
}

pessoa* busca( pessoa *lista, int id ) {
    pessoa *perc = lista;
    
    while( perc != NULL ) {
        if ( (*perc).id == id )
            return perc;    
        
        perc = (*perc).prox;        
    }
    
    return NULL;
}

boolean deleta( pessoa** lista, int id ) {
    pessoa *aux = *lista;
    pessoa *ant = *lista;
    boolean achou = FALSE;
    
    while( !achou && aux != NULL ) {
        if ( (*aux).id == id ) {
            achou = TRUE;
        } else {
            ant = aux;
            aux = (*aux).prox;
        }
    }
    
    if ( achou ) {
        if ( aux == *lista ) {        
            *lista = (*aux).prox;
        } else {        
            (*ant).prox = (*aux).prox;
        }
        free( aux );        
    }
    
    return achou;
}

void menu() {
    system( "cls" );
    printf( "*** Agenda ***" );
    printf( "\n 1 - Inserir" );
    printf( "\n 2 - Listar" );
    printf( "\n 3 - Buscar" );
    printf( "\n 4 - Remover" );
    printf( "\n 0 - Sair" );
    printf( "\n**************" );
    printf( "\n\n" );
}

int main() {
    pessoa *lista = NULL;
    pessoa *p = NULL;
    int tam = 0;
    int id;
    char nome[100];
    char telefone[100];
    int idade;
    float altura;
    char ch = '\0';
    
    do {
        fflush( stdin );
        
        menu();
        ch = getch();
        switch( ch ) {
            case '1':
                printf( "Informe o nome: " );
                gets(nome);
                printf( "Informe o telefone: " );
                gets(telefone);
                printf( "Informe a idade: " );
                scanf("%d",&idade);
                printf( "Informe a altura: " );
                scanf("%f",&altura);
                
                insere( &lista, ++tam, nome, telefone, idade, altura );
                
                printf( "\nPessoa inserida com sucesso!" );
                getch();                
                break;
            case '2':
                printf( "***** Lista de pessoas *****" );
                imprime_lista( lista );
                getch();
                break;
            case '3':
                printf( "Informe o ID: " );
                scanf("%d",&id);
                
                p = busca( lista, id );
                
                if ( p == NULL ) {
                    printf( "\nPessoa nao encontrada..!" );
                } else {                
                    printf( "\n" );
                    imprime_pessoa( p );
                }
                getch();
                break;
            case '4':
                printf( "Informe o ID: " );
                scanf("%d",&id);
                
                boolean removeu = deleta( &lista, id );                
                if ( removeu ) {
                    printf( "\nPessoa removida com sucesso...!" );
                } else {
                    printf( "\nPessoa nao encontrada..!" );
                }
                getch();                
                break;
        }
    } while ( toupper( ch ) != '0' );  
}

No exemplo acima, repare que há necessidade de inicialisar a variável lista com NULL. Isso por causa da função insere que verifica se a lista passada como parâmetro aponta para NULL.

E assim chegamos ao final deste curso de programação em C. No futuro pretendo produzir um curso em Java, onde, parte do que foi estudado nesse curso, facilitará muito o aprendizado da linguagem Java. Isso porque as duas linguagens têm muito em comum, já que a linguagem Java é derivada da linguagem C++ que é derivada da linguagem C.

Volte sempre e até a próxima!

Italo Info

Lista encadeada