Vamos voltar à nossa estrutura para um círculo:
struct s_pos { int x; int y; }; struct s_circulo { struct s_pos c; /* centro do círculo */ float r; /* seu raio */ };
Como definíamos variáveis do tipo struct s_circ?
struct s_pos { int x; int y; }; struct s_circulo { struct s_pos c; /* centro do círculo */ float r; /* seu raio */ }; int main() { struct s_circ var; }
O problema é que fica um tanto quanto trabalhoso digitar sempre "struct". Seria legal podermos substituir "struct s_circ" por um único nome, digamos "circ", rebatizando este tipo de dado. Como fazemos isso? Com typedef:
typedef struct s_pos { int x; int y; } pos; typedef struct s_circulo { pos c; /* posição do centro do círculo */ float r; /* seu raio */ } circ; int main() { circ var; var.r = 2.3; var.c.x = 4; var.c.y = 2; }
A forma geral de typedef é:
typedef tipo novo_nome;
onde "tipo" é qualquer tipo de dado do C (inclusive struct), e "novo_nome" é o novo nome pelo qual este tipo também será conhecido (o nome anterior continua valendo). Funciona como um apelido que damos a um tipo.
No caso acima, demos um novo nome, "pos", à estrutura s_pos. Ou seja, agora podemos definir uma variável para esta estrutura tanto usando o nome real dela:
struct s_circ var;
quanto usando seu novo nome, seu apelido:
circ var;
Note que usamos var, declarado como "circ", como se tivesse sido declarado como "struct s_circ".
E os nomes da struct e do tipo, precisam ser diferentes? Não, não precisam, ou seja, podemos fazer o seguinte:
typedef struct pos { int x; int y; } pos; typedef struct circ { pos c; /* posição do centro do círculo */ float r; /* seu raio */ } circ; int main() { circ var; var.r = 2.3; var.c.x = 4; var.c.y = 2; }
apesar disso, é aconselhável manter os nomes diferente (por exemplo, adicionando um "s_" quando for nome da estrutura), para não se confundir durante a programação. Mas isso fica inteiramente a cargo do programador.
Vale lembrar que, com typedef, você não está criando um novo tipo, apenas dando um apelido a um tipo já existente.
Mas typedef não é usado somente para poupar tempo de digitação quando da programação. Devido ao fato dele poder ser usado com qualquer tipo do C, ele pode servir para aumentar a legibilidade do programa, bem como sua organização. Por exemplo:
typedef float nota; int main() { nota x; }
Aqui, logo ao vermos a definição de x, sabemos não só o que ele carrega (se float, int etc), mas o significado disso, o que o dado é, o que será guardado no x (no caso, uma nota). Isso seguramente aumenta a legibilidade do programa.
O interessante disso é que, uma vez tendo definido um novo nome para um tipo, podemos usá-lo como tipo base para outro nome:
typedef float nota; typedef nota nota_neg; int main() { nota x; nota_neg y; }
Agora "nota_neg" é outro nome para "nota", que é outro nome para "float". Podemos então fazer:
typedef float nota; typedef nota nota_neg; int main() { nota x; nota_neg y; float z; }
e as 3 variáveis guardarão exatamente o mesmo tipo de dado.
Um detalhe importante é que typedef não pode ser usado com vetores. Isso porque vetores não são um tipo em C (são, de fato, ponteiros para o primeiro elemento de uma lista). Ou seja, não podemos fazer:
typedef int v[10] vetor;
ou
typedef int [10] vetor;
ou qualquer coisa do gênero. Se quisermos usar vetores (e conseqüentemente matrizes e strings), teremos que usar como ponteiros:
typedef int * vetor; int main() { vetor v; }
Mas note que, neste caso, v não é um vetor, mas sim um ponteiro para inteiro. Se quisermos guardar algo nele, teremos que alocar dinamicamente:
#include <stdio.h> #include <stdlib.h> typedef int * vetor; int main() { vetor v; int i; v = (vetor)malloc(5*sizeof(int)); if (!v) { printf("Erro de alocação\n"); exit(1); } for (i=0; i<5; i++) v[i] = 0; }
ATENÇÃO! O seguinte programa está correto:
typedef int * vetor; int main() { vetor v[5]; }
porém, o que ele faz? Ele aloca um vetor de 5 elementos do tipo vetor. Ou seja, ele aloca um vetor de 5 "int *", 5 ponteiros para inteiro. Cuidado, pois isso não é o mesmo que "int v[5]"!
Outro modo de definir tipos é usando o velho e bom define:
#define pos struct s_pos struct s_pos { int x; int y; }; #define circ struct s_circ struct s_circ { pos c; /* centro do círculo */ float r; /* seu raio */ }; int main() { circ x; x.r = 3.4; x.c.x = 9; x.c.y = 4; }
E qual a diferença entre eles? Na prática, muito pouca (veja em lista ligada). A maior diferença é que, com typedef, definimos um apelido para um tipo, já com define não demos apelido nenhum a ninguém. O compilador (de fato, o pré-compilador), ao encontrar o define, vai substituir todo string "circ" por "struct s-circ", e todo "pos" por "struct s_pos", no código fonte do programa, e só então compilar. Ou seja, na hora de compilar, apesar do programador ter digitado "circ x;", para o compilador é como se ele tivesse digitado "struct s_circ x;".
Vamos voltar ao nosso programa de notas, melhorando-o. Até agora temos 3 versões:
Mas e se nem o programador nem o usuário souberem o número total de notas? O que faremos? Usamos a mesma estratégia do item 2? Essa estratégia não é aceitável, pois sempre há a possibilidade do número de notas ultrapassar o número máximo que definimos. O ideal seria usarmos uma lista de notas, com o seguinte algoritmo:
inicialmente a lista está vazia enquanto o usuário não manda parar de ler leio um dado coloco este dado na lista
Nesse caso, o único limitante ao tamanho da lista é a total de memória do computador. E como implementamos esse tipo de algoritmo? Com listas ligadas.
Uma lista ligada é uma lista onde cada elemento - chamado de nó - contém um valor e um ponteiro para o elemento seguinte. Assim, sabendo onde está o primeiro elemento da lista, podemos chegar a qualquer outro elemento. Há vários tipos de listas ligadas:
e muitas outras mais. O limitante é apenas sua imaginação. Aqui iremos usar somente listas simples.
Mas e quais as vantagens e desvantagens de cada uma? Listas duplamente ligadas são fáceis de se percorrer, mas ocupam mais espaço na memória. Note que nessas eu posso, a partir de um elemento, voltar na lista, percorrê-la de trás para frente, pois tenho ponteiros que medizem onde estão o próximo elemento e o anterior.
As circulares simples são fáceis de percorrer e não ocupam muita memória. Mas se o número de elementos for grande, vai se comportar quase como uma lista simples.
Qual lista é a melhor? Depende do problema a ser resolvido.
Agora vamos definir operações básicas em listas:
Vamos ver então como criar uma lista ligada. Nos exemplos que seguem estaremos usando a lista ligada simples, conforme foi apresentada acima.
Antes de mais nada, vamos definir um nó na nossa lista:
/* defino um nó na lista */ struct s_nota { float v; struct s_nota *prox; };
ou, de forma mais organizada:
/* defino um ponteiro para um nó na lista */ typedef struct s_nota * p_nota; /* defino um nó na lista */ typedef struct s_nota { float v; p_nota prox; } nota;
Note que, dentro da estrutura s_nota, tenho um ponteiro para a própria estrutura s_nota. Este ponteiro servirá para apontar para a próxima estrutura na lista. Um terceiro modo de definir o né é:
#define nota struct s_nota struct s_nota { float v; nota *prox; };
Qual usar é realmente com você. Agora vamos ver o algoritmo do programa para tirar a média de um número indefinido de notas:
De início vemos que precisamos de pelo menos 2 funções: uma para criação da lista, e outra para inclusão de dados nela.
Vamos então criar a lista. Uma lista, antes de mais nada, precisa de algo que indique seu início (como em vetores). Este pode ser um ponteiro, que chamamos de cabeça da lista, e que apontará para o nó inicial (nó cabeça) da lista:
#define nota struct s_nota struct s_nota { float v; nota *prox; }; nota *criaLista() { return(NULL); } int main() { nota *cabeca; /* cabeça da lista */ cabeca = criaLista(); }
O que fizemos aqui? Antes de mais nada, criaLista() apenas retorna NULL, indicando que o ponteiro que receber seu valor não apontará para lugar algum. Ao fazermos "cabeca = criaLista()", estamos fazendo cabeça apontar para lugar algum, indicando que a lista está vazia (se o ponteiro para o nó cabeça da lista está vazio, isto quer dizer que não há nó cabeça).
Agora, como incluímos um elemento? Antes disso, temos que definir onde incluiremos o elemento. No nosso caso, não importa se o elemento será incluído no início ou fim da lista, uma vez que não nos importa a ordem com que as notas são fornecidas. Sendo assim, vamos incluir no início.
A idéia básica é a seguinte. Suponha que já temos a seguinte lista:
Repare no último ponteiro (saindo de e1). Ele está "aterrado", o que, conforme já dito, significa que ele é NULL, ou seja, não aponta para ninguém. Agora, para inserir um elemento no início da lista, criamos um novo elemento, fazendo um ponteiro auxiliar conter seu endereço na memória, ou seja, apontar para ele:
Faço o ponteiro saindo do nó que contém e4 (o campo "prox" da estrutura do nó) apontar para o mesmo nó apontado por "cabeça", ou seja, o nó inicial da lista:
E, finalmente, faço o ponteiro "cabeça" apontar para a nova cabeça da lista, ou seja, o nó apontado por "aux":
Pronto! Vista de outra forma nossa lista está assim:
E se a lista estiver inicialmente vazia, o algoritmo funciona? Vejamos, uma lista vazia é assim:
Procedemos como antes, criando o novo elemento:
Então fazemos o elemento apontado por cabeça ser o próximo elemento do novo elemento (no caso, nada):
Finalmente, fazemos o novo elemento ser a nova cabeça:
Funciona!
E como programamos isso? Precisamos de uma função para criar um nó, além de uma para incluir o nó na lista:
#include <stdio.h> #include <stdlib.h> /* a lista de notas */ #define lnota struct s_nota struct s_nota { float v; lnota *prox; }; /* Cria uma lista vazia. Retorna ponteiro para a cabeça da lista. */ lnota *criaLista() { return(NULL); } /* Cria um nó na lista. Retorna ponteiro para este nó, ou NULL em caso de erro. Param: nota - a nota a ser armazenada no nó */ lnota *criaNo(float nota) { lnota *aux; /* auxiliar */ /* aloco espaço para o nó */ if (!(aux = (lnota *)malloc(sizeof(lnota)))) { /* não pode alocar */ return(NULL); } /* alocou, carrego os valores */ aux->v = nota; aux->prox = NULL; /* retorno o ponteiro para o elemento criado */ return(aux); } /* Inclui um elemento no início da lista. Retorna ponteiro para o novo nó cabeça da lista, ou NULL em caso de erro. Param: cab - cabeça da lista nota - valor da nota a ser incluída */ lnota *incluiEl(lnota *cab, float nota) { lnota *aux; /* auxiliar */ /* crio o novo nó */ if (!(aux = criaNo(nota))) { /* houve problemas na criação do nó */ return(NULL); } /* criei o nó, faço a cabeça ser o elemento seguinte a ele */ aux->prox = cab; /* retorno a nova cabeça da lista */ return(aux); } /* Imprime a lista na tela. Param: cab - a cabeça da lista */ void imprimeL(lnota *cab) { lnota *p; /* auxiliar */ /* aponto p para o início da lista */ p = cab; /* imprimo cada elemento da lista */ while (p) { printf("nota: %f\n",p->v); p = p->prox; } } int main() { lnota *cabeca; /* cabeça da lista */ float nota; /* uma nota */ char resp; /* indica se continua o laço */ lnota *p; /* auxiliar */ float soma; /* soma das notas */ int n; /* número de notas */ /* inicio a lista */ cabeca = criaLista(); /* pego as notas */ do { printf("Entre uma nota: "); scanf("%f",¬a); /* incluo a nota na lista */ if (!(cabeca = incluiEl(cabeca, nota))) { printf("Erro na inclusão da nota na lista\n"); exit(1); } /* pergunto se há mais notas */ printf("Continua? (s/n) "); scanf(" %s",&resp); } while (resp == 's'); /* imprimo a lista na tela */ imprimeL(cabeca); /* calculo a média */ soma = 0; n = 0; p = cabeca; while (p) { soma += p->v; n++; p = p->prox; } /* dou a resposta */ printf("Média = %f\n", soma / n); }
Uma saída deste programa é:
Entre uma nota: 3 Continua? (s/n) s Entre uma nota: 6.7 Continua? (s/n) s Entre uma nota: 4.4 Continua? (s/n) s Entre uma nota: 9 Continua? (s/n) s Entre uma nota: 8.7 Continua? (s/n) n nota: 8.700000 nota: 9.000000 nota: 4.400000 nota: 6.700000 nota: 3.000000 Média = 6.360000
Copyright© 2005 Norton Trevisan Roman - Direitos Autorais Reservados.