E15.1 Digamos que uma LESC é uma lista encadeada sem cabeça que contém uma sequência crescente de números inteiros. Escreva uma função que intercale duas LESCs dadas, produzindo assim uma terceira LESC. Sua função não deve alocar novas células na memória, mas reaproveitar as células das duas listas dadas. Faça duas versões: uma recursiva e uma iterativa. Suponha que as células das listas são do tipo cell:
typedef struct cell *link;
struct cell {int item; link prox;};
E15.2 Escreva uma versão do algoritmo Mergesort que rearranje uma lista encadeada sem cabeça em ordem crescente (ou seja, transforme a lista dada em uma LESC). Use a função do exercício E15.1. Faça duas versões: uma recursiva e uma iterativa. Suponha que as células das listas são do tipo cell:
typedef struct cell *link;
struct cell {int item; link prox;};
DICA: Para encontrar um ponto próximo ao meio de uma lista encadeada, percorra a lista com dois ponteiros: um anda de célula em célula enquanto o outro anda de duas em duas.
E15.3 Repeteco de E14.5: Escreva uma função ff que receba um vetor v[1..k] tal que v[1..k-1] é um heap e transforme v[1..k] em heap. Sua função deve fazer no máximo 2 log k comparações entre elementos do vetor. (Esse tipo de função é conhecido como FixUp ou Swim. Ao contrário da função peneira estudada na aula, ela conserta o heap subindo, ou seja, repetindo a operação f = f/2.)
Depois, use ff para construir uma função que transforme qualquer vetor v[1..m] em heap. Sua função deve fazer no máximo 2 m log m comparações entre elementos do vetor.