MAC0122  Princípios de Desenvolvimento de Algoritmos

Home  |   Fórum  |   Livros  |   WWW  |   Diário  |   Tarefas  |   Panda  |   Alunos  |   Notas

Cadeias de caracteres (= strings)

Este é um resumo da seção 3.6, p.109-114, do livro do Sedgewick. Esta seção introduz o tipo-de-dados cadeia-de-caracteres. Também discute as funções da biblioteca padrão string, que implementam operações básicas sobre strings.  A seção também serve de pretexto para trabalhar a relação entre vetores e ponteiros.

Na linguagem C, uma cadeias de caracteres ou simplesmente cadeia (= string) é qualquer vetor de caracteres que termina com o caracter '\0'.  O número de caracteres da cadeia, sem contar o '\0' final, é o comprimento da cadeia.  Uma cadeia é representada pelo endereço do seu primeiro caracter. Portanto, se  s  é uma cadeia de comprimento m então

s[0] é o primeiro caracter,
s[1] é o segundo,  . . . ,
s[m-1] é o último caracter

de s.

Exercícios

  1. Qual o efeito desse trecho de código?
    a = '\0';  b = '0';
    print("%d", a+2, b+2);
    

Argumentos na linha de comando

É muito cômodo fornecer dados a um programa C através da linha de comando. Cada argumento é tratado como uma cadeia de caracteres.  A título de exemplo, vamos repetir o Program 3.7, p.87, de Sedgewick.

#include <stdlib.h>

int heads (void)
{
   return rand() <= RAND_MAX / 2;
}

// Este programa faz M experimentos. Cada experimento consiste em 
// contar o número de caras (= heads) em N jogadas de uma moeda. 
// O programa imprime um histograma dos resultados. 
// Os valores de M e N devem ser digitados na linha de comando.

int main (int argc, char *argv[])
{
   int i, j, cnt, N, M;
   int *f;

   N = atoi(argv[1]);
   M = atoi(argv[2]);
   f = malloc((N+1) * sizeof (int));
   if (a == NULL) {
      printf("A memória está esgotada!\n");
      return 1;
   }
   for (j = 0; j <= N; j++) f[j] = 0;
   for (i = 0; i < M; i++) {
      cnt = 0;
      for (j = 0; j < N; j++) 
         if (heads()) cnt++;
      f[cnt]++;
   }
   for (j = 0; j <= N; j++) {
      printf("%2d ", j);
      for (i = 0; i < f[j]; i += 10) printf("*");
      printf("\n");
   }
   free(f);
   return 0;
}

O vetor  argv[0..argc-1]  é um vetor de strings. O primeiro argumento, argv[0] é o nome do programa.


O programa abaixo (veja programa 3.15, p.112) procura todas as ocorrências de uma cadeia p em uma cadeia a. Diremos que a cadeia a é um texto e p é uma palavra.  Em inglês, p pode ser chamada de word ou pattern

#include <stdio.h>
#define N 10000

typedef char *palavra;

// O programa abaixo procura todas as ocorrências de uma palavra p
// em um texto a. A palavra deve ser digitada na linha de comando;
// o texto deve ser digitado depois da tecla ENTER. Para indicar o 
// fim do texto, digite CONTROL-D. O programa imprime todas as 
// posições no texto a partir das quais há uma ocorrência da palavra.

int main(int argc, palavra argv[])
{ 
    int i, j, t; 
    char a[N];
    palavra p;

    p = argv[1];
    for (i = 0; i < N-1; i++) {
       if ((t = fgetc(stdin)) == EOF) break;
       a[i] = t;
    }
    a[i] = 0;  // é o mesmo que a[i] = '\0' 
    for (i = 0; a[i] != 0; i++) {
       for (j = 0; p[j] != 0; j++)
          if (a[i+j] != p[j]) break;
       if (p[j] == 0) printf("%d ", i);
    }        
    printf("\n");
    return 0;
}

