Capítulo 7  Registros

Um registro (ou, como é chamado em C, uma estrutura) é um tipo, e também um valor desse tipo, que é um produto cartesiano de outros tipos, chamados de campos ou componentes do registro, com notações especiais para definição dos componentes do produto e para acesso a esses componentes.

Em matemática, e em algumas linguagens de programação, a forma mais simples de combinar valores para formação de novos valores é a construção de pares. Por exemplo, (10,’*’) é um par, formado por um primeiro componente, 10, e um segundo componente, ’*’. Um par é um elemento do produto cartesiano de dois conjuntos — o par (10,’*’) é um elemento do produto cartesiano do conjunto dos valores inteiros pelo conjunto dos valores de tipo char.

Naturalmente, além de pares, é também possível formar triplas, quádruplas, quíntuplas etc. — usualmente chamadas de tuplas — que são elementos de produtos cartesianos generalizados, ou seja, elementos de um produto de vários conjuntos.

Em linguagens de programação (como C por exemplo), no entanto, é mais comum o uso de registros, em vez de tuplas. Um registro é uma representação de um valor de um produto cartesiano, assim como uma tupla, mas cada componente, em vez de ser identificado pela sua posição (como no caso de tuplas), é identificado por um nome — usualmente chamado de rótulo. Cada componente tem um nome a ele associado.

Por exemplo, um valor como:

representa, em C, um registro com dois componentes, em que um deles tem rótulo x e o outro tem rótulo y. Nesse exemplo, o valor do componente é separado do rótulo pelo símbolo “=”. O registro  {y = '*', x = 10}  representa o mesmo valor que o registro  {x = 10, y = '*'} . Ou seja, a ordem em que os componentes de um registro é escrita não é relevante para determinação do valor representado, ao contrário do que ocorre com relação à ordem dos componentes de uma tupla. Deve existir, é claro, uma operação para selecionar um componente de um registro, assim como ocorre no caso de tuplas.

No entanto, em C a especificação de valores de tipo registro deve seguir uma ordem para os valores dos campos, que é a ordem em que os campos aparecem na definição do tipo registro, e só podem ser usados em declarações de variáveis, como veremos no exemplo a seguir.

Uma declaração de um tipo registro consiste de uma sequência de campos, cada um dos quais com um tipo e um nome. Por exemplo:

Em C, a definição acima consiste na definição de um tipo, de nome contaBancaria, ao qual se pode referir usando a palavra struct seguida do nome contaBancaria.

Por exemplo, a seguinte declaração cria uma variável desse tipo:

O tipo contaBancaria, assim como a variável conta, têm três campos ou componentes: numero, idCorrentista e saldo.

O acesso aos componentes é feito usando-se um valor de tipo registro seguido de um ponto e do nome do campo. Por exemplo, conta.numero tem tipo int. Analogamente, conta.idCorrentista tem tipo char* e conta.saldo tem tipo float.

Esses componentes denotam (podem ser usados ou modificados como) uma variável comum do tipo do campo.

Valores de tipo registro podem ser construídos em C mas apenas na inicialização de uma variável de tipo registro, de modo semelhante ao que ocorre no caso de arranjos. Um valor de tipo registro especifica valores a cada um dos campos do registro, entre chaves, como mostrado no exemplo a seguir.

O exemplo seguinte ilustra uma declaração de uma variável do tipo contaBancaria, definido acima, especificando um valor inicial para a variável:

A atribuição de um valor de tipo registro a outro copia, como esperado, o valor de cada campo do registro. Considere o seguinte exemplo:

Esse programa imprime:

7.1  Declarações de tipos com typedef

O uso de nomes para introdução de novos tipos é bastante útil, para documentação e legibilidade do programa, e isso ocorre particularmente no caso de tipos registro e outros tipos relacionados. Por exemplo, para dar um nome para um tipo que representa coordenados do plano cartesiano, ou dados de uma conta bancária, pode-se definir e usar tipos Ponto e ContaBancaria como a seguir:

7.2  Ponteiros para registros

Ponteiros para registros podem ser usadas para passar valores de tipo registro sem ter que copiar o registro, e também de modo a permitir a alteração de campos de registros.

Um ponteiro para um registro pode ser derreferenciado como normalmente, usando o operador *, mas existe em C a possibilidade de usar o operador ->, que além da derreferenciação faz também acesso a um campo de um registro. Por exemplo:

7.3  Estruturas de dados encadeadas

Em computação, uma estrutura de dados encadeada consiste de uma sequência de registros de tipo T que contêm um campo que é um ponteiro que pode ser nulo ou um ponteiro para um próximo registro de tipo T.

