Skip to content

Latest commit

 

History

History
251 lines (197 loc) · 7.52 KB

2-tipos-abstratos-de-dados.org

File metadata and controls

251 lines (197 loc) · 7.52 KB
Raw

Estrutura de Dados @@latex:\@@ 02 - Tipos Abstratos de Dados

Sumário

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 declaraçõ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 estruturados com TAD, compila-se todos códigos objetos com gcc -c ponto.c main.c gerando arquivos ponto.o e main.o então se faz a ligação deles com o comando gcc -o main.out ponto.o main.o.

A principal ideia de uma estrutura dessa é o poder de encapsular implementaçõ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 algoritmos, mas isso vou deixar para outro arquivo.

Exemplos de Tipos Abstratos de Dados

Estarei descrevendo nos próximos tópicos três implementações de TAD:

  • Point
  • Circle
  • Matrix

Point

Os métodos necessários para manipular um ponto é definido como:

/**
 * @brief struct Point as 2D space pointer
 */
typedef struct point Point;

/**
 * @brief create a new Point and set x an y
 *
 * @return the address of the allocated point
 */
Point* point_create(float x, float y);

/**
 * @brief free memory for the Point p
 * @param p Point to be free
 */
void point_free(Point *p);

/**
 * @brief Set the values of p.x and p.y
 */
void point_set(Point *p, float x, float y);

/**
 * @brief Get the values of p.x and p.y through the pointers *x and *y
 */
void point_get(Point *p, float *x, float *y);

/**
 * @brief calculate the euclidean distance between two points
 *
 * @return the distance of *px and *py as a float number
 */
float point_distance(Point *px, Point *py);

A implementação é totalmente escondida e provida pelo arquivo point.c. É possível encontrá-lo em point.c

Circle

A implementação do Circle é através do uso da TAD Point. Os métodos relacionados a essa TAD é descrito como:

/**
 * @brief define a Circle structure
 */
typedef struct circle Circle;

/**
 * @brief allocate a new circle on memory based on its parameters
 */
Circle* circle_create(Point *center, float radius);

/**
 * @brief free memory allocated by the circle c
 */
void circle_free(Circle *c);

/**
 * @brief Set the values of center and radius of structure
 */
void circle_set(Circle *c, Point *center, float radius);

/**
 * @brief Get the its internal attributes through the pointers passed
 */
void circle_get(Circle *c, Point *center, float *radius);

/**
 * @brief Check if the pointer /p point is inside of the circle
 */
int circle_point_inside(Circle *c, Point *point);

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:

  • 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 circle_get e circle_set.

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:

typedef struct matrix Matrix;

/**
 * @brief Create a new matrix
 * @return the address of the created matrix
 */
Matrix* matrix_create(int m, int n);


/**
 * @brief Free memory of the matrix
 */
void matrix_free(Matrix* matrix);


/**
 * @brief Get a value on position (i,j) of the matrix
 */
float matrix_get(Matrix *matrix, int i, int j);


/**
 * @brief Set a value on position(i,j) of the matrix
 */
void matrix_set(Matrix *matrix, int i, int j, float v);


/**
 * @brief Get the number of lines of the matrix
 */
int matrix_lines (Matrix *matrix);


/**
 * @brief Get the number of columns of the matrix
 * @return the number of columns
 */
int matrix_columns(Matrix *matrix);

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:

struct matrix {
    int lines;
    int columns;
    float *v;
};
struct matrix {
    int lines;
    int columns;
    float **v;
};

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 implementado todas as funções definidas no cabeçalho de interfaceamento da TAD. Um exemplo disso foi escrito em ../examples/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 matrix (9, 4).

Referências

  • CELES; WALDEMAR, 2004, Introdução a Estrutura de Dados, Capitulo 9, p.123