Strings

[chain-link-white-background-7197248.png]

Na linguagem C, uma string, ou cadeia de bytes, é um vetor de bytes em que o byte nulo, \0, é interpretado como fim da parte relevante do vetor.  Cada byte de uma string é tratado como um char e portanto uma string s é declarada assim:

char *s;

No seguinte exemplo, uma string é construída byte-a-byte:  depois da execução do fragmento de código

s = malloc (10 * sizeof (char));
s[0] = 'A';
s[1] = 'B';
s[2] = 'C';
s[3] = '\0';
s[4] = 'D';

o vetor s[0..3] contém a string  ABC.  O byte nulo marca o fim da string e a porção s[4..9] do vetor é ignorada.

Poderíamos tratar strings como um novo tipo-de-dados introduzindo a definição

typedef char *string;

Feito isso, todas as ocorrências de char * poderiam ser trocadas por string.

Sequências de caracteres

Strings são frequentemente usadas para representar sequências de caracteres.  Se todos os caracteres da sequência pertencem ao alfabeto ASCII — e portanto cada caractere é representado por um só byte — temos uma string ASCII.

Em geral, entretanto, cada caractere é representado por um vários bytes consecutivos.  Se nosso ambiente de programação usa codificação UTF-8, cada caractere é representado por 1 a 4 bytes consecutivos.  (A propósito, o código UTF-8 foi construído de tal maneira que o único caractere cujo código contém um byte nulo é o caractere nulo \0. Assim, o primeiro byte nulo da string, que indica o fim da string, também indica o fim da sequência de caracteres.)

Para extrair a sequência de caracteres da string de bytes é preciso decodificar a string.  Felizmente, o programador não precisa tratar da decodificação, pois as funções da biblioteca padrão stdio cuidam disso.  Por exemplo, a função printf com especificação de formato  %s  imprime a sequência de caracteres que a string representa em código UTF-8:

char s[100] = "àèìòù áéíóú";
printf ("diacríticos: %s\n", s);

Uma alternativa a printf é a função fputs (o nome é uma abreviatura de file put string) da biblioteca stdio, que grava uma string num arquivo:

fputs (s, stdout);

Leitura de strings.  A especificação de formato  %s  também pode ser usada com a função de leitura scanf:

char s[100];
scanf ("%s", s); 
printf ("string lida: %s\n", s);

Mas scanf lê a sequência de caracteres somente até o primeiro branco.  Para ler uma sequência de caracteres que contém brancos, use a função fgets (o nome é uma abreviatura de file get string) da biblioteca stdio.  Essa função lê uma linha de caracteres (que termina com um \n) e armazena-a em uma string (acrescentando um byte nulo no fim):

   char s[100];
   fgets (s, 100, stdin); 
   printf ("string lida: %s\n", s);

O segundo argumento de fgets é uma proteção contra linhas muito longas, mais longas que o espaço reservado para a string. No exemplo acima, se a linha tiver mais que 99 bytes, somente os 99 primeiros serão lidos e armazenados em s.  O número de caracteres lidos pode ser bem menor que 99 pois cada caractere pode ocupar até 4 bytes.

Exercícios 1

  1. Escreva uma função que decida se uma dada string é ASCII ou não.  Suponha codificação UTF-8.

Comprimento e endereço

O comprimento (= length) de uma string é o seu número de bytes, sem contar o byte nulo final.  Uma string é vazia se seu comprimento é zero.

O comprimento de uma string ASCII é igual ao número de caracteres da string.  Em geral, entretanto, o comprimento da string é maior que o número de caracteres.  É um bom exercício escrever uma função que calcule o seu número de caracteres em uma string.

O endereço de uma string é o endereço do seu primeiro byte, da mesma forma que o endereço de um vetor é o endereço de seu primeiro elemento.

Em discussões informais, é usual confundir uma string com o seu endereço. Assim, a expressão considere a string s deve ser entendida como considere a string cujo endereço é s.

