Alocação de Memória
Ao criar um programa em “C” usualmente temos que especificar as variáveis que vamos usar antes
de começar a executar o programa, reservando assim um espaço na memória.
As variáveis que são alocadas em posições fixas da memória são chamadas de variáveis estáticas, e as
de começar a executar o programa, reservando assim um espaço na memória.
As variáveis que são alocadas em posições fixas da memória são chamadas de variáveis estáticas, e as
variáveis que não possuem uma posição fixa e que são criadas e destruídas durante a execução
do programa são chamadas de variáveis dinâmicas.
A alocação de memória no computador pode ser dividida em dois grupos principais:
- Alocação Estática: os dados tem um tamanho fixo e estão organizados sequencialmente na memória do computador. Um exemplo típico de alocação estática são as variáveis globais, e os vetores (estáticos).
- Alocação Dinâmica: os dados não precisam ter um tamanho fixo, pois podemos definir para cada dado quanto de memória que desejamos usar. Sendo assim vamos alocar espaços de memória (blocos) que não precisam estar necessariamente organizados de maneira sequencial, podendo estar distribuídos de forma esparsa na memória do computador. Na alocação dinâmica, vamos pedir para alocar/desalocar blocos de memória, de acordo com a nossa necessidade, reservando ou liberando blocos de memória durante a execução de um programa. Para poder “achar” os blocos esparsos na memória usamos as variáveis do tipo Ponteiro (indicadores de endereços de memória). As variáveis locais e os parâmetros passados por valor são alocados dinamicamente.
Alocação Estática de Memória:
As estruturas de dados para armazenar um conjunto de dados (exemplo: um cadastro com
vários registros), podem ser organizadas de formas diferentes, de acordo com a maneira que os
dados são inseridos e retirados da memória do computador. As formas mais usuais são: as listas
lineares sequenciais (vetores simples), as filas, as pilhas e os deques.
Listas lineares sequenciais:
Uma maneira interessante de manipular este tipo de estruturas de dados, é através da
construção de um conjunto de rotinas genéricas e modulares de manipulação de listas seqüenciais.
Vamos aqui descrever uma possível proposta de um conjunto de rotinas empregadas para este fim.
Rotinas básicas de manipulação de Vetores:
- Estruturas de dados com alocação estática
- Inserção no final do vetor
- Remoção lógica dos elementos
Aplicação típica:
- Pequenos cadastros
Estrutura de dados:
typedef int Tipo_Dado;typedef struct {
Tipo_Dado Dado [MAX_VETOR];
int Excluido [MAX_VETOR];
int Inicio, Fim;
} Tipo_Vetor;
Rotinas:
void inicializa_vetor (Tipo_Vetor *V);
int insere_vetor (Tipo_Vetor *V; Tipo_Dado Dado);
int consulta_vetor (Tipo_Vetor V; int Indice; Tipo_Dado *Dado);
int acha_vetor (Tipo_Vetor V; Tipo_Dado Dado; int *Indice);
void lista_vetor (Tipo_Vetor V);
int exclui_vetor (Tipo_Vetor *V; int Indice);
int atualiza_vetor (Tipo_Vetor *V; int Indice; Tipo_Dado Novo_Dado);
void compacta_vetor (Tipo_Vetor *V);
int vazio_vetor (Tipo_Vetor V);
int quantidade_vetor (Tipo_Vetor V);
Exemplo: inserção de dados no vetor
int insere_vetor (V, Dado)
Tipo_Vetor *V;
Tipo_Dado Dado;
{
if (V->Fim < MAX_VETOR) /* Vetor nao esta cheio ? */
{
V->Dado[V->Fim]=Dado;
V->Excluido[V->Fim]=FALSO;
(V->Fim)++;
return(OK);
}
else
return(ERRO);
}
Filas – FIFO = “First In, First Out”:
Construção de um conjunto de rotinas genéricas e modulares de manipulação de filas.
Vamos aqui descrever uma possível proposta de um conjunto de rotinas empregadas para este fim.
Rotinas básicas de manipulação de FILAS usando vetores:
- Estruturas de dados com alocação estática
- Inserção no final da fila
- Remoção do início da fila
- Fila circular
Aplicação típica:
- Lista de elementos a espera de um tratamento
Estrutura de dados:
typedef int Tipo_Dado;
typedef struct {
Tipo_Dado Dado [MAX_FILA];
int Inicio, Fim;
} Tipo_Fila;
Rotinas:
void inicializa_fila (Tipo_Fila *F);
int insere_fila (Tipo_Fila *F; Tipo_Dado Dado);
int retira_fila (Tipo_Fila *F; Tipo_Dado *Dado);
void lista_fila (Tipo_Fila F);
int consulta_fila (Tipo_Fila F; int Indice; Tipo_Dado *Dado);
int cheia_fila (Tipo_Fila F);
int vazia_fila (Tipo_Fila F);
int quantidade_fila (Tipo_Fila F);
int acha_fila (Tipo_Fila F; Tipo_Dado Dado; int *Indice);
Exemplo: inserção de dados na fila
int insere_fila (F, Dado)
Tipo_Fila *F;
Tipo_Dado Dado;
{
int prox;
prox=F->Fim+1;
if (prox == MAX_FILA)
prox=0;
if (prox == F->Inicio)
return(ERRO);
else
{
F->Dado[F->Fim]=Dado;
F->Fim=prox;
return(OK);
}
}
Pilhas – LIFO = “Last In, First Out”:
Construção de um conjunto de rotinas genéricas e modulares de manipulação de pilhas.
Vamos aqui descrever uma possível proposta de um conjunto de rotinas empregadas para este fim.
Rotinas básicas de manipulação de PILHAS usando vetores:
- Estruturas de dados com alocação estática
- Inserção no topo da pilha
- Remoção do topo da pilha
Aplicação típica:
- Lista de “tarefas pendentes”, passagem de parâmetros nas linguagens de programação
Estrutura de dados:
typedef int Tipo_Dado;
typedef struct {
Tipo_Dado Dado [MAX_PILHA];
int Base, Topo;
} Tipo_Pilha;
Rotinas:
void inicializa_pilha (Tipo_Pilha *P);
int insere_pilha (Tipo_Pilha *P; Tipo_Dado Dado);
int retira_pilha (Tipo_Pilha *P; Tipo_Dado *Dado);
void exibe_pilha (Tipo_Pilha P);
int quantidade_pilha (Tipo_Pilha P);
int cheia_pilha (Tipo_Pilha P);
int vazia_pilha (Tipo_Pilha P);
void esvazia_pilha (Tipo_Pilha *P);
Exemplo: inserção de dados na pilha
int insere_vetor (P, Dado)
Tipo_Vetor *P;
Tipo_Dado Dado;
{
if (V->Fim < MAX_VETOR)
{
P->Dado[P->Fim]=Dado;
P->Excluido[P->Fim]=FALSO;
(P->Fim)++;
return(OK);
}
else
return(ERRO);
}
Deque – “Double Ended Queue”:
Construção de um conjunto de rotinas genéricas e modulares de manipulação de deques.
Vamos aqui descrever uma possível proposta de um conjunto de rotinas empregadas para este fim.
Rotinas básicas de manipulação de DEQUES usando vetores:
- Estruturas de dados com alocação estática
- Inserção no início ou no final do deque
- Remoção do início ou do final do deque
- Estrutura de dados “circular”
Aplicação típica:
- Lista de elementos com múltiplas formas de considerar/manipular a ordem destes
Estrutura de dados:
typedef int Tipo_Dado;
typedef struct {
Tipo_Dado Dado [MAX_DEQUE];
int Inicio, Fim;
} Tipo_Deque;
Rotinas:
void inicializa_deque (Tipo_Deque *D);
int insere_inicio_deque (Tipo_Deque *D; Tipo_Dado Dado);
int insere_final_deque (Tipo_Deque *D, Tipo_Dado Dado);
int retira_inicio_deque (Tipo_Deque *D; Tipo_Dado *Dado);
int retira_final_deque (Tipo_Deque *D; Tipo_Dado *Dado);
void lista_deque (Tipo_Deque D);
int acha_deque (Tipo_Deque D; Tipo_Dado Dado; int *Indice);
int cheio_deque (Tipo_Deque D);
int vazio_deque (Tipo_Deque D);
int quantidade_deque (Tipo_Deque D);
void apaga_deque (Tipo_Deque *D);
Alocação de Dinâmica de Memória:
As principais características da alocação dinâmica de memória são:
- Os dados se encontram espalhados na memória do computador em vários blocos;
- Geralmente as estruturas de dados são compostas por registros que incluem um campo
do tipo ponteiro (elo/link), o que nos permite encadear os dados e indicar onde está o
dado seguinte na memória (visto que os dados estão espalhados na memória do
computador);
- Podemos ir solicitando mais e mais memória a medida em que precisarmos de mais
espaço para armazenar as informações. Isso nos permite criar programas que usam
apenas a memória necessária... e por conseqüência, podemos rodar outros programas,
em uma mesma máquina, sem que um único programa monopolize toda a memória
disponível desta.
- Podemos liberar espaços de memória quando estes não forem mais necessários ao
programa.
Estas estruturas criadas com registros que são encadeados através do uso de ponteiros, que
estes blocos espalhados pela memória, vão resultar em estruturas denominadas de “listas
encadeadas” de alocação dinâmica. A figura abaixo mostra um exemplo de lista encadeada,
baseada na estrutura de dados descrita logo mais abaixo:
Listas encadeadas simples:
Construção de um conjunto de rotinas genéricas e modulares de manipulação de listas
encadeadas simples. Vamos aqui descrever uma possível proposta de um conjunto de rotinas
empregadas para este fim.
Rotinas básicas de manipulação de listas encadeadas simples:
- Estruturas de dados com alocação dinâmica
- Inserção no inicio da lista, no final da lista, ou de modo ordenado
- Remoção de qualquer elemento da lista (início, final, ou elemento especificado)
Aplicação típica:
- Lista de elementos de tamanho variável
Estrutura de dados:
typedef int Tipo_Dado;
typedef struct bloco {
Tipo_Dado Dado;
struct bloco *Proximo;
} Nodo;
Rotinas:
void inicializa_lista (Nodo **N);
int insere_inicio_lista (Nodo **N, Tipo_Dado Dado);
int insere_fim_lista (Nodo **N, Tipo_Dado Dado);
int insere_ordenando_lista (Nodo **N, Tipo_Dado Dado);
int remove_inicio_lista (Nodo **N, Tipo_Dado *Dado);
int remove_fim_lista (Nodo **N, Tipo_Dado *Dado);
int remove_elemento_lista (Nodo **N, Tipo_Dado Dado);
int quantidade_lista (Nodo *N);
void exibe_lista (Nodo *N);
int pesquisa_lista (Nodo **N, Tipo_Dado Dado);
int percorre_lista (Nodo **N, Tipo_Dado *Dado);
void apaga_lista (Nodo **N);
Exemplo: inserção de dados no inicio da lista encadeada
int insere_inicio_lista (N, Dado)
Nodo **N;
Tipo_Dado Dado;
{
Nodo *novo;
novo = (Nodo *) calloc ( 1, sizeof (Nodo) );
if ( novo == NULL )
return (ERRO); /* Não conseguiu alocar espaço na memória */
novo -> Dado = Dado;
novo -> Proximo = *N;
*N = novo;
return (OK);
}
Exemplo: inserção de dados no final da lista encadeada
int insere_fim_lista (N, Dado)
Nodo **N;
Tipo_Dado Dado;
{
Nodo *aux, *novo;
novo = (Nodo *) calloc ( 1, sizeof (Nodo) );
if ( novo == NULL )
return(ERRO);
novo -> Dado = Dado;
novo -> Proximo = NULL;
if ( *N == NULL )
*N = novo;
else {
aux = *N;
while ( aux -> Proximo != NULL )
aux = aux -> Proximo;
aux -> Proximo = novo;
}
return (OK)
}
Listas duplamente encadeadas
Construção de um conjunto de rotinas genéricas e modulares de manipulação de listas
duplamente encadeadas. Vamos aqui descrever uma possível proposta de um conjunto de rotinas
empregadas para este fim.
Rotinas básicas de manipulação de listas duplamente encadeadas:
- Estruturas de dados com alocação dinâmica
- Inserção no inicio da lista, no final da lista, ou de modo ordenado
- Remoção de qualquer elemento da lista (início, final, ou elemento especificado)
Aplicação típica:
- Lista de elementos de tamanho variável, permite percorrer a lista nos dois sentidos
Estrutura de dados:
typedef int Tipo_Dado;
typedef struct bloco_ld {
Tipo_Dado Dado;
struct bloco_ld *Proximo, *Anterior;
} Nodo_LD;
Rotinas:
void inicializa_ld (Nodo_LD **LD);
void posiciona_inicio_ld (Nodo_LD **LD);
void posiciona_fim_ld (Nodo_LD **LD);
int insere_antes_ld (Nodo_LD **LD, Tipo_Dado Dado);
int insere_depois_ld (Nodo_LD **LD, Tipo_Dado Dado);
int insere_inicio_ld (Nodo_LD **LD, Tipo_Dado Dado);
int insere_fim_ld (Nodo_LD **LD, Tipo_Dado Dado);
int insere_ordenando_ld (Nodo_LD **LD, Tipo_Dado Dado);
int pesquisa_ld (Nodo_LD **LD, Tipo_Dado Dado);
int remove_nodo_ld (Nodo_LD **LD, Tipo_Dado *Dado);
int remove_dado_ld (Nodo_LD **LD, Tipo_Dado *Dado);
int quantidade_ld (Nodo_LD *LD);
void exibe_ld (Nodo_LD *LD);
int percorre_lista (Nodo_LD **LD, Tipo_Dado *Dado);
void apaga_ld (Nodo_LD **LD);
Exemplo: posiciona o ponteiro no início da lista duplamente encadeada
void posiciona_inicio_ld (LD)
Nodo_LD **LD;
{
if ( *LD != NULL )
{
while ( (*LD) -> Anterior != NULL )
*LD = (*LD) -> Anterior;
}
}
Exemplo: inserção de dados antes da posição apontada na lista duplamente encadeada
int insere_antes_ld (LD, Dado)
Nodo_LD **LD;
Tipo_Dado Dado;
{
Nodo_LD *novo, *aux;
novo = (Nodo_LD *) calloc ( 1, sizeof (Nodo_LD) );
if ( novo == NULL )
return (ERRO);
novo -> Dado = Dado;
if ( *LD == NULL )
{
*LD = novo;
novo -> Anterior = NULL;
novo -> Proximo = NULL;
}
else
{
aux = (*LD) -> Anterior;
(*LD) -> Anterior = novo;
novo -> Proximo = (*LD)
novo -> Anterior = aux;
if ( aux != NULL )
aux -> Proximo = novo;
}
return (OK);
}
Exemplo: inserção de dados no início da lista duplamente encadeada
int insere_inicio_ld (LD, Dado)
Nodo_LD **LD;
Tipo_Dado Dado;
{
posiciona_inicio_ld(LD);
return ( insere_antes_ld (LD, Dado) );
}
Filas, Pilhas, Deques e Ordenação usando alocação dinâmica:
As filas, pilhas e deques podem ser facilmente implementadas usando rotinas genéricas de
manipulação de listas, sejam estas simples ou duplamente encadeadas. Uma vez que podemos
implementar facilmente rotinas de inserção no início e/ou no fim de uma lista encadeada, e também
podemos implementar facilmente rotinas de remoção do início e/ou do fim de uma lista encadeada
com alocação dinâmica, por conseqüência, podemos criar rotinas de manipulação destas outras
estruturas de dados baseadas nas rotinas descritas anteriormente. É importante salientar que em
alguns casos talvez seja interessante criar rotinas mais otimizadas, como por exemplo, na inserção
de nodos no final de uma lista. Neste caso, seria interessante que fosse evitada a necessidade de
percorrer toda a lista até encontrar o nodo final, cada vez que um novo nodo fosse adicionado no
final desta lista.
Filas:
- Insere no início
- Retira do fim
Pilhas:
- Insere no fim
- Retira do fim
Deques:
- Insere no início ou no fim
- Retira do início ou do fim
Ordenação:
- A inserção pode ser feita em qualquer posição, o que facilita a ordenação
Caso queiram ter uma menor abstração e aprimorar os conceitos do conteúdo abordado neste post, recomendo os videos abaixo:
Nenhum comentário:
Postar um comentário