MAC0122 Desenvolvimento de Algoritmos

Listas encadeadas

Este é um resumo da seção 3.3 (Linked Lists) e seção 3.4 (Elementary List Processing) do livro do Sedgewick.

Os programas desta página introduzem o conceito de lista encadeada (= linked list). Eis a estrutura de um nó (ou célula) da lista:

typedef struct node *link;
struct node { 
   int  item; 
   link next; 
};

Eis uma definição equivalente sem typedef:

struct node { 
   int          item; 
   struct node *next; 
};

Veja como podemos criar um nó z que contém 99 e aponta para si mesmo:

struct node z;
z.item = 99;
z.next = &z;

Eis uma operação análoga, que aloca o nó dinamicamente:

link x;
x = malloc(sizeof (struct node));
x->item = 99;
x->next = x;

O campo item é o conteúdo do nó. O campo next de cada nó é o endereço do nó seguinte da lista. O campo next do último nó da lista vale NULL. (Mas listas circulares não têm um último nó.)

Exercícios preliminares

Escreva um função que imprima o conteúdo (campo item) de uma lista encadeada que termina em NULL.
Suponha que lis é o endereço do primeiro node de uma lista encadeada que termina com NULL. Eu gostaria de somar 1 ao item de cada node. O trecho de código abaixo faz o serviço?
```
link t;
for (t = lis; t->next != NULL; t = t->next)
   t->item++;
```
Escreva uma função que receba uma lista encadeada terminada em NULL e devolva a soma das chaves dos nodes da lista. Escreva duas versões: uma iterativa e uma recursiva.
A função abaixo recebe uma lista encadeada ll e um número y. Ela deveria devolver o endereço do primeiro node da lista cujo item seja igual a y; se tal node não existe, a função deveria devolver NULL.
```
link procura (int y, link ll) {
   int achou;
   achou = 0;
   while (ll != NULL && achou == 0) {
      if (ll->item == y) achou = 1;
      ll = ll->next;
   }
   if (achou == 1) return ll;
   else return NULL;
}
```
A função funciona como deveria? Escreva uma nova versão da função que seja simples, curta e correta.
A função abaixo recebe uma lista encadeada ll e um número y. Ela deveria devolver o endereço do primeiro node da lista cujo item seja igual a y; se tal node não existe, a função deveria devolver NULL. A função produz o resultado esperado?
```
link procura (int y, link ll) {
   while (ll != NULL && ll->item != y)
      ll = ll->next;
   if (ll->item == y) return ll;
   else return NULL;
}
```
[Transformar lista em vetor] Escreva uma função que construa um vetor inteiro com o mesmo conteúdo de uma lista encadeada dada: o primeiro elemento do vetor deve ter o mesmo valor que o item do primeiro nó, o segundo elemento do vetor deve ter o mesmo valor que o item do segundo nó etc. Planeje com cuidado a entrada e a saída da sua função.

O problema de Josephus

O Programa 3.9 do Sedgewick ilustra a manipulação de uma lista encadeada circular. Segue uma versão ligeiramente modificada do programa:

#include <stdlib.h>

int main (int argc, char *argv[]) { 
   int N = atoi(argv[1]), M = atoi(argv[2]); 
   int last = josephus (N, M);
   printf("sobrou %d\n", last);
   return 0;
}

// A função josephus constroi uma roda de
// N pessoas numeradas de 1 a N. Em seguida,
// percorre a roda a partir de 1 eliminando
// cada M-ésima pessoa até que a roda seja
// reduzida a uma só pessoa. Devolve o
// número da pessoa que sobrou.

int josephus (int N, int M) { 
   int i;
   link t, x;

   x = t = malloc(sizeof (struct node));
   t->item = 1; 
   t->next = t;
   for (i = 2; i <= N; i++) { 
      x->next = malloc(sizeof (struct node));
      x = x->next;
      x->item = i;  
      x->next = t; // a lista é circular
   }
   while (x != x->next) {
      for (i = 1; i < M; i++) 
         x = x->next;
      // x->next será eliminado
      x->next = x->next->next;
   }
   return x->item;
}

A rigor, eu deveria ter usado a função free para liberar a memória alocada por malloc quando ela não é mais necessária.

(Vários livros do historiador Flavius Josephus podem ser encontrados no Projeto Gutenberg. Eu até copiei o The Antiquities of the Jews. É claro que isso é uma tradução do latin para o inglês: a língua inglesa não existia quando o livro foi escrito...)

Exercícios