Exercícios

  1. [Sedg 3.56]  Escreva uma função que receba uma cadeia de caracteres e imprima uma tabela que dê o número de ocorrências de cada caracter na cadeia. Escreva um programa para testar a função; o programa deve receber a cadeia através da linha de comando. Faça testes.
  2. [Sedg 3.57]  Escreva uma função que decida se uma cadeia de caracteres é ou não um palíndromo (ou seja, se o inverso da cadeia é igual a ela). Escreva um programa para testar a função; o programa deve receber a cadeia através da linha de comando. Faça os testes.
  3. [Sedg 3.59]  Escreva uma função que decida se uma cadeia de caracteres x é subcadeia de uma cadeia y. Escreva um programa que use a função para fazer o seguinte serviço: ao receber um texto y e uma sequência de palavras x1, x2, . . . , imprime uma lista das palavras que aparecem no texto. A sequência de palavras é fornecida ao programa como uma sequência de caracteres em que palavras consecutivas são separadas por um ou mais espaços em branco.
  4. [Sedg 3.61]  Escreva uma versão do programa 3.15 (veja acima) que manipule ponteiros em lugar de índices.

 


Veja minhas notas de aula sobre cadeias de caracteres.
Veja na página Brute Force algorithm do sítio Exact String Matching Algorithms uma animação java de um algoritmo semelhante ao descrito acima (clique em visualization).
Bons lugares para encontrar material para testar seu algoritmo de procura de palavras em textos:

Biblioteca padrão de manipulação de cadeias

Eis a descrição de algumas das funções da biblioteca string, cujo arquivo-interface é string.h.  O código pode não ser idêntico ao da biblioteca, mas é equivalente àquele.  Esse material foi copiado da tabela 3.2, p.111, de Sedgewick.

Exercícios

  1. O que há de errado com o seguinte trecho de código?
        char *a,  *b;
        a = "cenoura";
        b = "cereja";
        if (a < b)
           printf("%s precede %s no dicionário", a, b);
    
  2. [Roberts, p.128]  O que há de errado?
         char *src = "Alo";
         char *dst;
         strcpy(dst, src);
    
  3. [Sedgewick, p.113]  O que há de errado com o seguinte trecho de código, que pretende encontrar todas as ocorrências de uma palavra p em um texto a?
         for (i = 0; i < strlen(a); i++)
            if (strncmp(&a[i], p, strlen(p)) == 0)
               printf("%d ", i);
    
  4. [Sedg 3.60]  Escreva uma função que receba uma cadeia de caracteres e substitua cada subcadeia de dois ou mais espaços em branco por um só caracter ' '.
  5. [Sedg 3.62]  Escreva uma função que calcule o comprimento da mais longa sequência de espaços em branco em uma cadeia de caracteres. Escreva uma função que faça o serviço examinando o menor número possível caracteres. Escreva um programa para testar sua função.
  6. Escreva o código de uma função que faça o mesmo que strncat.
  7. Considere o programa, visto acima, de busca de uma palavra em um texto. Reescreva o programa usando as funções strncat e strcmp.
  8. Escreva uma função que receba uma cadeia, converta todas as letras acentuadas nas correspondentes letras sem acentos (á em aÉ em Eu em uÇ em C,  etc.) e devolva a cadeia resultante. Faça duas versões: na primeira, a cadeia resultante é guardada no mesmo espaço da cadeia dada; na segunda, um novo espaço é alocado para a cadeia resultante.
  9. Escreva uma função que decida se duas cadeias de mesmo comprimento diferem em exatamente uma posição.

Pig Latin

Pig Latin é uma língua artificial que deforma palavras em inglês (para criar um efeito engraçado, suponho). Eis alguns exemplos:

english           pig latin
computer omputercay
structure ucturestray
number umbernay
organize organizeway
interface interfaceway
pointer ointerpay
address addressway

A função abaixo foi copiada (com algumas modificações) da figura 3-5, p.130, do livro de Roberts.

#include <ctype.h>
#include <string.h>

