Programação com a Linguagem C

 

Estruturas

 

·       Uma estrutura é uma coleção de uma ou mais variáveis de qualquer tipo, colocadas juntas sob um único nome (registro do PASCAL).

·       Estruturas auxiliam na organização de dados complexos, particularmente em grandes programas.

·       As estruturas permitem que o agrupamento de variáveis inter-relacionadas seja tratado como uma unidade.

·       A principal mudança introduzida pelo padrão ANSI é a definição da atribuição de estruturas - estruturas podem ser copiadas e atribuídas, passadas para funções, e retornadas de funções.

 

1 - Elementos Básicos

 

·       A palavra-chave struct introduz uma declaração de estrutura, que é uma lista de declarações entre chaves.

·       Uma declaração struct define um tipo:

 

     struct rótulo {lista de declarações};

 

·       O rótulo é opcional e dá nome ao tipo estrutura.

·       O fecha-chave que termina a lista de declarações pode ser seguido por uma lista de variáveis como na declaração de qualquer tipo básico:

 

     struct{ ... } x, y, z;

     struct data {

         int       dia;

         int       mes;

         int       ano;

         int       dia_ano;

         char      nome_mes[4];

     };

 

·       Os elementos que compõem uma estrutura são chamados de membros.

·       O rótulo de uma estrutura e uma variável, que não seja membro desta estrutura, podem ter o mesmo nome.

·       Definição de uma variável do tipo estrutura:

 

     struct { lista de declarações } v1, v2, ...;

 

   ou

 

     struct rótulo v1, v2, ...;

 

·       Exemplo:

 

     struct {

         int       dia;

         int       mes;

         int       ano;

         int       dia_ano;

         char      nome_mes[4];

     } d;

 

ou

 

     struct data d;

 

·       Uma estrutura pode ser inicializada na sua definição:

 

     struct data d = { 7, 8, 1822, 250, "set"};

 

·       Uma estrutura automática também pode ser inicializada por atribuição ou pela chamada de uma função que retorne uma estrutura do tipo correto.

·       A referência ao membro de uma estrutura é feita por uma construção do tipo:

 

     nome_da_estrutura.membro

 

·       Exemplo:

 

     bissexto = d.ano % 4 == 0 && d.ano % 100 != 0 ||                d.ano % 400 == 0;

     if (strcmp (d.nome_mes, " ago") == 0) ...

     d.nome.mes[0] = minusculo (d.nome_mes [0]);

 

·       Estruturas podem ser aninhadas:

 

     struct pessoa {

         char          nome [TAMNOME];

         char          endereco [TAMENDER];

         long          cep;

         long          cpf;

         double        salario;

         struct data   nascimento;

         struct data   contratacao;

     };

 

·       Se declararmos emp como:

 

     struct pessoa emp;

 

   então,

 

     emp.nascimento.mes /* mes que o empregado

                               nasceu */

 

2 - Estruturas e Funções

 

·       As únicas operações legais com uma estrutura são copiá-la e atribuí-la como uma unidade, tomar seu endereço com &, e acessar seus membros.

·       Cópia e atribuição incluem a passagem de argumentos para funções e também o retorno de valores de funções.

·       Ùma etrutura pode ser inicializada por uma lista de valores constantes dos membros.

·       Uma estrutura automática também pode ser inicializada por uma atribuição.

·       Há pelo menos três métodos possíveis de passar os dados de uma estrura para funções: passar os componentes separadamente, passar uma estrutura inteira, ou passar um apontador para ela. Todos os métodos têm seus pontos fortes e fracos.

·       Trabalharemos escrevendo algumas funções para manipulação de pontos e retângulos.

·       A primeira função, criaponto( ), receberá dois inteiros e retornara uma estrutura do tipo ponto:

 

     struct ponto {

         int  x;

         int  y;

     };

 

·       A estrutura retang define um retângulo através de pontos diagonalmente opostos:

 

     struct retang {

         struct ponto  p1;

         struct ponto  p2;

     };

 

struct ponto criaponto (int x, int y) /* cria um ponto a

     partir das coodenadas */

{

     struct ponto temp;

     temp.x = x;

     temp.y = y;

     return temp;

}

 

·       Não há conflito entre os nomes dos membros e as variáveis locais apenas, a reutilização dos nomes reforça a relação.

