aula06-ListaEnc

Prévia do material em texto

Listas Encadeadas 
Prof. Douglas Veras (douglas@deinfo.ufrpe.br) 
Algoritmos e Estruturas de Dados 
(Aperfeiçoamento) 
DEINFO 
Algoritmos e Estrutura de Dados I 
Listas Encadeadas 
 Características: 
 Tamanho da lista não é pré-definido 
 Cada elemento guarda quem é o próximo 
 Elementos não estão contíguos na memória 
 
info 
info 
prox 
info 
NULL 
info 
NULL 
info 
NULL 
prox 
prox 
Algoritmos e Estrutura de Dados I 
Sobre os Elementos da Lista 
 Elemento: guarda as informações sobre 
cada elemento. 
 Para isso define-se cada elemento como 
uma estrutura que possui: 
 campos de informações 
 ponteiro para o próximo elemento 
info 
prox 
Algoritmos e Estrutura de Dados I 
Sobre a Lista 
 Uma lista pode ter uma célula cabeça 
info 
prox prox 
info 
prox 
info 
NULL 
 Uma lista pode ter um apontador para o 
último elemento 
Último 
Algoritmos e Estrutura de Dados I 
Cria Lista Vazia 
NULL 
Cabeça 
Último 
Algoritmos e Estrutura de Dados I 
Inserção de Elementos na Lista 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
 3 opções de posição onde pode inserir: 
 1ª. posição 
 última posição 
 Após um elemento qualquer E 
Algoritmos e Estrutura de Dados I 
Inserção na Primeira Posição 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
info 
NULL prox 
Algoritmos e Estrutura de Dados I 
Inserção na Última Posição 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
info 
NULL prox 
Algoritmos e Estrutura de Dados I 
Inserção Após o Elemento E 
prox 
info 
prox 
info 
NULL 
Último 
info 
NULL prox 
Elem E 
info 
prox 
Algoritmos e Estrutura de Dados I 
Retirada de Elementos na Lista 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
 3 opções de posição de onde pode retirar: 
 1ª. posição 
 última posição 
 Um elemento qualquer E 
Algoritmos e Estrutura de Dados I 
Retirada do Elemento na 
Primeira Posição da Lista 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
Algoritmos e Estrutura de Dados I 
Retirada do Elemento E da Lista 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
Elem E Anterior 
Algoritmos e Estrutura de Dados I 
Retirada do Último Elemento da Lista 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
Anterior 
NULL 
Algoritmos e Estrutura de Dados I 
Estrutura da Lista Usando Apontadores 
typedef int TipoChave; 
 
typedef struct { 
 TipoChave Chave; 
 /* outros componentes */ 
} TipoItem; 
 
typedef struct Celula* Apontador; /*typedef int Apontador;*/ 
typedef struct Celula { 
 TipoItem Item; 
 struct Celula* pProx; /* Apontador pProx; */ 
} Celula; 
 
typedef struct { 
 Apontador pPrimeiro; 
 Apontador pUltimo; 
 int tamanho; 
} TipoLista; 
Algoritmos e Estrutura de Dados I 
Operações sobre Lista Usando 
Apontadores 
void FLVazia(TipoLista *pLista) 
{ 
 pLista->pPrimeiro = (Apontador) malloc(sizeof(Celula)); 
 pLista->pUltimo = pLista->pPrimeiro; 
 pLista->pPrimeiro->pProx = NULL; 
 pLista->tamanho = 0; 
} 
 
int LEhVazia(TipoLista* pLista) 
{ 
 return (pLista->pPrimeiro == pLista->pUltimo); 
} 
 
void LInsere(TipoItem x, TipoLista *pLista) 
{ 
 pLista->pUltimo->pProx = (Apontador) malloc(sizeof(Celula)); 
 pLista->pUltimo = pLista->pUltimo->pProx; 
 pLista->pUltimo->Item = x; 
 pLista->pUltimo->pProx = NULL; 
 pLista->tamanho = pLista->tamanho + 1; 
} 
Algoritmos e Estrutura de Dados I 
Operações sobre Lista Usando 
Apontadores 
void LImprime(TipoLista* pLista) 
{ 
 implemente… 
} 
Algoritmos e Estrutura de Dados I 
Operações sobre Lista Usando 
Apontadores 
void LImprime(TipoLista* pLista) 
{ 
 Apontador pAux; 
 pAux = pLista->pPrimeiro->pProx; 
 while (pAux != NULL) 
 { 
 printf("%d\n", pAux->Item.Chave); 
 pAux = pAux->pProx; 
 } 
} 
Algoritmos e Estrutura de Dados I 
Operações sobre Lista Usando 
Apontadores 
void void LRetira(Apontador p, TipoLista *lista , TipoItem 
*item) { 
/*−−O item a ser retirado e o seguinte ao apontado por p*/ 
 implemente.. 
} 
Algoritmos e Estrutura de Dados I 
Operações sobre Lista Usando 
Apontadores 
void void LRetira(Apontador p, TipoLista *lista , TipoItem *item) { 
/*−−O item a ser retirado eh o seguinte ao apontado por p*/ 
 Apontador q; 
 if (LEhVazia(lista ) || p == NULL || p->pProx == NULL) 
 { 
 printf ( " Erro : Lista vazia ou posicao nao existe \n" ) ; 
 return; 
 } 
 q = p->pProx; 
 *item = q->Item; 
 p->pProx = q->pProx; 
 if (p->pProx == NULL) 
 lista->pUltimo = p; 
 free(q) ; 
 lista->tamanho = lista->tamanho -1; 
} 
Algoritmos e Estrutura de Dados I 
Operações sobre Lista Usando 
Apontadores 
 Vantagens: 
 Permite inserir ou retirar itens do meio da lista a um custo 
