Este é um resumo da seção 3.6 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 cadeias de caracteres. 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.
Suporemos neste capítulo (e em todos os demais) que cada caracter ocupa apenas 1 byte e sua interpretação segue a tabela ISO-LATIN-1. Muitas vezes, usaremos apenas o subconjunto ASCII da tabela. (Veja Caracteres e a tabela ASCII e Esquemas de codificação.)
a = '\0'; b = '0';
print("%d %d\n", a+2, b+2);
É muito cômodo fornecer dados a um programa C por meio da linha de comando. Cada argumento é tratado como uma cadeia de caracteres. A título de exemplo, vamos repetir o Programa 3.7 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)
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; }
Brute Force algorithmdo sítio Exact String Matching Algorithms uma animação java de um algoritmo semelhante ao descrito acima.
Lendas do Sulde J. Simões Lopes Neto.)
Quincas Borbade Machado de Assis.)
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 de Sedgewick. (Estamos supondo codificação ISO-LATIN-1.)
int strlen(char *a) {
int i;
for (i = 0; a[i] != 0; i++) {}
return i;
}
Outra maneira de escrever o código:
char * b = a; while (*b != 0) b++; return b-a;
int strcmp(char *x, char *y) {
int i;
for (i = 0; x[i] == y[i]; i++)
if (x[i] == 0) return 0;
return x[i] - y[i];
}
Outra maneira de escrever o código:
while (*x == *y) {
x++;
y++;
if (*(x-1) == 0) return 0;
}
return *x - *y;
char *strcpy(char *y, char *x) {
int i;
for (i = 0; (y[i] = x[i]) != 0; i++) ;
}
Outra maneira de escrever o código:
while ((*y = *x) != 0) {
y++;
x++;
}
livresdepois do '\0' que marca o fim de x.
char *strcat(char *x, char *y) {
strcpy(a + strlen(x), y);
}
char *a, *b;
a = "cenoura";
b = "cereja";
if (a < b)
printf("%s precede %s no dicionário", a, b);
char *src = "Alo"; char *dst; strcpy(dst, src);
for (i = 0; i < strlen(a); i++)
if (strncmp(&a[i], p, strlen(p)) == 0)
printf("%d ", i);
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 do livro de Roberts. (Estamos supondo codificação ISO-LATIN-1. A função abaixo usa apenas o conjunto de caracteres ASCII.)
#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; }
Eric Roberts escreveu uma biblioteca de manipulação de cadeias que é mais amigável que a biblioteca padrão do C 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.