Exercícios 2

  1. Vazio versus null.  Suponha que s é uma string.  Qual a difereça entre as afirmações s é uma string vazia e s é NULL?
  2. Escreva uma função que decida se duas strings de mesmo comprimento diferem em exatamente uma posição.
  3. Número de caracteres.  Escreva uma função que calcule o número de caracteres de uma string que representa uma sequência de caracteres com codificação UTF-8.  (Sugestão: Estude a estrutura do código UTF-8.)  [Solução]

Constantes

Para especificar uma sequência de caracteres literal, ou seja, constante, basta embrulhar uma sequência de caracteres num par de aspas duplas. O byte nulo final fica subentendido. Por exemplo, "ABC" é uma sequência literal e o fragmento de código

char *s;
s = "ABC";

é essencialmente equivalente ao que aparece na introdução deste capítulo.  Os caracteres de uma sequência literal podem não ser ASCII.  Podemos ter, por exemplo,

char *s;
s = "ação";

Nesse caso (supondo codificação UTF-8), a string s terá 7 bytes: o primeiro e o último caracteres ocupam 1 byte cada, os dois caracteres do meio ocupam 2 bytes cada, e o byte nulo final ocupa mais um byte.

Sequência literais aparecem com frequência em programas C.  Basta lembrar que o primeiro argumento das funções printf e scanf é uma sequência literal:

scanf ("%d", &n);
printf ("O número de elementos é %d", n);

Exercícios 3

  1. Qual o efeito do seguinte fragmento de código?
    char *s;
    s = "ABC";
    printf ("%s\n", s);
    
  2. O que há de errado com a seguinte variante do exercício anterior?
    char s[20];
    s = "ABC";
    printf ("%s\n", s);
    
  3. Qual a diferença entre "A" e 'A'?
  4. Qual a diferença entre "mno" e "m\no"?  Qual a diferença entre "MNOP" e "MN0P"?  Qual a diferença entre "MN\0P" e "MN0P"?
  5. Escreva uma função que receba um byte c e devolva uma string cujo único byte é c.

Exemplo: contagem de vogais

A seguinte função conta o número de vogais em uma string:

int contaVogais (char s[]) {
   char *vogais;
   vogais = "aeiouAEIOU";
   int numVogais = 0;
   for (int i = 0; s[i] != '\0'; ++i) {
      char ch = s[i];
      for (int j = 0; vogais[j] != '\0'; ++j) {
         if (vogais[j] == ch) {
            numVogais += 1;
            break;
         }
      }
   }
   return numVogais;
}

Exercícios 4

  1. [Sedgewick 3.57]  Palíndromos.  Escreva uma função que decida se uma string ASCII é ou não um palíndromo (ou seja, se o inverso da string é igual a ela). Escreva um programa para testar a função.
  2. [Sedgewick 3.56]  [!] Escreva uma função que receba uma string ASCII e imprima uma tabela com o número de ocorrências de cada um dos 128 caracteres ASCII na string. Escreva um programa para testar a função.
  3. [Sedgewick 3.60]  [!] Escreva uma função que receba uma string e substitua cada segmento de dois ou mais espaços por um só espaço.
  4. Reescreva a função contaVogais para que ela conte não só as vogais ASCII como também as vogais com diacríticos.

Ordem lexicográfica

A ordem lexicográfica (erroneamente conhecida como ordem alfabética) de strings é análoga à ordem das palavras em um dicionário.  Uma string s é menor que uma string t se o primeiro byte de s que difere do byte correspondente de t é menor que o byte de t.

Para fazer a comparação lexicográfica de duas strings st, 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 k não está definido então s e t são idênticas ou uma é prefixo próprio da outra; no segundo caso, a string mais curta é lexicograficamente menor que a mais longa.

No caso de strings ASCII, a ordem entre caracteres (que determina a ordem lexicográfica) coincide com a ordem dada pela tabela ASCII.

