Universidade
Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência da Computação
Algoritmos e
Estruturas de Dados I
Cadeias de
caracteres
Uma boa parte dos programas de computador precisa representar e
manipular números e também seqüências de
caracteres. As necessidades numéricas são, grosso modo, atendidas pelos tipos
primitivos tais como int e double. As linguagens de alto-nível têm
diferentes abordagens para lidar com a necessidade de representar e manipular
as seqüências de caracteres. Na linguagem C as seqüências de caracteres podem ser representadas utilizando
arranjos de caracteres (char arrays ou arrays of chars).
O trecho de programa:
char s[]=
{‘a’, ‘b’, ‘c’, ‘\0’};
Corresponde a definir 4 variáveis: (1) s[0] iniciada com ‘a’, (2) s[1] inicada com ‘b’, (3) s[2] iniciada com ‘c’ e (4) s[3] iniciada
com ‘\0’. Os projetistas da linguagem C decidiram proporcionar comodidade ao
programador que ao invés da inicialização acima pode-se
escrever:
char s[]=″abc″;
Esta última sentença tem exatamente o mesmo efeito da primeira. Ambas as
sentenças utilizam uma conveniência da linguagem/compilador que é a omissão do
limite da dimensão e correspondem à:
char s[4]=
{‘a’, ‘b’, ‘c’, ‘\0’};
char s[4]=″abc″;
Lembrando da relação entre arranjos e ponteiros,
contraste as declarações acima com a seguinte declaração:
char *pstr=″abc″;
Neste caso foi definida uma região de memória correspondente a 1(uma)
variável pstr e uma região de memória contendo a
constante string “abc” (que envolve o caractere nulo.
ou seja a sequência ‘a’, ‘b’, ‘c’,’\0’). O valor da variável pstr corresponde ao endereço de memória do inicio da cadeia
de caracteres (pstr recebe o endereço do caractere
‘a’). o ponteiro pstr pode
ser posteriormente modificado (via comando de atribuição) para apontar para
qualquer outro caractere! O trecho acima corresponde à definição de apenas uma
variável. Podemos modificar pstr através de uma
atribuição:
pstr=<expressão>;
Mas não podemos modificar os caracteres da constante string
“abc\0”:
char *pstr=”abc”;
*pstr=’x’; //resultado imprevisivel!!!
pstr[2]=’a’ //rsultado imprevisivel!!!!
Em função de um ponteiro corresponder a uma variável e dos projetistas da
linguagem quererem oferecer o literal do tipo string de maneira “confortável”, podemos fazer a atribuição
de um literal do tipo string para uma variável do
tipo ponteiro mesmo fora do contexto de declaração:
char *pstr=″abc″;
printf(″%s\n″, pstr);
pstr=”defghi”;
//corresponde a atribuir o >>endereco<<
da constante “defghi”
printf(″%s\n″, pstr);
Podemos usar ponteiros para caracteres de maneira similar a
arranjos:
char
s[]=”abc”;
char *pstr;
pstr=s;
*pstr=’x’; //ok! ou pstr[0]=’x’;
Apesar da intenção dos projetistas da linguagem C de que os
ponteiros e arranjos pudessem ser usados de maneira intercambiável, há
importantes diferenças quando declaramos e usamos ponteiros e arranjos. Além do
fato de que os arranjos (os identificadores de arranjos) só existem em tempo de
compilação, o “açucar sintático” relacionado aos strings de inicialização não tem o mesmo efeito:
na sentença:
char s[]=”abc”;
temos 4 variáveis: (i) s[0], (ii) s[1], (iii) s[2] e s[3] que corresponde ao caractere nulo ou 0; na
sentença:
char *pstr=”abc”;
temos apenas 1(uma) variável: pstr (as posições de
memória onde estão ‘a’ seguido de ‘b’ seguido de ‘c ‘ seguido de
‘\0’correspondem a uma região de constantes e não há garantia de que estas
posições possam ser usadas como variáveis, o efeito é indefinido caso o
programador insista em usá-las, por exemplo, para atribuição: pstr[1]=’d’;).
Um problema também um pouco “sutil” é o fato de que na
definição “char s[]=”abc”;” o identificador s equivale a
&s[0] e esta equivalência ocorre até a nível de tipo. o
valor de s é o mesmo de &s mas o tipo do primeiro valor é <ponteiro para
char> e o tipo de &s é <ponteiro para arranjo de char>. Isto é
discutido nas aulas.
Devem ser observadas as diferenças entre “arranjos de char”
e “arranjos de ponteiros para char” e o “conforto”que a linguagem/compilador fornece para o
programador. Considere a sentença abaixo:
char s[][5]={″″,
″a″,″ab″,″abc″,″abcd″};
Esta sentença corresponde a definir 25 variáveis (do tipo
char), de s[0][0] até s[4][4] com os valores:
00000a0000ab000abc00abcd0
Os cinco literais do tipo string
são abreviações de constantes do tipo char, é uma situação mais confortável do
que escrever:
char s[][5]={{0,0,0,0,0},{'a',
0,0,0,0}, {'a', 'b', 0,0,0},{'a','b','c',0,0}, {'a','b','c','d',0}};
Considere agora a sentença
char *s[]={″″,
″a″,″ab″,″abc″,″abcd″};
Esta sentença corresponde a definir 5 variáveis (do tipo
ponteiro para char), de s[0] até s[4]. Os cinco literais do tipo string servem para definir constantes na memória e as cinco
variáveis recebem os cinco endereços onde foram
colocados cada um dois respectivos literais. ë uma
situação mais confofrtável do que escrever:
char *s0=″″; char
*s1=″a″; char *s2=″ab″;
char *s3=″abc″;
char *s4=″abcd″};
char *s[]={s0,s1,s2,s3,s4};
O que é importante observar é que um “literal string” é tratado de mais de uma maneira dependendo do
contexto onde ele é usado. Um dos usos corresponde a alocar uma sequência de
valores do tipo char terminada com NULO e a avaliação corresponde ao endereço
do primeiro valor. Outro uso é um “açucar sintático”
para abreviar usos de sequências de valores do tipo char
Operações e funções
sobre os caracteres e cadeias de caracteres
Existem muitas funções pré-definidas na linguagem C para
manipulação de cadeias de caracteres, para utilizá-las deve ser colocado no
inicio do programa a sentença:
#include <string.h>
A função strcpy(s,t) copia o string
t para o string s, ou tentando falar com menos
“vícios”: a função strcpy copia a sequência de
caracteres apontada por t para a região de memória apontada por s. strcpy corresponde ao trecho de programa:
int i;
i=0;
while((s[i]=t[i])!=’\0’) i++;
A versão acima corresponde à visão “arranjo”! Abaixo a visão
“ponteiros”:
char *f=t;
..char *d=s;
while((*d=*f)!=’\0’){f++;
d++;}
Programadores C ficam satisfeitos em poder escrever:
char *f=t;
..char *d=s;
while((*d++=*f++)!=’\0’);
ou ainda
(lembrando que o “false” corresponde a zero!!!)
char *f=t;
..char *d=s;
while(*d++=*f++);
A função strcpy(s,t) tem como efeito a cópia do string t no string s; o valor
retornado pela função strcpy é o endereço de t
Voltando ao assunto de ponteiros e arranjos, observe que o
seguinte trecho de programa “tem significado” ou “é válido”:
char *pc=”abc”;
char ac[]=”xyz”;
strcpy(ac,
pc);
E o resultado é que as variáveis/componentes do arranjo ac passam a conter ‘a’, ‘b’, ‘c’ e \0 respectivamente. Mas o
resultado deste trecho é imprevisível:
char *pc=”abc”;
char ac[]=”xyz”;
strcpy(pc. ac);
Pois a região de memória correspondente ao
string “abc” pode ser, por exemplo, apenas
para leitura!
A função strcmp(s,t) compara os caracteres
apontados por s e t e retorna um valor negativo, zero ou positivo se a cadeia
apontada por s é lexicograficamente menor, igual ou maior, respectivamente, do
que a cadeia apontada por t. O valor é obtido subtraindo os caracteres na
primeira posição onde s e t são diferentes.
No programa abaixo fazemos a ordenação de cadeias de
caracteres sem movimentaras cadeias, fazemos o rearranjo dos ponteiros para as
cadeias:
#include <stdio.h>
#include <stdlib.h>
void ordenaPorSelecao(char
*a[], int N){
int i,j,indMenor;
char *aux;
for(i=0; i<N-1; i++){
indMenor=i;
for(j=i+1; j<N; j++)
if(strcmp(a[j],a[indMenor])<0) indMenor=j;
aux=a[i]; a[i]=a[indMenor];
a[indMenor]=aux;
}
}
int main(int
argc, char *argv[]){
char *elem[]={"e1234",
"b123456", "c12", "a123","d12345"};
int cnt;
for(cnt=0; cnt<5; cnt++) printf("%s\n", elem[cnt]);
ordenaPorSelecao(elem,5);
printf("-------------\n");
for(cnt=0; cnt<5; cnt++) printf("%s\n", elem[cnt]);
system("PAUSE");
return 0;
}
No programa acima não estamos ordenando diretamente
(movimentando) as cadeias de caracteres, na verdade estamos ordenando
(movimentando) os ponteiros do arranjo de ponteiros onde cada ponteiro
corresponde ao endereço de um arranjo de caracteres. O registro de ativação
correspondente à chamada da função de ordenação, com relação ao parâmetro a corresponde a um
ponteiro para arranjo de ponteiros para arranjo de caracteres.
Exercícios
- Escreva uma função int strlen() utilizando operadores de ponteiros (Sugestão de solução)
- Escreva uma função int strlen() utilizando operadores de indexação (Sugestão de solução)
- Escreva uma função int strncmp(cs,ct, n), utilizando
operadores de ponteiros, que compara no máximo n caracters
da cadeia apontada por cs com a cadeia apontada
por ct, retorna um int
negativo se a cadeia de cs<ct, retorna 0 se cs==ct e retorna um int maior
que zero se cs>ct.
- Escreva a função strncmp no estilo arranjo&indexação.
- Escreva um trecho de
programa que imprime se as letras maiúsculas são maiores ou menores,
lexicograficamente, que as letras minúsculas. (solução)
- Escreva um trecho de
programa que transforma um inteiro menor que 4000 e maior que zero em uma
cadeia de caracteres correspondente a um número romano e vice versa.
Os trechos abaixo mostram diferentes estilos de solução:
void UserConvert(void){
int
num;
printf("Entre
com numero:");
scanf("%i",
&num);
while
(num >= 1000){printf("M");num -=
1000;}
if
(num >= 900){ printf("CM"); num -= 900;
}if
(num >= 500){printf("D"); num -= 500;
}if
(num >= 400){printf("CD"); num -= 400;
}
while
(num >= 100){printf("C"); num -=
100;}
if (num
>= 90){ printf("XC"); num -= 90;
}if
(num >= 50){ printf("L"); num -= 50;
}if
(num >= 40){ printf("XL"); num -= 40;
}
while
(num >= 10){printf("X"); num -=
10;}
if
(num >= 9){ printf("IX"); num -= 9;
}if
(num >= 5){ printf("V"); num -= 5;
}if
(num >= 4){ printf("IV"); num -= 4;
}
while
(num >= 1){printf("I");num -= 1;}
}
--------------------------------------------
static char *u[]={"",
"I", "II", "III", "IV",
"V", "VI", "VII",
"VIII","IX" };
static char *d[]={"",
"X", "XX", "XXX", "XL",
"L", "LX", "LXX",
"LXXX","XC" };
static char *c[]={"",
"C", "CC", "CCC", "CD",
"D", "DC", "DCC",
"DCCC","CM" };
static char *m[]={"",
"M", "MM", "MMM"};
int romano2arabico(char *strRomano){
int
i; int ind=0;
int
num=0;
//tenta encontrar milhares
for(i=3; i>0; i--)if(strncmp(strRomano, m[i], strlen(m[i]))==0)
break;
num=1000*i; strRomano+=i;
for(i=9; i>0; i--)if(strncmp(strRomano, c[i], strlen(c[i]))==0)
break;
num=num+100*i; strRomano+=i;
for(i=9; i>0; i--)if(strncmp(strRomano, d[i], strlen(d[i]))==0)
break;
num=num+10*i; strRomano+=i;
for(i=9; i>0; i--)if(strncmp(strRomano, u[i], strlen(u[i]))==0)
break;
num=num+i;
return
num;
}
int main(int argc, char *argv[])
{
printf("entre
com romano:");
char buf[200];
scanf("%s",
buf);
printf("%d\n",
romano2arabico(buf));...
- Escreva um trecho de
programa que produz um arranjo de caracteres que seja o resultado da concatenaçao dos primeiros caracteres das palavras
separadas por espaço em branco e que comecem com letra maíuscula.
Exemplo: o string
"Universidade Federal de Minas Gerais" deve resultar em
"UFMG".