Capítulo 5
Apontadores (pointers)
e
Vetores
Pointers (1)





Um pointer é uma variável que contém o
endereço de outra variável.
Uso intenso em C.
Às vezes pointers são a única forma de
expressar uma computação.
Em geral levam a um código mais eficiente e
compacto que outras alternativas.
Atenção! Podem tornar o código complexo e de
difícil entendimento.
Pointers (2)


Um computador típico possui um vetor de
células de memórias numeradas ou endereçadas
consecutivamente, que podem ser manipuladas
individualmente ou em grupos contínuos,
dependendo do tipo da variável em questão.
Um pointer é um grupo de células (usualmente
de 2 a 4) que podem conter um endereço.
char c;
Pointers (3)





O operador unário & fornece o endereço de um objeto.
p = &c; /* atribui o endereço de c a p */
/* diz-se que p aponta para c */
& só se aplica a objetos na memória: variáveis e elementos
de vetor.
Não pode ser aplicado a expressões, constantes ou
variáveis register.
* é o operador (unário) de indireção ou deferenciação. Ele
acessa o objeto apontado pelo pointer.
Pointers (4)
Como declarar um pointer e como usar & e *:
int x = 1, y = 2, z[10];
int *ip; /* ip is a pointer to int */
ip = &x; /* ip now points to x */
y = *ip; /* y is now 1 */
*ip = 0; /* x is now 0 */
ip = &z[0]; /* ip now points to z[0] */
 int *ip; → é um mneumônico. Diz que a
expressão *ip é um int.

Pointers (5)



A sintaxe da declaração para uma variável tem
forma similar à sintaxe de expressões em que a
variável pode aparecer.
O mesmo se dá nos casos envolvendo
declarações de funções.
double *dp, atof(char *);
informa que, em uma expressão, *dp e atof(s)
possuem valores do tipo double, e que o
argumento de atof é um apontador para char.
Pointers (5)



A declaração de um pointer implica em que ele
restringe-se a apontar para um tipo de dados
específico (integer, char, float, etc...)
Exceção: pointer para void, que pode conter
qualquer tipo de apontador, todavia não pode ser
diferenciado por si só.
Se ip aponta para o inteiro x, então *ip pode
ocorrer em qualquer contexto onde x poderia
ocorrer.
*ip = *ip + 10; /* incrementa *ip de 10 */
Pointers (6)


Os operadores unários * e & têm maior precedência que os
operadores aritméticos.
y = ip + 1 /* adiciona 1 ao valor do objeto apontado por ip e
atribui o resultado a y */

*ip += 1 /* incrementa o objeto apontado por ip */

++*ip


''
(*ip)++ /* os parênteses são necessários, pois os operadores
unários (e.g. * e ++) são avaliados da direita para a esquerda
*/
Como os pointers são variáveis, podem ser usados sem
diferenciação. Seja ip um pointer para um integer.
iq = ip /* iq apontará para qualquer coisa apontada por ip */
Call by value



Em C os argumentos são passados às funções
por valor (call by value).
Se invocamos a função
swap(a, b); /* intenção: trocar a por b e viceversa */
a partir de uma função g, isto não ocorrerá para
variáveis a e b declaradas em g.
Para obtermos o efeito intencionado é necessário
o uso de pointers.
Call by reference (1)



Invocando a função da forma
swap(&a, &b); /* call by reference */
&a e &b são, respectivamente, pointers para a e
b. Na função swap os parâmetros são declarados
como pointers e tem-se acesso aos operandos
indiretamente, por meio deles.
Os argumentos apontadores permitem que a
função swap tenha acesso e altere objetos na
função que a invocou.
Call by reference (2)
main ()
{ …
swap(&a, &b);
…
}
void swap(int *px, int *py)
{
int temp;
/* interchange *px and *py */
temp = *px;
*px = *py;
*py = temp;
}
Call by reference (3)




Exemplo: função getint que lê e executa a conversão de
entrada em formato livre, dividindo um fluxo de
caracteres em valores inteiros, um inteiro por chamada.
getint deve indicar o valor lido/convertido e também
indicar a condição de fim de arquivo ou não.
Estes valores devem ser retornados por vias distintas,
pois o valor de EOF poderia ser o valor de um inteiro
no fluxo de entrada.
Solução: getint retorna o estado de fim de arquivo,
enquanto usa um argumento apontador para armazenar
o valor lido/convertido na função que invocou getint.
Call by reference (4)

