MAC121 - Lista 1 - Listas encadeadas

Para vários exercícios abaixo, você pode escrever tanto uma versão recursiva como uma versão não recursiva da função. Tente fazer as duas versões para praticar recursão além de manipulação de listas encadeadas.

Escreva uma função com protótipo
```
int soma (Celula *ini);
```
que recebe uma lista encadeada ini de números inteiros e devolve a soma dos números na lista. Suponha que a lista encadeada não tem cabeça de lista.

Escreva uma função com protótipo
```
int conta (apont p, int x);
```
que recebe uma lista encadeada ini de números inteiros e um inteiro x, e devolve o número de vezes que x aparece na lista. Suponha que a lista encadeada não tem cabeça de lista.

Considere as declarações
```
#define FALSE 0
```
```
#define TRUE  1
```
Escreva uma função com protótipo
```
int crescente (Celula *ini);
```
que recebe uma lista encadeada ini de números inteiros e devolve TRUE se a lista está em ordem crescente e FALSE caso contrário. Suponha que a lista encadeada não tem cabeça de lista.

Escreva uma função com protótipo
```
void acrescenta (Celula *ini, int delta);
```
que recebe uma lista encadeada ini de números inteiros e soma delta no conteúdo de cada elemento da lista, removendo elementos cujo resultado da soma seja nulo. Suponha que a lista encadeada tem cabeça de lista.

Escreva uma função com protótipo
```
void remove_todos (Celula *ini, int x);
```
que remove todas as cópias de x da lista encadeada apontada por ini. Suponha que a lista tem cabeça de lista.

Escreva uma função
```
void tira_repetição (Celula *ini);
```
que remove todos os elementos repetidos da lista encadeada ini, deixando apenas uma cópia de cada um. Suponha que a lista tem cabeça. Utilize a função do exercício anterior mesmo que você não a tenha feito.

Um conjunto de números inteiros pode ser armazenado em uma lista encadeada. Por representarem conjuntos, tais listas não têm elementos repetidos. Escreva uma função com protótipo
```
Celula *interseccao (Celula *ini1, Celula *ini2);
```
que recebe duas listas encadeadas ini1 e ini2, sem cabeça de lista, cada uma contendo um conjunto de números inteiros, e devolve uma nova lista encadeada sem cabeça, com a interseção dos dois conjuntos. Você não deve destruir as listas dadas. Você deve alocar novas células para compor a lista resultante.
Escreva uma função com protótipo
```
Celula *uniao (Celula *ini1, Celula *ini2);
```
que recebe duas listas encadeadas ini1 e ini2, sem cabeça de lista, cada uma contendo um conjunto de números inteiros, e devolve uma nova lista encadeada sem cabeça, com a união dos dois conjuntos. (Não se esqueça que sua lista devolvida não deve ter repetições, para representar corretamente um conjunto.) Você não deve destruir as listas dadas. Você deve alocar novas células para compor a lista resultante.
As suas funções ficariam mais simples se as listas tivessem cabeça?

Refaça o exercício acima supondo que as listas dadas estejam ordenadas em ordem crescente. A lista devolvida agora deve também estar ordenada.

Escreva uma função com protótipo
```
void ordena (Celula *ini);
```
que recebe uma lista encadeada ini com inteiros e rearraja essa lista de forma que ela fique em ordem crescente, devolvendo o início da lista resultante. Suponha que a lista tem cabeça. Não troque o conteúdo das células. Apenas altere, quando necessário, os apontadores para ordenar a lista (imagine que as informações guardadas em cada célula da lista são muitas e que seria muuuuito caro trocar o conteúdo de duas células).