constante (importante quando a lista tem de ser mantida em 
ordem). 
 Bom para aplicações em que não existe previsão sobre o 
crescimento da lista (o tamanho máximo da lista não precisa ser 
definido a priori). 
 
 Desvantagem: 
 Utilização de memória extra para armazenar os apontadores. 
Algoritmos e Estrutura de Dados I 
Exemplo de Uso Listas - Vestibular 
 Num vestibular, cada candidato tem direito a 
três opções para tentar uma vaga em um dos 
sete cursos oferecidos. 
 Para cada candidato é lido um registro: 
 Chave: número de inscrição do candidato. 
 NotaFinal: média das notas do candidato. 
 Opção: vetor contendo a primeira, a segunda e a 
terceira opções de curso do candidato. 
 
Algoritmos e Estrutura de Dados I 
Exemplo de Uso Listas - Vestibular 
 Problema: distribuir os candidatos entre os 
cursos, segundo a nota final e as opções 
apresentadas por candidato. 
 
 Em caso de empate, os candidatos serão 
atendidos na ordem de inscrição para os 
exames. 
Algoritmos e Estrutura de Dados I 
Vestibular - Possível Solução 
 Ordenar registros pelo campo NotaFinal, 
respeitando a ordem de inscrição; 
 Percorrer cada conjunto de registros com mesma 
NotaFinal, começando pelo conjunto de NotaFinal 
10, seguido pelo de NotaFinal 9, e assim por diante. 
 Para um conjunto de mesma NotaFinal tenta-se 
encaixar cada registro desse conjunto em um dos 
cursos, na primeira das três opções em que houver 
vaga (se houver). 
Algoritmos e Estrutura de Dados I 
Vestibular - Possível Solução 
 Primeiro refinamento: 
main() 
{ 
 ordena os registros pelo campo NotaFinal ; 
 for Nota = 10 até 0 do 
 while houver registro com mesma nota do 
 if existe vaga em um dos cursos de opcao do candidato 
 then insere registro no conjunto de aprovados 
 else insere registro no conjunto de reprovados; 
 imprime aprovados por curso ; 
 imprime reprovados; 
} 
Algoritmos e Estrutura de Dados I 
Vestibular - Classificação dos Alunos 
 Uma boa maneira de representar um conjunto de 
registros é com o uso de listas. 
 Ao serem lidos, os registros são armazenados em 
listas para cada nota. 
 Após a leitura do último registro os candidatos estão 
automaticamente ordenados por NotaFinal. 
 Dentro de cada lista, os registros estão ordenados 
por ordem de inscrição, desde que os registros 
sejam lidos na ordem de inscrição de cada 
candidato e inseridos nesta ordem. 
Algoritmos e Estrutura de Dados I 
Vestibular– Representação da 
Classificação dos Alunos 
Algoritmos e Estrutura de Dados I 
Vestibular - Classificação dos Alunos por 
Curso 
 As listas de registros são percorridas, iniciando-se 
pela de NotaFinal 10, seguida pela de NotaFinal 9, 
e assim sucessivamente. 
 Cada registro é retirado e colocado em uma das 
listas da abaixo, na primeira das três opções em 
que houver vaga. 
 Se não houver vaga, o registro é colocado em uma 
lista de reprovados. 
 Ao final a estrutura acima conterá a relação de 
candidatos aprovados em cada curso. 
 