·       criaponto ( ) pode agora ser utilizada para inicializar qualquer estrutura dinamicamente, ou para fornecer argumentos da estrutura para uma função:

 

     struct retang tela;

     struct ponto meio;

     struct ponto criaponto (int, int);

 

     tela.pt1 = criaponto(0, 0)

     tela.pt2 = criaponto (XMAX, YMAX);

 

     meio = criaponto ((tela.pt1.x + tela.pt2.x/2,

                          tela.pt1.y + tela.pt2.y)/2);

 

·       Conjunto de funções para fazer aritmética com pontos:

 

     struct ponto somaponto (struct ponto p1,

                                 struct ponto p2)

     /* soma dois pontos */

     {

         p1.x += p2.x;

         p1.y += p2.y;

         return p1;

     }            

 

     int ptemret (struct ponto p, struct retang r)

     /* retorna 1 se p em r, 0 se não */

     {

         return p.x >= r.pt1.x && p.x <= r.pt2.x

         && p.y >= r.pt1.y && p.y <= r.pt2.y

     }

 

·       Assumimos que o retângulo considerado estava numa forma padrão onde as coordenadas de p1 são menores que as de p2. A função a seguir retorna um retângulo em forma canônica:

 

     #define   min (a, b) ((a) < (b) ? (a) : (b))

     #define   max (a, b) ((a) > (b) ? (a) : (b))

 

     struct retang canonret (struct retang t)

     /* torna canonica coordenadas de retângulo */

     {

         struct retang temp;

         temp.pt1.x = min (r.pt1.x, r.pt2.x);

         temp.pt1.y = min (r.pt1.y, r.pt2.y);

         temp.pt2.x = max (r.pt1.x, r.pt2.x);

         temp.pt2.y = max (r.pt1.y, r.pt2.y);

         return temp;

     }

 

·       Se uma estrutura maior tiver de ser passada para uma função, é geralmente mais eficiente passar um apontador do que copiar do que copiar a estrutura inteira:

 

     struct ponto *pp;

 

·       Se pp aponta para uma estrutura do tipo ponto, *pp é a estrutura, e (*pp).x e (*pp).y são seus membros.

·       Para usar pp poderíamos escrever, por exemplo:

 

     struct ponto  origem, *pp;

     pp = &origem;

     printf ("origem eh (%d, %d)\n", (*pp).x, (*pp).y);

 

·       Os parênteses são necessários, pois a precedência  do operador de membro (.) é maior que *.

·       Os apontadores para estruturas são usados com tanta freqüência que existe uma notação alternativa usada para referenciar membros de estruturas.

·       Se p é um apontador para uma estrutura, então para referenciar um membro podemos usar:

 

     p->membro_da_estrutura

     printf ("origem eh (%d, %d)\n", pp->x, pp->y);

 

·       Os operadores . e -> são associativos da esquerda para direita, e se tivermos

 

     struct retang, r, *rp = r;

 

·          então, as seguintes expressões são equivalentes:

 

     r.pt1.x

     rp->pt1.x

     (r.pt1).x

     (rp->pt1).x

 

 

·       O operadores . e -> para estruturas, ( ) para funções, e [] para subscritos têm maior precedência.

·       Dada a declaração:

 

     struct {

         int       tam;

         char      *cad;

     } *p;

·          então:

 

     ++p->tam /* incrementa tam */

     (++p)->tam /* incrementa p, antes de acessar tam /*

     (p++)->tam /* incrementa p, depois de acessar tam */

     p++->tam /* incrementa p, depois de acessar tam */

     *p->cad /* objeto apontado por cad */

     *p->cad++ /* incrementa cad após acessar o objeto

                   apontado */

     (*p->cad)++ /* incrementa objeto apontado por cad */

     *p++->cad /* incrementa p após acessar o objeto

                   apontado */

 

3 - Arranjos de Estruturas

 

·       Estruturas são apropriadas para gerenciar arranjos de variáveis inter-relacionadas.

·       Exemplo de tabela com palavras-chaves e número de ocorrências:

 

     struct chave {

         char      *pal_chave;

         int       cont_chave;

     } tab_chave [NCHAVES];

 

   ou

 

     struct chave {

         char      *pal_chave;

         int       cont_chave;

     };

     struct chave  tab_chave [NCHAVES];

 

