APC - Strings

Prévia do material em texto

Algoritmos e 
Programação de 
Computadores 
Disciplina: 116301 
 
Profa. Carla Denise Castanho 
Prof. Marcio Victorino 
 
Universidade de Brasília – UnB 
Instituto de Ciências Exatas – IE 
Departamento de Ciência da Computação – CIC 
10. STRINGS 
Computação básica - carlacastanho@cic.unb.br 
Representação de Caracteres 
 Já vimos que computadores são excelentes para 
lidar com números. 
 Na verdade, computadores são capazes de lidar 
apenas com números, lembre-se que tudo em um 
computador é representado por meio de números 
em código binário. 
 Mas então como nós conseguimos trabalhar com 
letras do alfabeto e palavras? 
Computação básica - carlacastanho@cic.unb.br 
Representação de Caracteres 
 No computador, os caracteres, i.e., letras, algarismos, sinais de 
pontuação, comandos de controle e vários outros símbolos, são 
armazenados por meio de um código numérico. 
 Cada símbolo recebe um código único. Por exemplo, em ANSI C, a 
letra ‘A’ maiúscula tem o código 65. 
 Existem diversos padrões para definir tanto os códigos quanto a forma 
de armazenar caracteres. Ex.: EBCDIC, ASCII, ISSO-8859, UTF-8, UTF-
16, etc... 
 Em ANSI C, usamos o padrão ASCII (American Standard Code for 
Information Interchange). Nesse formato, cada caractere ocupa 1 
byte e existem 256 símbolos diferentes. Uma variável do tipo char 
guarda exatamente 1 caractere. 
Computação básica - carlacastanho@cic.unb.br 
Tabela ASCII 
Computação básica - carlacastanho@cic.unb.br 
Sequências de Caracteres 
 Se um char guarda um caractere, então uma frase 
ou palavra nada mais é que uma sequência de 
chars, que também chamamos de string. 
Podemos usar um vetor para representá-la. 
 Mas para manipular strings, o computador precisa 
saber onde a sequência termina. Como fazer isso? 
Computação básica - carlacastanho@cic.unb.br 
Sequências de Caracteres 
 Podemos guardar o tamanho da string, como fazemos com 
vetores em geral... 
 Ou podemos colocar uma marca no final da string, logo 
após o último caractere. 
 Essa última opção é mais interessante, pois evita que 
precisemos guardar o tamanho da string em uma variável 
separada ou passá-lo como um parâmetro extra de uma 
função. 
 A linguagem C trabalha com essa última abordagem. 
 
Computação básica - carlacastanho@cic.unb.br 
Sequências de Caracteres 
 Portanto, na nossa representação, uma string é um vetor de caracteres, e 
seu final será indicado por uma posição do vetor contendo o valor NULO. Em 
C, esse valor é indicado por '\0' (lê-se “barra zero”). 
 Dado que as strings são vetores, podemos fazer uma série de operações sobre 
elas: 
 concatenar duas ou mais strings; 
 acessar um elemento (caractere) específico; 
 extrair substrings; 
 comparar duas strings segundo algum critério; 
 ordenar os caracteres segundo algum critério; 
 etc... 
 
Computação básica - carlacastanho@cic.unb.br 
Exemplo 
 Faça um algoritmo que leia duas strings de, no máximo, 20 caracteres e intercale as 
letras de cada uma delas, em uma outra string (de até 40 caracteres). O tamanho será 
igual para as duas strings de entrada, e sempre menor ou igual a 20. 
Computação básica - carlacastanho@cic.unb.br 
Exemplo 
 Faça um algoritmo que leia duas strings de, no máximo, 20 caracteres e intercale as 
letras de cada uma delas, em uma outra string (de até 40 caracteres). O tamanho será 
igual para as duas strings de entrada, e sempre menor ou igual a 20. 
Computação básica - carlacastanho@cic.unb.br 
Exemplo – Intercalação de Strings 
Algoritmo Intercala 
Variáveis 
 S1, S2 : vetor [21] de caracteres 
 S3 : vetor [41] de caracteres 
 i : inteiro 
Início 
 Leia (S1) 
 Leia (S2) 
 i ← 0 
 Enquanto (S1[i] ≠ NULO) faça 
 S3[2 * i] ← S1[i] 
 S3[2 * i + 1] ← S2[i] 
 i ← i + 1 
 Fim-Enquanto 
 S3[2 * i] ← NULO 
 Escreva (“String resultante: ”, S3) 