O loop que se segue preenche um vetor de
inteiros, a partir de chamadas consecutivas à
getint.
int n, array[SIZE], getint(int *);
for (n = 0; n < SIZE && getint(&array[n]) != EOF; n++)
;


Ver prog43-chap05-pg81
Analisar a função scanf (secção 7.4 do livro
texto, inclusa em <stdio.h>)
Pointers e vetores (1)
Em C há uma forte relação entre apontadores e
vetores. As operações que podem ser realizadas
com subscritos de um vetor, também podem ser
feitas com apontadores (+ rápidas).
 int a[10]; int *pa;
pa = &a[0];
pa

Pointers e vetores (2)


x = *pa; /* atribui o conteúdo de a[0] a x */
Se pa aponta para um elemento particular de um vetor,
então pa+1 aponta para o próximo elemento, e pa+i
para i elementos após, independentemente do tipo ou
tamanho dos elementos no vetor a.
Pointers e vetores (3)



Há uma correspondência direta entre indexação
e aritmética com ponteiros.
Por definição o valor de uma variável ou
expressão do tipo vetor é o endereço do
elemento zero do vetor.
pa = &a[0]; /* é equivalente a: */
pa = a;
a[i] é equivalente a *(a+i) e, aplicando-se &:
&a[i] é idêntico a a+i.
Pointers e vetores (4)



Se pa é um pointer, expressões podem usá-lo
como um subscrito. Assim,
pa[i] é idêntico a *(pa+i).
Quando uma função é invocada, tendo o nome
de um vetor como argumento, o parâmetro
correspondente será a posição do elemento
inicial do vetor.
Na função chamada o parâmetro comporta-se
como uma variável local.
Pointers e vetores (5)




Um argumento do tipo nome de vetor é um pointer, i.e.,
um endereço.
Veja outra versão de strlen que usa este fato (prog44chap05-pg83.c)
s é um pointer. Incrementá-lo é perfeitamente legal.
As seguintes invocações de strlen são válidas:
strlen("hello, world"); /* string constant */
strlen(array); /* char array[100]; */
strlen(ptr); /* char *ptr; */
Pointers e vetores (6)
Como parâmetros formais na definição de uma
função, as construções
char [s]; e char *s;
são equivalentes.
 char *s; indica explicitamente que o parâmetro é
um pointer.
 É possível passar apenas parte de um vetor para
uma função.
f(&a[i]) ou f(a+i)

Pointers e vetores (7)



Na declaração dos parâmetros poder-se-ia ter:
f(int arr[]) { ... } ou
f(int *arr) { ... }
Também é permitida indexações do tipo p[-1] …
p[-i], desde que estejam dentro dos limites do
vetor maior.
É ilegal a referência a objetos que não se
encontrem dentro dos limites do vetor.
Aritmética com endereços (1)

Seja p um pointer para algum elemento de um vetor.

p++ incrementa p, para que aponte para o próximo elemento.





p+=i incrementa p para que aponte i elementos além do elemento
atualmente apontado por p.
Ver prog45-chap05-pg85.c → alocador de memória rudimentar.
alloc(n) retorna um pointer para n posições consecutivas de
caracteres, as quais podem ser usadas pelo invocador de alloc para
armazenar caracteres.
afree(p), libera a área adquirida, para que possa ser usada mais
tarde.
As funções são rudimentares, porque as chamadas a afree devem
ser feitas na ordem inversa das chamadas a alloc, isto é, a área de
armazenamento gerenciada por alloc e afree é uma pilha.
Aritmética com endereços (2)





A biblioteca padrão do C fornece as funções análogas
malloc e free que não têm tais restrições.
Implementação mais simples: alloc → fornece partes de
um grande vetor de caracteres, denominado allocbuf.
Este vetor é privado a alloc e afree.
Como alloc e afree manipulam apontadores e não índices
de vetores, as outras funções não precisam saber o nome
do vetor, o qual pode ser declarado como static no
arquivo fonte contendo alloc e afree.
Precisa-se controlar quanto de allocbuf já foi usado.
Usa-se o pointer allocp para o próximo elemento livre.
Aritmética com endereços (3)

