Strings e cadeias de caracteres

[string of numbers and letters]

Grande parte dos dados no mundo todo está na forma de texto. Em outras palavras, grande parte dos dados está registrada em cadeias de caracteres. Muitas dessas cadeias são strings em arquivos digitais.  Este capítulo discute a relação entre cadeia de caracteres e strings.

Sumário:

Strings

Na linguagem C, uma string é um vetor de bytes em que o byte nulo 00000000 é interpretado como uma sentinela que marca o fim da parte relevante do vetor.  Eis um pequeno exemplo de string:

01000001 01000010 01000011 00000000 01000100

(os símbolos 0 e 1 representam bits).  Nesse exemplo, apenas os 4 primeiros bytes constituem a string propriamente dita.

O comprimento (= length) de uma string é o seu número de bytes, sem contar o byte nulo final.  (Assim, a string do exemplo acima tem comprimento 3.)  Uma string é vazia se tem comprimento zero.

Cada byte de uma string é tratado como um char e portanto uma string é um vetor de chars. (Poderíamos ter dito unsigned char; isso não faria diferença na prática.)  Para quebrar a associação entre char e caractere, podemos usar byte como sinônimo de char.

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

O seguinte exemplo constrói uma string str byte-a-byte. Depois da execução do fragmento de código, o vetor str[0..3] contém a string  01000001 01000010 01000011 00000000.  A porção str[4..9] do vetor é ignorada.

byte *str;
str = malloc (10 * sizeof (byte));
str[0] = 65;
str[1] = 66;
str[2] = 67;
str[3] =  0;
str[4] = 68;

Podemos tratar strings como um novo tipo-de-dados. Para isso, basta introduzir o typedef abaixo e passar a escrever string no lugar de char *.

typedef char *string;

Exercícios 1

  1. Escreva uma função booleana que decida se duas strings de mesmo comprimento diferem em exatamente um byte.
  2. Escreva uma função que receba um byte b e devolva uma string cujo único byte é b.
  3. Vazio versus null.  Suponha que str é uma string.  Qual a difereça entre as afirmações str é vazia e str é NULL?
  4. Pedaço de string.  Escreva uma função que receba uma string str e inteiros positivos ij e devolva uma string com o mesmo conteúdo que o segmento str[i..j].  Escreva duas versões: na primeira, sua função não deve alocar novo espaço e pode alterar a string str que recebeu; na segunda, sua função deve devolver uma cópia do segmento str[i..j] e não pode alterar a string str que recebeu.
  5. Escreva uma função booleana que receba strings s e t e decida se s é um segmento de t.  Escreva um programa que use sua função para contar o número de ocorrências de uma string s em uma string t.

Cadeias de caracteres

Uma cadeia de caracteres é uma sequência de caracteres. Esta página, por exemplo, é uma longa cadeia de caracteres.  O comprimento de uma cadeia de caracteres é o número de caracteres da cadeia. Por exemplo, a cadeia

Função C99

tem comprimento 10 (o sétimo caractere é um espaço).

Em arquivos digitais, e na memória do computador, cadeias de caracteres são representadas por strings.  No caso de cadeias de caracteres ASCII, cada caractere é representado por um único byte, sendo a representação definida pela tabela ASCII. Strings desse tipo serão chamadas strings ASCII. O valor de cada byte de uma tal string pertence ao intervalo 0..127.  Por exemplo, a cadeia de caracteres  Funcao C99  é representada pela string  70 117 110 99 97 111 32 67 57 57 0.

Agora considere as cadeias em que nem todos os caracteres pertencem ao alfabeto ASCII. Como estamos supondo que nosso ambiente de programação usa codificação UTF-8, cada caractere não-ASCII (como À, ã, ç, é, ≤, etc.) é representado por dois, três, ou até quatro bytes consecutivos e esses bytes não pertencem ao intervalo 0..127. (Cada uma das letras acentuadas usadas em português ocupa apenas dois bytes.)  Por exemplo, a cadeia de caracteres  Função C99  é representada pela string  70 117 110 195 167 195 163 111 32 67 57 57 0.  Os três primeiros caracteres são representados por 1 byte cada, os dois caracteres seguintes são representados por 2 bytes cada, os cinco últimos caracteres são representados por 1 byte cada, e há um byte nulo no fim.  Os detalhes dessa representação são discutidos no capítulo Unicode e UTF-8.