Fim 
Exemplo 
 Faça um algoritmo que leia duas strings de, no máximo, 20 caracteres e intercale as 
letras de cada uma delas, em uma outra string (de até 40 caracteres). O tamanho será 
igual para as duas strings de entrada, e sempre menor ou igual a 20. 
Exemplo – Intercalação de Strings 
Algoritmo Intercala 
Variáveis 
 S1, S2 : vetor [21] de caracteres 
 S3 : vetor [41] de caracteres 
 i : inteiro 
Início 
 Leia (S1) 
 Leia (S2) 
 i ← 0 
 Enquanto (S1[i] ≠ NULO) faça 
 S3[2 * i] ← S1[i] 
 S3[2 * i + 1] ← S2[i] 
 i ← i + 1 
 Fim-Enquanto 
 S3[2 * i] ← NULO 
 Escreva (“String resultante: ”, S3) 
Fim 
As strings são declaradas como vetores de caracteres. 
Precisamos declarar uma posição a mais, para guardar 
o caractere NULO. 
Exemplo 
 Faça um algoritmo que leia duas strings de, no máximo, 20 caracteres e intercale as 
letras de cada uma delas, em uma outra string (de até 40 caracteres). O tamanho será 
igual para as duas strings de entrada, e sempre menor ou igual a 20. 
Computação básica - carlacastanho@cic.unb.br 
Exemplo – Intercalação de Strings 
Algoritmo Intercala 
Variáveis 
 S1, S2 : vetor [21] de caracteres 
 S3 : vetor [41] de caracteres 
 i : inteiro 
Início 
 Leia (S1) 
 Leia (S2) 
 i ← 0 
 Enquanto (S1[i] ≠ NULO) faça 
 S3[2 * i] ← S1[i] 
 S3[2 * i + 1] ← S2[i] 
 i ← i + 1 
 Fim-Enquanto 
 S3[2 * i] ← NULO 
 Escreva (“String resultante: ”, S3) 
Fim 
As strings são declaradas como vetores de caracteres. 
Precisamos declarar uma posição a mais, para guardar 
o caractere NULO. 
Podemos usar diretamente Leia (scanf) para ler strings, não é 
preciso um loop para ler elemento a elemento como fazemos 
com os vetores em geral. Além disso, a função já coloca o 
caractere NULO ao final da string para nós! 
Exemplo 
 Faça um algoritmo que leia duas strings de, no máximo, 20 caracteres e intercale as 
letras de cada uma delas, em uma outra string (de até 40 caracteres). O tamanho será 
igual para as duas strings de entrada, e sempre menor ou igual a 20. 
Computação básica - carlacastanho@cic.unb.br 
Exemplo – Intercalação de Strings 
Algoritmo Intercala 
Variáveis 
 S1, S2 : vetor [21] de caracteres 
 S3 : vetor [41] de caracteres 
 i : inteiro 
Início 
 Leia (S1) 
 Leia (S2) 
 i ← 0 
 Enquanto (S1[i] ≠ NULO) faça 
 S3[2 * i] ← S1[i] 
 S3[2 * i + 1] ← S2[i] 
 i ← i + 1 
 Fim-Enquanto 
 S3[2 * i] ← NULO 
 Escreva (“String resultante: ”, S3) 
Fim 
As strings são declaradas como vetores de caracteres. 
Precisamos declarar uma posição a mais, para guardar 
o caractere NULO. 
Podemos usar diretamente Leia (scanf) para ler strings, não é 
preciso um loop para ler elemento a elemento como fazemos 
com os vetores em geral. Além disso, a função já coloca o 
caractere NULO ao final da string para nós! 
O teste S1[i] ≠ NULO verifica se a string já chegou ao fim. 
Neste caso em particular, como a especificação diz que S1 e S2 
têm o mesmo tamanho, basta testar uma delas. 
Exemplo 
 Faça um algoritmo que leia duas strings de, no máximo, 20 caracteres e intercale as 
