Baixe o app para aproveitar ainda mais
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
Compartilhar