·       Inicializando na definição:

 

     struct chave {

         char      *pal_chave;

         int       cont_chave;

     } tab_chave [] = {

         "auto", 0,

         "break", 0,

         "case", 0,

         . . .

         "while", 0

     };

 

·       Os pares poderiam ser especificados como:

 

     { "auto", 0 },

     { "break", 0 },

     { "case", 0 },

     . . .

 

mas, como são variáveis simples não é obrigatório o uso de {...}.

 

·       Exemplo de programa para contagem de palavras-chaves:

 

#include      <stdio.h>

#include      <ctype.h>

#include      <string.h>

#define  MAXPAL    100

 

main ()  /* conta palavras-chaves de C */

{

     int  n;

     char palavra[ MAXPAL ];

     while (lepal (palavra, MAXPAL) != EOF)

         if (isalpha (palavra [0])

              if ((n = pesq_binaria (palavra,

                   tab_chave, NCHAVES)) >= 0)

                   tab_chave [n].cont_chave++;

     for (n = 0; n < NCHAVES; n++)

         if (tab_chave [n].cont_chave > 0)

              printf ("%4d%s\n",

                      tab_chave [n].cont_chave,

                      tab_chave [n].pal_chave );

     return 0;

}

 

pesq_binaria (char *palavra, struct chave tab [], int n)

     /* acha palavra na tabela */

{

     int  cond, inicio, fim, meio;

     inicio = 0;

     fim = n - 1;

     while( inicio <= fim ) {

         meio = (inicio + fim) / 2;

         if ((cond = strcmp (palavra,

               tab [meio].pal_chave)) < 0 )

              fim = meio - 1;

         else if( cond > 0 )

              inicio = meio + 1;

         else

              return meio;

     }

     return -1;

}

 

·       NCHAVES poderia ser definida como:

 

#define NCHAVES (sizeof tab_chave / sizeof (struct chave))

 

lepal (char *palavra, int lim) /* le proxima palavra */

{

     int c, getch (void);

     void ungetch (int);

     char *p = palavra;

     while (isspace (c = getch( ))) {

         ;

     if (c != EOF) {

         *p = '\0';

         return c;

     }

     for (; --lim > 0; p++)

         if(!isalnum (*p = getch ( ))) {

              ungetch(*p);

              break;

         }

     *p = '\0';

     return palavra [0];

}

 

4 - Apontadores para Estruturas

 

·       Usando apontadores no lugar de índices de vetor vamos reescrever o programa de contagem de palavras:

 

#include      <stdio.h>

#include      <ctype.h>

#include      <string.h>

#define MAXPAL 100

 

int lepal (char *, int);

struct chave *pesq_binaria (char *, struct chave, int);

 

main ( )

     /* conta palavras-chave em C; versão c/ apontadores*/

{

     char palavra [MAXPAL];

     struct chave *p;

     while (lepal (palavra, MAXPAL) != EOF)

         if (isalpha(palavra [0]))

              if ((p = pesq_binaria (palavra,

                   tab_chave, NCHAVES != NULL)

                   p->cont_chave++;

     for (p = tab_chave; p < tab_chave + NCHAVES;

         p++)

         if (p->cont_chave > 0)

              printf("%4d %s\n", p->cont_chave,

                     p->palavra);

     return 0;

}

struct chave *pesq_binaria (char *palavra,

     struct chave *tab, int n)

     /* acha palavra em tab[0] ... tab[n-1] */

{

     int  cond;

     struct chave *inicio = &tab[0];

     struct chave *fim = &tab[n];

     struct chave *meio;

     while( inicio < fim ) {

         meio = inicio + (fim - inicio) / 2;

         if ((cond = strcmp (palavra,

              meio->palavra)) < 0 )

              fim = meio;

         else if (cond > 0)

              inicio = meio + 1;

         else

              return meio;

     }

     return NULL;

}

 

·       Nem sempre o tamanho de uma estrutura é a soma do tamanho dos seus membros. Devido ao alinhamento necessário para objetos diferentes, pode haver "buracos" numa estrutura.

·       O nome de uma estrutura pode ser difícil de ser reconhecido quando retorna um tipo complicadodo, como alternativa, poderíamos escrever:

 

struct chave *

pesq_binaria (char *palavra, struct chave *tab, int n)

 

5 - Estruturas Auto-referenciadas

 

·       Ocorre quando temos membros de uma estrutura apontando para o tipo da estrutura.

·       Exemplo de uma árvore binária que guarda palavras diferentes de um texto e o número de suas ocorrências:

 

struct nodo { /* nodo da árvore */

     char          *palavra; /* aponta para palavra */

     int           contador; /* número de ocorrências */

     struct nodo   *esq; /* filho da esq */

     struct nodo   *dir; /* filho da dir */

};

 

void impr_arvore (struct nodo *ap)

     /* imprime a árvore ap recursivamente */

{

     if (ap != NULL) {

         impr_arvore (ap->esquerda);

         printf ("%4d %s\n", ap->contador,

                 ap->palavra);

         impr_arvore (ap->dir);

     }

}

 

6 - Pesquisa em Tabela

 

·       Exemplo de uma tabela de símbolos e texto de reposição:

·       Estrutura do nodo:

 

     struct lista { /* entrada básica da tabela */

         struct lista *proximo; /* proxima entrada */

         char *nome; */ nome definido */

         char *def; /* texto substituto */

}

 

·       O arranjo de apontadores:

 

#define  TAMHASH   101

static struct lista *tabhash [TAMHASH]; /* tabela de

                                       apontadores */

·       Esquema:

 

·       A função hash:

 

unsigned hash (char *s) /*calcula o valor do hash */

{

     unsigned valhash;

     for (valhash = 0; *s != '\0'; s++)

         valhash = *s + 31 * valhash;

     return( valhash % TAMHASH );

}

 

struct lista *pesquisa (char *s)

     /*procura s em tabela hash */

{

     struct lista *as;

     for (as = tabhash [hash (s)]; as != NULL;

         as = as->proximo )

         if (strcmp(s, as->nome) == 0)

              return as; /* achou */

     return NULL; /* não achou */

}

 

7 - Campos

 

·       Um campo é definido como um conjunto de bits adjacentes dentro de um único int.

·       Definição de Campos:

 

     struct {

         unsigned  eh_palchave:1;

         unsigned  eh_externo:1;

         unsigned  eh_estatico:1;

     } sinalizadores;

 

·       Para ligar os bits:

 

     sinalizadores.eh_externo = 1;

 

·       Para desligar os bits:

 

     sinalizadores.eh_estatico = 0;

 

·       Parra testá-los:

 

     if (sinalizadores.eh_palchave == 0 )

         . . .

 

·       Um campo não pode ultrapassar os limites de um int.

·       Os campos não precisam ter nome (preenchimento)

·       O tamanho 0 força o alinhamento no início do próximo int.

·       Campos não têm sinal; só podem ser armazenados num int ou unsigned, não são arranjos e não têm endereços.

 

8 - Uniões

 

·       Uma união é uma variável que pode conter (em tempos diferentes) objetos de tipos e tamanhos diferentes.

·       Exemplo:

 

     union etip_u {

         int       vali;

         float         valf;

         char      *valc;

     } valu;

 

·       Qualquer um destes tipos podem ser atribuídos à variável.

·       O tipo recuperado deve ser o tipo mais recentemente armazenado (o controle é do programador)

·       Referência:

 

     nome_da_união.membro

  ou

     apontador_para_união->membro

 

·       Se a variável tipou é usada para lembrar o tipo armazenado, poderia ser escrito:

 

     if (tipou == INT)

         printf ("%d\n", valu.vali);

     else if (tipou == FLOAT)

         printf ("%f\n", valu.valf);

     else if (tipou == CADEIA)

         printf ("%s\n", valu.valc);

     else

         printf ("tipo incorreto %d em tipou\n", tipou);

 

9 - Typedef

 

·       É uma facilidade do C para criação de nomes de tipos de dados.

·       Exemplos:

 

     typedef int TAMANHO; /* sinônimos */

     TAMANHO tem, tamax;

     TAMANHO *tamanho[];

     typedef struct nodo {

         char *pal;

         int contador;

         struct nodo esquerda;

         struct nodo direita;

     } NODO, *AP_NODO;

 

     typedef int (*AFI)();

 

·       AFI é o tipo apontador para uma função que retorna um int.

 

     AFI strcmp, compnum, troca;

 

·       Razões de Uso:

-         proteger-se de problemas de transportabilidade (só altera onde houver problemas).

-         documentação.