Como prometido volto a falar de alocação de memória, em meu último post mencionei alocação estática e dinâmica de memória, e detalhei a alocação estática, agora vamos entrar em mais detalhes sobre a alocação 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 o vídeo abaixo:
Estrutura de dados - Alocação dinâmica de memória
"O conhecimento é uma sede insaciável, quanto mais bebemos, mais sede sentimos."
Eduardo Colamego.
Nenhum comentário:
Postar um comentário