letras de cada uma delas, em uma outra string (de até 40 caracteres). O tamanho será 
igual para as duas strings de entrada, e sempre menor ou igual a 20. 
Computação básica - carlacastanho@cic.unb.br 
Exemplo – Intercalação de Strings 
Algoritmo Intercala 
Variáveis 
 S1, S2 : vetor [21] de caracteres 
 S3 : vetor [41] de caracteres 
 i : inteiroInício 
 Leia (S1) 
 Leia (S2) 
 i ← 0 
 Enquanto (S1[i] ≠ NULO) faça 
 S3[2 * i] ← S1[i] 
 S3[2 * i + 1] ← S2[i] 
 i ← i + 1 
 Fim-Enquanto 
 S3[2 * i] ← NULO 
 Escreva (“String resultante: ”, S3) 
Fim 
Aqui estamos efetivamente manipulando os índices para 
intercalar as strings. Como isso funciona? Vamos fazer um 
“chinês”... 
 
 
 
 
 
 
 
 
 
 
Exemplo 
 Faça um algoritmo que leia duas strings de, no máximo, 20 caracteres e intercale as 
letras de cada uma delas, em uma outra string (de até 40 caracteres). O tamanho será 
igual para as duas strings de entrada, e sempre menor ou igual a 20. 
Computação básica - carlacastanho@cic.unb.br 
Exemplo – Intercalação de Strings 
Algoritmo Intercala 
Variáveis 
 S1, S2 : vetor [21] de caracteres 
 S3 : vetor [41] de caracteres 
 i : inteiro 
Início 
 Leia (S1) 
 Leia (S2) 
 i ← 0 
 Enquanto (S1[i] ≠ NULO) faça 
 S3[2 * i] ← S1[i] 
 S3[2 * i + 1] ← S2[i] 
 i ← i + 1 
 Fim-Enquanto 
 S3[2 * i] ← NULO 
 Escreva (“String resultante: ”, S3) 
Fim 
Aqui estamos efetivamente manipulando os índices para 
intercalar as strings. Como isso funciona? Vamos fazer um 
“chinês”... 
para i = 0 → 2 * i = 0 2 * i + 1 = 1 
para i = 1 → 2 * i = 2 2 * i + 1 = 3 
para i = 2 → 2 * i = 4 2 * i + 1 = 5 
para i = 3 → 2 * i = 6 2 * i + 1 = 7 
para i = 4 → 2 * i = 8 2 * i + 1 = 9 
para i = 5 → 2 * i = 10 2 * i + 1 = 11 
para i = 6 → 2 * i = 12 2 * i + 1 = 13 
... 
para i = 19 → 2 * i = 38 2 * i + 1 = 39 
Exemplo 
 Faça um algoritmo que leia duas strings de, no máximo, 20 caracteres e intercale as 
letras de cada uma delas, em uma outra string (de até 40 caracteres). O tamanho será 
igual para as duas strings de entrada, e sempre menor ou igual a 20. 
Computação básica - carlacastanho@cic.unb.br 
Exemplo – Intercalação de Strings 
Algoritmo Intercala 
Variáveis 
 S1, S2 : vetor [21] de caracteres 
 S3 : vetor [41] de caracteres 
 i : inteiro 
Início 
 Leia (S1) 
 Leia (S2) 
 i ← 0 
 Enquanto (S1[i] ≠ NULO) faça 
 S3[2 * i] ← S1[i] 
 S3[2 * i + 1] ← S2[i] 
 i ← i + 1 
 Fim-Enquanto 
 S3[2 * i] ← NULO 
 Escreva (“String resultante: ”, S3) 
Fim 
Ao final, precisamos colocar o caractere NULO logo após a 
última posição da string. Isso é necessário pois todas as 
funções que manipulam string esperam esse padrão, inclusive 
a função “Escreva” que vem logo em seguida. 
Exemplo 
 Analisando o algoritmo anterior, qual seria a saída para as entradas abaixo? 
 S1: "ABCDEFGHIJKLMNOPQRST" 
 S2: "abcdefghijklmnopqrst" 
 
 
 
 
 
 
 
 
 
 
 Computação básica - carlacastanho@cic.unb.br 
Exemplo 
 Analisando o algoritmo anterior, qual seria a saída para as entradas abaixo? 
 S1: "ABCDEFGHIJKLMNOPQRST" 
 S2: "abcdefghijklmnopqrst" 
 S3: "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrDsTt" 
 
 
 
 
 
 
 
 
 
 
 