Uma invocação alloc(n) verifica se há espaço disponível (n caracteres) em
allocbuf. Se houver, alloc retorna o valor corrente de allocp e, após,
incrementa o seu valor de n, a fim de apontar para o início da próxima área
livre; em caso contrário alloc retorna zero. afree(p) apenas faz que allocp
aponte para p, se este estiver dentro dos limites de allocbuf.
Aritmética com endereços (4)



Ver prog45-chap05-pg85.c
static char *allocp = allocbuf;
Define allocp como sendo um pointer para
caracter e o inicia para apontar para o início de
allocbuf, que é a próxima posição livre, quando o
programa tem início.
Isto também poderia ser escrito como:
static char *allocp = &allocbuf[0];
dado que o nome do vetor corresponde ao
endereço do elemento de índice zero.
Aritmética com endereços (5)

O teste
if (allocbuf + ALLOCSIZE - allocp >= n) { /* it fits */


Verifica se há espaço suficiente para atender a
um pedido de n caracteres. Se houver, alloc
retorna um pointer para um início de um bloco
de caracteres. Senão, alloc retorna zero,
indicando que não há espaço disponível.
A linguagem C garante que zero nunca é um
endereço válido para dados, logo pode ser usado
para sinalizar falta de espaço.
Aritmética com endereços (6)



Pointers e integers não são intercambiáveis.
Zero é a única exceção. A constante zero pode ser atribuída a um
pointer e um pointer pode ser comparado à constante zero.
Usualmente emprega-se a constante simbólica NULL, ao invés
de zero, como mneumônico indicativo de que este é um valor
especial para um pointer.

NULL é definido em <stdio.h>.

Sob certas circunstâncias pode-se comparar pointers.


Se p e q apontam para membros do mesmo vetor então relações
envolvendo ==, !=, >, >=, <, <= são válidas.
Todavia, o comportamento é indefinido para aritmética ou
comparações com pointers que não apontam para elementos do
mesmo vetor.
Aritmética com endereços (7)



Exceção: o endereço do primeiro elemento após o
fim de um vetor pode ser usado em aritmética de
apontadores.
Atenção: p+n significa o n-ésimo elemento a partir
da posição apontada por p, independente do tipo de
objeto para o qual p aponta. O compilador ajusta n,
de acordo com o tamanho dos objetos apontados
por p (int, long, struct, etc.).
q-p+1 é o número de elementos de p a q,inclusive.
Aritmética com endereços (7)



Exceção: o endereço do primeiro elemento após o
fim de um vetor pode ser usado em aritmética de
apontadores.
Atenção: p+n significa o n-ésimo elemento a partir
da posição apontada por p, independente do tipo de
objeto para o qual p aponta. O compilador ajusta n,
de acordo com o tamanho dos objetos apontados
por p (int, long, struct, etc.).
q-p+1 é o número de elementos de p a q,inclusive.
Aritmética com endereços (8)




Outra versão de strlen usando apontadores:
prog46-chap05-pg86.c
O número de caracteres da cadeia poderia ser muito
grande para ser armazenado em um int. O arquivo
header <stddef.h> define um tipo ptrdiff-t que é grande
o sufuciente para conter a diferença sinalizada de dois
valores de ponteiros.
No entanto, o ideal é usar size-t para o tipo do retorno de
strlen (compatibilidade com a biblioteca padrão).
size-t é o tipo inteiro não sinalizado retornado pelo
operador sizeof.
Aritmética com endereços (9)



A aritmética de apontadores é coerente. Se p aponta para o
i-ésimo elemento de um vetor v, p+1 apontará para o (i+1)ésimo elemento do vetor, independentemente do tipo de v
(char, integer, long, float, struct, etc.).
As operações válidas com ponteiros são: atribuições de
pointers do mesmo tipo, adição ou subtração de um pointer
e um int, adição ou subtração de pointers que apontam para
elementos de um mesmo vetor e atribuição ou comparação
com zero.
Todas as outras operações aritméticas com apontadores são
ilegais (somar, multiplicar, dividir, etc.), inclusive atribuir
um pointer de um tipo a um pointer de um outro tipo
(exceto para void sem o uso de type cast).
Pointers para caracteres e funções(1)





Uma constante do tipo cadeia é um vetor de caracteres.
Na representação interna o vetor é terminado por um '\0',
para que os programas possam encontrar o fim da cadeia.
O tamanho do vetor é, portanto, o tamanho da cadeia +1.
Tem-se acesso a uma constante do tipo cadeia, através de
um pointer para o seu primeiro elemento.
char *pmessage; /* (1) */
pmessage = "now is the time"; /* (2) */
atribui a pmessage um pointer para o array de
caracteres "now is the time''.
Pointers para caracteres e funções(2)

char *pmessage; /* (1) */
pmessage = "now is the time"; /* (2) */
atribui a pmessage um pointer para o array de caracteres "now is the time''.
Não se trata de uma cópia da cadeia. Apenas pointers estão envolvidos.

Atenção para as diferenças entre as definições:
char amessage[] = "now is the time"; /* an array */
char *pmessage = "now is the time"; /* a pointer */


amessage é um array. Elementos do array podem ser alterados, mas amessage sempre irá
referir-se à mesma área de armazenamento.
pmessage é um pointer, inicializado para apontar para uma cadeia constante; posteriormente o
pointer pode apontar para outros locais, mas o resultado é indefinido se tentarmos alterar o
conteúdo da cadeia.
+ pointers e vetores (1)



Programas ilustrativos com versões de funções úteis adaptadas da
biblioteca padrão.
strcpy(s,t) – copia a cadeia s para a cadeia t.
s = t; /* s=t; copiaria apenas o apontador e
caracteres */
não os

O prog47-chap05-pg88.c é uma versão simplificada de strcpy(s,t).

prog48-chap05-pg88.c é uma versão de strcpy(s,t) que usa pointers.

Programadores experientes em C prefiririam o código do prog49chap05-pg88.c.

Observe que a comparação com '\0' é redundante. Isto levaria ao
código mais compacto do prog50-chap05-pg88.c.
Vetores de pointers - p p/ p (1)




Pointers são variáveis. Como tal é possível se
ter um array de pointers.
Exemplo: escrever um programa que ordene um
conjunto de linhas de texto em ordem alfabética.
Versão simplificada do utilitário sort do UNIX.
Ver prog53-chap05-pg90.c.
Vetores de pointers - p p/ p (2)





Precisa-se de uma representação de dados que seja
eficiente e conveniente para linhas de tamanho
variável.
Solução: armazenar as linhas a serem ordenadas
contiguamente em um longo vetor de caracteres.
Poder-se-á ter acesso a cada linha por meio de um
pointer para o seu primeiro caracter.
Os pointers estarão armazenados em um vetor.
Duas linhas poderão ser comparadas invocando-se
strcmp com seus pointers.
Vetores de pointers - p p/ p (3)



Quando duas linhas fora de ordem precisarem ser
trocadas, basta-se trocar a ordem dos pointers e não as
próprias linhas de texto.
Esta solução elimina um problema de gerenciamento de
espaço não trivial e também o esforço computacional
associado à movimentação das próprias linhas.
O processo de ordenação envolve três passos:



Ler todas as linhas de entrada
Ordená-las
Imprimí-las na ordem desejada
Vetores de pointers - p p/ p (4)




A função responsável pela entrada (readlines) deve captar e
salvar os caracteres de cada linha e construir um array de
pointers para estas linhas.
Deve contar o número de linhas de entrada, uma vez que
esta informação é vital para os processos de classificação e
impressão.
A função de entrada só pode lidar com um número finito de
linhas de entrada. Assim retornará -1 (uma contagem
ilegal), se houver um número excessivo de linhas.
A função de saída (writelines) tem apenas que imprimir as
linhas na ordem em que estas se encontram no array de
pointers.
Vetores de pointers - p p/ p (5)


A função getline vem da seção 1.9.
O que há de novo é a declaração de lineptr:
char *lineptr[MAXLINES]
informa que lineptr é um vetor de MAXLINES
elementos, cada elemento sendo um pointer para
um char. Isto é, lineptr[i] é um pointer para
character, e *lineptr[i] é o character para o qual
ele aponta, o primeiro character da i-ésima linha
de texto salva da entrada.
Vetores de pointers - p p/ p (6)



Como lineptr é o nome de um array, ele pode ser visto
também como um pointer, o que possibilita uma versão
alternativa para o código de writelines.
Inicialmente, *lineptr aponta para a primeira linha;
cada iteração do loop avança para o próximo pointer de
linha, quando nlines é decrementado.
O algoritmo quicksort deve ser alterado (invocando a
função strcmp) para permitir a classificação em ordem
alfabética.
Vetores multidimensionais (1)




C provê arrays multidimensionais, embora, na
prática eles sejam menos usados que os arrays de
pointers.
Ver prog53a-chap05-pg92.c.
Considere o problema de conversão de datas, de dia
do mês para dia do ano e vice-versa.
Define-se duas funções para realizar as conversões:
day_of_year converte mês e dia em dia do ano
month_day converte o dia do ano em mês e dia.
Vetores multidimensionais (2)

month_day computa dois valores, assim, os
argumentos month e day serão pointers.
month_day(1988, 60, &m, &d)
torna m = 2 e d = 29 (February, 29th).
Essas funções necessitam ambas da mesma
informação, uma tabela com o número de dias
e em cada mês, e que apresentarão diferenças nos
anos bissextos.
static char daytab[2][13] = {{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};
Vetores multidimensionais (3)




O valor aritmético de uma expressão lógica (e.g. leap) é
zero (false) ou um (true), e assim pode-se usá-lo como um
subscrito para o array daytab.
O array daytab deve ser external a day_of_year e
month_day, de modo que ambas as funções possam
utilizá-lo.
daytab foi declarado como char para ilustrar o uso
legítimo de char para armazenar small integers.
Array de duas dimensões em C → é um array
unidimensional, em que cada um de seus elementos é um
array.
Vetores multidimensionais (4)

daytab[i][j]

daytab[i,j]



/* [row][col] */
/* WRONG */
Os elementos são armazenados por linhas, assim
o subscrito mais à direita, ou coluna, varia mais
rapidamente.
Um array é inicializado por uma lista de
initializadores entre chaves.
Cada linha de um array bidimensional é
inicializada com uma sublista correspondente.
Vetores multidimensionais (5)


Se um array bidimensional tiver que ser passado para uma função, a
declaração do parâmetro na função deve incluir o número de colunas; o
número de linhas é irrelevante, pois o que é passado é um pointer para um
array de linhas.
Se o array daytab tivesse que ser passado para uma função f, a declaração de
f seria:
f(int daytab[2][13]) { ... } , ou
f(int daytab[][13]) { ... }
, ou ainda
f(int (*daytab)[13]) { ... } que diz que o parâmetro é um pointer para um
array de 13 inteiros.


Os parênteses são necessários, pois os colchetes [] têm maior precedência que
*. Sem eles a declaração int *daytab[13] seria um array de 13 pointers para
inteiros.
Em geral, apenas a primeira dimensão (subscrito) de um array é opcional.
Todas as outrasprecisam ser especificadas.
Inicialização de arrays de pointers






Problema: escrever uma função month_name(n) que retorne um
pointer para uma cadeia de caracteres contendo o nome do nésimo mês.
Ver prog53b-chap05-pg94.c
A declaração static char *name[] diz que name é um array de
pointers para cadeias de caracteres.
O inicializador é uma lista de cadeias de caracteres.
Os caracteres da i-ésima cadeia são colocados em alguma posição
de memória e um pointer para eles é armazenado em name[i].
Como o tamanho do array name não é especificado, o compilador
conta os inicializadores e calcula o número de elementos do
array.
Pointers x arrays multidimensionais(1)



Dadas as declarações
int a[10][20];
int *b[10];
então a[3][4] e b[3][4] são sintaticamente referências
legais a um único inteiro.
No entanto, a é um verdadeiro array bidimensional –
200 áreas de memória correspondendo a um int foram
separadas.
O cálculo convencional de um subscrito retangular
20*linha+coluna é usado para encontrar o elemento
a[linha,coluna].
Pointers x arrays multidimensionais(2)




Para b a declaração aloca 10 pointers, mas não os
inicializa. A inicialização deve ser feita explicitamente,
ou estaticamente ou via código.
Se cada elemento de b apontar para um array de 20
elementos, então haverá 200 ints alocados, além de 10
células para os pointers.
A vantagem do array de pointers é que as linhas do
array podem ser de tamanhos diferentes.
Um dos usos mais freqüentes dos arrays de pointers é
armazenar cadeias de caracteres de tamanhos diversos,
como na função month_name.
Arrays de pointers x array bidimensional
Argumentos da linha de comando(1)


Em C há uma forma de se executar um
programa passando argumentos na linha de
comando.
Quando main é ativado ele recebe dois
argumentos:
argc – o número de argumentos na linha de
comando;
argv – um pointer para um array de cadeias de
caracteres que contém os argumentos, um por
cadeia.
Argumentos da linha de comando(2)


Por convenção argv[0] é o nome pelo qual o programa foi
chamado, de modo que argc é pelo menos 1.
Considere o programa echo, que ecoa, na saída padrão os
argumentos que recebe em sua linha de comando:
eeepc@asus:~$ echo hello, world
imprimiria na saída padrão (terminal):
hello, world

Neste caso, argv[0]=''echo''
argv[1]=''hello,''
argv[2]=''world''

Adicionalmente o padrão requer que argv[argc] seja um
pointer com o valor null.
Argumentos da linha de comando(3)



A primeira versão de echo trata argv como um array de pointers para
caracteres.
ver prog54-chap05-pg95.c.
argv é um pointer para um array de pointers. Assim, pode-se manipular
o pointer, ao invés do índice do array.

Ver prog55-chap05-pg96.c.

Alternativamente poder-se-ia escrever o printf como:
printf((argc > 1) ? "%s " : "%s", *++argv);

Ou seja, o argumento de formato de printf pode ser uma expressão.
Argumentos da linha de comando(4)






ver prog56-chap05-pg96.c.
Incrementa melhorias no programa de pesquisa de
padrão (seção 4.1 – prog32-chap04-pg60.c)
O padrão a ser pesquisado será especificado pelo
primeiro argumento da linha de comando.
:~$ find padrao
Similar ao utilitário grep do unix.
A função da biblioteca padrão strstr(s,t) retorna um
pointer para a primeira ocorrência da cadeia t na cadeia
s, ou NULL se não houver pelo menos uma ocorrência.
strstr(s,t) é declarada em <string.h>.
Argumentos da linha de comando(5)


Elaborar mais o programa de pesquisa de padrão para ilustrar outras
construções com pointers.
Agora, existirão dois argumentos opcionais:
→ o primeiro (-x) diz “imprima todas as linhas, exceto as que casem
com o padrão”;
→ o segundo (-n) diz “preceda cada linha impressa pelo seu número”.



:~$ find -x -n padrao
Argumentos opcionais devem ser permitidos em qualquer ordem e o
programa deve ser independente do número de argumentos presentes.
Além do mais, os usuários podem combinar os argumentos opcionais,
como em:
:~$ find -xn padrao

Ver programa prog57-chap05-pg97.c.
Argumentos da linha de comando(6)





argc é decrementado e argv é incrementado antes de cada argumento
opcional. Ao final do loop, se não houver erros, argc informa quantos
argumentos ainda restam a processar e argv aponta para o primeiro desses
argumentos.
Assim, argc deveria ser 1 e argv deveria apontar para o padrão.
Observe que *++argv é um pointer para um argumento do tipo cadeia de
caracteres (string), logo (*++argv)[0] é o seu primeiro caracter.
Uma forma alternativa válida seria **++argv. Como [] vincula mais
fortemente que * e ++, os parênteses tornam-se necessários. Sem eles a
expressão seria equivalente a *++(argv[0]).
. Aliás, usou-se essa expressão no loop mais interno, aonde o objetivo era
caminhar ao longo de um argumento específico do tipo cadeia. No loop mais
interno, a expressão *++argv[0] incrementa o pointer argv[0]!
Pointers para funções (1)



Em C uma função não é uma variável, mas é
possível definir-se um pointer para uma função.
Este pointer pode ser atribuído, colocado em
arrays, passado para funções, retornado de
funções, etc.
Este conceito será ilustrado com uma alteração
do prog53 (ordena as linhas de entrada), em que,
na presença de um argumento opcional, as
linhas serão ordenadas numericamente e não
lexicograficamente.
Pointers para funções (2)


Um ordenador usualmente consiste de 3 partes:
i) uma comparação, que determina a ordenação de
qualquer par de objetos;
ii) uma troca, que inverte a sua ordem;
iii) um algoritmo de ordenação, que realiza as
comparações e trocas até que os objetos estejam na
ordem.
O algoritmo de ordenação é independente das
operações de comparação e troca, de sorte que, ao
invocá-lo com diferentes funções de comparação e
troca, obter-se-á a ordenação por diferentes critérios.
Pointers para funções (3)



