Tipos e Estruturas de Dados

Lista de Exercícios - 2 - Listas 

1) Escreva funcoes para as operacoes remanescentes do 
TAD lista generalizadas. COnsidere uma versao para cada lista: contínua/estatica;
                         dinamica/sisplesmente encadaedada e dinamica/duplamente encadeada

- Retirar(Dado x, Lista *l)
- Substituir(int p, Dado novo, Lista *l)
- Dado Recuperar(int pos, Lista *l)


2)Escreva uma programa contendo um menu com as principais
funcoes (inserir, retirar, etc..) que permita realizar
as principais operacoes numa lista simplemente e duplamente encadeada.


 3)
// Esta função insere uma nova celula em uma 
// lista encadeada. A nova celula tem conteudo
// x e é inserida entre a celula apontada por 
// p e a seguinte. Supõe-se de p != NULL.

void insere (int x, celula *p)
{
   celula *nova;
   nova = mallocX (sizeof (celula));
   nova->conteudo = x;
   nova->prox = p->prox;
   p->prox = nova;
}

Seja a  seguinte versão da funcao insere, dada acima. Ela funciona? Justifique.

void insere (int x, celula *p) {
   celula nova;
   nova.conteudo = x;
   nova.prox = p->prox;
   p->prox = &nova; }


4) Escreva uma função que copie um vetor para uma lista encadeada. Faça duas versões: 
uma iterativa e uma recursiva.

5) Escreva uma função que copie uma lista encadeada para um vetor. Faça duas versões: 
uma iterativa e uma recursiva. 

6) Escreva uma função que faça uma cópia de uma lista dada.

7) Escreva uma função que concatena duas listas encadeadas (isto é, "amarra" a 
segunda no fim da primeira). 

8) Escreva uma função que conta o número de células de uma lista encadeada.

9) Escreva uma função que verifica se duas listas dadas são iguais, ou melhor, se 
têm o mesmo conteúdo. Faça duas versões: uma iterativa e uma recursiva. 

10) Escreva uma função que desaloca (função free) todos os nós de uma lista encadeada.  
Estamos supondo, é claro, que cada nó da lista foi originalmente alocado por malloc. 
IMplemente uma versão recursiva e outra nao recursiva. Analise qual as desvantagens 
da versão recursiva que voce implementou.


11) Escreva uma função que inverte a ordem das células de uma lista encadeada 
(o primeiro passa a ser o último, o segundo passa a ser o penúltimo etc.). 
Faça isso sem usar espaço auxiliar: somente altere os ponteiros. 
Dê duas soluções: uma iterativa e uma recursiva. 

12) Escreva uma função que intercale duas listas encadeadas ondenadas em uma terceira
lista, de forma a manter a ordenacao.