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 dos caracteres + 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 a cadeia de caracteres  −9876 . (Veja a tabela ASCII.)

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 aparece 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

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 01011010.  No caso de 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.  Assim, para decidir se s é lexicograficamente menor que t basta fazer o seguinte. Procure a primeira posição, digamos k, em que as duas strings diferem. Se s[k] < t[k] então s é lexicograficamente menor que t.  Se s[k] > t[k] então t é lexicograficamente menor que s.  Se k não está definido então s e t são iguais ou uma é prefixo próprio da outra; no segundo caso, a string mais curta é lexicograficamente menor que a mais longa.

Uma lista de strings está em ordem lexicográfica se cada string da lista é 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.)  No caso de strings ASCII, a ordem lexicográfica é análoga à ordem em que palavras aparecem em um dicionário (embora coloque todas as letras maiúsculas antes de todas as minúsculas).  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

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 da seguinte maneira 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 recebe duas strings e compara as duas lexicograficamente. Ela 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;
}

(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. Nesse caso, a ordem lexicográfica entre as strings coincide com a ordem em que as cadeias apareceriam em um dicionário (pois a ordem  ... 0 .. 9 .. A B .. Z .. a b .. z ...  em que os caracteres aparecem na tabela ASCII é consistente com a ordem alfabética usual). Por exemplo, a seguinte sequência de palavras está em ordem lexicográfica:

abacaXi
abacate
abacates
abacaxi

Exercícios 3