#define MaxWord  20

typedef char *string;

// Function: PigLatin
// ------------------
// This function translates a word from English to Pig Latin.  
// The rules for forming Pig Latin words are as follows:
// 
// o If the word begins with a vowel, add "way" to the
//   end of the word.
// o If the word begins with a consonant, extract the 
//   consonants up to the first vowel, move that substring
//   to the end of the word, and add "ay". 
// 
// Examples: Inglês     PigLatin
//           ----------------------
//           ash        ashtray
//           structure  ucturestray
//           pointer    ointerpay
//           address    addressway

string PigLatin(string word)
{
    string vp; string pig;
    int wordLength;

    wordLength = strlen(word);
    vp = FindFirstVowel(word);
    if (vp == word) {
        wordLength += 3;
    } else if (vp != NULL) {
        wordLength += 2;
    }
    pig = malloc(wordLength * sizeof (char) + 1);
    if (vp == NULL) {
       strcpy(pig, word);
    } else if (vp == word) {
       strcpy(pig, word);
       strcat(pig, "way");
    } else {
       strcpy(pig, vp);
       strncat(pig, word, vp - word);
       strcat(pig, "ay");
    }
    return pig;
}

// The FindFirstVovel function returns the address of the 
// first vowel in word. If word does not contain a vowel, 
// the function returns NULL. 

string FindFirstVowel(string word)
{
    char *cp;
    for (cp = word; *cp != '\0'; cp++) {
       char c = tolower(*cp);
       if (c == 'a' || c == 'e' || c == 'i' 
           || c == 'o' || c == 'u')
              return cp;
    }
    return NULL;
}


int main(void)
{
    char word[MaxWord+1];

    printf("Enter a word with no more than %d letters: ", MaxWord);
    scanf("%s", word);
    printf("Pig Latin: %s\n", PigLatin(word));
    return 0;
}

Exercícios

  1. A documentação da função PigLatin omite o caso de palavras sem vogais (talvez porque o inglês, ao contrário do checo, não tem palavras desse tipo). O que a função faz com uma palavra que só têm consoantes?
  2. Escreva um programa que use a função PigLatin para traduzir um texto que consiste de uma sequência de palavras.
  3. Invente uma versão do Pig Latin que seja interessante e engraçada em português. Implemente sua ideia.

A biblioteca strlib de Roberts

Eric Roberts escreveu uma biblioteca de manipulação de cadeias que é mais amigável que a biblioteca padrão pois faz as necessárias alocações dinâmicas internamente. O arquivo-interface dessa biblioteca é strlib.h e a correspondente implementação está em strlib.c.

Veja como a função PigLatin fica mais simples e mais legível se usarmos as funções da biblioteca de Roberts:

#include "strlib.h"

string PigLatin(string word)
{
    int vp; 
    string head, tail;

    vp = FindFirstVowel(word);
    if (vp == -1) {
        return word;
    } else if (vp == 0) {
        return Concat(word, "way");
    } else {
       head = SubString(word, 0, vp - 1);
       tail = SubString(word, vp, StringLength(word) - 1);
       return Concat(tail, Concat(head, "ay"));
    }
}

A definição  typedef char* string  faz parte do arquivo-interface strlib.h.


Mais exercícios

  1. [Bom!]  Escreva uma função que remova os comentários de um arquivo HTML. Um comentário HTML é qualquer coisa que esteja entre  <!--  e  -->.  Comentários não podem ser encaixados. Sua função deve receber um arquivo HTML e gravar um novo arquivo sem os comentários. Você poderia aproveitar para verificar se os comentários no arquivo original estão devidamente demarcados (verificar se o arquivo não contém algo como  <!-- . . . <!--,  por exemplo).

 


URL of this site: www.ime.usp.br/~pf/mac0122-2002/
Last modified: Fri Nov 28 10:46:37 BRST 2014
Paulo Feofiloff
IME-USP

Valid HTML 4.01 Transitional    Valid CSS!