Strings e cadeias de caracteres

[string of numbers and letters]

Grande parte dos dados no mundo todo tem a forma de texto. Em outras palavras, grande parte dos dados está em cadeias de caracteres. Muitas dessas cadeias estão armazenadas como strings em arquivos digitais.  Este capítulo discute os conceitos de cadeia de caracteres e string e a relação entre esses conceitos.

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.  Entretanto, para evitar confusão entre char e caractere, podemos adotar byte como sinônimo de char:

typedef char byte;

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:

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

Depois da execução desse fragmento de programa, o vetor str[0..3] contém a string 01000001 01000010 01000011 00000000.  A porção str[4..9] do vetor é ignorada.

Poderíamos tratar strings como um novo tipo-de-dados. Para isso, bastaria introduzir o typedef abaixo e passar a escrever string no lugar de byte *.

typedef byte *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 c e devolva uma string cujo único byte é c.
  3. Vazio versus null.  Suponha que str é uma string.  Qual a difereça entre as afirmações str é uma string 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 a função para contar o número de ocorrências de uma string s em uma string t.

Cadeias de caracteres

Um texto, ou cadeia de caracteres, é uma sequência de símbolos tipográficos (letras, dígitos, sinais de pontuação, etc.).  Esta página, por exemplo, consiste em uma longa cadeia de caracteres. Eis um exemplo muito menor:

Função C99

(o sétimo caractere da cadeia é um espaço).  O comprimento de uma cadeia de caracteres é o número de caracteres da cadeia.  A cadeia do exemplo tem comprimento 10.

Strings.  Em arquivos digitais e na memória do computador, cadeias de caracteres são representadas por strings.  Para definir essa representação, é preciso convencionar uma correspondência entre caracteres e bytes. A correspondência mais antiga e mais básica é a tabela ASCII, que associa a cada caractere do alfabeto ASCII um byte entre 00000000 e 01111111, ou seja, entre 0127.  Por exemplo, a cadeia de caracteres  ABC  é representada pela string  65 66 67 0.  Qualquer string cujos bytes pertencem ao intervalo 0..127 é chamada string ASCII.

Caracteres que não pertencem ao alfabeto ASCII (como á, ã, é, ç, etc.) são representados por dois ou mais bytes consecutivos. Como estamos supondo que nosso ambiente de programação usa codificação UTF-8, cada caractere é representado por até quatro bytes consecutivos e o primeiro byte de cada caractere não-ASCII é maior que 127.  (Veja a tabela UTF-8 encoding table and Unicode characters.)  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.

O código UTF-8 foi construído de tal maneira que o caractere \0 (que pertence ao alfabeto ASCII) é 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 str é uma string que representa uma cadeia de caracteres C. Dê uma cota inferior e uma cota superior para o comprimento de str em função do comprimento de C.  Repita o exercício supondo que str é uma string ASCII.
  2. [Sedgewick 3.57]  Palíndromos.  Escreva uma função booleana que decida se uma string ASCII dada é um palíndromo (ou seja, se o inverso da string é igual a ela). Escreva um programa para testar a função.
  3. [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 um dos caracteres do alfabeto ASCII na string. Escreva um programa para testar a função.
  4. [Sedgewick 3.60]  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 depois de remover a restrição a strings ASCII.
  5. ★ Escreva uma função booleana que decida se uma dada string é ASCII ou não.  Suponha codificação UTF-8.
  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]

Leitura e escrita de cadeias

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.  Felizmente, a função printf com a 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 alternativa a printf é a função fputs (o nome é uma abreviatura de file put string) da biblioteca stdio. Essa função grava uma string num arquivo. Por exemplo,

fputs (str, arquivo);

Se o segundo argumento for stdout, a string str exibida na tela do terminal depois de ser convertida em uma cadeia de caracteres.

Leitura.  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 do teclado, converte a cadeia numa string (acrescentando um byte nulo ao final) e armazena a string no vetor str:

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

A função scanf interrompe a leitura ao encontrar o primeiro caractere branco (espaço, tabulação, fim de linha, etc.).  Para ler uma cadeia de caracteres que contém brancos, use a função fgets (o nome é uma abreviatura de file get string) da biblioteca stdio.  Se o último argumento de fgets for stdin, a função lê uma cadeia de caracteres do teclado até o fim da linha (tecla ), converte a cadeia numa string, e armazena a string no endereço indicado pelo primeiro agumento:

byte str[100];
fgets (str, 100, stdin); 

O segundo argumento de fgets é uma proteção contra linhas muito longas, mais longas que o espaço reservado para o primeiro argumento. No exemplo acima, se o número de bytes da cadeia de caracteres a ser lida for maior que 99, somente os 99 primeiros bytes serão armazenados em str.  (Se algum dos caracteres for representado por dois ou mais bytes, o número de caracteres lidos pode ser menor que 99.)

Cadeias constantes

Para especificar uma cadeia constante, basta embrulhar a cadeia num par de aspas duplas retas.  (Cadeias constantes aparecem com frequência em programas C; basta lembrar o 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,

byte *str;
str = "ABC";

produz efeito semelhante ao que aparece num dos exemplos acima.  Os caracteres de uma cadeia constante não precisam pertencer ao alfabeto ASCII; podemos, por exemplo, dizer

str = "Função";

Nesse caso, supondo codificação UTF-8, a string str terá 9 bytes: os três primeiros caracteres ocupam 1 byte cada, os dois caracteres seguintes ocupam 2 bytes cada, o último caractere ocupa 1 byte, e há um byte nulo no fim.

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;
}

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 depois de remover 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.