POnteiros

20/02/2014

Algoritmos e Estrutura de Dados
Aula 6 – Listas

Uso de Arrays para outras estrutura de dados
Vantagem:
1. São mais simples de implementar
2. São mais fáceis de compreender e manipular
Desvantagens:
1. Possuem limitação quanto à quantidade de elementos 2. Pode ou não ser totalmente populado
3. Pode haver necessidade de mais espaço
4. As operações de inserção e retirada tornam-se caras Característica:
1. Os elementos são armazenados a uma distância fixa de memória entre eles.

1

20/02/2014

Listas
Características:
1. Utilizam posições descontinuadas da RAM
2. Precisam de um link para o endereço da próxima posição
3. Tornam mais baratas as operações de inserção e retirada
4. Dispensam o cálculo de endereços.
Tipos:
1. Simplesmente encadeadas: apenas um ponteiro para o sucessor 2. Duplamente encadeadas: um apontador para o antecessor e outro para o sucessor
3. Ordenadas: a inserção deve garantir que a ordem da lista será mantida
4. Circulares: apontador próximo do último aponta para o primeiro e o anterior do primeiro aponta para o último.

Listas Simples

2

20/02/2014

Listas Simples

Alocação Dinâmica de Memória
• incluir a biblioteca standard do C: stdlib.h e stdio. h (malloc() e free())
• possibilidade de libertar memória à medida que deixa de ser precisa
• a função malloc permite alocar blocos de memória em tempo de execução void * malloc( size_t );

número de bytes alocados

/* retorna um ponteiro void para n bytes de memória não iniciados. Se não há memória disponível malloc retorna NULL
*/

3

20/02/2014

Alocação Dinâmica de Memória
• A função malloc() (memory allocation)
• reserva uma porção de memória, retornando um apontador genérico (tipo void *) para o ínicio da porção reservada, ou o valor NULL no caso da reserva ser impossível
• A sua utilização é representada no exemplo seguinte com uso da técnica de casting: int *pi; pi= (int *) malloc (sizeof(int));
/*