Computação básica - carlacastanho@cic.unb.br 
Exemplo 
 Analisando o algoritmo anterior, qual seria a saída para as entradas abaixo? 
 S1: "ABCDEFGHIJKLMNOPQRST" 
 S2: "abcdefghijklmnopqrst" 
 S3: "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrDsTt" 
 
 E para essas entradas? 
 S1: "AAAAAA" 
 S2: "BBBBBB" 
 
 
 
 
 
 Computação básica - carlacastanho@cic.unb.br 
Exemplo 
 Analisando o algoritmo anterior, qual seria a saída para as entradas abaixo? 
 S1: "ABCDEFGHIJKLMNOPQRST" 
 S2: "abcdefghijklmnopqrst" 
 S3: "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrDsTt" 
 
 E para essas entradas? 
 S1: "AAAAAA" 
 S2: "BBBBBB" 
 S3: "ABABABABABAB“ 
 
 
 
 
 Computação básica - carlacastanho@cic.unb.br 
Exemplo 
 Analisando o algoritmo anterior, qual seria a saída para as entradas abaixo? 
 S1: "ABCDEFGHIJKLMNOPQRST" 
 S2: "abcdefghijklmnopqrst" 
 S3: "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrDsTt" 
 
 E para essas entradas? 
 S1: "AAAAAA" 
 S2: "BBBBBB" 
 S3: "ABABABABABAB“ 
 
 Observe que a marca ao final da string permite que trabalhemos com strings 
menores que 20 caracteres, dando alguma flexibilidade. 
 
 
 
Computação básica - carlacastanho@cic.unb.br 
Strings em C 
 A Linguagem C suporta o tratamento de strings 
por meio da biblioteca <string.h>. 
 Todas as funções dessa biblioteca tratam strings 
como vetores de caracteres, com seu final 
indicado pelo caractere '\0' logo após a última 
posição. Esse caractere tem o código 0 na tabela 
ASCII. 
Computação básica - carlacastanho@cic.unb.br 
Strings em C 
 A função scanf deve ser chamada de maneira especial para ler uma string 
que contenha espaços em branco. 
 Em geral, essa função para de ler no primeiro espaço em branco que 
encontra. Se quisermos que ela somente pare ao achar uma nova linha, 
devemos chamá-la assim: 
 
 
 
 O getchar logo em seguida é muito importante para ler o caractere '\n' 
que ficou na entrada. Se você quiser, pode chamar também assim: 
 
 
 Nesse caso, a função vai ler até encontrar um '\n', em seguida, o %*c vai 
fazer a função ler e ignorar exatamente 1 caractere, dispensando o getchar. 
 
Computação básica - carlacastanho@cic.unb.br 
Exemplo – Usar scanf para ler uma string até nova linha. 
 scanf("%[^\n]s", string1); 
 getchar(); 
Exemplo – Usar scanf para ler uma string até nova linha – outra versão. 
 scanf("%[^\n]s%*c", string1); 
Strings em C 
Programa em C do exemplo de intercalação 
#include <stdio.h> 
 
int main () { 
 int i; 
 char S1[21], S2[21], S3[41]; 
 
 scanf("%s", S1); 
 scanf("%s", S2); 
 for (i = 0; S1[i] != '\0'; i++) { 
 S3[2 * i] = S1[i]; 
 S3[2 * i + 1] = S2[i]; 
 } 
 S3[2 * i] = '\0'; 
 printf("%s\n", S3); 
 
 return 0; 
} 
Computação básica - carlacastanho@cic.unb.br 
Strings em C – A biblioteca <string.h> 
Computação básica - carlacastanho@cic.unb.br 
Função Descrição 
int strlen(char *str) Retorna o número de caracteres em str, sem contar o '\0'. 
char* strstr(char* palheiro, 
 char* agulha) 
Procura pela primeira ocorrência da substring agulha em 
palheiro e retorna um ponteiro para a posição desta ocorrência 
ou NULL (ponteiro especial que não aponta para nada) caso não 
haja nenhuma ocorrência. 
int strcmp(char *str1, char 
 *str2) 
