E18.1 Onde estão os erros? Escreva uma documentação melhor.
// Recebe um vetor v com n elementos // e rearranja o vetor em ordem crescente // usando o algoritimo Mergesort. // Consome tempo proporcional a 3 n log n comparações. // void mrg_srt (int v[], int n);
E18.2 Por que esse código é feio? Escreva versão melhor.
int verifica (int v[], int n) {
int i, anterior = v[0], vai = 1;
for (i = 1; i < n && vai; i++) {
if (anterior > v[i]) vai = 0;
anterior = v[i];
}
return vai;
}
E18.3 Por que esse código é feio? Escreva versão melhor.
int verifica (int v[], int n) {
int i;
if (n > 1) {
for (i = 1; i < n; i++)
if (v[i-1] > v[i]) return 0;
}
return 1;
}
E18.4 Escreva a expressão infixa equivalente à seguinte expressão polonesa:
A B C D E F - * - G H * - * + I 3 * -
E18.5 Digamos que nosso alfabeto contém apenas as letras a, b e c. Escreva uma função que determine se uma dada string X sobre nosso alfabeto é ou não da forma WcM onde W é uma sequência de letras que só contém a e b e M é o inverso de W (ou seja, M é W lido de trás pra frente). Dica: Suponha que você tem à sua disposição as funções usuais de manipulação de pilhas (empilha, desempilha e testa se a pilha está vazia).
E18.6 (Inspirado na pilha de execução de programas e na diretiva #include do compilador gcc.) Começamos com um exemplo. Suponha dadas as seguintes listas de palavras:
0: banana batata 1: cadeira 2: camisa #0 calças #1 meias 3: gato #2 #0 4: #0 avião #2
Queremos que o comando execute #4
imprima a lista de palavras
banana batata avião camisa banana batata calças cadeira meias
Escreva uma função não-recursiva exec que faça isso. A função recebe um vetor v[0..n-1] de listas encadeadas (sem cabeça) cada uma de cujas cujas células
struct cx {
char *str;
struct cx *prox;
};
typedef struct cx celula;
contém uma palavra. A função também recebe um índice k no intervalo 0..n-1 e tem a missão de imprimir a lista de palavras v[k] interpretando as palavras que começam com # de maneira especial. Se uma palavra str começa com #, todos os caracteres depois de # são dígitos decimais e a palavra deve ser substituída pela lista de palavras v[atoi(str+1)], recursivamente.
Dica: Use uma pilha de ponteiros para células. Cada ponteiro contém o endereço da próxima célula a ser processada.