Exercícios (Listas)
Contato
- Jean Paulo Martins (jeanmartins utfpr edu br)
- Sala 105, Bloco S (UTFPR - Campus Pato Branco)
Conteúdo
Exercícios
swap
Dadas duas listas encadeadas list* a e list* b. Implemente uma função que troque o conteúdo das listas.
void swap(list* a, list* b);
Exemplo:
Suponhamos como exemplo as listas encadeadas
a: 1 -> 2 -> 3 -> 4 -> NULL
b: 11-> 12 ->13 ->14 -> NULL
Após a aplicação de swap(a, b), elas se tornariam:
a: 11-> 12 ->13 ->14 -> NULL
b: 1 -> 2 -> 3 -> 4 -> NULL
splice
Dadas duas listas encadeadas list* a e list* b. Implemente uma função que insira todos os elementos de b em uma dada posição int pos. Os nós de b devem ser removidos neste processo, ou seja, ao final, b estará vazia.
void splice(list* a, list* b, int pos);
Exemplo:
Suponhamos como exemplo as listas encadeadas
a: 1 -> 2 -> 3 -> 4 -> NULL
b: 11-> 12 ->13 ->14 -> NULL
Após a aplicação de splice(a, b, 2), elas se tornariam:
a: 1 -> 2 -> ( 11-> 12 ->13 ->14 ) -> 3 -> 4 -> NULL
b: NULL
Os parenteses servem apenas para indicar a inclusão de b em a.
merge
Dadas duas listas encadeadas contendo números ordenados: list* a e list* b. Implemente uma função que insira todos os elementos de b na lista a de modo que ao final, a lista a ainda esteja ordenada. Os nós de b devem ser removidos neste processo, ou seja, ao final, b estará vazia.
void merge(list* a, list* b);
Exemplo:
Suponhamos como exemplo duas listas encadeadas ordenadas.
a: 1 -> 2 -> 12 -> 14 -> NULL
b: 3 -> 4 -> 11 -> 13 -> NULL
Após a aplicação de merge(a, b), elas se tornariam:
a: 1 -> 2 -> 3 -> 4 -> 11-> 12 ->13 ->14 -> NULL
b: NULL
DICA: é possível obter a lista final ordenada percorrendo ambas as listas apenas uma vez!
reverse
Dada uma lista encadeada qualquer list* a. Implemente uma função que retorne outra lista encadeada em que a ordem dos elementos de a esteja invertida.
list* reverse(list* a);
Exemplo:
Suponhamos como exemplo a listas encadeadas a seguir.
a: 1 -> 2 -> 12 -> 14 -> NULL
A aplicação de reverse(a) deve retornar uma lista:
b: 14 -> 12 -> 2 -> 1 -> NULL
removeif
Assim como demais operadores da linguagem C, uma função também pode ser passada como referência. Isto é, também podemos utilizar ponteiros para funções. Por exemplo, considere uma função que verifique se um dado número é par.
bool iseven(Type value) {
return value % 2 == 0;
}
Um ponteiro para uma função deste tipo, pode ser declarado da seguinte forma:
int (*functionPtr)(Type value);
functionPtr = &iseven;
Após a atribuição, functionPtr pode ser utilizado para verificar se um número é par.
bool par = (*functionPtr)(10);
Agora suponhamos que tivéssemos outra função de mesmo tipo, a qual apenas verifica se um dado número é igual a outro predefinido (989 neste exemplo).
bool is989(Type value) {
return value == 989;
}
Observe que apesar de diferentes, essas funções tem a mesma estrutura, ambas recebem um valor e retornam um bool. Assim, poderíamos atribui-las a functionPtr.
functionPtr = &is989;
Após a atribuição, functionPtr pode ser utilizada para verificar se um número é igual a 989.
Para exemplificarmos um tipo de situação onde ponteiros para função se tornam úteis. Consideremos o caso da função removeif, a qual recebe uma lista list* a e um ponteiro para função.
void removeif(list* a, bool (*fptr)(Type));
Como fptr pode apontar para diferentes funções (todas avaliam uma característica do valor recebido), removeif se torna mais genérica, e poderia ser utilizada para remover todos números pares, passando-se a função de comparação como argumento:
removeif(a, &iseven);
Ou, de forma análoga, poderia ser utilizada para remover todos nós com valor 989
removeif(a, &is989);
Dada essa descrição, implemente a função removeif.
unique
Dada uma lista qualquer list* a. Implemente uma função que remova nós com valores repetidos, deixando apenas um nó com cada valor.
void unique(list* a);
Exemplo:
Considere como exemplo a lista a seguir:
a: 1 -> 2 -> 3 -> 2 -> 10 -> 1 -> 3 -> 12 -> 10 -> NULL
Após a aplicação de unique(a), ela se tornaria
a: 1 -> 2 -> 3 -> 10 -> 12 -> NULL