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 inserçã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>
#include <ctype.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 {
menu();
printf( "Informe a opcao: " );
fflush( stdin );
fflush( stdout );
ch = getchar();
printf( "\n" );
switch( ch ) {
case '1':
printf( "Informe o nome: " );
scanf("%s",nome);
printf( "Informe o telefone: " );
scanf("%s",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!" );
fflush( stdin );
fflush( stdout );
getchar();
break;
case '2':
printf( "***** Lista de pessoas *****" );
imprime_lista( lista );
fflush( stdin );
fflush( stdout );
getchar();
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 );
}
fflush( stdin );
fflush( stdout );
getchar();
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..!" );
}
fflush( stdin );
fflush( stdout );
getchar();
break;
}
} while ( toupper( ch ) != '0' );
}
No exemplo acima, repare que há necessidade de inicializar 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.
Repare também que, assim como na aula de arquivos, foi necessário o uso da função fflush para limpar os buffers de entrada e saída padrões antes de cada leitura do teclado.
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!