Resolva o problema de Josephus usando um vetor em lugar de uma lista. Discuta as vantagens e desvantagens.
Implemente o crivo de Eratóstenes usando uma lista no lugar do vetor a. Discuta as vantagens e desvantagens.
Escreva um função que imprima o conteúdo (campo item) de uma lista encadeada circular como a usada no problema de Josephus.
[Sedg 3.24] Escreva uma função que, ao receber o endereço de um nó de uma lista encadeada circular, devolva o número de nós da lista.
[Sedg 3.27] Dados (os endereços de) nós x e t de uma lista encadeada circular, escreva um fragmento de código que desloque o nó seguinte a t para a posição que segue o nó x.
[Sedg 3.28] O programa 3.9 de Sedgewick faz duas vezes mais atribuições de links que o necessário porque insiste em manter uma lista circular no início de cada iteração durante a fase de construção da lista. Modifique o programa para que evitar esse trabalho extra.
[South Pacific Contest, 1993] Um problema de Josephus é de ordem M se as pessoas são eliminados da roda de M em M. Dados inteiros positivos N1 e N2, decidir qual o menor k tal que a pessoa k não será a sobrevivente de um problema de Josephus de ordem 15 qualquer que seja N no intervalo fechado [N1,N2]. (O problema pode não ter solução). Versão mais complicada: o processo de eliminação pode acontecer tanto no sentido crescente (ou seja, a contagem é 1, 2, 3, … quanto no sentido decrescente (ou seja, a contagem é N, N-1, N-2, … ).
[Transformar vetor em lista] Escreva uma função recursiva que receba um vetor de inteiros a[p..r] e construa uma lista encadeada com o mesmo conteúdo do vetor. A lista deve terminar com NULL (ou seja, não deve ser circular).

Inversão de lista

A função abaixo é cópia do Programa 3.10 do Sedgewick.

typedef struct node *link;
struct node { 
   int item; 
   link next; 
};

// A função reverse recebe o endereço do
// primeiro nó de uma lista encadeada cujo
// último nó aponta para NULL. A função
// inverte a lista (ou seja, faz com que o
// último nó seja o primeiro, o penúltimo
// seja o segundo etc.) e devolve o endereço
// do primeiro nó da nova lista.

link reverse (link x) { 
   link t, y = x, r = NULL;
   while (y != NULL) { 
      t = y->next; 
      y->next = r; 
      r = y; 
      y = t; 
   }    
   return r;
}

Invariante: No começo de cada iteração, imediatamente antes da comparação de y com NULL,

y é o começo de um segmento final da lista original e
r é o resultado da inversão do correspondente segmento inicial da lista original.

Exercícios

[Sedg 3.61] Escreva uma função que faça um serviço análogo ao do programa de busca de uma palavra em um texto mas use listas encadeadas para representar o texto e a palavra. Suponha que cada nó da lista contém um caracter. Para testar sua função, escreva uma main que encontre todas as ocorrências de uma palavra um texto. Melhor: troque todas as ocorrências da palavra por uma outra palavra (por exemplo, troque todas as ocorrências de excessão por exceção). As duas palavras devem ser fornecidas na linha de comando e o texto digitado no teclado (ou redirecionado de um arquivo). Escreva uma função auxiliar que leia o texto e transforme-o em lista encadeada. Faça testes interessantes. Para testar o seu programa com algum texto real, veja o Projeto Gutenberg.
[Roberts 12.7] Suponha que cadeias de caracteres são armazenadas em listas encadeadas com um caracter por nó. Escreva funções análogas a strlen, strcmp, strcpy e strcat da bibloteca string.

Construção de uma lista ordenada

O trecho de programa abaixo é uma cópia do Programa 3.11 do Sedgewick. Ele ilustra o conceito de lista-com-cabeça (ou lista encabeçada). O valor do campo item do nó-cabeça é ignorado.

struct node heada, headb;
link t, u, x, a = &heada, b;

// O trecho de programa abaixo produz uma
// lista encadeada cujos nós estão em ordem
// crescente do campo item. A lista tem N+1
// nós. O primeiro nó é a cabeça (= head) da
// lista e o seu campo item é ignorado (a
// presença de um nó-cabeça simplifica a
// manipulação da lista vazia). Os valores
// do campo item são inteiros aleatórios no
// intervalo [0..999].

   for (i = 0, t = a; i < N; i++) {
      t->next = malloc(sizeof *t); 
      t = t->next; 
      t->next = NULL;
      t->item = rand() % 1000;
   }

   b = &headb; 
   b->next = NULL;
   for (t = a->next; /*A*/ t != NULL; t = u) { 
      u = t->next;
      for (x = b; x->next != NULL; x = x->next)
         if (x->next->item > t->item) break;
      t->next = x->next; 
      x->next = t; 
   }

Comentário: De acordo com Roberts, a maneira de gerar inteiros aleatórios que Sedgewick usa acima não é boa. É melhor copiar o código da função RandomInteger.

Invariante: No começo de cada iteração do segundo processo iterativo, ou seja, a cada passagem pelo ponto A,

t é o começo de um segmento final da lista a;
b é o começo de uma lista encadeada encabeçada que termina em NULL;
b está em ordem crescente, ou seja, x->item ≤ x->next->item para cada x;
b é uma permutação do segmento inicial de a que vai até o nó anterior a t.

Acho que a segunda parte do código ficaria mais legível assim:

   b = &headb; 
   b->next = NULL;
   t = a->next;
   while (/*A*/ t != NULL) {
      x = b; 
      while (x->next != NULL && x->next->item <= t->item)
         x = x->next;
      u = t->next;
      t->next = x->next; 
      x->next = t; 
      t = u;
   }

Exercícios

Escreva uma versão do código acima que não use nó cabeça-de-lista.
[Sedg 3.34] Suponha que x é o (endereço do) primeiro nó de uma lista encadeada não circular (ou seja, o último nó aponta para NULL). Escreva um fragmento de código que encontre o nó que tem o maior item e transfira esse nó para o fim da lista.
[Sedg 3.38] Escreva uma função que receba o endereço do primeiro nó de uma lista encadeada não circular (ou seja, o último nó aponta para NULL), faça uma cópia da lista, e devolva o endereço do primeiro nó da cópia.
[Sedg 3.39, simplificada] Escreva uma função que receba o endereço (do primeiro nó) de uma lista encadeada não circular (ou seja, o último nó aponta para NULL) e retire da lista todos os nós cujo item vale 0. Faça duas versões: na primeira, o primeiro nó da lista é um nó-cabeça (o valor de item é irrelevante); na segunda, a lista não tem nó-cabeça (sua função deve devolver algo nesse caso?).
[Sedg 3.47] Os nós de uma lista encadeada são usualmente alocados por meio da função malloc. Em geral, quando um nó é retirado da lista ele pode ser liberado, por meio da função free, para que o correspondente espaço de memória possa ser reaproveitado. Escreva uma função que, ao receber o endeço de uma lista não circular (o último nó aponta para NULL), libera todos os nós da lista.
[Roberts 12.6] Suponha dada uma lista encadeada primária cada um de cujos nós aponta para uma outra lista encadeada cujos nós contêm caracteres. Exemplo: o primeiro nó da lista primária aponta para uma lista que contém 'A' e 'B', nessa ordem (a lista termina com NULL); o segundo nó da lista primária aponta para uma lista que contém 'C'; o terceiro e último nó aponta para uma lista que contém 'D' e 'E', nessa ordem. Agora escreva uma função que receba uma lista do tipo primário e amarre todas as listas secundárias, uma após a outra, em um única lista. No exemplo acima, o resultado seria uma lista que contém 'A', 'B', 'C', 'D' e 'E', nessa ordem. Sua função não deve usar malloc.

Veja minhas notas de aula sobre listas encadeadas.

Mais exercícios

[Remover zeros] Suponha dada uma lista encadeada que terminada com NULL e não tem nó-cabeça. Suponha que os nós da lista têm a forma
```
typedef struct node *link;
struct node { int item; link next; } ;
```
Escreva uma função que remova da lista todos os nós que têm item == 0 sem alterar a ordem relativa dos demais nós. Escreva duas versões da função: uma iterativa e uma recursiva.
[Sedg 3.53-3.54] Dado um conjunto de nós, suponha que cada um aponta para si mesmo ou para um outro nó (ou seja, nenhum nó aponta para NULL). Mostre que se partirmos de qualquer nó e seguirmos os ponteiros acabaremos necessariamente em um ciclo. Escreva um fragmento de código que receba o endereço de um dos nós e calcule o número de diferentes nós que serão visitados ao seguir os ponteiros. O seu código não deve modificar os nós e não deve usar mais que uma quantidade fixa de memória auxiliar.
[Encontrar o ponto médio de uma lista] Escreva uma função que receba uma lista encadeada e devolve o endereço de um nó que esteja o mais próximo possível do meio da lista. Faça isso sem contar explicitamente o número de nós da lista.
Escreva e teste uma versão mais rápida do programa que conta o número de pares de pontos próximos em um quadrado unitário. A ideia é subdividir o quadrado unitário em quadrados menores de tal forma que pontos próximos estejam no mesmo sub-quadrado ou em sub-quadrados vizinhos. O problema está resolvido no livro do Sedgewick; resta entendê-lo, adaptá-lo e testá-lo. O código do Sedgewick está espalhado por várias páginas do livro. A parte principal é o Programa 3.20 (a two-dimensional array of lists).

Um esclarecimento sobre o jargão que se usa ao falar de ponteiros

Suponha que temos nós do tipo node:

typedef struct node *link;
struct node { 
   int item; 
   link next; 
};

Suponha também que pp é um ponteiro para um nó do tipo que acabamos de definir.

struct node meu_nó;
link pp;
pp = &meu_nó;

Poderíamos dizer que o valor da variável pp é o endereço do nó. Mas é mais simples dizer

pp é o endereço do nó.

Essa abreviatura é exatamente a mesma que se usa em frases do tipo se t é a temperatura no interior da geladeira então...; não se diz se o valor da variável t é a temperatura no interior da geladeira.

No mundo da liguagem C, usa-se uma abreviatura ainda mais radical: diz-se simplemente

pp é o nó.