Listas encadeadas exercicios

Estruturas de Dados

Listas Encadeadas – Exercícios

29/5/2006

(c) Dept. Informática - PUC-Rio

1

Referências
Waldemar Celes, Renato Cerqueira, José Lucas Rangel,
Introdução a Estruturas de Dados, Editora Campus
(2004)
Exercícios Parte II (pág. 214)

29/5/2006

(c) Dept. Informática - PUC-Rio

2

Exercícios Parte II
2.6. Considerando listas de valores inteiros, implemente uma função que receba como parâmetro uma lista encadeada e um valor inteiro n e divida a lista em duas, de tal forma que a segunda lista comece no primeiro nó logo após a primeira ocorrência de n na lista original. A figura a seguir ilustra essa separação:

Essa função deve obedecer ao protótipo:
Lista* separa (Lista* l, int n);

A função deve retornar um ponteiro para a segunda sub-divisão da lista original, enquanto l deve continuar apontando para o primeiro elemento da primeira subdivisão da lista.
29/5/2006

(c) Dept. Informática - PUC-Rio

3

Exercícios Parte II
/* função separa */
Lista* separa (Lista* l, int n)
{
Lista* p; /* variável auxiliar para percorrer a lista */
Lista* q; /* variável auxiliar para nova lista */ for (p = l; p != NULL ; p = p->prox) if (p->info == n)
{q = p->prox; p->prox = NULL; return q;} return NULL;
}

29/5/2006

(c) Dept. Informática - PUC-Rio

4

2004.1 – P2 – Questão 1

29/5/2006

(c) Dept. Informática - PUC-Rio

5

2004.1 – P2 – Questão 1
/* concatena modificando l1 */
Lista* concatena (Lista* l1, Lista* l2)
{
Lista* p; /* variável auxiliar para percorrer a lista */
Lista* q; /* variável auxiliar para criar a nova lista */ if (l1 == NULL) return l2; p = l1; do { q = p; p = p->prox;
} while(p != NULL); q->prox = l2; return l1;
}

29/5/2006

(c) Dept. Informática - PUC-Rio

6

2004.1 – P2 – Questão 2

29/5/2006

(c) Dept. Informática - PUC-Rio

7

2004.1 – P2 – Questão 2
Lista* constroi (int n, int* v)
{
Lista* p; /* variável auxiliar para percorrer a lista