2 tipos abstratos de dados

Prévia do material em texto

Estrutura de Dados
02 - Tipos Abstratos de Dados
Manoel Vilela
<2017-08-29 Tue 20:16>
Sumário
1 Resumo 1
2 Exemplos de Tipos Abstratos de Dados 2
2.1 Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Circle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Referências 8
1 Resumo
Na aula de hoje foi comentado sobre a ideia mais primitiva que se conhece
sobre orientação a objetos, antes mesmo desse paradigma ser famoso como
hoje. Encapsulamento via Tipos Abstratos de Dados.
A ideia principal é criar uma estrutura e seus métodos que a manipulam
de forma isolada e encapsulada. Para uma estrutura chamada Ponto por
exemplo, é possível definir um arquivo ponto.h que recebe todas suas decla-
rações e um arquivo ponto.c que definirá essas declarações, seja da estrutura
e seus métodos.
Usualmente o arquivo ponto.h serve para ser incluso em outro arquivo
que usará essa estrutura, geralmente um outro programa por exemplo main.c
então passar informações que essas funções deverão ser ligadas no processo
de linking para então gerar um binário.
De uma maneira geral, o processo de compilação para projetos estrutura-
dos com TAD, compila-se todos códigos objetos com gcc -c ponto.c main.c
1
gerando arquivos ponto.o e main.o então se faz a ligação deles com o co-
mando gcc -o main.out ponto.o main.o.
A principal ideia de uma estrutura dessa é o poder de encapsular imple-
mentações e reduzir a complexidade de código disponível para o programador
numa determinada camada, criando interfaces para manipular estruturas em
níveis sucessivos de abstração.
Houve um tópico adicional no final da aula sobre complexidade de algo-
ritmos, mas isso vou deixar para outro arquivo.
2 Exemplos de Tipos Abstratos de Dados
Estarei descrevendo nos próximos tópicos três implementações de TAD:
• Point
• Circle
• Matrix
2.1 Point
Os métodos necessários para manipular um ponto é definido como:
2
1 /**
2 * @brief struct Point as 2D space pointer
3 */
4 typedef struct point Point;
5
6 /**
7 * @brief create a new Point and set x an y
8 *
9 * @return the address of the allocated point
10 */
11 Point* point_create(float x, float y);
12
13 /**
14 * @brief free memory for the Point p
15 * @param p Point to be free
16 */
17 void point_free(Point *p);
18
19 /**
20 * @brief Set the values of p.x and p.y
21 */
22 void point_set(Point *p, float x, float y);
23
24 /**
25 * @brief Get the values of p.x and p.y through the pointers *x and *y
26 */
27 void point_get(Point *p, float *x, float *y);
28
29 /**
30 * @brief calculate the euclidean distance between two points
31 *
32 * @return the distance of *px and *py as a float number
33 */
34 float point_distance(Point *px, Point *py);
Código 1: Cabeçalho da TAD Point definido em point.h.
A implementação é totalmente escondida e provida pelo arquivo point.c.
É possível encontrá-lo em point.c
3
2.2 Circle
A implementação do Circle é através do uso da TAD Point. Os métodos
relacionados a essa TAD é descrito como:
1 /**
2 * @brief define a Circle structure
3 */
4 typedef struct circle Circle;
5
6 /**
7 * @brief allocate a new circle on memory based on its parameters
8 */
9 Circle* circle_create(Point *center, float radius);
10
11 /**
12 * @brief free memory allocated by the circle c
13 */
14 void circle_free(Circle *c);
15
16 /**
17 * @brief Set the values of center and radius of structure
18 */
19 void circle_set(Circle *c, Point *center, float radius);
20
21 /**
22 * @brief Get the its internal attributes through the pointers passed
23 */
24 void circle_get(Circle *c, Point *center, float *radius);
25
26 /**
27 * @brief Check if the pointer /p point is inside of the circle
28 */
29 int circle_point_inside(Circle *c, Point *point);
Código 2: Cabeçalho da TAD Circle definido em circle.h
Ou seja, temos estes 5 métodos relacionado a manipulação do dado Circle.
Foram omitidos nessa amostra as declarações dos seguintes métodos:
4
• circle_set_radius
• circle_set_center
• circle_get_radius
• circle_get_center
Já que estes métodos são apenas açúcar sintático para os métodos circleget
e circleset.
2.3 Matrix
Um tipo abstrato matrix pode ser definido independente da estrutura
de acesso, com suas implementações variadas internamente. Um tipo de
interfaceamento durante o encapsulamento pode ser provida pelo seguinte
cabeçalho:
5
1 typedef struct matrix Matrix;
2
3 /**
4 * @brief Create a new matrix
5 * @return the address of the created matrix
6 */
7 Matrix* matrix_create(int m, int n);
8
9
10 /**
11 * @brief Free memory of the matrix
12 */
13 void matrix_free(Matrix* matrix);
14
15
16 /**
17 * @brief Get a value on position (i,j) of the matrix
18 */
19 float matrix_get(Matrix *matrix, int i, int j);
20
21
22 /**
23 * @brief Set a value on position(i,j) of the matrix
24 */
25 void matrix_set(Matrix *matrix, int i, int j, float v);
26
27
28 /**
29 * @brief Get the number of lines of the matrix
30 */
31 int matrix_lines (Matrix *matrix);
32
33
34 /**
35 * @brief Get the number of columns of the matrix
36 * @return the number of columns
37 */
38 int matrix_columns(Matrix *matrix);
Código 3: Cabeçalho da TAD matrix definida em matrix.h
6
As possíveis representações dessa estrutura internamente, podem ser feita
de duas maneiras assim como foi comentado no módulo 0 desse seriado de
notas.
Na qual as possíveis definições para struct matrix são:
1 struct matrix {
2 int lines;
3 int columns;
4 float *v;
5 };
Código 4: Definição de uma matriz através de um vetor linear.
1 struct matrix {
2 int lines;
3 int columns;
4 float **v;
5 };
Código 5: Definição de uma matriz através de um vetor de ponteiros.
Cada definição deve ser separada por outro código-fonte que gerará um
código-objeto específico. Para cada um desses arquivos, deve ser implemen-
tado todas as funções definidas no cabeçalho de interfaceamento da TAD.
Um exemplo disso foi escrito em src/tad/matrix.
Bom, adicionalmente foi escrito o módulo matrix-utils para cálculo do
valor máximo de uma matriz e também uma forma elegante da impressão
dessa mesma matriz.
+-------------------------------------------------------+
| 0.00 1.00 2.00 3.00 4.00 5.00 6.00 7.00 8.00 |
| 9.00 10.00 11.00 12.00 13.00 14.00 15.00 16.00 17.00 |
| 18.00 19.00 20.00 21.00 22.00 23.00 24.00 25.00 26.00 |
| 27.00 28.00 29.00 30.00 31.00 32.00 33.00 34.00 35.00 |
+-------------------------------------------------------+
Procedimento matrix_print(Matrix *matrix) aplicado para uma ma-
trix (9, 4).
7
3 Referências
• CELES; WALDEMAR, 2004, Introdução a Estrutura de Dados, Capi-
tulo 9, p.123
8
	Resumo
	Exemplos de Tipos Abstratos de Dados
	Point
	Circle
	Matrix
	Referências