(a) O que é ordem lexicográfica? (b) Na linguagem de programação C, como é determinada essa ordem? (c) Esboce um algoritmo que explica como é realizada a comparação lexicográfica entre duas strings.
Passo 1
Você me pediu três coisas claras:
(a) definição do que é ordem lexicográfica;
(b) como essa ordem é determinada na linguagem C;
(c) um esboço de algoritmo que explique como a comparação lexicográfica entre duas strings é feita.
Não há outros dados no enunciado — vou assumir que trabalhamos com strings típicas em C: sequências de bytes terminadas por um caractere nulo
(a) definição do que é ordem lexicográfica;
(b) como essa ordem é determinada na linguagem C;
(c) um esboço de algoritmo que explique como a comparação lexicográfica entre duas strings é feita.
Não há outros dados no enunciado — vou assumir que trabalhamos com strings típicas em C: sequências de bytes terminadas por um caractere nulo
'\0'.Passo 2
O que é, na prática, ordem lexicográfica — explicação intuitiva e relaxada.
Imagine o dicionário: palavras são ordenadas comparando letra por letra. A primeira letra diferente decide quem vem antes; se uma palavra é prefixo da outra (por exemplo, “casa” e “casal”), a mais curta vem primeiro. Isso é exatamente a ideia da ordem lexicográfica: comparar sequências elemento a elemento usando uma ordem já definida sobre os símbolos (por exemplo, a ordem das letras).
Imagine o dicionário: palavras são ordenadas comparando letra por letra. A primeira letra diferente decide quem vem antes; se uma palavra é prefixo da outra (por exemplo, “casa” e “casal”), a mais curta vem primeiro. Isso é exatamente a ideia da ordem lexicográfica: comparar sequências elemento a elemento usando uma ordem já definida sobre os símbolos (por exemplo, a ordem das letras).
Passo 3
Definição formal (com notação simples).
Seja um alfabeto com ordem total (ou seja, para quaisquer dois símbolos e
podemos dizer se
,
ou
). Seja cada string uma sequência de símbolos:
e
. Dizemos que
lexicograficamente se, e somente se, existe um índice
tal que:
Seja um alfabeto com ordem total (ou seja, para quaisquer dois símbolos
e
ou se
é prefixo de
e
.
Aqui: é o
-ésimo símbolo de
;
e
são os comprimentos de
e
.
Aqui:
Passo 4
Exemplos concretos para ficar mais firme na ideia.
- Comparando “abc” e “abd”: as primeiras duas letras são iguais, na terceira temos ‘c’ < ‘d’, portanto “abc” < “abd”.
- Comparando “ab” e “abc”: todas as letras de “ab” coincidem com as iniciais de “abc”, e “ab” é mais curta, logo “ab” < “abc”.
- Comparando “Apple” e “apple” em um ordenamento baseado em ASCII: ‘A’ tem código
e ‘a’ tem código , então “Apple” < “apple”.
Passo 5
Agora: como isso se traduz em C (parte b) — princípios gerais.
Em C, strings são arrays de bytes terminados por
Em C, strings são arrays de bytes terminados por
'\0'. A comparação lexicográfica padrão (como a feita por strcmp) ocorre olhando byte a byte, do início ao fim, até:- encontrar dois bytes diferentes, caso em que a ordem é decidida pelo valor numérico desses bytes na tabela de caracteres da execução (normalmente ASCII ou outra tabela de execução), ou
- encontrar o caractere nulo
'\0'em ambas as strings (significando igualdade), ou - encontrar
'\0'numa das strings enquanto a outra continua (a mais curta — cujo'\0'apareceu primeiro — é considerada menor).
Importante notar alguns detalhes práticos:
- O conjunto de códigos (ASCII, EBCDIC, etc.) é implementacional; na prática é quase sempre ASCII/UTF-8 na maioria dos sistemas modernos, mas o C usa a “tabela de execução” do ambiente.
- Funções como
strcmptratam os bytes; não fazem comparação sensível a regras de locale (acentos, regras linguísticas) — para isso existem funções de collation específicas (ex.: em bibliotecas externas). - Problemas com
charassinado: muitos implementadores convertem os bytes paraunsigned charantes de compará-los para evitar efeitos de sinal em valores maiores que.
Passo 6
Exemplo numérico em C (detalhando os passos):
Comparar
Comparar
s = "A" e t = "a":- Ler primeiro byte de
s: caractere'A'com código numérico geralmente. - Ler primeiro byte de
t: caractere'a'com código numérico geralmente. - Como
, sé menor quet. A funçãostrcmp(s,t)retornaria um valor negativo (por exemplo,) indicando s < t.
Passo 7
Esboço de algoritmo (passo a passo) — versão didática e fácil de entender (parte c).
Objetivo do algoritmo: dizer se duas strings e
são “menor”, “iguais” ou “maior” lexicograficamente. Vou usar terminologia próxima de C, mas simples.
Objetivo do algoritmo: dizer se duas strings
Algoritmo em palavras:
- Comece no índice
. - Enquanto nem
nem for '\0':
a. Se, então comparar os códigos numéricos de e : se então ; senão . Interrompa.
b. Se, incremente e continue. - Se saiu do laço porque ambos
s[i]et[i]são'\0', então. - Se saiu do laço porque um deles é
'\0'e o outro não, a string cujo'\0'apareceu primeiro (ou seja, a mais curta) é a menor.
Passo 8
Esboço em pseudocódigo bem claro (estilo amigo que explica cada linha)
pseudocódigo:
- i ← 0
- enquanto true faça
- c1 ← byte em s[i]
- c2 ← byte em t[i]
- se c1 = c2 então
- se c1 = ‘\0’ então retorne “iguais” // ambos terminaram ao mesmo tempo
- i ← i + 1 // continuar comparando próximo caractere
- senão // c1 ≠ c2
- se (unsigned char) c1 < (unsigned char) c2 então retorne “s < t”
- senão retorne “s > t”
- fim enquanto
Explicação das escolhas no pseudocódigo:
- Casting para
(unsigned char)evita problemas quandocharé tratado como valor negativo pelo compilador. Assim a comparação baseia-se nos valores de 0 a 255 dos bytes. - A complexidade é linear:
onde e são comprimentos das strings, porque paramos na primeira diferença ou no fim.
Passo 9
Traço um exemplo passo a passo com o algoritmo (para fixar):
Comparar
Comparar
s = "cas" e t = "casa":-
: s[0]='c',t[0]='c'iguais → i=1. -
: s[1]='a',t[1]='a'iguais → i=2. -
: s[2]='s',t[2]='s'iguais → i=3. -
: s[3]='\0',t[3]='a'→ ‘\0’ < ‘a’, logos < t. Isso confirma a regra do prefixo.
Passo 10
Notas práticas e armadilhas para a prova (dicas rápidas e úteis):
- Lembre-se: strcmp e afins são byte-wise e não seguem regras de idioma. Para ordenação “linguística”, use bibliotecas de collation.
- Sempre considere a representação dos caracteres (ASCII/UTF-8): em UTF-8, caracteres acentuados ocupam vários bytes — comparação byte a byte não corresponde necessariamente à ordenação por carácter ou por aparência.
- Em código C real, a implementação clássica de
strcmpcostuma retornar um inteiro negativo, zero ou positivo; muitas implementações usam a expressão(unsigned char)c1 - (unsigned char)c2ou simplesmenteif (c1 < c2) return -1; if (c1 > c2) return 1;.
Resposta
(a) Ordem lexicográfica é a ordem de dicionário: comparar duas sequências símbolo a símbolo; a primeira posição em que differem decide a ordem, e se uma é prefixo da outra a mais curta vem primeiro.
(b) Em C a ordem é determinada comparando os bytes das strings um a um usando os valores numéricos dos caracteres na tabela de execução (normalmente ASCII); a comparação pára na primeira diferença ou no
(c) Algoritmo (esboço): percorrer índices comparando
e
; se
então decidir pela ordem conforme os valores numéricos (por exemplo, retornar
se
,
se
); se ambos chegarem a
(b) Em C a ordem é determinada comparando os bytes das strings um a um usando os valores numéricos dos caracteres na tabela de execução (normalmente ASCII); a comparação pára na primeira diferença ou no
'\0'; a comparação é byte-wise (não sensível a locale) e normalmente os bytes são tratados como unsigned char para evitar problemas de sinal.(c) Algoritmo (esboço): percorrer índices
'\0' simultaneamente retornar “iguais”; se um chegar a '\0' e o outro não, a string cujo '\0' aparece primeiro é menor.