O código UTF-8 foi definido de tal maneira que o caractere \0 é o único cujo código contém um byte nulo. Assim, o primeiro byte nulo da string indica o fim da string bem como o fim da cadeia de caracteres que a string representa.

Exercícios 2

  1. Suponha que a string str é a representação UTF-8 de uma cadeia de caracteres s. Dê uma cota inferior e uma cota superior para o comprimento de str em função do comprimento de s.  Repita o exercício supondo que str é uma string ASCII.
  2. ★ Escreva uma função booleana que decida se uma dada string é ASCII ou não.
  3. [Sedgewick 3.57]  Palíndromos.  Escreva uma função booleana que decida se uma dada cadeia de caracteres ASCII é um palíndromo (ou seja, se o inverso da cadeia é igual a ela). A cadeia é representada por uma string. Escreva um programa para testar sua função.
  4. [Sedgewick 3.56]  Escreva uma função que receba uma string ASCII e exiba uma tabela com o número de ocorrências de cada caractere na string. Escreva um programa para testar sua função.
  5. ★ Escreva uma função que receba uma string ASCII e substitua cada segmento de dois ou mais espaços por um só espaço. Refaça o exercício sem a restrição a strings ASCII.
  6. Número de caracteres.  Escreva uma função que receba uma string e calcule o comprimento da cadeia de caracteres que a string representa em código UTF-8.  (Dica: Estude a estrutura do código UTF-8.)  [Solução: ./solucoes/string4.html]

Leitura e escrita de cadeias de caracteres

Para obter a cadeia de caracteres que uma dada string representa, é preciso decodificar a string.  No caso de strings ASCII, a decodificação é simples: basta consultar a tabela ASCII. Em geral, entretanto, a decodificação é mais complexa (em parte porque nem toda string é uma representação UTF-8 válida de uma cadeia de caracteres).  Felizmente, a função printf com especificação de formato  %s  cuida da decodificação. Por exemplo, o fragmento de programa

byte str[100] = {97,195,167,195,163,111,0};
printf ("%s\n", str);

exibe a cadeia de caracteres

ação

uma vez que o par of bytes 195 167 representa ç e o par of bytes 195 163 representa ã em código UTF-8.

A especificação de formato  %s  também pode ser usada com a função de leitura scanf. Por exemplo, o fragmento de programa abaixo lê uma cadeia de caracteres (sem brancos) do teclado, acrescenta um byte nulo ao final, e armazena a string resultante no vetor str:

byte str[100];
scanf ("%s", str); 

Cadeias constantes

Para especificar uma cadeia constante, basta embrulhá-la num par de aspas duplas (caracteres 34).  Cadeias constantes aparecem com frequência em programas C: basta lembrar do primeiro argumento das funções printf e scanf.

Quando uma cadeia constante é atribuída a uma string, ela é convertida numa sequência de bytes e um byte nulo é acrescentado ao final. Por exemplo, depois do fragmento

byte *str;
str = "ABC";

a string str contém  65 66 67 0.  Os caracteres de uma cadeia constante não precisam pertencer ao alfabeto ASCII; podemos, por exemplo, dizer

str = "Função";

Nesse caso a string str terá nove bytes em codificação UTF-8.

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

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

(A letra y também é uma vogal?)

Exercícios 3

  1. Qual o efeito dos dois fragmentos de programa a seguir? O que há de errado com o segundo?
    byte *s;
    s = "ABC";
    printf ("%s\n", s);
    
    byte s[20];
    s = "ABC";
    printf ("%s\n", s);
    
  2. Qual a diferença entre "A"'A'?
  3. 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"?
  4. Reescreva a função contaVogais sem a restrição a strings ASCII. Suponha que a string representa um texto em português e conte as letras á, ã, É, etc. como vogais.
  5. Remove acentos.  Escreva uma função que remova todos os sinais diacríticos de uma cadeia de caracteres dada, trocando Á por A, ã por a, ç por c, e assim por diante.  A cadeia de caracteres dada é representada por uma string em código UTF-8. Você pode supor que apenas os caracteres usados em português aparecem na cadeia, e portanto cada caractere ocupa no máximo 2 bytes. O resultado da função deve ser uma string ASCII.