A comparação lexicográfica de duas linhas é feita
pela função strcmp e a comparação numérica por
numcmp, que compara duas linhas com base em
seus valores numéricos e retorna o mesmo tipo de
condição que strcmp.
Estas duas funções são declaradas em main e um
pointer para elas é passado como argumento ao
invocar-se qsort.
Não se incluiu o processamento de erros para os
argumentos de qsort→ foco nas ideias principais.
Pointers para funções (4)


Na invocação de qsort, strcmp e numcmp são
endereços de funções. Como se sabe que são
funções o operador & não é necessário.
qsort foi escrito para processar quaisquer tipos de
dados. Como indicado em seu protótipo:
void qsort(void *lineptr[], int left, int right,
int (*comp)(void *, void *));
qsort espera um array de pointers, dois inteiros e
uma função com dois argumentos do tipo pointers.
Pointers para funções (5)




O tipo pointer genérico void é usado para os
argumentos tipo pointer.
Qualquer tipo de pointer pode ser moldado (typecast)
para void* e trazido de volta sem qualquer perda de
informação.
O molde elaborado do argumento da função molda os
argumentos da função de comparação.
int (*comp)(void *, void *)
informa que comp é um pointer para uma função que
tem dois argumentos void* e retorna um int.
Pointers para funções (6)



