Estrutura de Dados em C

Prévia do material em texto

Estruturas de Dados - Listas Lineares
AULA 04
Ocupação Circular
Listas com Descritor
AULA 04
Ocupação Circular
Listas com Descritor
Estruturas de Dados - Listas Lineares
Ocupação CircularOcupação Circular
Estruturas de Dados - Listas Lineares
Ocupação circular
5 6 7 8 92 3 40 1 10 11 12
Início 
da LLFinal 
da LL
X
Estruturas de Dados - Listas Lineares
Ocupação circular
Problema dos Algoritmos
Estruturas de Dados - Listas Lineares
Ocupação circular
Problema dos Algoritmos
Início 
da LL
Final 
da LL
Início 
da LL
Final 
da LL
Estruturas de Dados - Listas Lineares
16 17 18 19 2013 14 1511 12 21 22 23
Ocupação circular utilizando parte do 
arranjo
Início 
da LLFinal 
da LL
Estruturas de Dados - Listas Lineares
Ocupação Circular
duas listas sobre o mesmo arranjo
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
Espaço para L1 Espaço para L2
Início 
da LL
Final 
da LL
Início 
da LL
Final 
da LL
Estruturas de Dados - Listas Lineares
• Dados
– ???? 
• Operações
– ?????
Lista linear – TAD Genérico
Estruturas de Dados - Listas Lineares
• Dados
typedef struct T_Produto {
int cod;
char nome[40];
float preco; 
}TProduto;
int inicio, fim, maximo; 
TProduto Lista[MAX];
• Operações
– void inicializa (TProduto t[], int *inicio, int *fim);
– void insere (TProduto t[], int *inicio, int *fim, int posicao);
– void remove (TProduto t[], int *inicio, int *fim, int posicao);
– int consulta ( TProduto t[], int inicio, int fim, int posicao)
– void destroi (TProduto t[], int *inicio, int *fim);
Lista linear – TAD Genérico
Estruturas de Dados - Listas Lineares
Listas com DescritorListas com Descritor
Estruturas de Dados - Listas Lineares
Listas Lineares com Descritor
Descritor contém diversas informações 
sobre a lista linear :
• localização
• acesso
• estrutura
• conteúdo
• ... 5 6 7 8 92 3 40 1 10 11 12
42 5 17 9
6 6 32 7
Estruturas de Dados - Listas Lineares
• índice do início da lista
• índice do final da lista
• comprimento da lista
• índice do menor valor contido na lista
• índice do maior valor contido na lista
Exemplo de descritor
5 6 7 8 92 3 40 1 10 11 12
X
Descritor de LLDLista
42 5 17 9
6 6 32 7
Estruturas de Dados - Listas Lineares
Lista vazia com descritor
6 7 8 9 103 4 51 2 11 12X
DLista 0-1 -1
Comprimento da lista
Último nodo da lista
Primeiro nodo da lista
5 6 7 8 92 3 40 1 10 11
Estruturas de Dados - Listas Lineares
Acesso à LL com Descritor em 
forma de arranjo
x[DLista[0]].nome � Nome contido no primeiro nodo da lista
x [DLista[1]].preco� Valor contido no último nodo da lista
DLista[2] � comprimento da lista. A informação está contida 
diretamente no descritor, não sendo necessário percorrer a 
lista para obtê-la.
typedef struct T_Produto {
int cod;
char nome[40];
float preco; 
}TProduto;
int DLista[3];
Estruturas de Dados - Listas Lineares
Acesso à LL com Descritor em 
forma de registro
X [DLista.inicio].Nome � Nome contido no primeiro nó da lista
X [DLista.fim].Valor � Valor contido no último nó da lista
DL.maior � Maior valor contido no campo valor de 
todos os nós da lista. Neste caso não é necessário acessar 
o arranjo, pois a informação já está contida no descritor.
typedef struct T_Descritor {
int inicio;
int fim;
int maior; 
}TDescritor;
typedef struct T_Produto {
int cod;
char nome[40];
float preco; 
}TProduto;
Estruturas de Dados - Listas Lineares
• facilidade de referência à lista
void insere (TProduto t[], TDescritor d[], int posicao);
em vez de 
void insere (TProduto t[], int *inicio, int *fim, int posicao);
• afastamento do usuário dos detalhes da 
representação interna
Vantagens da utilização de
descritor
Estruturas de Dados - Listas Lineares
IA IL N FAFL
Descritor informando espaço disponível 
para a lista no arranjo
5 6 7 8 92 3 40 1 10 11 12
Nr. Nodos
da lista
6
Índice de início do espaço 
disponível no arranjo
Índice de final do 
espaço disponível
no arranjo
0 122 7
Índice de início da lista
Índice de final da lista
ÍNDICES !!!
X
DLista
Estruturas de Dados - Listas Lineares
Descritor informando espaço disponível 
para a lista no arranjo
16 17 18 19 2013 14 1511 12 21 22 23
IA IL N FAFL
2212 13 186
X
DLista
Estruturas de Dados - Listas Lineares
Duas LL implementadas sobre o 
mesmo arranjo, com descritores
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
10 11 4 14 17
IA IL N FAFL
Espaço para L1 Espaço para L2
18 20 5 24 24
IA IL N FAFL
Estruturas de Dados - Listas Lineares
16 17 18 19 2013 14 1511 12 21 22 23
IA IL N FAFL
2311 13 186
A
Declarações para os algoritmos
apresentados
Algoritmos implementando a alocação circular - mais complexos 
mas mais eficientes
Estruturas de Dados - Listas Lineares
Lista vazia com descritor
5 6 7 8 92 3 40 1 10 11 12
IA IL N FAFL
120 -1 -10
IA IL N FAFL
2311 -1 -10 OU
IA IL N FAFL
2311 10 100
16 17 18 19 2013 14 1511 12 21 22 23
DLista
L
DLista DLista
L
Estruturas de Dados - Listas Lineares
IA IL N FAFL
2311 13 186
Inserir novo nodo
LL com descritor - contigüidade física
16 17 18 19 2013 14 1511 12 21 22 23
ANo início
16 17 18 19 2013 14 1511 12 21 22 23
ANo final
16 17 18 19 2013 14 1511 12 21 22 23
ANo meio
Estruturas de Dados - Listas Lineares
Inserir novo nodo no início
LL com descritor - contigüidade física
IA IL N FAFL
2311 13 186
16 17 18 19 2013 14 1511 12 21 22 23
A
16 17 18 19 2013 14 1511 12 21 22 23
A?
IA IL N FAFL
2311 11 186
16 17 18 19 2013 14 1511 12 21 22 23
A
197
712
Estruturas de Dados - Listas Lineares
Inserir novo nodo no final
LL com descritor - contigüidade física
IA IL N FAFL
2311 13 186
16 17 18 19 2013 14 1511 12 21 22 23
A
7 19
A
16 17 18 19 2013 14 1511 12 21 22 23
?
IA IL N FAFL
2311 188 231615
16 17 18 19 2013 14 1511 12 21 22 23
A
9
Estruturas de Dados - Listas Lineares
Inserir novo nodo no meio
LL com descritor - contigüidade física
IA IL N FAFL
2311 13 186
16 17 18 19 2013 14 1511 12 21 22 23
A
Pos = 3
16 17 18 19 2013 14 1511 12 21 22 23
A
197
• FL = FA - abrir espaço para a frente, alterando IL
Estruturas de Dados - Listas Lineares
• Dados
– ???? 
• Operações
– ?????
Lista linear – TAD Genérico
Estruturas de Dados - Listas Lineares
• Dados
typedef struct T_Produto {
int cod;
char nome[40];
float preco; 
}TProduto;
• Operações
– void inicializa (TProduto t[], TDescritor *d);
/*inicializa as variáveis do descritor e percorre o array zerando todas as posições*/
– void insere (TProduto t[], TDescritor *d, int posicao);
/*insere um novo produto na posição desejada e atualiza descritor*/
– void remove (TProduto t[], TDescritor *d, int posicao);
/*remove o produto da posição especificada deslocando os elementos do array*/
– int consulta ( TProduto t[], TDescritor d, int posicao);
/*consulta o elemento da posição especificada*/
– void destroi (TProduto t[], TDescritor *d);
/* reinicializa o array*/
Lista linear – TAD Genérico
typedef struct T_Descritor {
int inicio;
int fim;
}TDescritor;
Estruturas de Dados - Listas Lineares
Exercício
• Implementar uma função para a inserção 
de produtos em ordem alfabética em uma 
lista.
– A função deve utilizar ocupação circular
– Os deslocamentos de elementos devem ser 
otimizados
– Utilizar um descritor em forma de registro 
para facilitar o acesso à lista