Buscar

Estrutura de dados - Aula 07 - Listas Encadeadas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 27 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 27 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 27 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Prof. Adriano Teixeira de Souza 
 Listas encadeadas ou listas ligadas 
representam uma seqüência de objetos na 
memória do computador. 
 
 Exemplo: Lista de afazeres 
1. Comprar uma lâmpada 
2. Trocar uma lâmpada queimada 
3. Procurar uma conta no quarto 
4. Pagar uma conta na internet 
5. Desligar o computador 
6. Dormir 
Próxima 
ação Ação atual 
 Na lista de afazeres anterior, uma tarefa 
dependia da execução da tarefa anterior 
 
2 
1. Comprar 
lâmpada 
3 
2. Trocar 
lâmpada 
4 
3. Procurar 
conta 
5 
4. Pagar 
conta 
6 
5. Desligar 
micro 
fim 6. Dormir 
Dormir 
Desligar 
micro 
Pagar 
conta 
Procurar 
conta 
Trocar 
lâmpada 
 Como representar a lista anterior em um 
programa escrito na Linguagem C? 
◦ Primeira opção: vetores ou matrizes 
Comprar 
lâmpada 
Tarefa: 
Índice: 1 2 3 4 5 6 
 Primeira opção: vetores ou matrizes 
◦ Como acrescentar “Ligar micro”? 
Dormir 
Desligar 
micro 
Pagar 
conta 
Ligar 
micro 
Procurar 
conta 
Trocar 
lâmpada 
Comprar 
lâmpada 
Tarefa: 
Índice: 1 2 3 4 5 6 7 
 Primeira opção: vetores ou matrizes 
◦ Os itens da lista são armazenados em posições 
contíguas de memória. 
 
◦ A lista pode ser percorrida em qualquer direção. 
 
◦ A inserção de um novo item pode ser realizada 
após o último item com custo constante. 
 
◦ A inserção de um novo item no meio da lista requer 
um deslocamento de todos os itens localizados 
após o ponto de inserção. 
 
◦ Retirar um item do início da lista requer um 
deslocamento de itens para preencher o espaço 
deixado vazio. 
 Segunda opção: ponteiros 
◦ Estruturas de dados dinâmicas: estruturas de dados 
que contém ponteiros para si próprias. 
struct lista { 
char nome_tarefa[30]; 
float duracao; 
char responsavel[30]; 
... 
struct lista *prox; 
}; 
ponteiro para a 
própria estrutura lista 
 
 Representação gráfica de um elemento da lista: 
 
 
 
 
 
◦ Cada item é encadeado com o seguinte, mediante uma 
variável do tipo ponteiro. 
◦ Permite utilizar posições não contíguas de memória. 
◦ É possível inserir e retirar elementos sem necessidade de 
deslocar os itens seguintes da lista. 
campos de informação 
próximo nó 
 Cada item em particular de uma lista pode ser 
chamado de elemento, nó, célula, ou item. 
 O apontador para o início da lista também é 
tratado como se fosse uma célula (cabeça), para 
simplificar as operações sobre a lista. 
 O símbolo / representa o ponteiro nulo (NULL), 
indicando o fim da lista. 
3 
5 
p 
2 
/ 4 
 Podemos realizar algumas operações sobre 
uma lista encadeadas, tais como: 
◦ Inserir itens; 
◦ Retirar itens; 
◦ Buscar itens. 
 
 Para manter a lista ordenada, após realizar 
alguma dessas operações, será necessário 
apenas movimentar alguns ponteiros (de um 
a três elementos). 
 Outras operações possíveis: 
◦ Criar uma lista 
◦ Destruir uma lista 
◦ Ordenar uma lista 
◦ Intercalar duas listas 
◦ Concatenar duas listas 
◦ Dividir uma lista em duas 
◦ Copiar uma lista em outra 
Prof. Adriano Teixeira de Souza 
typedef struct { 
 float info; 
 struct No* proximo; 
} No; 
 
