1 tipos estruturados

Prévia do material em texto

Estrutura de Dados
01 - Matrizes e Tipos Estruturados
Manoel Vilela
<2017-08-22 Tue 22:16>
Sumário
1 Resumo 1
2 Struct, notações e armazenamento 2
3 Typedef 3
4 Estrutura Círculo 3
5 Vetor de Estruturas 5
5.1 Armazenamento como Vetor de Estruturas . . . . . . . . . . . 5
5.1.1 Estático . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5.1.2 Dinâmico . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.2 Armazenamento como Vetor de Ponteiro de Estruturas . . . . 7
5.2.1 Estático . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.2.2 Dinâmico . . . . . . . . . . . . . . . . . . . . . . . . . 9
1 Resumo
Nessa aula terminamos de ver os tipos de alocação de matrizes e também
foi comentado através de uma pergunta que fiz sobre as implicações de uso,
tal como eficiência. No caso da alocação de uma matriz por ponteiros a
resolução de referência é dupla, pois é necessário primeiro pegar o endereço da
linha e depois com o índice da coluna o valor da posição (i,j). Por outro lado,
na alocação de matriz por vetor o acesso é único, pois após a transformação
dos índices, estamos nada mais que acessando um elemento de um único
1
vetor. Isso pode ser relevante em sistemas críticos que há uma frequência de
acesso das estruturas muito alto.
Na outra parte da aula, tivemos introdução a "Tipos Estruturados de
Dados". Ou, simplesmente, TAD (Tipos Abstratos de Dados) — em inglês
conhecido como Abstract Data Types. Tipos estruturados nada mais são que
tipos compostos por tipos primitivos da linguagem ou outros tipos estrutu-
rados já definidos. Por exemplo, um muito simples é o ponto euclidiano:
1 struct Ponto {
2 int x;
3 int y;
4 };
Os tópicos que foram dados se resume a:
1. Criar estruturas em C através da keyword struct;
2. A notação de ponto para estruturas;
3. Notação de seta para ponteiros de estruturas;
4. Como um struct é armazenada em memória;
5. Uso de typedef pra criar aliases para tipos.
6. Exemplos variados dos tópicos acima.
2 Struct, notações e armazenamento
Uma estrutura é um dado composto por um ou mais dados primitivos
(ou outras estruturas), onde pode se armazenar diferente tipos de dados num
mesmo bloco de memória (contígua).
Como demonstrado anteriormente com o exemplo do struct Ponto, dois
membros são declarados como x e y. Estruturas são semelhantes a vetores
no sentido de armazenamento, esses membros são armazenados lado a lado
e o acesso de futuros membros são determinados pelo seu tipo.
Necessariamente, o endereço de uma estrutura é o endereço do seu pri-
meiro membro (nesse caso x). O que ocorria de maneira semelhante com os
vetores. Para o acesso dos seus membros é usado a notação de ponto, como
segue o exemplo:
2
1 int main(void) {
2 struct Ponto p;
3 p.x = 10;
4 p.y = 20;
5
6 }
A ordem de acesso é determinística por conta que a ordem da declaração
dos membros no struct importa. A partir do tamanho que cada tipo arma-
zenará, o compilador determina a quantidade de passos necessário a ser feito
pra chegar ao endereço do próximo membro.
Como fim de apenas uma simple facilidade, isto é, um açúcar sintático, é
provida uma sintaxe alternativa para a manipulação de estrutura de pontei-
ros. De forma equivalente (*pp).x é igual a pp->x, sendo pp uma variável
do tipo struct *Ponto.
3 Typedef
Typedef é criado como uma forma de alias para tipos já definidos.
1 typedef int StudentId;
2
3 typedef struct {
4 int x;
5 int y;
6 } Ponto;
Código 1: Exemplos de definição de estruturas e tipos em C.
O struct anônimo acima é uma maneira mais simples de definir um novo
tipo. No entanto, o usuário ainda se quiser poderá declarar a estrutura sepa-
radamente, assim como também declarar junto e passar o nome da estrutura
ou não.
3
1 struct Ponto {
2 int x;
3 int y;
4 };
5
6 typedef struct Ponto Ponto;
7
8 typedef struct _Ponto {
9 int x;
10 int y;
11 } _Ponto;
Código 2: Exemplos alternativos de declaração de tipos e estruturas em C.
4 Estrutura Círculo
Estarei escrevendo alguns exemplos dado em sala no diretório src/
circle/.
Em geral eu defini os arquivos as estruturas:
• Point
• Circle
Alguns métodos adicionais foram feitos pra facilitar a estrutura, como
new_point(), new_circle(), read_point() e read_circle().
A estrutura de arquivos é dada como:
src/circle
=> Makefile
=> circle.c
=> circle.h
=> point.c
=> point.h
=> pause.h
=> main.c
Em geral os headers (arquivos terminados com .h) contém apenas de-
clarações das estruturas e de seus métodos. Adicionalmente, o cabeçalho
pause.h possui algumas definições para ser fácil de importado. Eu escrevi
4
esse cabeçalho para possuir um método portável de chamar uma função
pause, já que isto possa às vezes ser necessário quando executado no Win-
dows — pois é uma prática comum nesse sistema o usuário apenas clicar no
executável, então abrir uma janela de terminal que fecha após o program ser
finalizado (necessitando pausar a aplicação pra observar a saída).
As principais estruturas definidas respectivamente em point.h e circle.h
são:
1 typedef struct {
2 float x;
3 float y;
4 } Point;
5
6
7 typedef struct {
8 Point center;
9 float r
10 } Circle;
Da qual a primeira representa um ponto no plano euclidiano e a segunda
um círculo. Os seus principais métodos são float distance(Point *px,
Point *py) e int point_inside(Circle *c, Point *p). Para mais in-
formações, por favor, olhe as definições no código fonte de cada estrutura
(point.c e circle.c). O código é legível e documentado.
5 Vetor de Estruturas
Vetores de estruturas podem ser alocados de diferente maneiras, cada um
com seus benefícios. Entre elas temos:
1. Armazenamento como vetor de estruturas.
2. Armazenamento como vetor de ponteiro de estruturas.
Nossa estrutura base para comparação será:
5
1 typedef struct {
2 char nome[81];
3 float ira;
4 } Aluno;
Código 3: Estrutura Aluno definido em aluno.h.
5.1 Armazenamento como Vetor de Estruturas
Temos a eficiência no acesso, mas não pode ser liberado uma vez que
é alocado. Além do mais, essa estrutura que não pode ser liberada pode
ocupar grande memória.
Nesse caso, como sempre a estrutura estará viva na memória, é conveni-
ente usar um método para identificação das estruturas que de fato possuem
valores e estão sendo usadas. Recomenda-se usar a flag #define FREE -1
para o membro ira na inicialização de cada estrutura. Esse passo é inferido
nos códigos de exemplo e será detalhado na implementação.
5.1.1 Estático
No caso estático a memória uma vez alocada, não é possível liberá-la em
tempo de execução. Além disso você precisa saber a priori o tamanho a ser
alocado.
1 #include <stdio.h>
2 #include "aluno.h"
3
4 int main(void) {
5 Aluno alunos[80]; /* alocação na stack, não pode desalocar */
6 /* programa principal */
7 /* ... */
8
9 return 0;
10 }
Código 4: Exemplo de alocação estática com vetores de estruturas.
6
5.1.2 Dinâmico
Pode escolher o tamanho, mas uma vez alocada o programador só tem
duas opções:
• fazer realocação do vetor se quiser aumentar ou liberar
• liberar toda memória
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include "aluno.h"
4
5 int main(void) {
6 Aluno *alunos;
7 int n;
8 scanf("%d", &n);
9 alunos = (Aluno*) malloc(sizeof(Aluno)*n); /* alocação na heap */
10 /* programa principal */
11 /* ... */
12 /* liberação da memória */
13 free(alunos);
14 alunos = NULL;
15
16 return 0;
17 }
Código 5: Exemplo de alocação dinâmica com vetores de estruturas.
5.2 Armazenamento como Vetor de Ponteiro de Estruturas
Nesse caso a eficiência em memória é maior, pois até no caso estático
só armazenamos ponteiros de estruturas invés das estruturas por si. Vista
que o ponteiro de uma estrutura é muito menor que a estrutura em si (seja
qual ela for). Por outro lado,como cada acesso terá que ser feito uma
dupla dereference é usualmente um pouco mais lento que o método descrito
anteriormente.
No entanto, numa comparação geral, o ganho de eficiência de memória é
muito maior que a perda de desempenho no acesso. Então esse é o método
mais recomendado.
7
5.2.1 Estático
Para o caso estático devemos saber quantas estruturas queremos alocar
em tempo de compilação. Mas cada estrutura individual somente é alocada
quando necessário.
Interessante observar que apenas o vetor de ponteiros é estático e não
pode ser liberado. Mas as células individuais são alocadas dinamicamente e
podem ser desalocadas em tempo de execução.
No final ainda sempre ficará na memória na stack o vetor de ponteiros,
mas em comparação com o modelo anterior, isto é muito mais econômico,
visto que um ponteiro de uma estrutura é menor que a estrutura em si.
8
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include "aluno.h"
4
5 #define MAX 80
6
7 void aloca_aluno(Aluno** aluno) {
8 *aluno = (Aluno *) malloc(sizeof(Aluno)); // alocação na heap
9 }
10
11 int main(void) {
12 Aluno* alunos[MAX]; // alocação na stack, não pode desalocar
13 int i;
14 /* inicializar com NULL */
15 for(i = 0; i < MAX; i++) {
16 alunos[i] = NULL;
17 }
18 /* quando necessário aloca */
19 aloca_aluno(&alunos); /* aloca o primeiro */
20
21 /* programa principal */
22
23 /* libera no final somente as celulas que foram alocadas */
24 for(i = 0; i < MAX; i++) {
25 if (alunos[i] != NULL) {
26 free(alunos[i]);
27 }
28 }
29
30 return 0;
31 }
Código 6: Exemplo de alocação estática com vetor de ponteiros de estruturas
5.2.2 Dinâmico
Esse é o caso mais flexível de todos em memória. Podemos escolher em
tempo de execução o tamanho da memória necessária a ser alocada, de forma
econômica e podemos alocar somente quando necessário a estrutura através
9
do vetor de ponteiros de estruturas. Além disso tudo, podemos liberar a
memória quando for necessário.
10
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include "aluno.h"
4
5 Aluno** aloca_ponteiros_aluno(int n) {
6 return (Aluno **) malloc(sizeof(Aluno*) * n); // alocação na heap
7 }
8
9 int main(void) {
10 Aluno **alunos; // alocação na stack, não pode desalocar
11 int n;
12 printf("Digite a quantidade dealunos a serem alocados: ")
13 scanf("%d", &n);
14
15 /* aloca o vetor de ponteiros */
16 aloca_ponteiros_alunos(&alunos);
17
18 /* inicializar com NULL */
19 for(i = 0; i < MAX; i++) {
20 alunos[i] = NULL;
21 }
22
23 /* programa principal */
24 /* ... /*
25 /* fim do programa principal */
26
27
28 /* libera no final somente as celulas que foram alocadas */
29 for(i = 0; i < MAX; i++) {
30 if (alunos[i] != NULL) {
31 free(alunos[i]);
32 }
33 }
34
35 return 0;
36 }
Código 7: Exemplo de alocação dinâmica com vetor de ponteiros de estru-
turas
11
	Resumo
	Struct, notações e armazenamento
	Typedef
	Estrutura Círculo
	Vetor de Estruturas
	Armazenamento como Vetor de Estruturas
	Estático
	Dinâmico
	Armazenamento como Vetor de Ponteiro de Estruturas
	Estático
	Dinâmico