Manipulação de strings

[scissors cut tape]

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

Sumário:

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 −9876strtol ("-9876", NULL, 16)  devolve −39030.  O significado do segundo argumento não será discutido por enquanto.

Exercícios 1

  1. A-to-i.  Escreva uma função que imite comportamento de atoi mas verifica se a string dada é válida. Se a string for longa demais, descarte os últimos dígitos.)
  2. I-to-a.  Escreva uma função itoa (o nome é uma abreviatura de int to alphanumeric) que receba um inteiro n e devolva a string decimal que represente n. Por exemplo, o inteiro −123 deve ser convertido na string "-123".
  3. De string binária para int.  Escreva uma função que receba uma string de '0's e '1's (ou seja, bytes 4849), interprete essa string como um número natural em notação binária e devolva o correspondente int. Por exemplo, a string "1111011" deve ser convertida no inteiro 123. (Se a string for longa demais, descarte os últimos dígitos.)
  4. De int para string binária.  Escreva uma função que receba um int n e devolva a string de '0's e '1's (ou seja, bytes 4849) que represente n em notação binária. Por exemplo, o int 123 deve ser convertido na string "1111011".
  5. Escreva uma função para converter uma string decimal na correspondente string hexadecimal.  Para testar a função, escreva um programa que receba uma cadeia de caracteres decimal pela linha de comando e imprima a correspondente cadeia hexadecimal.  Repita o exercício para converter hexadecimal em decimal, depois decimal em octal, depois octal em decimal, etc.

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

  1. Escreva uma função que receba duas strings, digamos st, e diga se s é lexicograficamente menor que t.
  2. O seguinte fragmento de programa pretende decidir se abacate é lexicograficamente menor que banana. O que está errado?
    char *a, *b;
    a = "abacate"; b = "banana";
    if (a < b) 
       printf ("%s é menor que %s\n", a, b);
    else       
       printf ("%s é menor que %s\n", b, a);
    
  3. O seguinte fragmento de programa pretende decidir se abacate é lexicograficamente menor que amora. O que está errado?
    char *a, *b;
    a = "abacate"; b = "amora";
    if (*a < *b) 
       printf ("%s é menor que %s\n", a, b);
    else         
       printf ("%s é maior que %s\n", a, b);
    

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

  1. Qual a diferença entre as expressões  strcpy (s, t)  e  s = t ?
  2. Qual a diferença entre as expressões  if (strcmp (s, t) < 0)  e  if (s < t) ?
  3. Discuta as diferenças entre os três fragmentos de programa a seguir:
    char a[8], b[8];
    strcpy (a, "abacate"); strcpy (b, "banana");
    
    char *a = malloc (8), *b = malloc (8); 
    strcpy (a, "abacate"); strcpy (b, "banana");
    
    char *a, *b; 
    a = "abacate"; b = "banana";
    
  4. Estude a documentação da função strncpy da biblioteca string.
  5. Escreva uma função que receba uma string s e devolva uma cópia de s.  (Compare sua função com a função strdup da biblioteca string. Qual a diferença entre essa função e strcpy?)
  6. Escreva uma função que receba uma string ASCII s e um caractere ASCII c e devolva o índice da primeira posição em s que é igual a c.  (Compare sua função com a função strchr da biblioteca string.)  Agora faça uma versão mais geral da função para procurar c a partir de uma dada posição i.
  7. Escreva uma função que decida se um vetor vs[0..n-1] de strings está em ordem lexicográfica.
  8. ★ Suponha dado um vetor vs[0..n-1] de strings, em ordem lexicográfica, e uma string s.  Problema: se vs não contém uma string igual a s, inserir s no vetor de modo a manter a ordem lexicográfica. Escreva uma função que resolva o problema e devolva 1 se a inserção tiver sido feita e 0 em caso contrário.
  9. Ordem lexicográfica em português.  A ordem lexicográfica calculada pela função strcmp compara duas strings byte-a-byte, ignorando as características do eventual esquema de codificação. A menos que as strings sejam ASCII, a comparação produzida por strcmp não será a mesma de um dicionário de português.  No caso de strings que representam cadeia de carcteres em codificação UTF-8, por exemplo, use a variante strcoll de strcmp. ⚠ A ordem lexicográfica calculada por strcoll (o nome da função é uma abreviatura de string collate) usa a ordenação dos caracteres determinada pela variável de ambiente LC_COLLATE do seu sistema. Se o valor de LC_COLLATE é pt_BR.UTF-8, por exemplo, a ordem dos caracteres é  ... a A á Á à À â Â .. b B c C ç Ç d D .. z Z ...

    Use a função strcoll para escrever um programa que ordene lexicograficamente uma sequência de palavras em português em código UTF-8. As palavras são digitadas no terminal e a lista ordenada deve ser exibida na tela, uma por linha. Faça testes. Se o valor de LC_COLLATE no seu sistema não for pt_BR.UTF-8, você pode fazer algo assim:

    #include <locale.h>
    void main (void) {
       setlocale (LC_COLLATE, "pt_BR.UTF-8");
       ... código da ordenação ...
    }
    

    (Também pode mudar o valor de LC_COLLATE, temporariamente, antes de invocar o seu programa: ~$ LC_COLLATE="pt_BR.UTF-8" ./meuprograma.)