E19.0
Aquele exercício de que falei na aula.
Um vetor
v[p..r] está arrumado se existe j
em p..r tal que
v[p..j-1] ≤ v[j] < v[j+1..r] .
Escreva um algoritmo eficiente
que decida se v[p..r]
está arrumado.
Em caso afirmativo, o seu algoritmo deve devolver
o valor de j.
E19.1 Modifique o código abaixo de modo que ele receba um inteiro x e um vetor crescente v[p..r] e devolva um índice j tal que v[j-1] ≤ x < v[j]. (Dica: Comece por escrever o invariante do processo iterativo do código dado.)
// Esta função recebe um inteiro x e um vetor
// crescente v[0..n-1] com n >= 1. Ela devolve
// um índice j em 0..n tal que v[j-1] < x <= v[j].
int buscaBinaria (int x, int n, int v[]) {
int e, m, d;
e = -1; d = n;
while (e < d-1) {
m = (e + d)/2;
if (v[m] < x) e = m;
else d = m;
}
return d;
}
E19.2 Suponha dada um função interc (v, i, j, k) que recebe um vetor v[i..k-1] de inteiros tal que v[i..j-1] está em ordem crescente e v[j..k-1] está em ordem crescente e rearranja o vetor de modo que v[i..k-1] fique em ordem crescente. Qual o menor valor de j que interc deve aceitar? Qual o maior valor?
Use a função interc para escrever uma função mmmr (v, p, r) que rearranje um vetor v[p..r] de inteiros em ordem crescente.
E19.3 Imagine uma fila de números implementada em um vetor. Trate o vetor como uma variável global:
#define MAX 1000 int fila[MAX];
(Também trate como globais as variáveis que dão o estado da fila.) Escreva as três funções de manipulação da fila: entranafila(), filavazia(), saidafila().
Repita o execício com a fila implementada em uma lista encadeada.
E19.4 Este exercício trata de listas encadeadas sem cabeça que contêm números inteiros. Escreva uma função que faça a união de duas listas estritamente crescentes. A lista resultante deve ser ser estritamente crescente e deve ser construída com as células das duas listas dadas (portanto, a função não deve criar novas células).