(*comp)(v[i], v[left])
é coerente com a declaração: comp é um pointer
para a função. *comp é a função e o comando
acima é a chamada a esta função.
Os parênteses são necessários. Sem eles
int *comp(void *, void *) /* errado */
informaria que comp é uma função retornando
um pointer para um int.
A função swap é similar às anteriores, exceto
que as declarações são alteradas para void*.
Declarações complicadas (1)



Algumas declarações podem ser confusas.
Não podem ser lidas da esquerda para a direita e há um uso
intensivo de parênteses. Exemplo:
int *f();
/* f: function returning pointer to int */
int (*pf)(); /* pf: pointer to function returning int */
* é um operador de prefixo e possui menor precedência
que (), de modo que os parênteses são necessários para
forçarem a associação correta.
O uso de typedef (seção 6.7) permite sintetizar/simplificar
as declarações.
Declarações complicadas (2)


Conversão de código em C correspondente a uma declaração para
palavras e vice-versa.
prog-59-chap05-recursive_descent_parser-pg102
Exemplos:
char **argv → argv: pointer to pointer to char
int (*daytab)[13] → daytab: pointer to array[13] of int
int *daytab[13] → daytab: array[13] of pointer to int
void *comp() → comp: function returning pointer to void
void (*comp)() → comp: pointer to function returning void
char (*(*x())[])() → x: function returning pointer to array[] of pointer
to function returning char
char (*(*x[3])())[5] → x: array[3] of pointer to function returning pointer
to array[5] of char
Declarações complicadas (3)