No* cria (void) 
{ 
 return NULL; 
} 
 Podemos inserir itens: 
◦ No início de uma lista 
◦ No final de uma lista 
◦ No meio de uma lista 
p 5 2 / 4 
 O endereço armazenado no ponteiro p deve 
ser alterado para o endereço do item a ser 
acrescido à lista. 
3 
Prof. Adriano Teixeira de Souza 
No* insere (No* l, float v) 
{ 
 No* p = (No*) malloc(sizeof(No)); 
 p->info = v; 
 p->proximo = l; 
 
 return p; 
} 
 O endereço armazenado em p será alterado 
caso a lista esteja vazia ou 
 O campo prox do último item será alterado. 
/ 3 p 
/ 
3 / 5 p 
 Campo prox do item a ser inserido recebe o 
campo prox do item posterior 
 Campo prox do item antecessor recebe o 
endereço do item a ser inserido 
2 / 4 
5 
3 p 
lista[5].prox ← lista[2] 
lista[3].prox ← 5 
p 5 2 / 4 
 O endereço armazenado no ponteiro p deve 
ser alterado para o endereço do item que 
segue o primeiro item da lista. 
 O campo prox do último item será alterado 
caso a lista contenha mais de um item ou 
 O endereço armazenado em p será alterado 
para NULL. 
/ 3 p 
/ 
3 / 5 p 
 Item antecessor recebe o campo prox do 
item a ser removido 
5 2 / 4 3 p 
lista[3].prox ← lista[5].prox 
No* retira (No* l, float v) {//Em qualquer posicao 
 
 No* ant = NULL; 
 No* p = l; 
 
 while (p != NULL && p->info != v) { 
 ant = p; 
 p = p->proximo; 
 } 
 if (p == NULL) 
 return l; 
 if (ant == NULL) { 
 l = p->proximo; 
 }else { 
 ant->proximo = p->proximo; 
 } 
 free(p); 
 return l; 
} 
Prof. Adriano Teixeira de Souza 
No* busca (No* l,float v){ 
 No* q; 
 int i=0; 
 for (q=l; q!=NULL; q=q->proximo){ 
 if(q->info == v){ 
 printf("\n\nachou %d\n\n\n",i); 
 return q; 
 } 
 i++; 
 } 
 return NULL; 
} 
Prof. Adriano Teixeira de Souza 
void imprime (No* l){ 
 No* q; 
 for (q=l; q!=NULL; q=q->proximo) 
 printf("%f\n", q->info); 
} 
Prof. Adriano Teixeira de Souza 
void libera (No* l) { 
 No* q = l; 
 while (q!=NULL) { 
 No* t = q->proximo; 
 free(q); 
 q = t; 
 } 
} 
Prof. Adriano Teixeira de Souza 
main(){ 
 
 No* p = cria(); 
 p = insere (p,20.0); 
 p = insere (p,44.5); 
 p = insere (p,33.3); 
 p = insere (p,20.9); 
 imprime (p); 
 No* n = busca(p,20.3);//Busca 
 if (n != NULL){ 
 printf ("Encontrado: %f\n", n->info); 
 p=retira(p,n->info); 
 } 
 printf ("Configuracao da fila:\n"); 
 imprime (p); 
 libera (p); 
 
 system("pause"); 
 
} 
Prof. Adriano Teixeira de Souza 
No* insere_ordenado (No* l, float v) 
{ 
 No* novo = (No*) malloc(sizeof(No)); 
 novo->info = v; 
 
 No* ant = NULL; 
 No* p = l; 
 
 while (p != NULL && p->info < v) { 
 ant = p; 
 p = p->proximo; 
 } 
 if (ant == NULL) { 
 novo->proximo = l; 
 l = novo; 
 } else { 
 novo->proximo = ant->proximo; 
 ant->proximo = novo; 
 } 
 return l; 
}

Materiais relacionados

Perguntas relacionadas

Materiais recentes

Perguntas Recentes