TEP_Slides-03

Strings
COM11087-Tópicos Especiais em Programação I
[email protected]
2016-I
Introdução
 Uma estrutura de dados fundamental
 Crescente Importância
 Aplicações:
 Busca do Google
 Genoma Humano
2
2016-I
Caracteres Codificação
 Códigos de caracteres são mapeamentos entre
os símbolos que compõem um alfabeto e
números
 Computadores
são
fundamentalmente
definidos para trabalhar com números. O que
eles sabem é que cada símbolo é representado
por um número
 Exemplos:
 Alterar a fonte (bit-map)
 Trocar Idioma do SO
3
2016-I
Caracteres Codificação
 American Standard
Interchange (ASCII)
Code
for
Information
 Usa 1 byte (8 bits) para representar um
caractere
 O bit da esquerda é sempre 0 fazendo com que
haja 27 (128) caracteres representados
4
2016-I
Caracteres Codificação
5
2016-I
Exemplos de Aplicações
 Todas letras (maiúsculas e minúsculas) e os
dígitos aparecem sequenciamente, isso facilita
na hora de fazer um loop de “a” até “z”.
 Caracteres “não imprimíveis” possui os três bits
inicias como 0 ou todos os 7 bits como 1.
Facilita na eliminação desses caracteres na
impressão.
 Descobrir a posição de um caractere. Subtrair
do elemento da primeira posição (“I” – “A”+1) =
9
6
2016-I
Exemplos de Aplicações
 Converter de Maiúscula para mínuscula: “C”“A”+ “a”. Saber se é maíuscula > “A” e < “Z”.
 Ordem
alfabética
caracteres.
significa
ordem
dos
 “Nova Linha” (10) e “Backspace” (13) são
caracteres usados para marcar o fim de uma
linha na string.
7
2016-I
Observações
 Existem outras codificações
 ASCII é a principal e mais utilizada pela sua
economia de memória (1 byte)
 C e C++ usam o padrão de 1 byte para o tipo
char
 Java usa o padrão de 2 bytes para o tipo char
8
2016-I
Representação Strings
 C e C++ tratam strings como arrays de
caracteres finalizados com o caractere “nulo”
(elemento 0 na tabela ASCII)
 Se o elemento nulo não for explicitado colocase outros caracteres não-imprimíveis
 Cuidado com o tamanho da String que deve
garantidamente ter espaço para o caractere
nulo
 Vantagem: Acesso direto a um caractere da
string
9
2016-I
Representação Strings
 Uma outra possibilidade é usar a primeira
posição da string para armazenar o tamanho,
sem precisar assim do caracter nulo.
 Se
for
usar
frequentemente
a
inserção/eliminação de substrings, o uso de
lista encadeada pode ser viável
10
2016-I
Exemplo
Corporate name changes are occurring with ever greater
frequency, as companies merge, buy each other out, try to hide
from bad publicity, or even raise their stock price – remember
when adding a .com to a company’s name was the secret to
success!
These changes make it difficult to figure out the current name of a
company when reading old documents. Your company, Digiscam
(formerly Algorist Technologies), has put you to work on a program
which maintains a database of corporate name changes and does
the appropriate substitutions to bring old documents up to date.
Your program should take as input a file with a given number of
corporate name changes, followed by a given number of lines of
text for you to correct. Only exact matches of the string should be
replaced. There will be at most 100 corporate changes, and each
line of text is at most 1,000 characters long. A sample input is —
11
2016-I
Exemplo
4
"Anderson Consulting" to "Accenture"
"Enron" to "Dynegy"
"DEC" to "Compaq"
"TWA" to "American"
5
Anderson Accounting begat Anderson Consulting, which
offered advice to Enron before it DECLARED bankruptcy,
which made Anderson
Consulting quite happy it changed its name
in the first place!
Which should be transformed to —
Anderson Accounting begat Accenture, which
offered advice to Dynegy before it CompaqLARED bankruptcy,
which made Anderson
Consulting quite happy it changed its name
in the first place!
12
2016-I
Exemplo
13
2016-I
Exemplo
14
2016-I
Exemplo
15
2016-I
C++ Funções
string::size() /* string length */
string::empty() /* is it empty */
string::c_str() /* return a pointer to a C style string */
string::operator [](size_type i) /* access the ith character */
string::append(s) /* append to string */
string::erase(n,m) /* delete a run of characters */
string::insert(size_type n, const string&s) /* insert string s at n */
string::find(s)
string::rfind(s) /* search left or right for the given string */
string::first()
string::last() /* get characters, also there are iterators */
16
2016-I
Exercícios
• WERTYU
• Common Permutation
• Where’s Waldorf ?
• Crypt Kicker II
• Doublets
17
2016-I
Strings
COM11087-Tópicos Especiais em Programação I
[email protected]
2016-I