Mudanças entre as edições de "AULA 20 - Programação 1 - Graduação"
(27 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
Linha 16: | Linha 16: | ||
<syntaxhighlight lang=c> | <syntaxhighlight lang=c> | ||
− | + | struct cel { | |
− | + | int conteudo; | |
− | + | struct cel *prox; | |
− | + | }; | |
</syntaxhighlight> | </syntaxhighlight> | ||
+ | <br> | ||
+ | {| border="1" cellpadding="5" cellspacing="0" | ||
+ | ! style="background: #ffdead;" | 123 | ||
+ | ! style="background: #ffdead;" | ---> | ||
+ | |} | ||
+ | <br> | ||
+ | ;Sendo: | ||
+ | :'''123''': conteudo | ||
+ | :'''--->''': *prox | ||
+ | |||
+ | É conveniente tratar as células como um novo tipo-de-dados e atribuir um nome a esse novo tipo: | ||
+ | |||
+ | typedef struct cel celula; // célula | ||
+ | |||
+ | Uma célula c e um ponteiro p para uma célula podem ser declarados assim: | ||
+ | |||
+ | celula c; | ||
+ | celula *p; | ||
+ | |||
+ | |||
+ | |||
+ | Se '''c''' é uma célula então '''c.conteudo''' é o conteúdo da célula e '''c.prox''' é o endereço da próxima célula. Se '''p''' é o endereço de uma célula, então '''p->conteudo''' é o conteúdo da célula e '''p->prox''' é o endereço da próxima célula. Se '''p''' é o endereço da última célula da lista então: '''p->prox''' vale '''NULL'''. | ||
+ | |||
+ | <br> | ||
+ | {| border="1" cellpadding="5" cellspacing="0" | ||
+ | ! style="background: #ffdead;" | 123 | ||
+ | ! style="background: #ffdead;" | ---> | ||
+ | ! style="background: #ffdead;" | 234 | ||
+ | ! style="background: #ffdead;" | ---> | ||
+ | ! style="background: #ffdead;" | 345 | ||
+ | ! style="background: #ffdead;" | ---> | ||
+ | ! style="background: #ffdead;" | 456 | ||
+ | ! style="background: #ffdead;" | ---> | ||
+ | ! style="background: #ffdead;" | 567 | ||
+ | ! style="background: #ffdead;" | ---> | ||
+ | ! style="background: #ffdead;" | 678 | ||
+ | ! style="background: #ffdead;" | NULL | ||
+ | |} | ||
+ | <br> | ||
+ | |||
+ | ==Listas com cabeça e sem cabeça== | ||
+ | |||
+ | Uma lista encadeada pode ser organizada de duas maneiras diferentes. | ||
+ | |||
+ | :'''Lista com cabeça''': O conteúdo da primeira célula é irrelevante: ela serve apenas para marcar o início da lista. A primeira célula é a cabeça (= head cell = dummy cell) da lista. Digamos que ini é o endereço da primeira célula. Então ini->prox == NULL se e somente se a lista está vazia. Para criar uma lista vazia, basta fazer: | ||
+ | |||
+ | celula c, *ini; | ||
+ | c.prox = NULL; | ||
+ | ini = &c; | ||
+ | |||
+ | ou, se preferir alocar a primeira célula dinâmicamente, | ||
+ | celula *ini; | ||
+ | ini = malloc( sizeof (celula)); | ||
+ | ini->prox = NULL; | ||
+ | :'''Lista sem cabeça''': O conteúdo da primeira célula é tão relevante quanto o das demais. Nesse caso, a lista está vazia se o endereço de sua primeira célula é NULL. Para criar uma lista vazia basta fazer | ||
+ | |||
+ | celula *ini; | ||
+ | ini = NULL; | ||
+ | |||
+ | É preferível as listas sem cabeça porque são mais simples, porém, a vida do programador fica mais fácil quando as listas têm cabeça. | ||
+ | |||
+ | ;Exemplos: Para imprimir o conteúdo de uma lista encadeada com cabeça: | ||
+ | |||
+ | <syntaxhighlight lang=c> | ||
+ | // Imprime o conteúdo de uma lista encadeada | ||
+ | // com cabeça. O endereço da primeira célula é ini. | ||
+ | |||
+ | void imprima( celula *ini) { | ||
+ | celula *p; | ||
+ | for (p = ini->prox; p != NULL; p = p->prox) | ||
+ | printf( "%d\n", p->conteudo); | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | :Mesma função para lista sem cabeça: | ||
+ | |||
+ | <syntaxhighlight lang=c> | ||
+ | // Imprime o conteúdo de uma lista encadeada ini. | ||
+ | // A lista não tem cabeça. | ||
+ | |||
+ | void imprima( celula *ini) { | ||
+ | celula *p; | ||
+ | for (p = ini; p != NULL; p = p->prox) | ||
+ | printf( "%d\n", p->conteudo); | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | '''NOTE''' que o tipo de dados '''ini''' não inicializa no próximo (ini->prox) como no exemplo acima. | ||
+ | |||
+ | ===Busca em uma lista encadeada=== | ||
+ | |||
+ | Veja como é fácil verificar se um inteiro x pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista: | ||
+ | |||
+ | <syntaxhighlight lang=c> | ||
+ | // Esta função recebe um inteiro x e uma lista | ||
+ | // encadeada ini de inteiros, com celula-cabeça. | ||
+ | // A função devolve o endereço de uma celula que | ||
+ | // contém x ou devolve NULL se tal celula não | ||
+ | // existe. | ||
+ | |||
+ | celula *busca( int x, celula *ini) | ||
+ | { | ||
+ | celula *p; | ||
+ | p = ini->prox; | ||
+ | while (p != NULL && p->conteudo != x) | ||
+ | p = p->prox; | ||
+ | return p; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | =Exercícios propostos= | ||
Por vezes não se conhece o tamanho dos dados que se vai manipular e o uso de uma lista pode ser conveniente para | Por vezes não se conhece o tamanho dos dados que se vai manipular e o uso de uma lista pode ser conveniente para | ||
Linha 235: | Linha 345: | ||
! style="background: #cdc5bf;" | [[AULA 19 - Programação 1 - Graduação | << ]] | ! style="background: #cdc5bf;" | [[AULA 19 - Programação 1 - Graduação | << ]] | ||
! style="background: #cdc5bf;" | Aula 20 | ! style="background: #cdc5bf;" | Aula 20 | ||
− | ! style="background: #cdc5bf;" | [[ | + | ! style="background: #cdc5bf;" | [[AULA 21 - Programação 1 - Graduação | >> ]] |
|} | |} |
Edição atual tal como às 14h08min de 28 de maio de 2015
Objetivos
- Apresentar as listas encadeadas;
- Apresentar algumas aplicações.
Listas Encadeada
Trata-se uma representação de uma sequência de objetos, todos do mesmo tipo, na memória do computador. Cada elemento da sequência é armazenado em uma célula da lista: o primeiro elemento na primeira célula, o segundo na segunda e assim por diante.
Estrutura de uma lista encadeada
Uma lista encadeada (= linked list = lista ligada) é uma sequência de células; cada célula contém um objeto de algum tipo e o endereço da célula seguinte.
Vamos supor que os objetos armazenados nas células são do tipo int. A estrutura de cada célula de uma determinada lista pode ser definida assim:
struct cel {
int conteudo;
struct cel *prox;
};
123 | ---> |
---|
- Sendo
- 123: conteudo
- --->: *prox
É conveniente tratar as células como um novo tipo-de-dados e atribuir um nome a esse novo tipo:
typedef struct cel celula; // célula
Uma célula c e um ponteiro p para uma célula podem ser declarados assim:
celula c; celula *p;
Se c é uma célula então c.conteudo é o conteúdo da célula e c.prox é o endereço da próxima célula. Se p é o endereço de uma célula, então p->conteudo é o conteúdo da célula e p->prox é o endereço da próxima célula. Se p é o endereço da última célula da lista então: p->prox vale NULL.
123 | ---> | 234 | ---> | 345 | ---> | 456 | ---> | 567 | ---> | 678 | NULL |
---|
Listas com cabeça e sem cabeça
Uma lista encadeada pode ser organizada de duas maneiras diferentes.
- Lista com cabeça: O conteúdo da primeira célula é irrelevante: ela serve apenas para marcar o início da lista. A primeira célula é a cabeça (= head cell = dummy cell) da lista. Digamos que ini é o endereço da primeira célula. Então ini->prox == NULL se e somente se a lista está vazia. Para criar uma lista vazia, basta fazer:
celula c, *ini; c.prox = NULL; ini = &c;
ou, se preferir alocar a primeira célula dinâmicamente,
celula *ini; ini = malloc( sizeof (celula)); ini->prox = NULL;
- Lista sem cabeça: O conteúdo da primeira célula é tão relevante quanto o das demais. Nesse caso, a lista está vazia se o endereço de sua primeira célula é NULL. Para criar uma lista vazia basta fazer
celula *ini; ini = NULL;
É preferível as listas sem cabeça porque são mais simples, porém, a vida do programador fica mais fácil quando as listas têm cabeça.
- Exemplos
- Para imprimir o conteúdo de uma lista encadeada com cabeça:
// Imprime o conteúdo de uma lista encadeada
// com cabeça. O endereço da primeira célula é ini.
void imprima( celula *ini) {
celula *p;
for (p = ini->prox; p != NULL; p = p->prox)
printf( "%d\n", p->conteudo);
}
- Mesma função para lista sem cabeça:
// Imprime o conteúdo de uma lista encadeada ini.
// A lista não tem cabeça.
void imprima( celula *ini) {
celula *p;
for (p = ini; p != NULL; p = p->prox)
printf( "%d\n", p->conteudo);
}
NOTE que o tipo de dados ini não inicializa no próximo (ini->prox) como no exemplo acima.
Busca em uma lista encadeada
Veja como é fácil verificar se um inteiro x pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista:
// Esta função recebe um inteiro x e uma lista
// encadeada ini de inteiros, com celula-cabeça.
// A função devolve o endereço de uma celula que
// contém x ou devolve NULL se tal celula não
// existe.
celula *busca( int x, celula *ini)
{
celula *p;
p = ini->prox;
while (p != NULL && p->conteudo != x)
p = p->prox;
return p;
}
Exercícios propostos
Por vezes não se conhece o tamanho dos dados que se vai manipular e o uso de uma lista pode ser conveniente para armazená-los. Um sistema de estoque de produtos, por exemplo, poderia ser armazenado na forma de uma lista.
- Exemplo de lista ligada
#include <stdlib.h>
#include <stdio.h>
/*========================*/
/** OPERAÇÔES COM LISTA LIGADA ******/
/*========================*/
/*
tipos e variáveis globais
*/
struct TProduto{
int codigo;
struct TProduto *next;
} *head, *tail;
/*
adiciona item a cabeça da lista
retorna 0 se tudo ok e -1 se erro
*/
int add_nodo_head(int codigo)
{
}
/*
adiciona item ao final lista
retorna 0 se tudo ok e -1 se erro
*/
int add_nodo_tail(int codigo)
{
struct TProduto *p = malloc (sizeof(struct TProduto));
if (!p)
return -1;
p->codigo = codigo;
p->next = NULL;
if (tail==NULL) {
/* lista vazia */
tail = head = p;
}else {
/*lista não vazia */
tail->next = p;
tail = p;
}
return 0;
}
/*
imprimir lista
*/
void print_list()
{
}
main()
{
int i;
head = tail = NULL;
print_list ();
for (i=0;i<5;i++)
add_nodo_tail(i);
print_list ();
}
Exercício 1
No exercício anterior:
- Implementar a função add_node_head()
- Implementar a função print_list()
- Implementar a função delete_node(int codigo)
Exercício 2
Considere um sistema de estoque de uma livraria representado por uma tabela conforme abaixo. Elabore as funções para adicionar, remover e listar um livro na/da tabela. Considere que uma entrada livre possui o ponteiro titulo igual a NULL.
#include <stdio.h>
#define TAM 10
struct tLivro {
char *titulo;
char *autor;
char *isbn;
float *preco;
int estoque;
};
typedef struct tLivro TLivro;
TLivro Livros[10]; /* iniciar a tabela com NULL */
TLivro *retornar_entrada_livre()
{
}
int adicionar_livro()
{
char aux_isbn[20];
TLivro *p;
/* Ler ISBN */
if(verificar_livro_existe(aux_isbn)==1)
return 0;
if((p=retornar_entrada_livre())==NULL)
return -1;
/* Ler os dados do livro pelo teclado e colocar na estrutura
apontada por p*/
}
/* retorna 0 se removido com sucesso e -1 caso contrário */
int remover_livro(char *isbn)
{
}
void imprimir_dados_livro(char *isbn)
{
}
main()
{
/* testar as funções aqui */
}
Exercício 3
Refazer o exercício anterior usando filas.
Exercício 5
Seja a seguinte estrutura:
struct tipo_carro {
char *marca;
char *modelo;
int potencia;
};
typedef tipo_carro tcarro;
Implpementar as funções abaixo:
/* cria dinamicamente uma estrutura,
preenche os dados dos campos
e retorna um ponteiro para a estrutura criada
Retorna NULL caso não consiga alocar área
*/
tcarro *ler_carro()
{
}
/*
recebe dois ponteiros para estruturas do tipo carro e
retorna -1 caso pelo menos um dos ponteiros seja NULL,
retorna 0 se os modelos forem iguais
e retorna 1 se os modelos forem diferentes */
int compara_modeloa(tcarro *p1, tcarro *p2)
{
}
/* libera a área da estrutura passada como parâmetro */
void deleta_estrutura(tcarro *p)
{
}
main()
{
/*testar as funções aqui */
/* criar dois carros */
/* comparar o modelo dos dois carros. Testar o retorno */
/* liberar a área das estruturas */
}
Referência complementar
http://www.ime.usp.br/~pf/algoritmos/aulas/lista.html
<< | Aula 20 | >> |
---|