Escreva uma função que recebe duas cadeias de caracteres e verifica se elas são iguais. Sua função deve devolver o valor -1 para indicar que a primeira cadeia é lexigraficamente menor que a segunda. O valor 1 deve ser devolvido quando a segunda cadeia é menor que a primeira. Quando as duas cadeias forem iguais, a função deve devolver zero.
Passo 1
O que o enunciado pede (em linguagem bem clara):
- Escrever uma função que recebe duas cadeias de caracteres (vamos chamar de
e ). - A função deve devolver:
-
se for lexicograficamente menor que . -
se for lexicograficamente maior que . -
se e forem exatamente iguais.
-
Informações relevantes fornecidas (assunções usuais que vamos usar):
- As entradas são duas strings (cadeias de caracteres). Vou tratar cada string como uma sequência de caracteres terminada por um caractere nulo quando fizer a implementação em C.
- “Lexicograficamente” significa comparar caractere a caractere da esquerda para a direita; a primeira diferença determina a ordem. Se uma é prefixo estrito da outra, a mais curta é considerada menor.
- Não foi pedida uma solução com regras de ordenação linguística ou Unicode avançada — aplicarei a comparação por códigos de caractere (por exemplo, por valores ASCII/Unicode code unit).
Passo 2
O que significa “comparar lexicograficamente” — explicação didática e intuitiva:
- Imagine duas palavras numa lista de dicionário. Para saber qual vem primeiro, compara-se o primeiro caractere de cada palavra; se forem iguais, passa-se ao segundo, e assim por diante.
- Formalizando: suponha que os caracteres nas posições
sejam e . Se (pelo valor numérico do código do caractere), então . Se , então . Se todos os caracteres testados são iguais até que ambas terminem, então . - Exemplo rápido e concreto:
“casa” e “caso”. - Comparando letra a letra: ‘c’ = ‘c’, ‘a’ = ‘a’, ‘s’ = ‘s’, mas no quarto caractere ‘a’ < ‘o’ (pelo código), então
e a função deve devolver .
- Comparando letra a letra: ‘c’ = ‘c’, ‘a’ = ‘a’, ‘s’ = ‘s’, mas no quarto caractere ‘a’ < ‘o’ (pelo código), então
Passo 3
Algoritmo passo a passo (o que você deve fazer na prova):
- Percorrer as duas strings ao mesmo tempo com um índice
começando em . - Em cada passo, pegar
e . - Se
e forem diferentes: - Se
então retornar . - Caso contrário (isto é,
) retornar .
- Se
- Se
e forem iguais, incrementar e repetir. - Se chegar ao fim de ambas as strings ao mesmo tempo (ambos os caracteres são o terminador nulo), retornar
. - Se uma string terminar antes da outra (por exemplo,
termina e continua), então a que terminou primeiro é menor; nesse caso retornar se terminou antes, ou se terminou antes.
Observações práticas importantes:
- Em C usar comparação de valores de tipo
unsigned charao convertercharpara evitar problemas com caractere com bit de sinal. - Em linguagens de nível alto (Python, Java, etc.) a comparação de strings muitas vezes já tem suporte; mas no exame pode ser pedido que se implemente manualmente, então saber fazer caractere a caractere é essencial.
Passo 4
Complexidade e justificativa rápida (o que escrever numa prova para ganhar pontos):
- Tempo: no pior caso é necessário comparar cada posição até o fim da string — isto é
, onde é o comprimento da menor das duas strings. - Espaço:
extra (apenas índice e variáveis temporárias). - Essas anotações mostram que a solução é eficiente.
Passo 5
Cuidados e casos de borda que aparecem em provas (e como tratá-los):
- Strings vazias: se
e/ou forem vazias, o algoritmo acima funciona — a string vazia é menor que qualquer string não vazia. - Sensibilidade a maiúsculas/minúsculas: ‘A’ e ‘a’ têm códigos diferentes; se o enunciado exigir comparação case-insensitive, é preciso normalizar (por exemplo convertendo para minúsculas) antes de comparar.
- Unicode: comparar por code unit (por exemplo UTF-8 bytes ou UTF-16 code units) não é o mesmo que comparar por ordem linguística. Para a maioria dos exercícios básicos use comparação por unidades de código.
- Em C, cuidado com ponteiros nulos (
NULL) — em exercícios normalmente strings são válidas; se houver chance deNULL, cheque explicitamente.
Passo 6
Exemplos manuais (faça na prova para checar raciocínio):
- Exemplo 1:
“abc”, “abd”. - i=0: ‘a’=‘a’ → continua.
- i=1: ‘b’=‘b’ → continua.
- i=2: ‘c’ < ‘d’ → retorna
.
- Exemplo 2:
“teste”, “tes”. - i=0,1,2: iguais; i=3: ‘t’ vs terminador nulo de
→ terminou primeiro, então → retorna .
- i=0,1,2: iguais; i=3: ‘t’ vs terminador nulo de
- Exemplo 3:
“”, “” → retorna .
Passo 7
Como apresentar a solução na prova (comentário final)
- Escreva em pseudocódigo o laço de comparação e as três condições de retorno (
, , ); explique brevemente a complexidade e trate casos de borda (strings vazias, sensibilidade a maiúsculas). - Se pedirem código, implemente exatamente o que descreveu; siga as boas práticas da linguagem (por exemplo uso de
unsigned charem C).
Resposta
/* Função em C que compara duas strings lexicograficamente.
Retorna:
-1 se s1 < s2
0 se s1 == s2
1 se s1 > s2
*/
#include <stddef.h>
int compare(const char *s1, const char *s2) {
size_t i = 0;
while (s1[i] != '\0' && s2[i] != '\0') {
unsigned char c1 = (unsigned char) s1[i];
unsigned char c2 = (unsigned char) s2[i];
if (c1 < c2) return -1;
if (c1 > c2) return 1;
i++;
}
/* Se saímos do laço, pelo menos uma string terminou */
if (s1[i] == '\0' && s2[i] == '\0') return 0;
if (s1[i] == '\0') return -1;
return 1;
}