No caso de sequência de caracteres Unicode (em particular, sequência que incluem letras acentuadas), a ordem entre caracteres é a ordem crescente dos números Unicode.  A codificação UTF-8 foi constuída de tal maneira que a ordem lexicográfica baseada na comparação byte-a-byte coincide com a ordem lexicográfica baseada na comparação dos números Unicode!  (Mas a ordem lexicográfica também depende, de uma maneira que não sei explicar, da variável de ambiente LC_COLLATE.)

Exercícios 5

  1. Escreva uma função que receba duas strings ASCII digamos st.  e decida se s é lexicograficamente menor que t.
  2. O seguinte fragmento de código pretende decidir se abacate vem antes ou depois de banana no dicionário. O que há de errado?
    char *b, *a;
    a = "abacate"; b = "banana";
    if (a < b) printf ("%s vem antes de %s\n", a, b);
    else       printf ("%s vem depois de %s\n", a, b);
    
  3. O seguinte fragmento de código pretende decidir se abacate vem antes ou depois de amora no dicionário. O que há de errado?
    char *a, *b;
    a = "abacate"; b = "amora";
    if (*a < *b) printf ("%s vem antes de %s\n", a, b);
    else         printf ("%s vem depois de %s\n", a, b);
    

A biblioteca string

A biblioteca string da linguagem C (não confunda com a biblioteca obsoleta strings) contém várias funções de manipulação de strings.  Para usar essas funções, o seu programa deve incluir a interface string.h:

#include <string.h>

Eis as funções mais importantes da biblioteca:

Exercícios 6

  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 código 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. 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 completa da função, que procura c a partir de uma dada posição i.
  5. Escreva uma função que receba strings x e s e devolva o índice da posição a partir da qual x ocorre em s.  (Compare sua função com a função strstr da biblioteca string.)
  6. Escreva uma função que receba uma string s e inteiros positivos ij e devolva uma string com o mesmo conteúdo que o segmento s[i..j].  Escreva duas versões: na primeira, sua função não deve alocar novo espaço e pode alterar a string s que recebeu; na segunda, sua função deve devolver uma cópia do segmento s[i..j] e não pode alterar a string s que recebeu.
  7. Escreva uma função que receba uma string s e devolve 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?)
  8. Escreva uma função que receba strings s e t e decida se s é um segmento de t.  Escreva um programa que use a função para contar o número de ocorrências de uma string s em uma string t.
  9. [Sedgewick 3.62]  [!] Escreva uma função que calcule o comprimento do mais longo segmento de espaços em uma string. Procure examinar o menor número possível de elementos da string. Escreva um programa para testar sua função.
  10. Estude a documentação da função strncpy da biblioteca string.
  11. Escreva uma função que decida se um vetor vs[0..n-1] de strings está em ordem lexicográfica.
  12. 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.

Exercícios 7

  1. Escreva um programa para converter notação decimal em notação hexadecimal.  O seu programa deve receber, pela linha de comando, um número em notação decimal e imprimir a representação hexadecimal do número.  Repita o execício para converter hexadecimal em decimal, decimal em octal, octal em decimal, etc.
  2. Inteiro para string decimal.  Escreva uma função que receba um inteiro n e devolva a string ASCII de dígitos decimais que represente n da maneira usual. Por exemplo, o inteiro −123 deve ser convertido em "-123".
  3. String decimal para inteiro.  Escreva uma função que receba uma string ASCII de dígitos decimais e devolva o correspondente número inteiro positivo. Por exemplo, ao receber a string "123", devolve o inteiro 123.  (Se a string for longa demais, descarte os últimos dígitos.)  Depois, faça uma versão mais sofisticada da função que permita que o primeiro elemento da string seja '+' ou '-'.
  4. Inteiro para string binária.  Escreva uma função que receba um inteiro positivo n e devolva a string ASCII de 0s e 1s que represente n em notação binária. Por exemplo, o inteiro 123 deve ser convertido em "1111011".
  5. String binária para inteiro.  Escreva uma função que receba uma string ASCII de 0s e 1s, interprete essa string como um número natural em notação binária e devolva o valor desse número. (Se a string for longa demais, descarte os últimos dígitos.) Por exemplo, a string "1111011" deve ser convertida no inteiro 123.