Tutorial de Ponteiros e Arrays em C
Ted Jensen (Tradução César A. K. Grossmann)
%! Encoding : iso-8859-1
%! CmdLine : -t html --toc
%! PostProc : '
' ''
%! PostProc(html) : '\\br' '
'
%! PostProc : '\\br' ''
%! PostProc(html) : '(?)B>' '\1STRONG>'
%! PostProc(html) : '(?)I>' '\1EM>'
%! PostProc(html) : '\._' ''
%! PostProc : '\._' ''
%! PostProc(html) : '_\.' ''
= Prefácio =
Este documento foi feito como uma introdução aos ponteiros para
programadores iniciantes na linguagem C. Depois de vários anos de
leituras e contribuições a várias conferências sobre C, incluindo as da
FidoNet e UseNet, eu notei que um grande número de novatos no C parecem
ter uma dificuldade em entender os fundamentos do ponteiros. Eu resolvi
então assumir a tarefa de tentar explicar a eles em uma linguagem
simples e com muitos exemplos.
A primeira versão deste documento foi colocada no domínio público, assim
como esta. Ela foi escolhida por Bob Stout, que incluiu o mesmo como o
arquivo PTR-HELP.TXT, em sua coleção largamente distribuída de SNIPPETS.
Desde o lançamento original em 1995, eu acrescentei uma quantia
significativa de material e fiz algumas correções menores ao trabalho
original.
Na versão HTML 1.1, eu fiz um pequeno número de mudanças na apresentação
como resultado de comentários que recebi por email de todo o mundo. Na
versão 1.2 eu atualizei os dois primeiros capítulos para refletir a
mudança de compiladores 16 bits para compiladores 32 bits nos PCs.
== Agradecimentos ==
Existem tantas pessoas que contribuiram sem saber a este trabalho, por
causa das questões que eles colocaram no FidoNet C Echo, ou no Newsgroup
UseNet comp.lang.c, ou várias outras conferências em outras redes, que
seria impossível listar a todas. Agradecimentos em especial a Bob Stout,
que foi gentil em incluir a primeira versão deste material em seu
arquivo SNIPPETS.
== Sobre o Autor ==
Ted Jensen é um Engenheiro Eletrônico aposentado que trabalhou como
projetista de hardware ou gerente de projetistas de hardware no campo de
gravação magnética. Programação tem sido um hobby seu desde 1968,
quando ele aprendeu a perfurar cartões para serem executados em um
mainframe (o mainframe tinha 64K de memória de núcleo magnético!).
== Uso deste Material ==
Tudo que está contido aqui está liberado para o Domínio Público.
Qualquer pessoa pode copiar ou distribuir este material da maneira que
desejar. A única coisa que eu peço é que se este material for usado como
auxílio em uma class, eu apreciaria se ele fosse distribuído completo,
ou seja, incluindo todos os capítulos, prefácio e introdução. Eu também
apreciaria se, nestas circunstâncias, o instrutor desta classe me
enviasse uma nota em um dos endereços abaixo para me informar disto. Eu
escrevi este material na esperança que o mesmo fosse útil para outros e
como eu não estou pedindo nenhuma remuneração financeira, a única forma
de eu saber que eu atingi pelo menos parcialmente meu objetivo é através
deste feedback dos que acharam este material útil.
A propósito, você não precisa ser um instrutor ou professor para
contactar-me. Eu apreciarei uma nota de qualquer um que achar este
material útil, ou que tiver alguma crítica construtiva a oferecer.
Também estou disposto a responder a perguntas enviadas via email para o
endereço abaixo.
== Outras Versões Deste Documento ==
Além da versão hipertexto deste documento, eu disponibilizei outras
versões mais apropriadas para impressão ou para download do documento
completo. Se você está interesssado em manter-se atualizado com meu
progresso nesta área, ou quiser verificar se há versões mais recentes
deste documento, veja meu Wev Site em
http://www.netcom.com/~tiensen/ptr/cpoint.hm
Ted Jensen\br
Redwood City, California\br
tjensen@ix.netcom.com\br
Feb. 2000
= Introdução =
Se você quer ter proficiência em escrever código na linguagem C, tem
que ter um bom conhecimento sobre como usar ponteiros. Infelizmente, os
ponteiros C parecem representar um obstáculo para novatos,
particularmente para os que vêem de outras linguagens de computador,
como FORTRAN, Pascal ou BASIC.
Para ajudar estes novatos a entender ponteiros eu escrevi o material
presente. Para obter o máximo benefício deste material, eu acho
importante que o usuário consiga executar o código das várias listagens
contidas no artigo. Eu tentei, portanto, fazer com que todo o código
atendesse às normas ANSI, de forma que irá funcionar com qualquer
compilador que também atenda as mesmas normas ANSI. Eu também tentei
colocar o código em blocos no texto. Desta forma, com a ajuda de um
editor de textos ASCII, você pode copiar um dado bloco de código para um
novo arquivo e compilar o mesmo em seu sistema. Eu recomendo que os
leitores façam isto já que vai ajudar a entender o material.
+ O Que É Um Ponteiro? +
Uma das coisas que os novatos em C tem dificuldade é o conceito de
ponteiros. O objetivo deste tutorial é fornecer uma introdução aos
ponteiroes e o seu uso para estes novatos.
Eu descobri que uma das razões principais para os problemas que os
novatos tem com ponteiros é que eles tem um conhecimento fraco ou mínimo
sobre variáveis (da forma que são usadas em C). Assim, vamos começar a
discussão com as variáveis C em geral.
Uma variável em um programa é algo que tem um nome, e cujo valor pode
variar. A forma que o compilador e o linker tratam-nas é que eles
atribuem um bloco específico da memória do computador para guardar o
valor da variável. O tamanho do bloco depende do intervalo de valores
permitido à variável. Por exemplo, em um PC de 32 bits, o tamanho de uma
variável **integer** é 4 bytes. Em velhos PCs de 16 bits, era 2 bytes.
Em C o tamanho de um tipo de variável como o inteiro não precisa ser o
mesmo em todos os tipos de máquinas. Além disto, existe mais de um tipo
de variável inteira em C. Temos os **integers**, os **long integers**, e
os **short integers** que você vai encontrar em qualquer texto básico
sobre C. Este documento assume o uso de um sistema de 32 bits com
**integers** de 4 bytes.
Se você quiser saber o tamanho dos vários tipos de inteiros no seu
sisetma, execute o código abaixo que ele lhe dará esta informação.
---
#include
int main()
{
printf("size of a short is %d\n", sizeof(short));
printf("size of a int is %d\n", sizeof(int));
printf("size of a long is %d\n", sizeof(long));
}
---
Quando declaramos uma variável, informamos ao compilador duas coisas, o
nome da variável e o tipo da mesma. Por exemplo, declaramos uma variável
do tipo integer com o nome **k** escrevendo:
---
int k;
---
Ao ver a parte "`int`" nesta declaração o compilador reserva 4 bytes
de memória (em um PC) para guardar o valor do integer. Ele também monta
uma tabela de símbolos. Nesta tabela ele acrescenta o símbolo **k** e o
endereço relativo na memória em que estes 4 bytes foram separados.
Desta forma, se mais tarde escrevemos:
---
k = 2;
---
esperamos que, na execução, quando esta declaração for executada, o
valor 2 seja colocado na porção de memória reservada para guardar o
valor de **k**. Em C nos referimos a uma variável como o integer **k**
como sendo um "objeto".
Em um certo sentido existem dois "valores" associados ao objeto **k**.
Um é o valor do inteiro armazenado ali (2 no exemplo acima) e o outro é
o "valor" da localização de memória, isto é, o endereço de **k**. Alguns
textos se referem a estes dois valoers com a nomenclatura */rvalue/*
(right value, valor à direita, pronunciado "are value"), e */lvalue/*
(left value, valor à esquerda, pronunciado "el value") respectivamente.
Em algumas linguagens, o lvalue é o valor que pode aparecer do lado
esquerdo de um operador de atribuição '`=`' (isto é, o enderço para onde
o resultado da expressão do lado direito vai). O rvalue é o que está no
lado direito da declaração de atribuição, o **2** acima. Rvalues não
podem ser usados no lado esquerdo da declaração de atribuição. Desta
forma, **`2 = k;`** é ilegal.
Na verdade, a definição acima de "lvalue" foi um pouco modificada para o
C. De acordo com K&R II (página 197):[1]
"An */object/* is a named region of storage; an */lvalue/* is an
expression referring to an object."
("Um */objeto/* é uma região de armazenamento que tem nome; um
*/lvalue/* é uma expressão que refere um objeto.")
Entretanto, neste ponto, a definição originalmente citada acima é
suficiente. Conforme nos tornamos mais familiares com ponteiros iremos
entrar em mais detalhes sobre isto.
Vamos considerar agora:
---
int j, k;
k = 2;
j = 7; <-- linha 1
k = j; <-- linha 2
---
No exemplo acima, o compilador interpreta o **j** na linha 1 com sendo o
endereço da variável **j** (seu lvalue) e cria o código para copiar o
valor 7 para aquele endereço. Na linha 2, entretanto, o **j** é
interpretado como o seu rvalue (já que está no lado direito do operador
de atribuição `'='`). Ou seja, aí o **j** se refere ao valor
*/armazenado/* na posição de memória reservada para o **j**, neste caso,
o 7. Assim, o 7 é copiado para o endereço designado pelo lvalue **k**.
Em todos estes exemplos, estamos uando inetgers de 4 bytes de forma que
todas as cópias de rvalues de um local de armazenamento para outro é
feito pela cópia de 4 bytes. Se estivéssemos usando inteiros de 2 bytes,
estaríamos copiando 2 bytes.
Agora, digamos que temos uma razão para querer que uma variável armazene
um lvalue (um endereço). O tamanho necessário para armazenar este tipo
de valor depende do sistema. Em computadores desktop antigos com 64K de
memória total, o endereço de qualquer ponto na memória pode estar
contido em 2 bytes. Computadores com mais memória vão necessitar mais
bytes para conter um endereço. O tamanho real necessário não é tão
importanto, já que temos uma forma de informar ao compilador que o que
queremos armazenar é um endereço.
Este tipo de variável é chamado de */variável ponteiro/* (por razões que
esperamos que fiquem claras um pouco mais adiante). Em C quando
definimos uma variável ponteiro nós o fazemos precedendo o seu nome com
um asterisco. Em C também damos a nosso ponteiro um tipo que, neste
caso, refere-se ao tipo de dado armazenado no endereço que estaremos
armazenando em nosso ponteiro. Por exemplo, considere a declaração de
variável:
---
int *ptr;
---
**ptr** é o nome de nossa variável (como **k** era o nome de nossa
variável integer). O '`*`' informa ao compilador que queremos uma
variável ponteiro, isto é, ele deve separar tantos bytes quantos forem
necessários para armazenar um endereço na memória. O **int** diz que
pretendemos uasr nossa variável ponteiro para armazenar o endereço de um
inteiro. Deste tipo de ponteiro se diz que ele "aponta para" um inteiro.
Entretanto, note que quando escrevemos **`int k;`**, nós não damos a
**k** um valor. Se esta definição for feita fora de qualquer função,
compiladores ANSI irão colocar nelas o valor inicial zero. De forma
semelhante, **ptr** não tem um valor, já que não armazenamos um endereço
na declaração acima. Neste caso, novamente se a declaração estiver fora
de qualquer função, ela é inicializada para um valor que garantidamente
não aponta para qualquer objeto C ou função. Um ponteiro iniciado desta
forma é chamado de ponteiro "null".
O padrão de bits usado para um ponteiro null pode ou não resultar em
zero já que depende do sistema específico no qual o código está sendo
desenvolvido. Para fazer com que o código fonte seja compatível entre
vários compiladores em vários sistemas, uma macro é usada para
representar um ponteiro null. A macro recebe o nome `NULL`. Assim,
colocar o valor NULL em um ponteiro, como em uma declaração de
atribuição, como `ptr = NULL;`, garante que o ponteiro é um ponteiro
null. De forma similar, da mesma forma que alguém testa um valor inteiro
para ver se é zero, como em **`if(k == 0)`**, podemos testar se um
ponteiro é null usando **`if(ptr == NULL)`**.
Voltemos ao uso de nossa nova variável **ptr**. Suponha agora que
queremos armazenar em **ptr** o endereço de nossa variável inteira
**k**. Para isto, usamos o operador unário **&** e escrevemos:
---
ptr = &k;
---
O que o operador **&** faz é recuperar o lvalue (endereço) de **k**,
mesmo que **k** esteja no lado direito do operador '`=`' de atribuição,
e copia o mesmo para o conteúdo de nosso ponteiro ptr. Agora, diz-se que
ptr "aponta para" **k**. Continue conosco agora, há somente mais um
operador que precisamos discutir.
O "operador de dereferenciamento" é o asterisco, e é usado conforme o
exemplo abaixo:
---
*ptr = 7;
---
Esta linha irá copiar o 7 para o endereço apontado por **ptr**. Assim,
se **ptr** "aponta para" (contém o endereço de) **k**, a declaração
acima irá colocar em **k** o valor 7. Ou seja, quando usamos o '`*`'
desta forma, estamos nos referindo ao valor para o qual ptr está
apontando, não ao valor do ponteiro em si.
De forma semelhante, podemos escrever:
---
printf("%d\n", *ptr);
---
para escrever na tela o valor inteiro armazenado no endereço apontado
por **ptr**.
Uma forma de ver tudo isto junto é executar o seguinte programa e então
ervisar o código e a saída cuidadosamente.
Programa 1.1
---
/* Program 1.1 from PTRTUT10.TXT 6/10/97 */
#include
int j, k;
int *ptr;
int main(void)
{
j = 1;
k = 2;
ptr = &k;
printf("\n");
printf("j has the value %d and is stored at %p\n", j, (void *)&j);
printf("k has the value %d and is stored at %p\n", k, (void *)&k);
printf("ptr has the value %p and is stored at %p\n", ptr, (void *)&ptr);
printf("The value of the integer pointed to by ptr is %d\n", *ptr);
return 0;
}
---
Nota: Ainda temos que discutir os aspectos de C que requerem o uso da
expressão **`(void *)`** usada acima. Por enquanto, inclua a mesma no
seu código de teste. Iremos explicar as razões por trás desta expressão
mais tarde.
--------------------
Para revisar:
- Uma variável é declarada dando a ela um tipo e um nome (p.ex., **int k;**)
- Uma variável ponteiro é declarada dando a ela um tipo e um nome
(p.ex., **int *ptr**) onde o asterisco informa ao compilador que a
variável de nome **ptr** é uma variável ponteiro e o tipo informa ao
compilador que tipo o ponteiro aponta (inteiro neste caso).
- Uma vez que uma variável seja declarada, podemos obter seu endereço
precedendo o seu nome com o operador unário **&**, como em **&k**.
- Podemos "dereferenciar" um ponteiro, isto é, referirmos o valor para o
qual ele aponta, usando o operador unário '`*`' como em **`*ptr`**.
- O "lvalue" de uma variável é o valor de seu endereço, isto é, onde ela
está armazenada na memória. O "rvalue" de uma variável é o valor
armazenado naquela variável (naquele endereço).
== Referências ==
[1] "The C Programming Language" 2nd Edition\br
B. Kernighan and D. Ritchie\br
Prentice Hall\br
ISBN 0-13-110362-8
+ Tipos Ponteiros e Arrays +
Podemos avançar agora. Consideremos que precisamos identificar o
*/tipo/* da variável para o qual o ponteiro aponta, como em:
--- int *ptr;
Uma razão para fazer isto é que mais tarde, uma vez que ptr "aponte
para" alguma coisa, se escrevermos:
--- *ptr = 2;
o compilador saberá quantos bytes copiar para aquela localização de
memória apontada por **ptr**. Se **ptr** foi declarado como apontando
para um inteiro, 4 bytes serão copiados. De forma semelhante para
floats e doubles o número apropriado será copiado. Mas, definir o tipo
para o qual o ponteiro aponta permite um grande número de outras formas
que o compilador pode interpretar o código. Por exemplo, considere um
bloco de memória consistindo em dez inteiros em linha. Ou seja, 40 bytes
de memória são separados para armazenar 10 inteiros.
Agora, digamos que apontamos nosso ponteiro **ptr** para o
primeiro destes inteiros. Mais, vamos dizer que aquele inteiro está
localizado na posição de memória 100 (decimal). O que acontece quando
escrevemos:
--- ptr + 1;
Como o compilador "sabe" que se trata de um ponteiro (isto é, seu valor
é um endereço), e que está apontando para um inteiro (seu endereço
atual, 100, é o endereço de um inteiro), ele acrescenta 4 a **ptr**, em
vez de 1, assim o ponteiro "aponta" para o **próximo inteiro**, na
posição de memória 104. De forma semelhante, onde o **ptr** é declarado
como um ponteiro para um short, ele será acrescido de 2 em vez de 1. O
mesmo vale para outros tipos de dados, como floats, doubles, ou mesmo
tipos de dados definidos pelo usuário, como estruturas. Isto obviamente
não é o mesmo tipo de "adição" que normalmente pensamos. Em C, ela é
referida como adição usando "aritmética de ponteiros", um termo que
iremos retornar mais tarde.
De forma similar, já que **`++ptr`** e **`ptr++`** são equivalentes a
**`ptr + 1`** (apesar que o ponto no programa em que **ptr** seja
incrementado pode ser diferente), incrementar um ponteiro usando o
operador unário `++`, tanto pré ou pós, incrementa o endereço que ele
armazena pela quantidade `sizeof(type)` onde "`type`" é o tipo de objeto
apontado (isto é, 4 para um inteiro).
Como um bloco de 10 inteiros localizado de forma contígua na memória é,
por definição, um //array// de inteiros, temos aí um relacionamento
interessante entre arrays e ponteiros.
Considere o seguinte:
--- int my_array[] = {1, 23, 17, 4, -5, 100};
Temos aí um array contendo 6 inteiros. Nos referimos a cada um destes
inteiros via um subscrito a **my_array**, isto é, usando
**`my_array[0]`** a **`my_array[5]`**. Mas podemos alternativamente
acessá-los usando um ponteiro, como no exemplo abaixo:
---
int *ptr;
ptr = &my_array[0]; /* aponta nosso ponteiro para o primeiro
inteiro em nosso array */
---
E assim podemos escrever nosso array usando ou a notação de array, ou
dereferenciando nosso ponteiro. O seguinte código ilustra isto:
Programa 2.1
---
/* Program 2.1 from PTRTUT10.HTM 6/13/97 */
#include
int my_array[] = {1,23,17,4,-5,100};
int *ptr;
int main(void)
{
int i;
ptr = &my_array[0]; /* point our pointer to the first
element of the array */
printf("\n\n");
for (i = 0; i < 6; i++)
{
printf("my_array[%d] = %d ",i,my_array[i]); /*<-- A */
printf("ptr + %d = %d\n",i, *(ptr + i)); /*<-- B */
}
return 0;
}
---
Compile e execute o programa acima e note com cuidado as linhas A e B e
que o programa escreve os mesmos valores em cada caso. Também note como
dereferenciamos nosso ponteiro na linha B, isto é, primeiro
incrementamos ele e então dereferenciamos o novo ponteiro. Mude a linha
B para:
--- printf("ptr + %d = %d\n", i, *ptr++);
e execute o programa novamente... então mude para:
--- printf("ptr + %d = %d\n", i, *(++ptr));
e tente novamente. Cada vez tente prever o resultado e examine com
cuidado o resultado real.
Em C, o padrão declara que onde precisamos usar **&var_name[0]**,
podemos trocar por **var_name**, assim, no nosso código, onde
escrevemos:
--- ptr = &my_array[0];
podemos escrever:
--- ptr = my_array;
para obter o mesmo resultado.
Por causa disto que muitos textos se referem ao nome de um array como um
ponteiro. Eu prefiro pensar que "o nome do array é o endereço do
primeiro elemento do array". Muitos iniciantes (inclusive eu quando
estava aprendendo) tem a tendência de ficar confuso ao pensar nisto como
um ponteiro. Por exemplo, enquanto podemos escrever
--- ptr = my_array;
não podemos escrever
--- my_array = ptr;
A razão é que enquanto **ptr** é uma variável, **my_array** é uma
constante. Ou seja, o local onde o primeiro elemento de **my_array**
será armazenado não pode ser alterado uma vez que **my_array[]** tenha
sido declarado.
Um pouco antes, quando discutimos o termo "lvalue", eu citei K&R-2 onde
está declarado:
"An **object** is a named region of storage; an **lvalue** is an
expression referring to an object".
("Um **objeto** é uma região de armazenamento com nome; um **lvalue** é
uma expressão que se refere a um objeto").
Isto leva a um problema interessante. Como **my_array** é uma região de
armazenamento nomeada, por quê **my_array** na declaração acima não é um
lvalue? Para resolver este problema, alguns se referem a **my_array**
como sendo um "lvalue não modificável".
Modifique o programa exemplo acima trocando
--- ptr = &my_array[0];
para
--- ptr = my_array;
e execute novamente para ver se os resultados são idênticos.
Agora, vamos nos aprofundar um pouco mais na diferença entre os nomes
**ptr** e **my_array** como foram usados acima. Alguns autores se
referem ao nome de um array como sendo um ponteiro */constante/*. O que
isto quer dizer? Bem, para entender o termo "constante" neste sentido,
vamos retornar à nossa definição do termo "variável". Quando declaramos
uma variável nós separamos um ponto na memória para armazenar o valor do
tipo apropriado. Uma vez que isto foi feito, o nome da variável pode ser
interpretado em uma de duas formas. Quando usado no lado esquerdo do
operador de atribuição, o compilador interpreta como o local de memória
para o qual mover o valor resultante da avaliação do termo do lado
direito do operador de atribuição. Mas, quando usado no lado direito do
operador de atribuição, o nome da variável é interpretado como
significando o conteúdo armazenado naquele endereço de memória, separado
para armazenar o valor daquela variável.
Com isto em mente, vamos agora considerar a mais simples das constantes,
como em:
---
int i, k;
i = 2;
---
Aqui, enquanto **i** é uma variável e então ocupa espaço na porção
dedicada aos dados na memória, **2** é uma constante e, como tal, em vez
de receber memória no segmento de dados, ela está inserida diretamente
no segmento de código da memória. Ou seja, enquanto escrever algo como
**`k = i;`** diz ao compilador para criar código que na execução irá
procurar a localização de memória **&i** para determinar o valor a ser
movido para **k**, o código criado por **`i = 2;`** simplemente coloca
**2** no código e não há referências ao segmento de dados. Ou seja,
tanto **k** quanto **i** são objetos, mas **2** não é um objeto.
De forma similar, no exemplo acima, como **my_array** é uma constante,
uma vez que o compilador estabelece onde o array será armazenado, ele
"sabe" o endereço de **`my_array[0]`** e ao ver:
--- ptr = my_array;
ele simplesmente usa este endereço como uma constante no segmento de
código e, portanto, não está fazendo referência ao segmento de dados.
Este pode ser um bom momento para explicar um pouco mais o uso da
expressão **`(void *)`** usada no Programa 1.1 no Capítulo 1. Como já
vimos, podemos ter ponteiros de vários tipos. Até agora discutimos
ponteiros para inteiros e ponteiros para caracteres. Nos capítulos
seguintes aprenderemos sobre ponteiros a estruturas e mesmo ponteiros a
ponteiros.
Também aprendemos que em diferentes sistemas o tamanho de um ponteiro
pode variar. Da mesma forma, é possível que o tamanho de um ponteiro
possa variar dependendo do tipo de objeto apontado. Assim, da mesma
forma que com os inteiros você pode ter problemas se tentar atribuir um
inteiro long a uma variável do tipo short, você pode ter problemas se
tentar atribuir valores de ponetiros de vários tipos para variáveis
ponteiro de outros tipos.
Para minimizar este problema, o C permite ponteiros do tipo void.
Podemos declarar este tipo de ponteiro escrevendo:
--- void *vptr;
Um ponteiro void é um tipo de ponteiro genérico. Por exemplo, enquanto o
C não permite a comparação de um ponteiro do tipo inteiro com um
ponteiro do tipo caracter, por exemplo, qualquer um deles pode ser
comparado a um ponteiro void. Obviamente, como com outras variáveis,
//casts// podem ser usados para converter de um tipo de ponteiro para
outro, nas circunstâncias apropriadas. No Programa 1.1 do Capítulo 1 eu
fiz um //cast// dos ponteiros para inteiros para ponteiros void para que
ficassem compatíveis com a especificaçãod e conversão de %p. Nos
capítulos seguintes, outros //casts// serão feitos por razões a serem
apresentadas.
Bem, foi bastante coisa técnica para digerir, e eu não espero que um
iniciante tentenda tudo isto na primeira leitura. Com o tempo e
experiência você vai voltar e reler os dois primeiros capítulos. Por
ora, vamos avançar para o relacionamento entre os ponteiros, arrays de
caracter, e strings.
+ Ponteiros e Strings +
O estudo de strings é útil para entender mais o relacionamento entre
ponteiros e arrays. Ele também torna fácil ilustrar como algumas das
funções string padrão do C podem ser implementadas. Finalmente, ele
ilustra como e quando os ponteiros podem e devem ser passados à funções.
Em C, strings são arrays de caracteres. Isto não é necessariamente
verdadeiro em outras linguagens. Em BASIC, Pascal, FORTRAN e várias
outras linguagens, uma string tem seu próprio tipo de dados. Mas em C,
não. Em C uma string é qualquer array de caracteres terminado com um
caracter binário zero (também chamado de nul ou nulo, escrito como
**`'\0'`**). Para começar nossa discussão vamos escrever algum código
que, enquanto serve como ilustração, você provavelmente nunca escreverá
algo parecido em um programa real. Considere, por exemplo:
---
char my_string[40];
my_string[0] = 'T';
my_string[1] = 'e';
my_string[2] = 'd':
my_string[3] = '\0';
---
Apesar de ninguém nunca escrever uma string desta forma, o resultado
final é um array de caracteres **terminado com um caracter nul**. Por
definição, em C, uma string é um array de caracteres terminada com o
caracter nul. Perceba, entretanto, que "**nul**" **não é* o mesmo que
"**NULL**". 'nul' refere-se ao zero como definido pela seqüência de
escape **`'\0'`**. Ela ocupa um byte de memória. NULL, por outro lado, é
o nome da macro usada para iniciar ponteiros nulos. NULL é definido por
`#define` em um arquivo de cabeçalho em seu compilador C, nul pode não
ser definido em lugar nenhum.
Como escrever o código acima pode demorar bastante, o C permite duas
formas alternativas de chegar ao mesmo fim. Primeiro, pode-se escrever:
--- char my_string[40] = ('T', 'e', 'd', '\0'};
Mas isto também usa mais digitação do que é conveniente. Assim, o C
permite:
--- char my_string[40] = "Ted";
Quando as aspas duplas são usadas, em vez das aspas simples (ou plicas),
como nos exemplos anteriores, o caracter nul (**`'\0'`**) é
automaticamente acrescentado no fim da string.
Em todos os casos acima, a mesma coisa acontece. O compilador separa um
bloco contíguo de memória de tamanho 40 bytes para guardar os caracteres
e inicia o mesmo de forma que os 4 primeiros caracteres são **Ted\0**.
Agora, considere o seguinte programa:
Programa 3.1
---
/* Program 3.1 from PTRTUT10.HTM 6/13/97 */
#include
char strA[80] = "A string to be used for demonstration purposes";
char strB[80];
int main(void)
{
char *pA; /* a pointer to type character */
char *pB; /* another pointer to type character */
puts(strA); /* show string A */
pA = strA; /* point pA at string A */
puts(pA); /* show what pA is pointing to */
pB = strB; /* point pB at string B */
putchar('\n'); /* move down one line on the screen */
while(*pA != '\0') /* line A (see text) */
{
*pB++ = *pA++; /* line B (see text) */
}
*pB = '\0'; /* line C (see text) */
puts(strB); /* show strB on screen */
return 0;
}
---
No exemplo acima começamos definindo dois arrays de caracteres de 80
caracteres cada. Como eles são definidos globalmente, eles são
inicializados com **`'\0'`**s primeiro. Então **strA** tem os 42
primeiros caracteres inicializados para a string entre aspas.
Agora, avançando no código, declaramos dois ponteiros de caracter e
mostramos a string na tela. Então "apontamos" o ponteiro **pA** para
**strA**. Isto é, via a declaração de atribuição nós copiamos o endereço
de **strA[0]** em nossa variável **pA**. Agora usamos **puts()** para
mostrar o que está apontado por **pA** na tela. Considere aqui que o
protótipo da função **puts()** é:
--- int puts(const char *s);
Por enquato, ignore o **const**. O parâmetro passado a **puts()** é um
ponteiro, ou seja, é o **valor** de um ponteiro (já que todos os
parâmetros em C são passados por valor), e o valor de um ponteiro é o
endereço para o qual ele está apontando, ou, simplesmente, um endereço.
Assim, quando escrevemos **puts(strA);** como vimos antes, estamos
passando o endereço de **strA[0]**.
De forma similar, quando escrevemos **puts(pA);** estamos passando o
mesmo endereço, já que fizemos **`pA = strA;`**
Isto posto, seguimos o código até a declaração **while()** na linha A. A
linha A declara:
Enquanto o caracter apontado por **pA** (isto é, **`*pA`**) não for um
caracter nul (isto é, o terminador **`'\0'`**), fazemos o seguinte:
A linha B declara: copie o caracter apontado por **pA** para o espaço
apontado por **pB**, então incremente **pA**, de forma que aponte para o
próximo caracter e **pB** aponte para o próximo espaço.
Quando copiamos o último caracter, **pA** aponta agora para o caracter
de terminação nul e o laço termina. Entretanto, não copiamos o caracter
nul. E, por definição uma string em C **deve** ser terminada por um nul.
Assim, nós acrescentamos o caracter nul com a linha C.
É bastante educacional executar este programa com seu depurador ao mesmo
tempo que examina **strA**, **strB**, **pA** e **pB** e andando passo a
passo pelo programa. E até mais educacional se em vez de simplesmente
definir **strB[]** como foi feito acima, colocarmos um valor inicial
como:
--- strB[80] = "1234567890123456789012345678901234567890";
onde o número de dígitos usado seja maior que o comprimento de **strA**
e então repetir o procedimento de seguir passo a passo o programa ao
mesmo tempo que examina as variáveis acima. Faça esta experiência!
Voltando ao protótipo de **puts()** por um momento, o "const" é usado
como um modificador de parâmetros que informa ao usuário que a função
não irá modificar a string apontada por **s**, isto é, a string será
tratada como uma constante.
Obviamente, o que o programa acima ilustra é uma forma simples de copiar
uma string. Após brincar com o código acima até ter um bom entendimento
do que está acontecendo, podemos seguir com a criação de nosso próprio
substituto para o **strcpy()** que vem com o C. Ele pode ficar assim:
---
char *my_strcpy(char *destination, char *source)
{
char *p = destination;
while (*source != '\0')
{
*p++ = *source++;
}
*p = '\0';
return destination;
}
---
Neste caso, eu segui a prática usada na rotina padrão que é retornar um
ponteiro para o destino.
Novamente, a função é projetada para aceitar os valores de dois
ponteiros de caracteres, isto é, endereços, e assim no programa anterior
podemos escrever:
---
int main(void)
{
my_strcpy(strB, strA);
puts(strB);
}
---
Eu mudei um pouco da forma usada no C padrão que teria o protótipo:
--- char *my_strcpy(char *destination, const char *source);
Aqui, o modificador "const" é usado para garantir ao usuário que a
função não modificará o conteúdo apontado pelo ponteiro origem. Você
pode provar isto modificando a função acima, e seu protótipo, para
incluir o modificador "const" como mostrado. Então, dentor da função
você pode acerscentar uma declaração que tente mudar o conteúdo do que
é apontado pela fonte, como em:
--- *source = 'X';
que normalmente mudaria o primeiro caracter da string para um X. O
modificador const deve fazer que seu compilador aponte isto como um
erro. Tente e veja.
Agora, vamos considerar algumas das coisas que os exemplos acima nos
mostraram. Primeiro, considere o fato que **`*ptr++`** deve ser
interpretado como retornando o valor apontado por **ptr** e em seguida
incrementando o valor do ponteiro. Isto tem a ver com a precedência de
operadores. Onde escrevemos **`(*ptr)++`** nós incrementaremos, não o
ponteiro, mas o que o ponteiro aponta! Isto é, se usado no primeiro
caracter da string exemplo o 'T' seria incrementado para um 'U'. Você
pode escrever um código exemplo simples para ilustrar isto.
Lembre novamente que uma string nada mais é que um array de caracteres,
com o último caracter sendo um **`'\0'`**. O que fizemos acima é tratar
com a cópia de um array. Aconteceu ser um array de caracteres, mas a
técnica pode ser aplicada a um array de inteiros, doubles, etc. Naqueles
casos, entretanto, não estaremos tratando com strings e portanto o fim
do array não será marcado com um valor especial como o caracter nulo.
Podemos implementar uma versão que dependa de um valor especial para
identificar o fim. Por exemplo, podemos copiar um aray de inteiros
positivos marcando o fim com um inteiro negativo. Por outro lado, é mais
usual que quando escrevermos uma função para copiar um array de itens
que não strings, passemos para a função o número de itens a serem
copiados bem como o endereço do array, por exemplo, algo como o indicado
pelo protótipo abaixo:
--- void int_copy(int *ptrA, int *ptrB, int nbr);
onde **nbr** é o número de inteiros a serem copiados. Você pode querer
brincar com esta idéia e criar um array de inteiros e ver se consegue
escrever a função **int_copy()** e fazê-la funcionar.
Isto permite usar funções para tratar arrays grandes. Por exemplo, se
temos um array de 5000 inteiros que queremos manipular com uma função,
precisamos passar para a função só o endereço do array (e qualquer
informação auxiliar como o nbr acima, dependendo do que estamos
fazendo). O array em si **não** é passado, isto é, o array inteiro não é
copiado e colocado na pilha antes do chamado à função, só seu endereço é
enviado.
Isto é diferente de passar, por exemplo, um inteiro a uma função. Quando
passamos um inteiro fazemos uma cópia do inteiro, isto é, o seu valor é
obtido e colocado na pilha. Dentro da função qualquer manipulação do
valor passado não pode afetar de forma alguma o valor original. Mas, com
arrays e ponteiros podemos passar o endereço da variável e, portanto,
manipular os valores das variáveis originais.
+ Mais Sobre Strings +
Bem, progredimos um bom tanto em tão pouco tempo! Vamos olhar para trás
um pouco e ver o que foi feito no Capítulo 3, sobre cópias de Strings,
mas em uma luz diferente. Considere a seguinte função:
---
char *my_strcpy(char dest[], char source[])
{
int i = 0;
while (source[i] != '\0')
{
dest[i] = source[i];
i++;
}
dest[i] = '\0';
return dest;
}
---
Lembre que strings são arrays de caracteres. Aqui escolhemos usar a
notação de array em vez de notação de ponteiros para fazer a cópia. O
resultado é o mesmo, isto é, a string é copiada usando esta notação tão
correto quanto antes. Isto levanta alguns pontos interessantes para
discussão.
Como os parâmetros são passados por valor, tanto no passar o ponteiro
caracter ou o nome do array, como no exemplo acima, o que é realmente
passado é o endereço do primeiro elemento de cada array. Assim, o valor
numérico do parâmetro é o mesmo, caso usemos um ponteiro de caracter ou
um nome de array como parâmetro. Isto parece implicar que de alguma
forma **`source[i]`** é o mesmo que **`*(p+i)`**.
De fato, isto é verdadeiro, isto é, onde está escrito **`a[i]`** pode-se
substituir com **`*(a+i)`** sem qualquer problema. De fato, o compilador
irá criar o mesmo código em qualquer dos casos. Assim nos vemos que a
aritmética de ponteiro é a mesma coisa que a indexação de array.
Qualquer uma das duas sintaxes produz o mesmo resultado.
Isto NÃO quer dizer que ponteiros e arrays são a mesma coisa, eles não
são. Estamos apenas dizendo que para identificar um dado elemento em um
array temos a escolha de duas sintaxes, uma usando indexação de array e
outra usando aritmética de ponteiros, o que dá resultados idênticos.
Agora, olhando para a última expressão, parte dela, **(a+i)**, é uma
simples adição usando o operador `+` e as regras do C dizem que esta
expressão é comutativa. Ou seja, **(a+i)** é idêntico a **(i+a)**.
Assim, podemos escrever **`*(i+a)`** com a mesma facilidade que
escrevemos **`*(a+i)`**.
Mas **`*(i+a)`** poderia vir de **i[a]**! Disto decorre a curiosa
verdade que, se:
---
char a[20];
int i;
---
escrever
--- a[3] = 'x';
é o mesmo que escrever
--- 3[a] = 'x';
Tente! Crie um array de caracteres, inteiros ou longs, etc. e atribua ao
terceiro ou quarto elemento um valor usando a abordagem convencional e
então escreva o valor para ter certeza que está funcionando. Então
reverta a notação de array como foi feito acima. Um bom compilador não
vai reclamar e os resultados serão idênticos. Uma curiosidade... nada
mais!
Agora, olhando para nossa função acima, quando escrevemos:
--- dest[i] = source[i];
defido ao fato que a indexação de array e a aritmética de ponteiro dá os
mesmos resultados, podemos escrever isto como:
--- *(dest + i) = *(source + i);
Mas isto toma 2 adições para cada valor de i. Adições, falando em termos
gerais, tomam mais tempo que incrementos (como os feitos usando o
operador `++`, como em **`i++`**). Isto pode não ser verdade em
compiladores modernos com otimização, mas não se pode ter certeza.
Assim, a versão de ponteiro pode ser um pouco mais rápida que a versão
de array.
Outra forma de tornar mais rápida a versão de ponteiro seria mudar:
--- while (*source != '\0')
para simplesmente
--- while (*source)
já que o valor entre parêntesis irá resultar em zero (FALSE) no mesmo
momento em cada um dos casos.
Neste ponto você pode querer experimentar um pouco escrevendo seus
próprios programas usando ponteiros. A manipulação de strings é um bom
lugar para experimentar. Você pode querer escrever sua própria versão de
funções padrão como:
---
strlen();
strcat();
strchr();
---
e quaisquer outras que você possa ter em seu sistema.
Voltaremos as strings e sua manipulação via ponteiros em um outro
capítulo. Por enquanto, vamos mudar e discutir um pouco de estruturas.
+ Ponteiros e Estruturas +
Como você sabe, podemos declarar a forma de um bloco de dados contendo
diferentes tipos de dados via uma declaração de estrutura. Por exemplo,
um arquivo de pessoal pode conter estruturas que se pareçam com algo
assim:
---
struct tag {
char lname[20]; /* último nome */
char fname[20]; /* primeiro nome */
int age; /* idade */
float rate; /* p. ex. 12.75 por hora */
};
---
Digamos que temos um punhado destas estruturas em um arquivo em disco e
queremos ler cada uma e escrever o primeiro e último nomes de cada um de
forma que tenhamos uma lista das pessoas em nossos arquivos. As
informações restantes não devem ser escritas. Faremos isto escrevendo
com uma chamada de função e passando para aquela umção um ponteiro para
a estrutura à mão. Para demonstração eu irei usar somente uma estrutura,
mas perceba que o objetivo aqui é escrever a função, não a leitura do
arquivo que, presumivelmente, nós sabemos como fazer.
Para revisão, lembre que podemos acessar membros de estruturas com o
operador ponto, como em:
Programa 5.1
---
/* Program 5.1 from PTRTUT10.HTM 6/13/97 */
#include
#include
struct tag {
char lname[20]; /* last name */
char fname[20]; /* first name */
int age; /* age */
float rate; /* e.g. 12.75 per hour */
};
struct tag my_struct; /* declare the structure my_struct */
int main(void)
{
strcpy(my_struct.lname,"Jensen");
strcpy(my_struct.fname,"Ted");
printf("\n%s ",my_struct.fname);
printf("%s\n",my_struct.lname);
return 0;
}
---
Agora, esta estrutura em particular é bem pequena comparada com muitas
usadas em programas C. Aos dados acima queremos acrescentar:
---
date_of_hire; (data types not shown)
date_of_last_raise;
last_percent_increase;
emergency_phone;
medical_plan;
Social_S_Nbr;
etc.....
---
Se temos um grande número de empregados, o que querermos é manipular os
dados nestas estruturas através de funções. Por exemplo, podemos querer
que uma função escreva o nome do empregado listado em qualquer estrutura
passada ao mesmo. Entretanto, no C original (Kernighan & Ritchie, 1st
Edition) não era possível passar uma estrutura, somente um ponteiro para
uma estrutura podia ser passado. Em ANSI C, é permitido passar a
estrutura completa. Mas, como nosso objetivo aqui é aprender mais sobre
ponteiros, não iremos fazer isto.
De qualquer forma, se passamos a estrutura toda isto significa que
teremos de copiar todo o conteúdo da estrutura da função que está
fazendo a chamada para a função chamada. Em sistemas que usam pilha,
isto é feito empurrando o conteúdo da estrutura para a pilha. Com
estruturas enormes isto pode ser um problema. Entretanto, passar um
ponteiro usa um mínimo do espaço da pilha.
De qualquer forma, como esta é uma discussão sobre ponteiros, iremos
discutir como passar um ponteiro de de estrutura e como usá-lo dentro de
uma função.
Considere o caso descrito, ou seja, queremos uma função que irá aceitar
como parâmetro um ponteiro para uma estrutura e que dentro daquela
função queremos acessar os membros da estrutura. Por exemplo, queremos
escrever o nome do empregado em nossa estrutura exemplo.
Certo, agora sabemos que nosso ponteiro irá apontar para uma estrutura
declarada usando struct tag. Declaramos um ponteiro destes com a declaração:
--- struct tag *str_ptr;
e apontamos para a nossa estrutura exemplo com:
--- st_ptr = &my_struct;
Agora, podemos acessar um dado membro dereferenciando o ponteiro. Mas,
como nós dereferenciamos o ponteiro a uma estrutura? Bem, considere o
fato que podemos querer usar o ponteiro para mudar a idade do empregado.
Poderíamos escrever:
--- (*str_ptr).age = 63;
Olhe esta linha com cuidado. Ela diz, substitua o que está entre
parêntesis pelo que **st_ptr** está apontando, que é a estrutura
**my_struct**. Assim, isto faz o mesmo que **my_struct.age**.
Entretanto, esta expressão é usada com uma certa freqüência, e os
projetistas de C criaram uma sintaxe alternativa com o mesmo significado
que é:
--- st_ptr->age = 63;
Com isto em mente, olhe para o seguinte programa:
Programa 5.2
---
/* Program 5.2 from PTRTUT10.HTM 6/13/97 */
#include
#include
struct tag{ /* the structure type */
char lname[20]; /* last name */
char fname[20]; /* first name */
int age; /* age */
float rate; /* e.g. 12.75 per hour */
};
struct tag my_struct; /* define the structure */
void show_name(struct tag *p); /* function prototype */
int main(void)
{
struct tag *st_ptr; /* a pointer to a structure */
st_ptr = &my_struct; /* point the pointer to my_struct */
strcpy(my_struct.lname,"Jensen");
strcpy(my_struct.fname,"Ted");
printf("\n%s ",my_struct.fname);
printf("%s\n",my_struct.lname);
my_struct.age = 63;
show_name(st_ptr); /* pass the pointer */
return 0;
}
void show_name(struct tag *p)
{
printf("\n%s ", p->fname); /* p points to a structure */
printf("%s ", p->lname);
printf("%d\n", p->age);
}
---
Novamente, é bastante informação para ser absorvida de uma só vez. O
leitor deve compilar e executar os vários trechos de código e usando um
depurador monitar coisas como **my_struct** e **p** enquanto executa
passo a passo **main** e seguindo o código até para dentro do código da
função para ver o que está acontecendo.
+ Um Pouco Mais Sobre Strings, e Arrays de Strings +
Bem, vamos voltar um pouco às strings. Na discussão que se segue, todas
as atribuições devem ser entendidas como sendo globais, ou seja, feitas
fora de qualquer função, incluindo `main()`.
Nós apontamos em um capítulo anterior que podemos escrever:
--- char my_string[40] = "Ted";
o que irá alocar espaço para um array de 40 bytes e colocar a string nos
primeiros 4 bytes (três para os caracteres entre aspas e o quarto para
guardar o terminador **`'\0'`**).
Na verdade, se tudo o que quiséssemos era armazenar o nome "Ted"
poderíamos ter escrito:
--- char my_name[] = "Ted";
e o compilador contaria os caracteres, deixaria espaço para o caracter
nul e armazenar o todal de quatro caracteres na posição de memória que
seria retornada pelo nome do array, neste caso, **my_name**;
Em alguns códigos, em vez do acima, você pode ver:
--- char *my_name = "Ted";
que é a abordagem alternativa. Existe uma diferença entre elas? A
resposta é... sim. Usando a notação de array 4 bytes de armazenamento no
bloco de memória estática é separado, um para cada caracter e um para o
caracter nul terminador. Mas na notação de ponteiro os mesmos 4 bytes
são requeridos, **mais** N bytes para armazenar a variável ponteiro
**my_name** (onde N depende do sistema, mas usualmente é um mínimo de 2
bytes e pode ser 4 ou mais).
Na notação arary, **my_name** é uma abreviação para **&my_name[0]** que
é o endereço do primeiro elemento do array. Como a localização do array
é fixo durante o tempo de execução, esta é uma constante (e não uma
variável). Na notação de ponteiro, **my_name** é uma variável. Sobre
qual o **melhor** método, isto depende do que você vai fazer no resto do
programa.
Avancemos um passo adiante e consideremos o que acontece se cada uma
destas declarações é feita dentro de uma função em vez de ser feita
globalmente, fora dos limites de qualquer função.
---
void my_function_A(char *ptr)
{
char a[] = "ABCDE"
.
.
}
void my_function_B(char *ptr)
{
char *cp = "FGHIJ"
.
.
}
---
No caso de **my_function_A**, o conteúdo, ou valor(es) do array **a[]**
é considerado como sendo os dados. O array é dito como tendo
inicialmente os valores ABCDE. NO caso de **my_function_B** o valor do
ponteiro **cp** é considerado como sendo o dado. O ponteiro inicialmente
aponta para a string **FGHIJ**. Tanto em **my_function_A** e
**my_function_B** as definições são variáveis locais e assim a string
**ABCDE** é armazenada na pilha, bem como é o valor do ponteiro **cp**.
A string **FGHIJ** pode ser armazenada em qualquer lugar. Em meu sistema
ela é armazenada no segmento de dados.
A propósito, a inicialização de variáveis automáticas de array como eu
fiz em **my_function_A** seria ilegal no velho K&R C e somente
"amadureceu" no mais recente ANSI C. Um fato que pode ser importante
quando se considera portabilidade e compatibilidade retroativa.
Como estamos discutindo o relacionamento/diferenças entre ponteiros e
arrays, vamos dar uma olhada em arrays multi-dimensionais. Considere,
por exemplo, o array:
--- char multi[5][10];
O que isto significa? Bem, vamos considerar da seguinte forma.
--- char ._multi[5]_.[10];
Vamos pegar a parte sublinhada como se fosse o "nome" de um array. Então
colocando antes a parte **char** e após acrescentarmos a parte
**[10]**, nós etmos um array de 10 caracteres. Mas o nome **multi[5]** é
por si só um array indicando que existem 5 elementos, cada um deles
sendo um array de 10 caracteres. Assim nós temos um array de 5 arrays de
10 caracteres cada.
Assumindo que tenhamos preenchido este array bidimensional com dados de
algum tipo. Na memória, ele pode parecer como tendo sido formado pela
inicialização de 5 arrays separados, usando algo como:
---
multi[0] = {'0','1','2','3','4','5','6','7','8','9'}
multi[1] = {'a','b','c','d','e','f','g','h','i','j'}
multi[2] = {'A','B','C','D','E','F','G','H','I','J'}
multi[3] = {'9','8','7','6','5','4','3','2','1','0'}
multi[4] = {'J','I','H','G','F','E','D','C','B','A'}
---
Ao mesmo tempo, elementos individuais podem ser endereçados usando a
sintaxe:
---
multi[0][3] = '3';
multi[1][7] = 'h';
multi[4][0] = 'J';
---
Como os arrays são contíguos na memória, nosso bloco de memória para a
matriz acima pode ser algo do tipo:
---
0123456789abcdefghijABCDEFGHIJ9876543210JIHGFEDCBA
^
|_____ starting at the address &multi[0][0]
---
Note que eu **não** escrevi **`multi[0]="0123456789"`**. Se eu tivesse
feito isto, um terminador **`'\0'`** seria acrescentado aos caracters
contidos entre aspas. Seria este o caso se eu tivesse separado espaço
para 11 caracteres por linha em vez de 10.
Meu objetivo acima é ilustrar como a memória é arranjada para arrays de
duas dimensões. Ou seja, este é um array bidimensional de caracteres,
NÃO um array de "strings".
Agora, o compilador sabe quantas colunas estão presentes no array de
forma que ele pode interpretar **multi + 1** como o endereço do 'a' na
segunda linha acima. Ou seja, ele acrescenta 10, o número de colunas,
para obter sua posição. Se estivermos lidando com inteiros e um array
com a mesma dimensão o compilador acrescentaria **10*sizeof(int)** que,
em minha máquina, seria 20. Assim, o endereço de 9 na quarta linha acima
seria **&multi[3][0]** ou **(multi + 3)** em notação de ponteiro. Para
obter o conteúdo do segundo elemento na quarta linha nós
acrescentaríamos 1 a seu endereço e dereferenciaríamos o resultado como
em
--- *(*(multi + 3) + 1)
Com um pouco de raciocínio, podemos ver que:
---
*(*(multi + row) + col) e
multi[row][col] dão o mesmo resultado.
---
O programa seguinte ilustra isto usando arrays de inteiros em vez de
arrays de caracteres.
Programa 6.1
---
/* Program 6.1 from PTRTUT10.HTM 6/13/97*/
#include
#define ROWS 5
#define COLS 10
int multi[ROWS][COLS];
int main(void)
{
int row, col;
for (row = 0; row < ROWS; row++)
{
for (col = 0; col < COLS; col++)
{
multi[row][col] = row*col;
}
}
for (row = 0; row < ROWS; row++)
{
for (col = 0; col < COLS; col++)
{
printf("\n%d ",multi[row][col]);
printf("%d ",*(*(multi + row) + col));
}
}
return 0;
}
---
Por causa da dupla de-referência exigida na versão com ponteiros, o nome
de um array bi-dimensional é geralmente dito como sendo o equivalente a
um ponteiro para ponteiro. Com um array tridimensional nós estaríamos
lidando com um array de arrays de arrays e alguns diriam que seu nome
seria o equivaletne a um ponteiro para ponteiro para ponteiro.
Entretanto, nós aqui separamos um bloco de memória inicialmente para o
array usando a notação de array. Portanto, estamos lidando com uma
constante, não uma variável. Ou seja, estamos falando sobre um endereço
fixo, e não uma variável ponteiro. A função de dereferência usada acima
permite que acessemos qualquer elemento no array de arrays sem precisar
mudar o valor daquele endereço (o endereço de **multi[0][0]** como dado
pelo símbolo **multi**).
+ Mais Sobre Arrays Multi-Dimensionais +
No capítulo anterior nós notamos que, dado
---
#define ROWS 5
#define COLS 10
int multi[ROWS][COLS];
---
nós podemos acessar os elementos individuais do array **multi** usando
ou
--- multi[row][col]
ou
--- *(*(multi + row) + col)
Para entender melhor o que está acontecendo, vamos trocar
--- *(multi + row)
por **X** como em
--- *(X + col)
Agora, a partir disto nós vemos que o **X** funciona como um ponteiro,
já que a expressão é de-referenciada e sabemos que **col** é um inteiro.
Aqui a aritmética usada é um tipo especial, chamada "aritmética de
ponteiros". Isto significa que, como estamos falando de um array de
inteiros, o endereço apontado por (ou seja, pelo valor de)
**X + col + 1** deve ser maior que o endereço **X + col** por uma
quantia igual a **sizeof(int)**.
Como conhecemos o leiaute da memória para arrays de duas dimensões,
podemos determinar que na expressão **multi + row** como a usada acima,
**multi + row + 1** deve incrementar de valor uma quantia igual à
necessária para "apontar para" a próxima linha, que neste caso deve ser
uma quantia igual a **COLS * sizeof(int)**.
Isto diz que se a expressão **`*(*(multi + row) + col)`** deve ser
avaliada corretamente na execução, o compilador deve gerar o código que
leve em consideração o valor de **COLS**, isto é, a segunda dimensão.
Devido à equivalência das duas formas de expressão, isto é verdadeiro
quer estejamos usando a expressão com ponteiros como aqui, ou a
expressão de array **multi[row][col]**.
Assim, para calcular qualquer das expressões, um total de 5 valores
devem ser conhecidos:
+ O endereço do primeiro elemento do array, que é retornado pela
expressão **multi**, isto é, o nome do array.
+ O tamanho do tipo de elementos do array, neste caso, **sizeof(int)**.
+ A segunda dimensão do array.
+ O valor do índice da primeira dimensão, **row** neste caso.
+ O valor do índice da segunda dimensão, **col** neste caso.
Dado tudo isto, considere o problema de designar uma função para
manipular os valores de elementos de um array previamente declarado. Por
exemplo, pode-se colocar em todos os elementos do array **multi** o
valor 1.
---
void set_value(int m_array[][COLS])
{
int row, col;
for (row = 0; row < ROWS; row++)
{
for (col = 0; col < COLS; col++)
{
m_array[row][col] = 1;
}
}
}
---
E para chamar esta função usaríamos:
--- set_value(multi);
Agora, a partir da função nós usamos os valores que foram definidos via
`#define` como ROWS e COLS que estabelecem os limites para os laços.
Mas estes `#define` são apenas constantes no que tange ao compilador,
isto é, não há nada que conecte estes números ao tamanho do array dentro
da função. **row** e **col** são variáveis locais, obviamente. A
definição formal de parâmetros permite que o compilador determine as
características associadas com o valor do ponteiro que será passado em
tempo de execução. Nós realmente não precisamos a primeira dimensão e,
como veremos mais tarde, existem ocasiões onde iremos perferir não
definí-los dentro da definição de parâmetro, fora o hábito ou
consistência, eu não usei aqui. Mas a segunda dimensão deve ser usada e
foi vista na expressão para o parâmetro. A razão por que precisamos dela
para resolver **m_array[row][col]** já foi descrita. Enquanto o
parâmetro define o tipo de dados (**int** neste caso) e as variáveis
automáticas para linha e coluna são definidas nos laços, somente um
valor podoe ser passado usando um único parâmetro. Neste caso, é o valor
de **multi** como notado na declaração de chamada, isto é, o endereço do
primeiro elemento, geralmente referido como sendo um ponteiro para o
array. Assim, a única forma que temos de informar o compilador da
segunda dimensão é incluindo-a explicitamente na definição do parâmetro.
De fato, em geral todas as dimensões de ordem maior que um são
necessárias quando se trata de arrays multi-dimensionais. Ou seja, se
estamos falando de arrays de 3 dimensões, a segunda e terceira dimensões
devem ser especificadas na definição do parâmetro.
+ Ponteiros Para Arrays +
Ponteiros, obviamente, podem ser "apontados" para qualquer tipo de
objeto de dado, incluindo arrays. Enquanto era evidente quando
discutíamos o programa 3.1, é importante expandir sobre como fazer isto
quando se trata de arrays multi-dimensionais.
Para revisar, no Capítulo 2 nós declaramos que dado um array de inteiros
nós podemos apontar a um ponteiro de inteiro daquele array usando:
---
int *ptr;
ptr = &my_array[0]; /* aponta nosso ponteiro para o primeiro
inteiro em nosso array */
---
Como declaramos lá, o tipo da variável ponteiro deve ser o mesmo tipo do
primeiro elemento do array.
Além disto, podemos usar um ponteiro como parâmetro formal de uma função
que é projetada para manipular um array, por exemplo.
Dado:
---
int array[3] = {'1', '5', '7'}/
void a_func(int *p);
---
Alguns programadores podem preferir escrever o protótipo da função como:
--- void a_func(int p[]);
o que informa a outros que poderão usar esta função que a mesma é feita
para tratar os elementos de um array. Obviamente, em qualquer dos casos,
o que realmente é passado é o valor de um ponteiro para o primeiro
elemento do array, independente de que notação é usada no protótipo da
função ou definição. Note que se a notação de array é usada, não há
necessidade de passar a dimensão do array já que não estamos passando o
array inteiro, apenas o endereço do primeiro elemento.
Voltemos agora ao problema do array de 2 dimensões. Como foi dito no
capítulo anterior, o C interpreta um array bidimensional como um array
de arrays de uma só dimensão. Sendo este o caso, o primeiro elemento de
um array bidimensional de inteiros é um array de uma dimensão de
inteiros. E um ponteiro para um array bidimensional de inteiros deve ser
um ponteiro para aquele tipo de dados. Uma forma de conseguir isto é
através do uso da palavra-chave "`typedef`". O `typedef` atribui um novo
nome a um tipo de dados especificado. Por exemplo:
--- typedef unsigned char byte;
faz com que o nome **byte** signifique o tipo **unsigned char**.
Portanto
--- byte b[10];
será um array de **unsigned char**.
Note que na declaração typedef, a palavra **byte** foi substituída pelo
que normalmente seria o nome de nosso **unsigned char**. Ou seja, a
regra para usar **typedef** é que o novo nome para o tipo de dados é o
nome usado na definição do tipo de dado. Assim, em:
--- typedef int Array[10];
Array torna-se um tipo de dados para um array de 10 inteiros, isto é,
**Array my_arr;** declara **my_arr** como sendo um array de 10 inteiros
e **Array arr2d[5];** cria **arr2d** como um array de 5 arrays de 10
inteiros cada.
Note que **Array *pld;** faz de **pld** um ponteiro para um array de 10
inteiros. Como **`*pld`** aponta para o mesmo tipo de **arr2d**,
atribuir o endereço do array bidimensional **arr2d** para **pld*, o
ponteiro ao array de uma dimensão de 10 inteiros, é aceitável. Isto é,
**`pld = &arr2d[0];`** ou **`pld = arr2d;`** estão corretos.
Como o tipo de dados que usamos para nosso ponteiro é um array de 10
inteiros, deveremos esperar que incrementar **pld** por 1 irá mudar seu
valor de **10*sizeof(int)**, que é o que acontece. Ou seja,
**sizeof(*pld)** é 20. Você pode provar isto para você mesmo escrevendo
e rodando um pequeno e simples programa.
Agora, enquanto usar typedef torna as coisas mais claras para o leitor e
mais fáceis para o programador, isto realmente não é necessário. O que
precisamos é uma forma de declarar um ponteiro como **pld** sem a
necessidade da palavra-chave **typedef**. Isto pode ser feito, e
--- int (*p1d)[10];
é a declaração correta, isto é, **pld** aqui é um ponteiro para um array
de 10 inteiros da mesma forma que ele seria se fosse declarado usando o
tipo Array. Note que isto é diferente de
--- int *p1d[10];
que faria que **pld** fosse o nome de um array de 10 ponteiros para o
tipo **int**.
+ Ponteiros e Alocação Dinâmica de Memória +
Existem vezes em que é conveniente alocar memória durante a execução do
programa usando **malloc()**, **calloc()**, ou outras funções de
alocação. Usar esta abordagem permite protelar a decisão sobre o tamanho
do bloco de memória necessário para armazenar um array, por exemplo,
para o momento de execução do programa. Ou permite usar uma seção da
memória para armazenar um array de inteiros em certo momento no tempo, e
quando aquela memória não é mais necessária, ela pode ser liberada para
outros usos, como o armazenamento de um array de estruturas.
Quando a memória é alocada, a função de alocação (como **malloc()**,
**calloc()**, etc.) retorna um ponteiro. O tipo deste ponteiro depende
do tipo do compilador usado, se é um velho compilador K&R ou um
compilador ANSI novo. Com o compilador antigo o tipo do ponteiro
retornado é **char**, com o compilador ANSI é **void**.
Se você está usando um compilador mais antigo, e quer alocar memória
para um array de inteiros, você terá que fazer um cast do ponteiro char
retornado para um ponteiro inteiro. Por exemplo, para alocal espaço para
10 inteiros, poderíamos escrever:
---
inf *iptr;
iptr = (int *)malloc(10 * sizeof(int));
if (iptr == NULL)
{ ... Rotina de erro vem aqui ... }
---
Se você está usando um compilador ANSI, **malloc()** retorna um ponteiro
**void** e como um ponteiro void pode ser atribuído a uma variável
ponteiro de qualquer tipo, o cast **(int *)** mostrado acima não é
necessário. A dimensão do array pode ser determinada durante a execução
e não é necessária durante a compilação. Ou seja, o **10** acima poderia
ser uma variável lida de um arquivo de dados ou teclado, ou calculada
baseada em alguma necessidade, durante a execução.
Devido à equivalência entre a notação de array e ponteiros, uma vez que
**iptr** tenha sido criado como mostrado acima, pode-se usar a notação
de array. Por exemplo, pode-se escrever:
---
int k;
for (k = 0; k < 10; k++)
iptr[k] = 2;
---
para colocar em todos os elementos o valor 2.
Mesmo com um entendimento razoavelmente bom de ponteiros e arrays,
se existe um lugar em que o novato em C provavelmente irá tropeçar na
primeira vez que trabalhar, é a alocação dinâmica de arrays
multidimensionais. Em geral, gostaríamos de poder acessar elementos
destes arrays usando notação de array, e não notação de ponteiro, sempre
que possível. Dependendo da aplicação podemos ou não conhecer as duas
dimensões durante a compilação. Isto nos leva a várias formas de
executar a tarefa.
Como já vimos, quando alocando dinamicamente um array de uma dimensão,
sua dimensão pode ser determinada durante a execução. Agora, quando
usando alocação dinâmica de arrays de ordem maior, nós não precisamos
saber a primeira dimensão durante a compilação. Se precisamos ou não
conhecer as dimensões maiores depende de como iremos escrever o código.
Aqui eu irei discutir vários métodos para alocar dinamicamente espaço
para arrays bidimensionais de inteiros.
Primeiro, iremos considerar casos em que a segunda dimensão é conhecida
durante a compilação.
== Método 1 ==
Uma forma de lidar com o problema é através do uso da palavra chave
**typedef**. Para alocar um array bidimensional de inteiros, lembre que
as duas notações seguintes resultam na geração do mesmo código objeto:
--- multi[row][col] = 1; *(*(multi + row) + col) = 1;
Também é verdade que as duas notações a seguir geram o mesmo código:
--- multi[row] *(multi + row)
Como o da direita deve resultar em um ponteiro, a notação de array na
esquerda também deve resultar em um ponteiro. De fato, **multi[0]** irá
retornar um ponteiro para o primeiro inteiro na primeira linha,
**multi[1]** um ponteiro para o primeiro inteiro na segunda linha, etc.
Na verdade, **multi[n]** retorna um ponteiro para o n-ésimo array deste
array de arrays. Aqui a palavra **ponteiro** está sendo usada para
representar um valor de endereço. Apesar deste uso ser comum na
literatura, quando estiver lendo este tipo de declaração deve-se ser
cuidados para distinguir entre o endereço constante de um array e uma
variável ponteiro que é um objeto de dados em si.
Considere agora:
Programa 9.1
---
/* Program 9.1 from PTRTUT10.HTM 6/13/97 */
#include
#include
#define COLS 5
typedef int RowArray[COLS];
RowArray *rptr;
int main(void)
{
int nrows = 10;
int row, col;
rptr = malloc(nrows * COLS * sizeof(int));
for (row = 0; row < nrows; row++)
{
for (col = 0; col < COLS; col++)
{
rptr[row][col] = 17;
}
}
return 0;
}
---
Neste exemplo eu assumi que se estava usando um compilador ANSI, assim
um cast no ponteiro void retornado por **malloc()** não é necessário. Se
você estiver usando um compilador K&R antigo você terá de fazer o cast
usando:
--- rptr = (RowArray *)malloc(... etc.
Usando esta abordagem, **rptr** tem todas as características de um nome
de array (exceto que rptr é modificável), e a notação de array pode ser
usada pelo resto do programa. Isto também significa que se você pretende
escrever uma função para modificar o conteúdo do array, deve usar COLS
como parte dos parâmetros formais da função, como nós fizemos quando
discutimos a passagem de arrays bidimensionais para uma função.
== Método 2 ==
No Método 1 acima, rptr acabou sendo um ponteiro para o tipo "um array
de uma dimensão de COLS inteiros". Acontece que existe uma sintaxe que
pode ser usada para este tipo sem a necessidade do **typedef**. Se
escrevermos:
--- int (*xptr)[COLS];
a variável **xptr** terá todas as mesmas características da variável
**rptr** no Método 1 acima, e não precisamos usar a palavra-chave
**typedef**. Aqui, **xptr** é um ponteiro para um array de inteiros e o
tamanho do array é dado pelo **`#define COLS`**. A colocação dos
parêntesis torna a notação de ponteiros predominante, mesmo que a
notação de array tenha uma maior precedência. Isto é, se tivéssemos
escrito
--- int *xptr[COLS];
teríamos definido **xptr** como um array de ponteiros mantendo um número
de ponteiros igual ao definido por COLS. Não é a mesma coisa, de forma
nenhuma. Entretanto, arrays de ponteiros tem seu uso na alocação
dinâmica de arrays bidimensionais, como veremos nos dois métodos a
seguir.
== Método 3 ==
Considere o caso onde não conhecemos o número de elementos de cada
linha durante a compilação, isto é, tanto o número de linhas e o número
de colunas devem ser determinados durante a execução. Uma forma de fazer
isto seria criar um array de ponteiros do tipo **int** e então alocar
espaço para cada linha e apontar cada um destes ponteiros a cada uma
destas linhas. Considere o exemplo:
Programa 9.2
---
/* Program 9.2 from PTRTUT10.HTM 6/13/97 */
#include
#include
int main(void)
{
int nrows = 5; /* Both nrows and ncols could be evaluated */
int ncols = 10; /* or read in at run time */
int row;
int **rowptr;
rowptr = malloc(nrows * sizeof(int *));
if (rowptr == NULL)
{
puts("\nFailure to allocate room for row pointers.\n");
exit(0);
}
printf("\n\n\nIndex Pointer(hex) Pointer(dec) Diff.(dec)");
for (row = 0; row < nrows; row++)
{
rowptr[row] = malloc(ncols * sizeof(int));
if (rowptr[row] == NULL)
{
printf("\nFailure to allocate for row[%d]\n",row);
exit(0);
}
printf("\n%d %p %d", row, rowptr[row],
rowptr[row]);
if (row > 0)
printf(" %d",(int)(rowptr[row] - rowptr[row-1]));
}
return 0;
}
---
No código acima, **rowptr** é um ponteiro a um ponteiro do tipo **int**.
Neste caso ele aponta para o primeiro elemento de um array de ponteiros
para o tipo **int**. Considere o número de chamadas a **malloc()**:
---
Para obter espaço para o array de ponteiros 1 chamada
Para obter espaço para as linhas 5 chamadas
-----
Total 6 chamadas
---
Se você escolher usar esta abordagem, note que mesmo que você possa usar
a notação de array para acessar elementos individuais do array, como por
exemplo, **`rowptr[row][col] = 17;`**, isto não significa que os dados
no "array bidimensional" estejam contíguos na memória.
Voc~e pode, entretanto, usar notação de array como se ele fosse um bloco
contínuo de memória. Por exemplo, você pode escrever:
--- rowptr[row][col] = 176;
exatametne como se rowptr fosse o nome de um array bidimensional criado
durante a compilação. Obviamente **row** e **col** devem estar nos
limites do array que foi criado, exatamente como em um array criado
durante a compilação.
Se você quer ter um bloco contíguo de memória dedicado ao armazenamento
de elementos no array você pode fazer como no exemplo abaixo:
== Método 4 ==
Neste método nós alocamos um bloco de memória para guardar o array
inteiro primeiro. Então criamos um array de ponteiros para apontar para
cada linha. Assim, mesmo que o array de ponteiros seja usado, o array em
si está contíguo na memória. O código é como segue:
Programa 9.3
---
/* Program 9.3 from PTRTUT10.HTM 6/13/97 */
#include
#include
int main(void)
{
int **rptr;
int *aptr;
int *testptr;
int k;
int nrows = 5; /* Both nrows and ncols could be evaluated */
int ncols = 8; /* or read in at run time */
int row, col;
/* we now allocate the memory for the array */
aptr = malloc(nrows * ncols * sizeof(int));
if (aptr == NULL)
{
puts("\nFailure to allocate room for the array");
exit(0);
}
/* next we allocate room for the pointers to the rows */
rptr = malloc(nrows * sizeof(int *));
if (rptr == NULL)
{
puts("\nFailure to allocate room for pointers");
exit(0);
}
/* and now we 'point' the pointers */
for (k = 0; k < nrows; k++)
{
rptr[k] = aptr + (k * ncols);
}
/* Now we illustrate how the row pointers are incremented */
printf("\n\nIllustrating how row pointers are incremented");
printf("\n\nIndex Pointer(hex) Diff.(dec)");
for (row = 0; row < nrows; row++)
{
printf("\n%d %p", row, rptr[row]);
if (row > 0)
printf(" %d",(rptr[row] - rptr[row-1]));
}
printf("\n\nAnd now we print out the array\n");
for (row = 0; row < nrows; row++)
{
for (col = 0; col < ncols; col++)
{
rptr[row][col] = row + col;
printf("%d ", rptr[row][col]);
}
putchar('\n');
}
puts("\n");
/* and here we illustrate that we are, in fact, dealing with
a 2 dimensional array in a contiguous block of memory. */
printf("And now we demonstrate that they are contiguous in memory\n");
testptr = aptr;
for (row = 0; row < nrows; row++)
{
for (col = 0; col < ncols; col++)
{
printf("%d ", *(testptr++));
}
putchar('\n');
}
return 0;
}
---
Considere, novamente, o número de chamadas a malloc()
---
Para obter espaço para o array de ponteiros 1 chamada
Para obter espaço para o array de ptrs 1 chamada
-----
Total 2 chamadas
---
Agora, cada chamada a **malloc()** cria um overhead adicional de espaço
já que **malloc()** é geralmente implementado pelo sistema operacional
formando uma lista ligada que contém dados sobre o tamanho do bloco.
Mas, mais importante, com grandes arrays (várias centenas de linhas)
manter o controle do que precisa ser liberado quando chega a hora pode
ser problemático. Isto, combinado com a contiguidade do bloco de dados
que permite a inicialização de tudo para zero usando o **memset()**,
parece que torna a segunda alternativa a preferida.
Como um exemplo final de arrays multidimensionais iremos ilustrar a
alocação dinâmica de um array de três dimensões. Este exemplo irá
ilustrar uma coisa mais a ser verificada quando se faz este tipo de
alocação. Por razões citadas acima, iremos utilizar a abordagem
apresentada na segunda alternativa. Considere o seguinte código:
Programa 9.4
---
/* Program 9.4 from PTRTUT10.HTM 6/13/97 */
#include
#include
#include
int X_DIM=16;
int Y_DIM=5;
int Z_DIM=3;
int main(void)
{
char *space;
char ***Arr3D;
int y, z;
ptrdiff_t diff;
/* first we set aside space for the array itself */
space = malloc(X_DIM * Y_DIM * Z_DIM * sizeof(char));
/* next we allocate space of an array of pointers, each
to eventually point to the first element of a
2 dimensional array of pointers to pointers */
Arr3D = malloc(Z_DIM * sizeof(char **));
/* and for each of these we assign a pointer to a newly
allocated array of pointers to a row */
for (z = 0; z < Z_DIM; z++)
{
Arr3D[z] = malloc(Y_DIM * sizeof(char *));
/* and for each space in this array we put a pointer to
the first element of each row in the array space
originally allocated */
for (y = 0; y < Y_DIM; y++)
{
Arr3D[z][y] = space + (z*(X_DIM * Y_DIM) + y*X_DIM);
}
}
/* And, now we check each address in our 3D array to see if
the indexing of the Arr3d pointer leads through in a
continuous manner */
for (z = 0; z < Z_DIM; z++)
{
printf("Location of array %d is %p\n", z, *Arr3D[z]);
for ( y = 0; y < Y_DIM; y++)
{
printf(" Array %d and Row %d starts at %p", z, y, Arr3D[z][y]);
diff = Arr3D[z][y] - space;
printf(" diff = %d ",diff);
printf(" z = %d y = %d\n", z, y);
}
}
return 0;
}
---
Se você seguiu este tutorial até este ponto, não deve ter problemas
decifrando o código acima com base apenas nos comentários. Há alguns
pontos que eu gostaria de destacar. Comecemos com a linha que tem:
--- Arr3D[z][y] = space + (z*(X_DIM * Y_DIM) + y*X_DIM);
Note que aqui **space** é um ponteiro para caracter, que tem o mesmo
tipo de **Arr3D[z][y]**. É importante que quando se está somando um
inteiro, como o resultante da expressão
**(z*(X_DIM * Y_DIM) + y*X_DIM)** a um ponteiro, o resultado é um novo
valor de ponteiro. E quando se está atribuindo valoers de ponteiro a
variáveis de ponteiro os tipos dos dados do valor e da variável devem
combinar.
+ Ponteiros Para Funções +
Até agora discutimos ponteiros para objetos de dados. C também permite a
declaração de ponteiros para funções. Ponteiros para funções tem uma
variedade de usos e alguns deles serão discutidos aqui.
Considere o seguinte problema real. Você quer escrever uma função que é
capaz de ordenar virtualmente qualquer coleção de dados que podem ser
armazenados em um array. Este pode ser um array de strings, ou inteiros,
ou floats, ou mesmo estruturas. O algoritmo de ordenamento pode ser o
mesmo para todos. Por exemplo, ele pode ser um simples algoritmo
//bubble sort//, ou o algoritmo mais complexo //shell sort// ou
//quick sort//. Iremos utilizar um simples //bubble sort// para nossa
demonstração.
Sedgewick[1] descreveu o //bubble sort// usando código C configurando
uma função que quando recebe um ponteiro para um array irá ordenar o
mesmo. Se chamarmos esta função **bubble()**, um programa de ordenamento
é descrito por bubble_1.c, que segue:
Programa bubble_1.c
---
/*-------------------- bubble_1.c --------------------*/
/* Program bubble_1.c from PTRTUT10.HTM 6/13/97 */
#include
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int a[], int N);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int a[], int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (a[j-1] > a[j])
{
t = a[j-1];
a[j-1] = a[j];
a[j] = t;
}
}
}
}
/*---------------------- end bubble_1.c -----------------------*/
---
O //bubble sort// é um dos ordenamentos mais simples. O algoritmo
examina o array do segundo até o último elemento, comparando cada
elemento com o que o precede. Se um dos elementos que precede é maior
que o elemento atual, os dois são trocados de forma que o maior vai
ficando próximo do fim do array. No primeiro passo, isto resulta no
maior elemento indo para o fim do array. O array é agora limitado a
todos os elementos exceto o último e o processo é repetido. Isto coloca
o próximo maior elemento na posição anterior à do maior elemento. O
processo é repetido por um número de vezes igual ao número de elementos
menos 1. O resultado final é um array ordenado.
Aqui nossas funções foram feitas para ordenar um array de inteiros.
Assim, na linha 1 estamos comparando inteiros e nas linhas 2 a 4 estamos
usando um inteiro temporário para guardar inteiros. O que queremos fazer
agora é ver se podemos converter este código de forma que possamos usar
qualquer tipo de dado, isto é, não ficarmos restritos a inteiros.
Ao mesmo tempo não queremos ter que analisar nosso algoritmo e o código
associado com ele toda vez que usarmos o mesmo. Começamos removendo a
comparação de dentro da função **bubble()** de forma a tornar
relativamente fácil modificar a função de comparação sem ter que
reescrever porções relacionadas ao algoritmo em sim. O resultado está em
bubble_2.c:
Programa bubble_2.c
---
/*---------------------- bubble_2.c -------------------------*/
/* Program bubble_2.c from PTRTUT10.HTM 6/13/97 */
/* Separating the comparison function */
#include
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int a[], int N);
int compare(int m, int n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int a[], int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare(a[j-1], a[j]))
{
t = a[j-1];
a[j-1] = a[j];
a[j] = t;
}
}
}
}
int compare(int m, int n)
{
return (m > n);
}
/*--------------------- end of bubble_2.c -----------------------*/
---
Se nosso objetivo é fazer nossa rotina de ordenamento independente do tipo
de dados, uma forma de fazer isto é usar ponteiros para o tipo void para
apontar para os dados em vez de usar o tipo inteiro. Como partida nesta
direção, vamos modificar algumas coisas no programa acima de forma que
ponteiros possam ser utilizados. Para começar, vamos ficar com ponteiros
para o tipo inteiro.
Programa bubble_3.c
---
/*----------------------- bubble_3.c -------------------------*/
/* Program bubble_3.c from PTRTUT10.HTM 6/13/97 */
#include
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int *p, int N);
int compare(int *m, int *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int *p, int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare(&p[j-1], &p[j]))
{
t = p[j-1];
p[j-1] = p[j];
p[j] = t;
}
}
}
}
int compare(int *m, int *n)
{
return (*m > *n);
}
/*------------------ end of bubble3.c -------------------------*/
---
Note as alterações. Estamos agora passando um ponteiro para um inteiro
(ou array de inteiros) para **bubble()**. E de dentro de bubble estamos
passando ponteiros para os elementos do array que queremos comparar para
a nossa função de comparação. E, obviamente, estamos dereferenciando
estes ponteiros em nossa função **compare()** para fazer a comparação em
si. Nosso próximo passo será converter os ponteiros em **bubble()** para
ponteiros do tipo void de forma que a função fique mais insensível ao
tipo. Isto está mostrado no bubble_4.
Programa bubble_4.c
---
/*------------------ bubble_4.c ----------------------------*/
/* Program bubble_4.c from PTRTUT10,HTM 6/13/97 */
#include
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int *p, int N);
int compare(void *m, void *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int *p, int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare((void *)&p[j-1], (void *)&p[j]))
{
t = p[j-1];
p[j-1] = p[j];
p[j] = t;
}
}
}
}
int compare(void *m, void *n)
{
int *m1, *n1;
m1 = (int *)m;
n1 = (int *)n;
return (*m1 > *n1);
}
/*------------------ end of bubble_4.c ---------------------*/
---
Note que, ao fazer isto, em **compare()** temos que introduzir o
casting do ponteiro tipo void para o tipo real sendo ordenado. Mas, como
veremos mais tarde, isto não é problema. E como o que está sendo passado
para **bubble()** ainda é um ponteiro para um array de inteiros, temos
que fazer o cast destes ponteiros para ponteiros para inteiros quando
passamos os mesmos como parâmetros em nossa chamada a **compare()**.
Agora vamos tratar do prolema do que passamos para **bubble()**.
Queremos que o primeiro parâmetro para aquela função seja também um
ponteiro para void. Mas, isto significa que dentro de **bubble()**
precisamos fazer algo sober a variável **t**, que é atualmente um
inteiro. Além disso, onde usamos **`t = p[j-1];`** o tipo de
**`p[j-1]`** precisa ser conhecido para saber quantos bytes copiar para
a variável **t** (ou o que quer que coloquemos no lugar de **t**).
Atualmente, no bubble_4.c, o conhecimento dentro de **bubble()** sobre o
tipo do dado sendo ordenado (e, portanto, o tamanho de cada elemento
individual) é obtido do fato que o primeiro parâmetro é um ponteiro para
o tipo inteiro. Se queremos que **bubble()** ordente qualquer tipo de
dado, precisamos fazer que aquele ponteiro aponte para o tipo **void**.
Mas, ao fazer isto, iremos perder a informação sobre o tamanho dos
elementos individuais dentro do array. Assim, em bubble_5.c, iremos
acrescentar um parâmetro separado para tratar esta informação de
tamanho.
Estas alterações, de bubble_4.c para bubble_5.c são, talvez, um pouco
mais extensivas que as que fizemos nos exemplos anteriores. Assim,
compare cuidadosamente os dois módulos para ver as diferenças.
Programa bubble_5.c
---
/*---------------------- bubble5.c ---------------------------*/
/* Program bubble_5.c from PTRTUT10.HTM 6/13/97 */
#include
#include
long arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(void *p, size_t width, int N);
int compare(void *m, void *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr, sizeof(long), 10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%ld ", arr[i]);
}
return 0;
}
void bubble(void *p, size_t width, int N)
{
int i, j;
unsigned char buf[4];
unsigned char *bp = p;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare((void *)(bp + width*(j-1)),
(void *)(bp + j*width))) /* 1 */
{
/* t = p[j-1]; */
memcpy(buf, bp + width*(j-1), width);
/* p[j-1] = p[j]; */
memcpy(bp + width*(j-1), bp + j*width , width);
/* p[j] = t; */
memcpy(bp + j*width, buf, width);
}
}
}
}
int compare(void *m, void *n)
{
long *m1, *n1;
m1 = (long *)m;
n1 = (long *)n;
return (*m1 > *n1);
}
/*--------------------- end of bubble5.c ---------------------*/
---
Note que eu mudei o tipo dos dados do array de **int** para **long**
para ilustrar as mudanças necessárias na função **compare()**. Dentro de
**bubble()** eu me descartei da variável **t** (que teríamos de ter
mudado do tipo **int** para o tipo **long**). Eu acrescentei um buffer
de tamanho 4 de //unsigned char//, que é o tamanho necessário para
armazenar um long (isto será novamente alterado em futuras modificações
a este código). O ponteiro unsigned char **`*bp`** é usado para apontar
para a base do array a ser ordenado, isto é, o primeiro elemento daquele
array.
Temos também que modificar o que é passado a **compare()**, e como
faremos a troca dos elementos que a comparação indica precisarem ser
trocados. O uso de **memcpy()** e a notação de ponteiros em vez da
notação de array ajuda na redução da sensibilidade ao tipo.
Novamente, fazer uma comparação cuidadosa de bubble_5.c com bubble_4.c
pode resultar em um entendimento maior sobre o que está acontecendo e
por quê.
Agora vamos para bubble_6.v, onde iremos usar a mesma função bubble()
que usamos em bubble_5 para ordenar strings em vez de inteiros longos.
Obviamente temos que alterar a função de comparação já que a forma que
strings são comparadas é diferente da forma que inteiros longos são
comparados. E em bubble_6.c nós excluímos as linhas de **bubble()** que
estavam comentadas em bubble_5.c
Programa bubble_6.c
---
/*--------------------- bubble6.c ---------------------*/
/* Program bubble_6.c from PTRTUT10.HTM 6/13/97 */
#include
#include
#define MAX_BUF 256
char arr2[5][20] = { "Mickey Mouse",
"Donald Duck",
"Minnie Mouse",
"Goofy",
"Ted Jensen" };
void bubble(void *p, int width, int N);
int compare(void *m, void *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 5; i++)
{
printf("%s\n", arr2[i]);
}
bubble(arr2, 20, 5);
putchar('\n\n');
for (i = 0; i < 5; i++)
{
printf("%s\n", arr2[i]);
}
return 0;
}
void bubble(void *p, int width, int N)
{
int i, j, k;
unsigned char buf[MAX_BUF];
unsigned char *bp = p;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
k = compare((void *)(bp + width*(j-1)), (void *)(bp + j*width));
if (k > 0)
{
memcpy(buf, bp + width*(j-1), width);
memcpy(bp + width*(j-1), bp + j*width , width);
memcpy(bp + j*width, buf, width);
}
}
}
}
int compare(void *m, void *n)
{
char *m1 = m;
char *n1 = n;
return (strcmp(m1,n1));
}
/*------------------- end of bubble6.c ---------------------*/
---
Mas, o fato que **bubble()** tenha ficado inalterado daquilo que foi
usado em bubble_5.c indica qeu a função é capaz de ordenar uma grande
variedade de tipos de dados. O que falta fazer é passar para
**bubble()** o nome da função de comparação que queremos utilizar, de
forma que a função seja realmente universal. Da mesma forma que um array
é o endereço do primeiro elemento do array no segmento de dados, o nome
de uma função traduz-se para o endereço daquela função no segmento de
código. Assim, precisamos usar um ponteiro para uma função. Neste caso,
a função de comparação.
Ponteiros para funções devem combinar com as funções apontadas no
número e tipo dos parâmetros e o tipo do valor de retorno. Em nosso
caso, declaramos nosso ponteiro para função como:
--- int (*fptr)(const void *p1, const void *p2);
Noet que se tivéssemos escrito:
--- int *fptr(const void *p1, const void *p2);
teríamos feito o protótipo para uma função que retorna um ponteiro do
tipo **int**. Isto por que em C o operador parêntesis () tem uma
precedência maior que o operador * ponteiro. Colocando o parêntesis em
torno da string (*fptr) nós indicamos que estamos declarando um ponteiro
para uma função.
Abora nós modificamos nossa declaração de **bubble()** pelo acréscimo,
como seu quarto parâmetro, um ponteiro de função do tipo apropriado. É
assim que o protótipo da função fica:
---
void bubble(void *p, int width, int N,
int(*fptr)(const void *, const void *));
---
Quando chamarmos **bubble()**, nós inserimos o nome da função de
comparação que queremos utilizar. O programa bubble_7.c ilustra como
esta abordagem permite o uso da mesma função **bubble()** para ordenar
diferentes tipos de dados.
Programa bubble_7.c
---
/*------------------- bubble7.c ------------------*/
/* Program bubble_7.c from PTRTUT10.HTM 6/10/97 */
#include
#include
#define MAX_BUF 256
long arr[10] = { 3,6,1,2,3,8,4,1,7,2};
char arr2[5][20] = { "Mickey Mouse",
"Donald Duck",
"Minnie Mouse",
"Goofy",
"Ted Jensen" };
void bubble(void *p, int width, int N,
int(*fptr)(const void *, const void *));
int compare_string(const void *m, const void *n);
int compare_long(const void *m, const void *n);
int main(void)
{
int i;
puts("\nBefore Sorting:\n");
for (i = 0; i < 10; i++) /* show the long ints */
{
printf("%ld ",arr[i]);
}
puts("\n");
for (i = 0; i < 5; i++) /* show the strings */
{
printf("%s\n", arr2[i]);
}
bubble(arr, 4, 10, compare_long); /* sort the longs */
bubble(arr2, 20, 5, compare_string); /* sort the strings */
puts("\n\nAfter Sorting:\n");
for (i = 0; i < 10; i++) /* show the sorted longs */
{
printf("%d ",arr[i]);
}
puts("\n");
for (i = 0; i < 5; i++) /* show the sorted strings */
{
printf("%s\n", arr2[i]);
}
return 0;
}
void bubble(void *p, int width, int N,
int(*fptr)(const void *, const void *))
{
int i, j, k;
unsigned char buf[MAX_BUF];
unsigned char *bp = p;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
k = fptr((void *)(bp + width*(j-1)), (void *)(bp + j*width));
if (k > 0)
{
memcpy(buf, bp + width*(j-1), width);
memcpy(bp + width*(j-1), bp + j*width , width);
memcpy(bp + j*width, buf, width);
}
}
}
}
int compare_string(const void *m, const void *n)
{
char *m1 = (char *)m;
char *n1 = (char *)n;
return (strcmp(m1,n1));
}
int compare_long(const void *m, const void *n)
{
long *m1, *n1;
m1 = (long *)m;
n1 = (long *)n;
return (*m1 > *n1);
}
/*----------------- end of bubble7.c -----------------*/
---
== Referências ==
[1] "Algorithms in C"\br
Robert Sedgewick\br
Addison-Wesley\br
ISBN 0-201-51425-7
= Epílogo =
Eu escrevi o material que o leitor tem em mãos agora para dar uma
introdução a ponteiros para novatos no C. Em C, quanto mais se entende
sobre ponteiros, maior a flexibilidade que se tem no código escrito. O
texto acima foi expandido do meu primeiro trabalho neste tópico que
recebeu o nome de ptr_help.txt e era encontrado nas primeiras versões da
coleção de código C SNIPPETS de Bob Stout. O conteúdo nesta versão foi
atualizado a partir do código em PTRTUTOT.ZIP incluído em SNIP9510.ZIP.
Eu estou sempre pronto a aceitar críticas construtivas sobre este
material, ou solicitações de revisão para a adição de outro material
relevante. Assim sendo, se você tiver questões, comentários, críticas,
etc. sobre esta apresentação, eu apreciaria imensamente seu contato via
email para minha conta em tjensen@ix.netcom.com.