Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Manipulação de strings

Este capítulo trata da conversão de strings em números e das operações básicas sobre strings implementadas na biblioteca string.

Strings que representam números

Uma cadeia de caracteres decimal é qualquer sequências de dígitos decimais (caracteres 0 a 9) possivelmente precedida do caractere + ou − .  Uma string decimal é qualquer string ASCII que representa uma cadeia de caracteres decimal.  Por exemplo, a string decimal  45 57 56 55 54 0  representa (veja a tabela ASCII) a cadeia de caracteres  −9876 .

Como converter uma string decimal no correspondente número do tipo int?  A função atoi (o nome é uma abreviatura de alphanumeric to int) da biblioteca stdlib recebe uma string decimal e devolve o correspondente int. Infelizmente, a função não verifica se a string representa um int válido (em particular, não verifica se a string é longa demais) e assim abre as portas para erros. Isso pode ser explorado por terceiros mal-intencionados, especialmente quando usado no tratamento de argumentos na linha de comando.  Diante isso, é melhor usar a função strtol, embora ela seja mais complexa.

A função  strtol  (o nome é uma abreviatura de string to long) da biblioteca stdlib converte uma string decimal no correspondente long int.  A função aceita não só strings decimais como também strings em outras bases: o terceiro argumento especifica a base.  Por exemplo,

strtol ("-9876", NULL, 10)

devolve o número −9876 e  strtol ("-9876", NULL, 16)  devolve −39030.  O significado do segundo argumento não será discutido por enquanto.

Exercícios 1

Ordem lexicográfica

Dizemos que um byte b é menor que um byte c se o número representado por b em notação binária é menor que o número representado por c.  Por exemplo, 01000001 é menor que 01000010.  No conjunto dos bytes cujo primeiro bit é 0, essa relação de ordem entre bytes é consistente com a ordem usual ('A' < 'B' < ... < 'Z') das letras no alfabeto ASCII conforme a tabela ASCII.

Agora que definimos a relação de ordem entre bytes, podemos tratar da relação de ordem entre strings.  Dizemos que uma string  s  é lexicograficamente menor que uma string  t  se o primeiro byte de s que difere do correspondente byte de t é menor que o byte de t.  Mais precisamente, s é lexicograficamente menor que t se

s[k] < t[k]

para o menor k tal que s[k] ≠ t[k]. Ademais, se tal k não existe então s e t são iguais ou uma é prefixo próprio da outra; no segundo caso, a string mais curta é considerada lexicograficamente menor que a mais longa.

Uma sequência de strings está em ordem lexicográfica se cada string da sequência é igual ou lexicograficamente menor que cada uma das seguintes. (Há quem diga ordem alfabética em lugar de ordem lexicográfica, mas isso não está correto.)  Por exemplo, a seguinte lista de strings está em ordem lexicográfica:

a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d

(Veja também o verbete Ordem lexicográfica no apêndice.)

Exercícios 2

A biblioteca string

A biblioteca string (não confunda com a biblioteca obsoleta strings) contém várias funções de manipulação de strings.  Segue uma descrição das funções mais importantes da biblioteca.

String length.  A função strlen recebe uma string e devolve o seu comprimento.  Essa função poderia ser escrita assim:

unsigned int strlen (char *s) {
   int k;
   for (k = 0; s[k] != '\0'; ++k) ;
   return k;
}

String copy.  A função strcpy recebe duas strings e copia a segunda (inclusive o byte nulo final) para o espaço ocupado pela primeira. O conteúdo original da primeira string é perdido. Não invoque a função se o comprimento da primeira string for menor que o da segunda.  (Buffer overflow é uma das mais comuns origens de bugs de segurança!)  Essa função poderia ser escrita assim:

void strcpy (char *s, char *t) {
   int i;
   for (i = 0; t[i] != '\0'; ++i) 
      s[i] = t[i];
   s[i] = '\0';
}

(Na verdade, a função strcpy não é do tipo void: ela devolve o seu primeiro argumento. Isso é útil em algumas situações, mas em geral o usuário só está interessado no efeito colateral da função e não no que ela devolve.)

A função strcpy pode ser usada como segue para obter um efeito semelhante ao do exemplo no início do capítulo Strings e cadeias de caracteres:

char s[10];
strcpy (s, "ABC");

String compare.  A função strcmp compara duas strings lexicograficamente, byte-a-byte. A função devolve um número estritamente negativo se a primeira string for lexicograficamente menor que a segunda, devolve 0 se as duas strings são iguais, e devolve um número estritamente positivo se a primeira string for lexicograficamente maior que a segunda.  Essa função poderia ser escrita assim:

int strcmp (char *s, char *t) {
   int i;
   for (i = 0; s[i] == t[i]; ++i)
      if (s[i] == '\0') return 0;
   unsigned char si = s[i], ti = t[i];
   return si - ti;
}

Embora os parâmetros da função sejam do tipo char *, a função se comporta como se eles fossem do tipo unsigned char *.  (Vale lembrar que o valor da expressão  si - ti  é calculado em aritmética int e não módulo 256.)

Se as strings s e t são ASCII, elas representam cadeias de caracteres ASCII e nesse caso a ordem lexicográfica entre as strings é derivada da ordem em que os caracteres aparecem na tabela ASCII. Por exemplo, a seguinte sequência de palavras ASCII está em ordem lexicográfica:

abacaXi
abacate
abacates
abacaxi

Se as strings não são ASCII (ou seja, se têm bytes maiores que 127), a ordem lexicográfica é mais difícil de entender e um tanto inútil. Supondo, como estamos, que a codificação é UTF-8, cada string representa uma cadeia de caracteres em que cada caractere é representado por 1, 2, 3 ou 4 bytes consecutivos. (No caso do português, cada letra básica é representada por 1 byte e cada letra com sinal diacrítico é representada por apenas 2 bytes.)  Como strcmp compara as strings byte-a-byte e não caractere-a-caractere, a sequência de palavras

abrir
abóbora
acordar
acácia
adaptar
aço
ação

está ordem lexicográfica. Aqui, abrir aparece antes de abóbora pois o primeiro dos dois bytes de ó, que vale 195, é maior que o único byte de r, que vale 114.

String collate.  Para comparar strings não-ASCII usa-se a função strcoll da biblioteca string. O comportamento dessa função depende do valor que a variável de ambiente LC_COLLATE tem no seu sistema. Partiremos do princípio de que nossos sistemas usam codificação UTF-8 e que o valor de LC_COLLATE é pt_BR.UTF-8.  (Digite locale no seu terminal para saber o valor dessa variável.)

A função strcoll recebe duas strings que representam cadeias de caracteres e verifica a posição relativa dessas cadeias numa ordem de dicionário que respeita as normas da língua local (determinada por LC_COLLATE). A função devolve um número estritamente negativo se a primeira cadeia vem antes da segunda, devolve zero se as duas cadeias são iguais, e devolve um número estritamente positivo se a primeira cadeia vem depois da segunda.  Por exemplo, a seguinte sequência de palavras está em ordem de dicionário:

abóbora
abrir
acácia
ação
aço
acordar 
adaptar

(Note que todas as variantes acentuadas e maiúsculas de cada letra são mantidas juntas.)  O seguinte exemplo em ordem de dicionário sugere que essa ordem não é uma simples ordem lexicográfica:

aquela
àquela
aquelas
àquelas
aquele
àquele
aqueles
àqueles 

Exercícios 3