Retorna: um número negativo (<0) se str1 for lexicograficamente 
menor que str2; 0 se forem lexicograficamente iguais; e um 
número positivo (>0) se str1 for lexicograficamente maior que 
str2. 
O que significa lexicograficamente? A função compara, caractere a 
caractere, duas strings S1 e S2. Se o primeiro caractere de S1 
diferente de S2 tiver um código ASCII maior que o de S2, então S1 é 
maior que S2, e vice-versa. Se ambas começam com os mesmos 
caracteres mas uma é maior que a outra, a maior é considerada 
maior. A tabela ASCII atribui códigos que garantem a ordem 
alfabética da língua inglesa (desde que todas as letras sejam 
maiúsculas ou todas minúsculas). 
Strings em C – A biblioteca <string.h> 
Computação básica - carlacastanho@cic.unb.br 
Função Descrição 
int strcasemp(char *str1, 
 char *str2) 
Possui um comportamento similar a strcmp, mas ignora diferenças 
entre maiúsculas e minúsculas. 
char* strcat(char* cabeca, 
 char* cauda) 
Concatena cauda ao final de cabeca e retorna cabeca. O vetor 
que contem cabeca deve ter um tamanho suficiente para conter as 
duas strings mais um '\0'.char* strcpy(char *destino, 
 char *fonte) 
Copia a string em fonte o para destino. O vetor que contem 
destino deve ter um tamanho suficiente para conter fonte. 
char* strchr(char *str, 
 char c) 
Procura pela primeira ocorrência do caractere c em str e retorna 
um ponteiro para a posição desta ocorrência ou NULL, caso não 
ocorra. 
Strings – Exercícios 
 ATENÇÃO! Estes exercícios devem ser feitos sem a utilização da biblioteca <string.h>. A 
única função que você pode usar é strlen. 
1. Faça um algoritmo em C que leia duas strings e concatene-as em uma terceira string, 
mostrando o resultado na tela. Você pode definir o tamanho máximo das strings, mas o 
usuário poderá informar strings de tamanhos diferentes. 
2. Uma prova de 10 questões com cinco alternativas (A, B, C, D e E) de múltipla escolha foi 
aplicada em uma turma. Faça um algoritmo que leia o gabarito, o número de alunos e as 
respostas de cada aluno, e diga a maior nota obtida. 
 Exemplo de entrada: 
 Gabarito: ABCDEABCDE 
 Nro alunos: 3 
 Respostas aluno 1: ABCAABAAAA 
 Respostas aluno 2: ABCDABAAAA 
 Respostas aluno 3: ABCDEABCDD 
 Saída: 
 Maior nota obtida: 9. 
 
Computação básica - carlacastanho@cic.unb.br 
Strings – Exercícios 
 ATENÇÃO! Estes exercícios devem ser feitos sem a utilização da biblioteca <string.h>. A única função 
que você pode usar é strlen. 
 
3. Faça um programa que leia, via teclado, duas strings (de no máx. 20 posições) formadas apenas por letras 
e espaços brancos. O programa deve repassar estas duas strings para uma função que imprime uma lista 
das palavras que aparecem simultaneamente nas duas strings. Pode-se supor que em cada uma das strings 
não há palavras repetidas. Obs: lembre-se de que as frases digitadas podem ser menor que 20. Neste 
programa a impressão é feita na função. Não há retorno! 
 
4. Uma forma bem rudimentar de compactar textos pode ser representando caracteres repetidos como o 
número de repetições seguido do caractere. Escreva um programa que leia uma cadeia de caracteres e 
para cada um deles que possua adjacentes iguais a ele, grave em outra string o número de repetições e 
apenas uma cópia dele, e imprima apenas o caractere sem o número, caso naquela ocorrência não haja 
repetições. Assuma que um caractere se repete, no máximo, 9 vezes em cada grupo. 
 Exemplo da string de entrada: AAABCCCCCBBBCCAAA 
 Exemplo da string de saída: 3AB5C3B2C3A 
 Obs: para converter um inteiro n < 10 em um char, faça '0' + n 
Computação básica - carlacastanho@cic.unb.br 
Strings – Exercícios 
 ATENÇÃO! Estes exercícios devem ser feitos sem a utilização da biblioteca 
<string.h>. A única função que você pode usar é strlen. 
 
5. Crie um programa que leia o nome de uma pessoa (20 caracteres) e o 
escreva de trás para frente. Você pode usar a função strlen para descobrir 
o tamanho do nome digitado (ex: tamanho = strlen(nome), assim a 
variável tamanho receberá o número de caracteres armazenados na string 
nome). 
 
 
 
 
 
 
Computação básica - carlacastanho@cic.unb.br