Por exemplo, uma lista encadeada de registros com campos de tipo int pode ser formada com registros do seguinte tipo:

Listas encadeadas são estruturas de dados flexíveis, pois não requerem tamanho máximo, como arranjos. Elas podem crescer e decrescer de tamanho à medida que dados vão sendo inseridos e removidos.

A desvantagem, em relação ao uso de arranjos, é que o acesso a um componente da estrutura de dados requer um tempo que depende da posição desse componente na estrutura: o acesso a cada componente depende de acesso a cada um dos componentes anteriores a ele na lista.

Árvores binárias podem ser formadas de modo similar. Por exemplo, uma árvore binária com nodos que contêm campos de tipo int pode ser formada com registros do seguinte tipo:

O seguinte exemplo ilustra o uso de uma lista encadeada para evitar a restrição de se ter que especificar um número máximo de valores, necessário para uso de arranjo. Considere o problema do Exercício Resolvido 1, da seção 5.5.5, que propõe que um texto qualquer seja lido e seja impressa a frequência de todos os caracteres que ocorrem no texto. Considere que o problema não especifica o tamanho do texto. A solução a seguir usa uma lista encadeada de caracteres para armazenar o texto, em vez de uma cadeia de caracteres.

Em casos como esse, pode ser mais adequado usar um arranjo flexível, com um tamanho máximo que pode ser aumentado, testando, antes de cada inserção de um novo valor no arranjo, se esse tamanho máximo foi atingido. Se o tamanho máximo for atingido, um novo arranjo é alocado com um tamanho maior (por exemplo, o dobro do tamanho anterior), o arranjo antigo é copiado para o novo, e o novo arranjo passa a ser usado, no lugar do antigo. Arranjos flexíveis são estruturas de dados bastante usadas em programas escritos em linguagems como, por exemplo, Java e C++.

7.4  Exercícios Resolvidos

1. Escreva um programa que funcione como o exemplo fornecido na seção 5.3 mas sem a condição de que o número de valores a serem impressos, em ordem impressa, seja fornecido. Ou seja, escreva um programa que leia do dispositivo de entrada padrão qualquer número de valores inteiros, separados por um ou mais espaços ou linhas, e imprima esses valores na ordem inversa em que foram lidos.

   Solução:

   #include <stdio.h> #include <stdlib.h> struct nodoLista { int val; struct nodoLista* prev; }; typedef struct nodoLista nodoLista; int main() { int val, numValLidos; struct nodoLista *cur, *prev = NULL; while (1) { numValLidos = scanf("%d", &val); if (numValLidos != 1) break; cur = malloc(sizeof(nodoLista)); cur -> val = val; cur -> prev = prev; prev = cur; } while (cur != NULL) { printf("%d ", ur -> val); cur = cur -> prev; } }

   A solução usa a notação ponteiro -> campo, que é uma abreviação para (*ponteiro).campo.

