Estruturas de Dados Dinâmicas
CAP Diogo Silva
Academia da Força Aérea
Estruturas estáticas
Estruturas de dados que vimos:
- array
- string (=array)
- struct
Estas estruturas são estáticas, i.e. o seu tamanho é fixo e definido no início.
int mat[10][10];
char frase[200];
struct aluno {
char nome[50];
int nip;
}
Alocação dinâmica de memória
Com alocação dinâmica de memória, aprendemos a criar estruturas de dados com um tamanho definido durante a execução do programa.
// allocate array, vec_size=size of vector
int * vect = calloc(vec_size, sizeof(int));
// allocate bidimensional array
// dim1_size = #lines, dim2_size = #cols
int ** mat = calloc(dim1_size, sizeof(int*));
for(int i=0; i<dim1_size; i++)
mat[i] = calloc(dim2_size, sizeof(int));
Mas depois de criadas, o tamanho destas estruturas não é alterado1, i.e. um array não pode crescer ou diminuir conforme a necessidade.
E as estruturas dinâmicas?
Estas crescem e diminuem conforme adicionamos ou removemos dados.
Além disso, a forma de organização e ligação entre os dados permite otimizar o tempo de várias operações ou o espaço ocupado.
Estruturas de dados dinâmicas
- Lista ligada simples
- Lista duplamente ligada
- Fila (queue)
- Pilha (stack)
- entre muitas outras…
Lista ligada simples
Um conjunto de elementos ligados não pela sua posição na memória (array), mas por referências explicitas entre elementos.
Lista ligada simples
Diagrama de lista ligada simples
- HEAD aponta para o elemento inicial da lista.
- Cada elemento aponta para o elemento seguinte (apontador).
Algumas caracteristicas 1/2
- O último elemento aponta sempre para
NULL
.
- Se a lista estiver vazia,
HEAD
aponta para NULL
.
- Só podemos percorrer a lista numa direção
- se quisermos o elemento na posição X, temos de percorrer todos os elementos nas posições [0,X[
Algumas caracteristicas 2/2
- sempre que removemos um elemento da lista, não esquecer de libertar a memória.
- Sempre que removemos um elemento
- libertar e memória associada.
- mudar a referência da lista que apontava para esse elemento
Lista ligada simples
Os elementos de uma lista ligada também são frequentemente denominados por nós.
Um nó pode ser implementado com struct
.
struct node {
int data;
struct node * next;
}
Exemplo
- Criar lista e primeiro nó
struct node * head;
head = malloc(sizeof(struct node));
head->data = 42;
head->next = NULL;
struct node * b = malloc(sizeof(struct node));
b->data = 87;
b->next = NULL;
- Adicionar segundo nó à lista
// adicionar b à lista
head->next = b;
Algumas operações em listas ligadas
- inserir novo elemento em determinada posição
- eliminar elemento em determinada posição
- tirar elemento de determinada posição
- procurar nó por valor
- contar número de nós
Lista duplamente ligada
Em tudo igual à lista ligada simples, mas cada nó aponta para o elemento anterior e para o seguinte.
Fila (queue)
- Parecida com uma lista ligada, mas os elementos são sempre adicionados no fim e retirados do início.
- O primeiro elemento a entrar é o primeiro elemento a sair (FIFO - first in first out)
Pilha (stack)
- Parecida com uma lista ligada, mas os elementos são sempre adicionados no fim e retirados do fim, ou adicionados no início e retirados do início.
- O último elemento a entrar é o primeiro elemento a sair (LIFO - last in first out)