dcl (rdparser) é baseado na gramática que especifica um declarator,
formalmente expressa no apêndice A, seção 8.5;
Forma simplificada do declarator:
dcl: optional *'s direct-dcl
direct-dcl: name
(dcl)
direct-dcl()
direct-dcl[optional size]

Esta gramática pode ser usada para analisar declarações.
(*pfa[]) () → pfa será identificado como name e assim é uma direct-dcl.
Então pfa[] é também uma direct-dcl. Então *pfa[] é reconhecido como
uma dcl, de sorte que (*pfa[]) é uma direct-dcl. Então (*pfa[])() é uma
direct-dcl e, portanto, uma dcl.
Declarações complicadas (4)

parser tree ou árvore de análise
Declarações complicadas (5)




O núcleo do programa dcl (rdparser) é um par de
funções dcl e dirdcl, que varrem (analisam) a
declaração, de acordo com a gramática.
Como a gramática é definida recursivamente, as
funções chamam umas às outras recursivamente,
enquanto vão reconhecendo partes da declaração.
O programa chama-se recursive-descent parser
(analisador recursivo de descendência).
prog-59-chap05-recursive_descent_parser-pg102
Declarações complicadas (6)



Caminhar no sentido inverso é mais fácil, em especial se
não nos importarmos em gerar parênteses redundantes.
prog-60-chap05-recursive_descent_parser-pg104
O programa indcl converte uma declaração em palavras do
tipo ``x is a function returning a pointer to an array of
pointers to functions returning char'', que expressaremos
como
x () * [] * () char
em char (*(*x())[])()


A sintaxe abreviada da entrada nos permitirá usar a função
gettoken.
undcl também usa as mesmas variáveis externas que dcl.