2. Escreva um programa que leia, do dispositivo de entrada padrão, resultados de partidas de um campeonato e imprima, no dispositivo de saída padrão, a lista dos nomes dos times que obtiveram maior número de pontos nesse campeonato. Cada vitória vale 3 pontos e cada empate vale 1 ponto.

   A entrada consiste dos seguintes dados, nesta ordem:

   1. uma linha contendo um número inteiro n, que especifica o número de times do campeonato;
   2. n linhas contendo dois valores i e s_i, onde i é um número inteiro entre 1 e n e s_i é o nome do time i; o nome de um time é uma cadeia de caracteres de tamanho máximo 30; a ordem em que essas n linhas aparecem na entrada deve ser irrelevante;
   3. várias linhas contendo 4 números inteiros não-negativos t₁ v₁ t₂ v₂, que indicam o resultado da partida entre o time t₁ e t₂: t₁ marcou v₁ gols e t₂ marcou v₂ gols; os resultados terminam com o fim da entrada (EOF).

   Os times na lista impressa devem estar separados por vírgula (se houver mais de um time com mais pontos), e a ordem é irrelevante. Por exemplo, se a entrada for:

   3

   1 America

   2 Atletico

   3 Cruzeiro

   1 1 2 2

   1 2 3 3

   2 1 3 1

   A saída deve ser: Atletico, Cruzeiro

   Isso porque o America perdeu do Atletico (1x2) e do Cruzeiro (2x3), e o Atletico empatou com o Cruzeiro (1x1).

   Solução: A solução apresentada usa arranjos para armazenar nomes de times e para armazenar pontos acumulados em partidas. Esses arranjos são indexados com o número do time menos 1 (porque os números de time variam entre 1 e n e arranjos em C sempre têm índice inicial igual a 0). O programa constrói uma lista de vencedores (times com maior número de pontos) à medida em que tal maior número de pontos é calculado. A lista de vencedores — chamada de maiores — é inicialmente nula. Para cada time, do primeiro ao último, se o número de pontos é maior do que o maior calculado até cada instante desta iteracão, o maior é atualizado, senão, se o número de pontos for igual, este é inserido na lista de maiores.

   #include <stdio.h> #include <stdlib.h> struct Maiores { int num; struct Maiores *prox; }; typedef struct Maiores Maiores; int main() { int n, num; scanf("%d", &n); char** times = malloc(n * sizeof(char*)); int i; const int tamMaxNomeTime = 31; // 31 devido a terminacao com '\0' for (i=0; i<n; i++) { scanf("%d", &num); times[num-1] = malloc(tamMaxNomeTime*sizeof(char)); scanf("%s", times[num-1]); } int numValLidos, num1, num2, gols1, gols2, *pontos; pontos = malloc(n * sizeof(int)); for (i=0; i<n; i++) pontos[i] = 0; while (1) { numValLidos = scanf("%d%d%d%d", &num1, &gols1, &num2, &gols2); if (numValLidos != 4) break; if (gols1>gols2) pontos[num1-1] += 3; else if (gols2>gols1) pontos[num2-1] += 3; else { pontos[num1-1]++; pontos[num2-1]++; } } Maiores* maiores = NULL; int maior = 0; for (i=0; i<n; i++) if (pontos[i] > maior) { maiores = malloc(sizeof(Maiores)); maiores->num = i; maiores->prox = NULL; maior = pontos[i]; } else if (pontos[i] == maior) { // novo elemento em maiores Maiores* novo = malloc(sizeof(Maiores)); novo->prox = maiores; novo->num = i; maiores = novo; } printf("%s", times[maiores->num]); maiores = maiores->prox; while (maiores!=NULL) { printf(", %s", times[maiores->num]); maiores = maiores -> prox; } printf("\n"); return 0; }

7.5  Exercícios

1. Escreva um programa que leia um valor inteiro positivo n, em seguida leia, caractere a caractere, uma cadeia de caracteres s de um tamanho qualquer, maior do que n, e imprima os n últimos caracteres de s, armazenando para isso a cadeia s como uma uma lista encadeada de caracteres onde um apontador é usado para apontar para o caractere anterior da cadeia.
2. Escreva um programa que leia um valor inteiro positivo n e, em seguida, uma sequência s de valores inteiros diferentes de zero, cada valor lido separado do seguinte por um ou mais espaços ou linhas, e imprima n linhas tais que: a 1^a linha contém os valores de s divisíveis por n, a 2^a linha contém os valores de s para os quais o resto da divisão por n é 1, etc., até a n-ésima linha, que contém os valores de s para os quais o resto da divisão por n é n−1. A entrada termina quando um valor igual a zero for lido. A ordem dos valores impressos em cada linha não é relevante.

   Use um arranjo de n posições com elementos que são registros representando listas encadeadas de valores inteiros.

   Exemplo: Considere a entrada:

   4 12 13 15 16 17

   Para essa entrada, a saída deve ser como a seguir:

   Valores divisiveis por 4: 16 12

   Valores com resto da divisao por 4 igual a 1: 17 13

   Nenhum valor com resto da divisao por 4 igual a 2

   Valores com resto da divisao por 4 igual a 3: 15

3. Reescreva o programa do exercício anterior de modo a fazer com que a ordem dos valores impressos seja a mesma ordem que os valores ocorrem na entrada. Para isso, use um arranjo de ponteiros para a última posição de cada lista encadeada.

7.6  Notas Bibliográficas

Existe uma vasta literatura sobre algoritmos e estruturas de dados em computação, que estendem o que foi abordado neste capítulo principalmente com o estudo mais detalhado de algoritmos para busca, inserção, remoção e ordenação de valores nessas estruturas de dados. Além de aspectos de implementação de estruturas de dados e de operações para manipulação das mesmas, essa literatura aborda em geral diferentes aplicações dos algoritmos e discute também aspectos de eficiência (ou complexidade, como é usual dizer em computação) de algoritmos.

Livros didáticos dedicados a esses temas incluem [27, 22, 19], os dois primeiros já traduzidos para a língua portuguesa e o terceiro escrito em português. [9] é um livro interessante, que adota a abordagem de programação funcional.