PR1022804 2025 1 AULA12

1 Listas Encadeada

OBJETIVOS

O aluno deverá conhecer:

• Listas encadeadas;
• Algumas aplicações.

METODOLOGIA

A aula será expositiva e dialogada, utilizando apresentação de texto base na Internet, onde serão mostrados exemplos testados programas no microcomputador do laboratório de informática.

INTRODUÇÃO

A Lista Encadeada nada mais é que uma representação de uma sequência de objetos, 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. Linked list ou lista encadeada e um tipo de estrutura de dados que contém um grupo de nós (conjunto de dados) interligados através de ponteiros, onde o ponteiro dentro da estrutura aponta para o próximo nó até que o ponteiro seja NULL indicando assim o fim da lista.

1.1 Estrutura de uma lista encadeada

Uma lista encadeada (linked list) é uma sequência de células onde 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 (struct) 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

1.2 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 dinamicamente,

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.

1.3 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; 
}

2 Exercícios

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(struct TProduto *ini)
{
      struct TProduto *p;
      for (p = ini->next; p != NULL; p = p->next)
      printf( "%d\n", p->codigo);
}
 
void main()
{
  int i;

  head = tail = NULL;

  for (i=0;i<5;i++)
     add_nodo_tail(i);

  print_list (head);
}

EXERCÍCIO 1

Para o exemplo 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 4

Seja a seguinte estrutura:

struct tipo_carro {
   char *marca;
   char *modelo;
   int  potencia;
};

typedef tipo_carro tcarro;

Implementar 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
 */
void 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_modelo(tcarro *p1, tcarro *p2)
{

}

/* libera a área da estrutura passada como parâmetro */
void deleta_estrutura(tcarro *p)
{

}

void main()
{
  /*testar as funções aqui */
  /* criar dois carros */
  /* comparar o modelo dos dois carros. Testar o retorno */
  /* liberar a área das estruturas */
}

2.1 EXEMPLO DA AULA

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct TFicha {
    int codigo;
    char nome[40];
    char fone[20];
    struct TFicha *prox;
} *cliente,*cabeca;

void Cadastrar(){
 struct TFicha *p =  malloc (sizeof(struct TFicha));
    printf("\nDigite codigo: ");
    scanf("%d",&p->codigo);
    printf("\nDigite Nome: ");
    fflush(stdin);
    scanf("%[^\n]",p->nome);
    printf("\nDigite Telefone: ");
    fflush(stdin);
    scanf("%[^\n]",p->fone);

    if (cliente==NULL) {
      /* lista vazia */
      cliente = cabeca = p;
   }else {
     /*lista não vazia */
       cliente->prox = p;
       cliente = p;
   }
}

void Imprimir(struct TFicha *ini) {
   struct TFicha *p;
   printf("\n\nCodigo  Nome                 Fone");
   for (p = ini; p != NULL; p = p->prox){
      printf( "\n%-d", p->codigo);
      printf( "\t%-20s", p->nome);
      printf( "\t%-20s", p->fone);
   }
}


void main(){

    cliente=NULL;
    int opcao;
    while (1){
        printf("\n\nEscolha:\n");
        printf("1 - Cadastrar\n");
        printf("2 - Imprimir\n");
        printf("3 - Sair\n");
        printf("-> ");
        scanf("%d",&opcao);
        switch (opcao)
        {
        case 1:
                Cadastrar(cliente);
                break;
            case 2:
                Imprimir(cabeca);
                break;
            case 3:
                return 0;
        }
    }
}

3 Referências

[1] http://www.ime.usp.br/~pf/algoritmos/aulas/lista.html

---