Algoritmos e Estrutura de Dados I 
Vestibular - Classificação dos Alunos por 
Curso 
Algoritmos e Estrutura de Dados I 
Vestibular - Segundo Refinamento 
main() 
{ 
 lê número de vagas para cada curso; 
 inicializa listas de classificação de aprovados e reprovados; 
 lê registro; 
 while Chave != 0 do //Ou while Chave do 
 { 
 insere registro nas listas de classificação, conforme nota final; 
 lê registro; 
 } 
} 
Algoritmos e Estrutura de Dados I 
Vestibular - Segundo Refinamento 
for Nota = 10 até 0 do 
{ 
 while houver próximo registro com mesma NotaFinal do 
 { 
 retira registro da lista; 
 if existe vaga em um dos cursos de opção do candidato 
 { 
 insere registro na lista de aprovados; 
 decrementa o número de vagas para aquele curso; 
 } 
 else insere registro na lista de reprovados; 
 obtém próximo registro; 
 } 
} 
imprime aprovados por curso; 
imprime reprovados; 
 
Algoritmos e Estrutura de Dados I 
Vestibular - Estrutura Final da Lista 
#define NOpcoes 3 
#define NCursos 7 
#define FALSE 0 
#define TRUE 1 
 
typedef short TipoChave; 
 
typedef struct TipoItem { 
 TipoChave Chave; 
 char NotaFinal; 
 char Opcao[NOpcoes]; 
} TipoItem; 
 
typedef struct Celula { 
 TipoItem Item; 
 struct Celula *pProx; 
} Celula; 
 
typedef struct TipoLista { 
 Celula *pPrimeiro, *pUltimo; 
 int tamanho; 
} TipoLista; 
Algoritmos e Estrutura de Dados I 
Vestibular - Estrutura Final da Lista 
TipoItem Registro; 
TipoLista Classificacao[11]; 
TipoLista Aprovados[NCursos]; 
TipoLista Reprovados; 
long Vagas[NCursos]; 
short Passou; 
long i, Nota; 
 
 
Algoritmos e Estrutura de Dados I 
Vestibular - Refinamento Final 
 Observe que o programa é completamente independente 
da implementação do tipo abstrato de dados Lista. 
void LeRegistro(TipoItem *Registro) 
{ /* os valores lidos devem estar separados por brancos */ 
 long i; 
 int TEMP; 
 scanf("%hd %d", &(Registro->Chave), &TEMP); 
 Registro->NotaFinal = TEMP; 
 for (i = 0; i < NOpcoes; i++) 
 { 
 scanf("%d", &TEMP); 
 Registro->Opcao[i] = TEMP; 
 } 
 scanf(“%*[^\n]”); /* limpa buffer - fflush(stdin);*/ 
 getchar(); 
} 
 
Algoritmos e Estrutura de Dados I 
Vestibular - Refinamento Final 
int main(int argc, char *argv[]) 
{ /*---Programa principal---*/ 
 for (i = 1; i <= NCursos; i++) 
 scanf("%ld", &Vagas[i-1]); 
 scanf("%*[^\n]"); /* limpa buffer – fflush(stdin); */ 
 getchar(); 
 for (i = 0; i <= 10; i++) 
 FLVazia(&(Classificacao[i])); 
 for (i = 0; i < NCursos; i++) 
 FLVazia(&(Aprovados[i])); 
 FLVazia(&Reprovados); 
 LeRegistro(&Registro); 
 while (Registro.Chave != 0) 
 { 
 LInsere(&Registro, &Classificacao[Registro.NotaFinal]); 
 LeRegistro(&Registro); 
 } 
 return 0; 
} 
Algoritmos e Estrutura de Dados I 
Vestibular - Refinamento Final 
 for (Nota = 10; Nota >= 0; Nota--) 
 { while (!LEhVazia(&Classificacao[Nota])) 
 { LRetira(Classificacao[Nota].Primeiro, &Classificacao[Nota], &Registro); 
 i = 0; 
 Passou = FALSE; 
 while (i < NOpcoes && !Passou) 
 { if (Vagas[Registro.Opcao[i]-1] > 0) 
 { LInsere(Registro, &(Aprovados[Registro.Opcao[i]-1]) ); 
 Vagas[Registro.Opcao[i]-1]--; 
 Passou = TRUE; 
 } 
 i++; 
 } 
 if (!Passou) LInsere(Registro, &Reprovados); 
 } 
 } 
 for (i = 0; i < NCursos; i++) 
 { printf("Relacao dos aprovados no Curso%ld\n", i+1); 
 Imprime(Aprovados[i]); 
 } 
 printf("Relacao dos reprovados\n"); 
 Imprime(Reprovados); 
 return 0; 
} 
Algoritmos e Estrutura de Dados I 
Vestibular - Refinamento Final 
 O exemplo mostra a importância de utilizar tipos abstratos de 
dados para escrever programas, em vez de utilizar detalhes 
particulares de implementação. 
 
 Altera-se a implementação rapidamente. Não é necessário 
procurar as referências diretas às estruturas de dados por 
todo o código. 
 
 Este aspecto é particularmente importante em programas de 
grande porte. 
Algoritmos e Estrutura de Dados I 
Exercícios 
 Pesquise como funciona e implemente uma 
lista duplamente encadeada